2021 年資訊科技產業專案設計課程面試範例

--- title: 2021 年資訊科技產業專案設計課程面試範例 tags: INFO2021 --- # 2021 年「[資訊科技產業專案設計] > 貢獻者: 就豪曉-Nonsense > ==[video](https://youtu.be/ALrXBr5HLQE)== ## 題目1 - 編號及名稱：`169. Majority Element` - 要求：系統會給一個大小為n的矩陣nums，返回矩陣內最常出現的元素，這個元素出現的頻率會大於`n/2`次。 ### 面試過程 1. 於面試官命題後，重複確認題目要求 ``` 是否只要找到矩陣內出現最多次的數字即可？ ``` 2. 舉出一個符合題目要求的範例 > **Input**：[2, 2, 2, 3, 3] > **Output**：2 3. 程式架構與使用函數 - `map<>`：儲存nums矩陣內數值與相同數字的出現次數 - `for()`：依序讀取矩陣內的數值 - `if()`：判斷數字的出現次數是否大於矩陣總數的一半 - `return`：將判斷後的結果返回 4. 程式撰寫 5. 依據面試官要求，提出更好的程式解法 ### 程式碼 ```c++= class Solution { public: int majorityElement(vector<int>& nums) { map<int,int> m; for(int i = 0;i < nums.size();i++){ m[nums[i]]++; if(m[nums[i]] > nums.size()/2){ return nums[i]; } } return 0; } }; ``` ### 改進方案因為題目有特別定義這個最常出現元素的出現頻率會大於總數的一半以上，我們可以先使用`sort()`函數將矩陣排序後，再去找出矩陣內的**中位數**，此數就會是矩陣內最常出現的元素。 ```c++= class Solution { public: int majorityElement(vector<int>& nums) { sort(nums.begin(), nums.end()); return nums[nums.size()/2]; } }; ``` ### 本次表現自己回看影片後才發現，於面試過程中太常使用「然後、那個」等等的贅字，往後應該要透過更多的練習，避免這樣的情況發生。 ## 題目2 - 編號及名稱：`771. Jewels and Stones` - 要求：系統會各給一個名為 jewels 還有 stones 的字串，找出 stones 字串中包含了多少 jewels 元素。字串內的元素只會有英文字母，且有分大小寫。 - 影片連結 - 中文：https://youtu.be/_F-5K2ygosc - 英文：https://youtu.be/u3NqvW61N34 ### 面試過程 1. 於面試官命題後，重複確認題目要求 ``` 是否只要找出 stones 字串中有多少字元與 jewels 字串中的字元相等即可？ ``` 2. 舉出一個符合題目要求的範例 > **Input**：jewels = "a", stones = "aab" > **Output**：2 3. 程式架構與使用函數 - `int rich`：儲存尋找到的寶石數量 - `巢狀迴圈`：依序讀取兩字串內的字元 - `if()`：判斷 stones 字元是否等於 jewels 字元 - `return`：將判斷後的結果返回 4. 程式撰寫 5. 依據面試官要求，提出更好的程式解法 ### 程式碼 ```c++= class Solution { public: int numJewelsInStones(string jewels, string stones) { int rich = 0; for(int i = 0;i < stones.size();i++){ for(int j = 0;j < jewels.size();j++){ if(stones[i] == jewels[j]) rich++; } } return rich; } }; ``` ### 改進方案一樣使用巢狀迴圈的架構，使用`for(auto a : b)`的方式將 b 元素的賦值給 a，透過這個方法能減少系統運行時間與程式碼長度。 ```c++= class Solution { public: int numJewelsInStones(string jewels, string stones) { int rich = 0; for(auto i : jewels){ for(auto j : stones){ if(i == j) rich++; } } return rich; } }; ``` ### 本次表現講解改進方案的程式架構時，對於程式內部的運作原理還不夠清楚，導致在作答時解釋的不夠完整。 ## 題目3 - 編號及名稱：`1689. Partitioning Into Minimum Number Of Deci-Binary Numbers` - 要求：找出最少需要多少組`deci-binary`數值才能組成題目給予的字串。 >**deci-binary**：字串內只包含 '0' 和 '1' ，同時字串開頭不為 '0' ### 面試過程 1. 於面試官命題後，重複確認題目要求 ``` 重新確認 deci-binary 數的定義 ``` 2. 舉出一個符合題目要求的範例 > **Is the string a deci-binary number？** > "1100" ==> (◯) > "112" ==> (✕) 3. 程式架構與使用函數 - 系統架構因 deci-binary 當中的最大值為 1 ，因此只要找到題目給予字串中的最大數值，即是我們所需最少組的 deci-binary。 - 使用函數 - `char major`：目前字串中的最大數值 - `for()`：依序讀取字串內的數值 - `if()`：判斷當前的數值是否大於目前儲存的最大數值 - `return`：返回字串中最大數值 4. 程式撰寫 5. 依據面試官要求，提出更好的程式解法 ### 程式碼 ```c++= class Solution { public: int minPartitions(string n) { char major = '0'; for(int i = 0;i < n.size();i++){ if(n[i] > major) major = n[i]; } return major - '0'; } }; ``` ### 改進方案透過`max_element()`函式和`指標`，有效增加程式運行速度和降低記憶體使用量。 ```c++= class Solution { public: int minPartitions(string n) { return *max_element(begin(n),end(n)) - '0'; } }; ``` ### 本次表現本次面試沒有完全遵照 REATCO 的回答步驟，先說明程式架構後，後來才補充為何想這樣撰寫。事後看影片時發現，會容易讓他人無法在第一時間得知我們想表達的資訊。 # 資訊產業專案設計_第二次作業 ## 題目1 - 編號及名稱：[169. Majority Element](https://leetcode.com/problems/majority-element/) - 要求：系統會給一個大小為 n 的陣列 nums，返回矩陣內最常出現的元素，這個元素出現的頻率會大於`n/2`次。 ### 面試過程 1. 於面試人員命題後，重複覆誦題目要求和重點關鍵字，並對其舉例說明 ``` 題目要求：找出陣列nums中出現頻率最高的元素 E.g., Input [2 2 2 3 3] Output 2 ``` 2. 與面試人員確認題目要求後，說明**程式架構**和**使用函數** - **程式架構** 依序讀取 nums 陣列中的數值，存取「陣列中數值」和「數值的出現次數」，同時判斷「數值的出現次數」是否大於陣列長度的一半以上。 - **使用函數** - `map<>`：儲存nums矩陣內數值與相同數字的出現次數 - `for()`：依序讀取矩陣內的數值 - `if()`：判斷數字的出現次數是否大於矩陣總數的一半 - `return`：將判斷後的結果返回 3. 程式碼撰寫 4. 依據面試官要求，提出更好的程式解法 ### 程式碼 ```cpp int major(vector<int>& nums){ map<int,int> m; for(int i = 0;nums.size() > i;i++){ m[nums[i]]++; if(m[nums[i]] > nums.size() / 2) return nums[i]; } } ``` ### 改進方案 **問**：太多人在解這題都使用`for`迴圈，能否使用其他解法？ **答**：題目有提及此元素的出現頻率會大於陣列長度的一半以上，因此可以使用`sort`函數先將陣列內的數值由小到大重新排列，再找出其中位數，此數就會是我們要的答案。 ```cpp int major(vector<int>& nums){ sort(nums.begin(),nums.end()); return nums[nums.size() / 2]; } ``` ### 本次表現整體流程還算流暢，該補充的地方也都有說明。但有時候邊說明邊打字的時候，還是會有點卡卡的，需要再加強練習。 ## 題目2 - 編號及名稱：[1689. Partitioning Into Minimum Number Of Deci-Binary Numbers](https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/) - 要求：題目將給予一組字串 n ，判斷最少需要多少組`deci-binary`才能組成此字串。 >**deci-binary**：字串內只包含 '0' 和 '1' ，同時字串開頭不為 '0' ### 面試過程 1. 於面試人員命題後，重複覆誦題目要求和重點關鍵字，並對其舉例說明 ``` 題目要求：找出組成字串的最少組deci-binary，這邊與面試人員重複確認deci-binary的定義 E.g., "1100" ==> (◯) "112" ==> (✕) ``` 2. 與面試人員確認題目要求後，說明**設計程式理念**、**程式架構**和**使用函數** - **程式設計理念** 因 deci-binary 數字中的最大值為字元'1'，只要找出字串 n 中的最大數值，此數就會是我們所需的最少組 deci-binary。 - **程式架構** 使用一變數來儲存字串內的最大數值，依序判斷字串內的數值是否大於我們當前的最大值。如果結果為大於，則將當前最大值更改為該值，反之，則繼續判斷字串的下一個數值。 - **使用函數** - `char major`：目前字串中的最大數值 - `for()`：依序讀取字串內的數值 - `if()`：判斷當前的數值是否大於目前儲存的最大數值 - `return`：返回字串中最大數值 3. 程式碼撰寫 4. 依據面試官要求，提出更好的程式解法 ### 程式碼 ```cpp int minDB(string n){ char major = '0'; for(int i = 0;n.size() > i;i++){ if(n[i] > major) major = n[i]; } return major - '0'; } ``` ### 改進方案 **問**：如果將 deci-binary 換成由'012'組成的字串，試問是否能達成原本的題目要求，找出最少需要多少組由'012'組成的字串才能組成字串 n？ **答**：在不更動原本程式的架構下，使用字串 n 和字串'012'的最大值，找出所需的最小組'012'字串。 > ex. 將字串 n 的最大值 / 字串 '012' 的最大值 > 9/2=4...1 => 5組 > 8/2=4...0 => 4組 > . > 結論：「商」和「餘式」之合即為最少組的字串數目 ```cpp int minDB(string n){ char major = '0'; for(int i = 0;n.size() > i;i++){ if(n[i] > major) major = n[i]; } return ((major - '0') / 2) +((major - '0') % 2); } ``` ### 本次表現設計變化題時，發現如果繼續使用 deci-binary 出題，題目的變化程度不大，因此最後決定使用另一組字串來命題。錄影實作後發現，雖然是延伸題，但是和先前的題目應該要有更多關聯性，下次設計變化題時會多注意。另外，回看影片才發現在英文面試部分可能太過緊張，有時會把character說成characteristic。 # 第三次作業 - 他評01 ## Interviewer ### 缺點 > [00:00](https://youtu.be/ALrXBr5HLQE) * 完全按照 leetcode 上面題目念，很可能會讓 interviewee 容易背出答案。 > [00:53](https://youtu.be/ALrXBr5HLQE?t=53) * 完全沒有想要追問的意思，或許可以反問 interviewee 如何去思考這個題目想要考甚麼 > [03:53](https://youtu.be/ALrXBr5HLQE?t=234) * 不要直接破題，也許可以問假如今天不限定於用 `0 , 1` ，你要用甚麼來組成比較好呢? > [06:18](https://youtu.be/ALrXBr5HLQE?t=379) * 結束的超突然 * 可以在跟 interviewee 討論更延伸的題目，像是時間複雜度、如何再優化 ### 優點 * 有題型變化 --- ## Interviewee ### 缺點 > [00:38](https://youtu.be/ALrXBr5HLQE?t=38) * 只說明 deci - binary ，沒有給 example * 沒有詢問數字的範圍 > [01:16](https://youtu.be/ALrXBr5HLQE?t=77) * 不需要鉅細靡遺講出所有程式的細節，而是要注重再用什麼方法上面就好 * 因為講程式細節，導致時間拉很長 ( 明明 code 很簡單 ) * code 可以簡化行數就盡量簡化，像是 `major = n[i]` 就可以直接寫在 `if` 後面 > [04:11](https://youtu.be/ALrXBr5HLQE?t=251) * 沒有舉例 * ~~隨便的字串~~ 改成字元 1 * 講解方法沒有很清楚，讓人不好理解你想要幹嘛 > [06:04](https://youtu.be/ALrXBr5HLQE?t=364) * 其實不用加括號也可以 * 可以去查關於運算子的執行順序 ### 優點 * 有闡述想法，沒有急著開始打 code # 第三次作業他評2 * 影片的聲音有點小聲，若是麥克風的問題可能需要調整一下 * 第一題在說明題目的部分，可能要清楚一點，把裡面的詞以及範圍要說明一下 * 在確認題目時，有將其example列出來，有比起單純用問的更清楚，很不錯 * 先講大概念的算法會比較簡潔一點，於coding時再一邊說明細節 * for loop內的東西都直接連在一起，適當的加上一些空白可以提升可讀性 * 在驗證程式正確性可以使用一些小例子(概念若清楚可以不用) * 進階題的部分可以再多一點互動 ## 第三次作業-他評3 ### Interviewer 缺點 - 在講解第一題時，可以透過舉例或是與Interviewee問答的過程來帶入題目 - 結束前可以再透過互動了解Interviewee是否明瞭題目的細節，或是進行其他進階延伸，結束的有點突然 ### Interviewee 優點 - 表達很清晰，語速穩定缺點 - 在提出解題想法的時候，可以告訴Interviewer自己在想到此方法前還考慮了什麼選擇，為什麼不選擇其他方法，提供更全面的觀點，也看起來比較不像是背答案 ## 第四次作業-他評4 ### Partitioning into Minimum **I. Interviewer** - 原題目與變化題要求直接，未與實際應用情況連結，容易讓interviewee直接背出答案。 - 未針對interviewee程式碼時間複雜度進行提問，要求做出優化。 **I. Interviewee** - 有依循REACTO步驟，重複並舉例題目範例:thumbsup:。 - [3.33](https://youtu.be/ALrXBr5HLQE?t=213)未針對程式碼舉測試例子，測試輸出是否符合題目需求。 - 在變化題依然有依據REACTO先進行復述及舉例:thumbsup: 。 - [5.28](https://youtu.be/ALrXBr5HLQE?t=328)相同處複製貼上，減少編寫時間:thumbsup:。 ## 第三次作業-他評5 ### Interviewee #### 優點： * 有進行REACTO步驟 * code解說清晰、好理解 #### 可改進： * 舉例只有確認什麼是deci binary，但會拿到的字串以及要用deci binary組合成的字串是什麼並沒有提到。 * for loop 中括號內的分號(;)後可以加一格空格，會讓人看起來比較清楚。 ### Interviewer #### 優點： * 有問延伸性的問題 #### 可改進： * Interviewer只有出題和說不錯喔，如果有更多的互動應該會更好。 * 可以針對interviewer的答題給出一些建議。