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

--- title: 2021 年資訊科技產業專案設計課程面試範例 tags: INFO2021 --- # 2021 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2021)」 > 貢獻者: 米兔Michelle > ==[video](https://youtu.be/oilMDfzOgx4)== ## 測驗1 ### 題目: * [Leetcode problem 1.](https://leetcode.com/problems/two-sum/) `Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. ` * Example: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Output: Because nums[0] + nums[1] == 9, we return [0, 1]. #### 測驗說明與問答 :male-teacher:: 好那給你一個integer的array叫做nums和一個叫target的整數，請你回傳該array裡面的2個index，使得他們裡面存的數加起來等於target。你可以假設只有唯一解。 :girl:: 好的，那所以題目的要求是希望我回傳一個array，並且裡面存的是兩個nums的index，且裡面存的數字總和是target。比如說有一個 [2,7,11,15] 然後target=9，那回傳的index就是[0,1]。請問是這樣嗎? :male-teacher:: 是得沒錯。 :girl:: 好那我想到的作法是我用兩層for loop 去掃過這個array ![](https://i.imgur.com/CjrQLcZ.png) :male-teacher:: 好那妳可以解釋一下他的時間複雜度以及相對應的程式碼嗎? :girl:: 那我認為他的時間複雜度是\begin{equation}O(n^2)\end{equation} :girl::`解釋` * 程式碼如下: ```c=1 /** * Note: The returned array must be malloced, assume caller calls free(). */ int* twoSum(int* nums, int numsSize, int target, int* returnSize){ int i=0,j=0; for(i=0;i<numsSize-1;i++){ for(j=i+1;j<numsSize;j++){ if(nums[i] + nums[j] == target){ *returnSize = 2; int* result = (int*)malloc(sizeof(int)*2); result[0] = i; result[1] = j; return result; } } } *returnSize = 0; return NULL; } ``` #### 變化題: :male-teacher:: 好那如果我把問題改成**不限制唯一解**的話，你的做法會是什麼呢? :girl:: 好那我的做法會是利用linked list的方式將資料做回傳，每一個node存的是一組解 ![](https://i.imgur.com/ACtOQqM.png) * 程式碼如下: ```c=1 struct node{ int first,second; struct node* next; }; typedef struct node Node; void addNode(Node* head,int _first,int _second){ Node *newnode = (Node*)malloc(sizeof(Node)); Node *curr = head; do{ if(curr->next != NULL) curr = curr->next; else{ newnode ->first = _first; newnode ->second = _second; newnode ->next = NULL; curr -> next = newnode; return; } }while(1); } Node* twoSum(int* nums, int numsSize, int target, int* returnSize){ int i=0 , j=0 , count = 0; Node *head = (Node*)malloc(sizeof(Node)); head->next = NULL; for(i = 0; i < numsSize-1; i++){ for(j = i+1; j < numsSize; j++){ if(nums[i] + nums[j] == target){ count++; addNode(head,i,j); } } } if(count!=0) { *returnSize = count*2; return head; } else { *returnSize = 0; return NULL; } } ``` :girl:: 而他的時間複雜度則是 \begin{equation}O(n)\end{equation} :girl:: 因為每次要放新的node的時候會先將pointer指到最後一個node。 :male-teacher:: 如果insert在最前面的話會更快吧? :girl:: 哎對哎，那我修改一下我的code ![](https://i.imgur.com/DjuylCS.png) * 修改的程式碼如下: ```c=1 void addNode(Node* head,int _first,int _second){ Node *newnode = (Node*)malloc(sizeof(Node)); newnode -> first = _first; newnode -> second = _second; newnode -> next = head -> next; head -> next = newnode; } ``` :::warning 更正: 在中文影片中不小心輸入錯誤(newnode->next = NULL )，已在英文影片作修改。 ::: ------ ## 測驗2 ### 題目: * [Leetcode problem 35.](https://leetcode.com/problems/search-insert-position/?fbclid=IwAR2cPc0xNfPWtJsdqQhHxrmu_XMbQ96jy4F7D2EwzwTM2737ugKAUFDTzgg) ` Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity ` * Example 1: Input: nums = [1,3,5,6], target = 5 Output: 2 * Example 2: Input: nums = [1,3,5,6], target = 2 Output: 1 * Example 3: Input: nums = [1,3,5,6], target = 7 Output: 4 * Example 4: Input: nums = [1,3,5,6], target = 0 Output: 0 #### 測驗說明與問答 :male-teacher:: 好那接下來第二題，給你一個由小到大排序好且每個integer都不一樣的array，還有一個target value，如果有找到跟target value一樣的數字則回傳該數字的index ；如果沒有就回傳他應該要放的位置的index。 :girl:: 好那所以題目的要求是希望我回傳一個index，如果有跟target一樣則回傳該index，沒有就回傳它應該放的位置。比如說有一個[1,3,5,6]，target = 5，那就要回傳2；如果target = 7，就要回傳4。 :girl:: 那我的作法是我用一層for loop去掃過array: ![](https://i.imgur.com/X1tylC6.png) :male-teacher:: 好那妳可以解釋一下他的時間複雜度以及相對應的程式碼嗎? :girl:: 那我認為他的時間複雜度是\begin{equation}O(logn)\end{equation} :girl::`解釋` * 程式碼如下 ```c=1 int searchInsert(int* nums, int numsSize, int target){ int small,i; for(i=0;i<numsSize;i++){ if(nums[i]<target) small = nums[i]; else if(nums[i] == target) return i; else{ return i; } } if(nums[numsSize-1]<target) return numsSize; else return 0; } ``` #### 變化題: :male-teacher:: 好那如果我把問題改成**陣列沒有排序**的話，你的做法會是什麼呢? :girl:: 好那我的做法會是先將array進行排序，我用的作法是quick sort，然後排序好後再進行跟原先一樣的步驟。而quick sort的時間複雜度則是: \begin{equation}O(nlogn)\end{equation} * 程式碼如下: ```c=1 #define swap(a,b) int t=a;a=b;b=t; void quickSort(int *arr,int front,int end){ if(front<end){ int pivot = arr[end]; int i = front - 1,j; for(j=front;j<end;j++){ if(arr[j]<pivot){ i++; swap(arr[i],arr[j]); } } i++; swap(arr[i],arr[end]); quickSort(arr,front,i-1); quickSort(arr,i+1,end); } } ``` ---- ## 表現檢討: * 可以多加善用註解，讓面試官更能理解我的想法，也可以讓自己在寫的時候不會因為太緊張而忘記剛剛寫了哪些東西。 * 注意: * 簡短的寫在code後面，避免降低可讀性 * 在寫code之前跟面試官陳述想法的時候也要順便考慮bound並將它講出來，避免讓面試官認為這是寫到一半的時候才想到的。 * 注意: * 一開始講也可能少考慮一些東西，但還是盡量有想到什麼就多提到一下。 * 英文還可以再更流暢。 * 面試官可以再對CODE做更多的提問。 ---- ## 第三次作業 - 他評01 ### Interviewer #### 優點 - 有在解法上做討論 #### 可改進 - 在一開始講解題目時可以在 doc 裡附上 example，讓 interviewer 更好解釋也讓 interviewee 更好理解 - 在 interviewee 直接開始寫 brute force 的時候應打斷，因為這部分沒有鑑別度 - interviewee 在 brute force 花太多時間應打斷，舉例說 addNode() 這 function 就不需要他去 implement - 沒有要求 interviewee 去優化解法，無法看出鑑別度 - 提出 addNode() 優化想法可以不要直接講出來，而是用提示引導 interviewee - 發現 interviewee 的程式碼有疑問應點出來，如第二題的 small variable 之必要性 - Implement quicksort 處應打斷，花費太多時間在題目本身以外 ### Interviewee #### 優點 - 在 Google Docs 上寫 code 很流暢 #### 可改進 - 一開始 $O(n^2)$ 的 brute force 不要急著把 code 寫出來，可以先簡介這個 brute force 的複雜度，然後詢問 interviewer 要不要你寫出來，要多互動讓 interviewer 看到他想看的東西 - Function Signature 應和 interviewer 確認，你的假設不一定正確，且有時定義不同的 Input 形式也會導致解法的不同 - 講解 approach 時可以考慮用例子輔助 - 這取決於公司和 interviewer 喜好，但小弟建議除非 interviewer 特別要求，面試不要用 C，可以幫自己省下很多麻煩，Interviewer 也會比較好理解程式碼。舉例來說當 solution 要用到 hashmap 或 stack 之類的就會造成自己不必要的麻煩 - 若 interviewer 沒有主動要求優化，也該自己提出可優化的想法 - 第二題的程式碼怪怪的，small 這個變數沒有意義(?，應盡量保持程式碼精簡 - 第二題在處理 input not sorted 的情況就遇到了 C 的缺點，Interviewer 可能根本不想看你 implement quicksort，比較好的做法應該是講完 approach 後詢問 interviewer 的意見 - Implement quicksort 可能可以讓 interviewer 看到你對演算法的理解，但也很有可能是浪費自己解到下一題的時間 - 第二題同樣沒寫到 optimal，我會認為 interviewer 想看到的是 binary search，但卻花費整整六分鐘在 implement quicksort 導致完全沒時間提到或寫到 binary search ## 第三次作業 - 他評02 ### 針對 interviewer 的檢討: #### 總結 * 有給 interviewee 提示，剩下的給 interviewer 實作 * 可以多跟 interviewee 討論程式碼，之後再問問題 #### 影片細節 * [16:04](https://youtu.be/oilMDfzOgx4?t=964) 提示 interviewee 有更快的方法 :+1: * [22:36](https://youtu.be/oilMDfzOgx4?t=1356) interviewer 應先閱讀一下程式碼，此時 interviewee 忘記為參數 target 補上型態，或是先問 interviewee 妳要不要再檢查一下你的程式碼 * [30:51](https://youtu.be/oilMDfzOgx4?t=1851) 此時不應句點，應跟 interviewee 討論一下程式碼或是提問，像是為何選擇 quick sort 而非 merge sort？ ### 針對 interviewee 的檢討: ### 總結 * 範例有說明清楚 * 講話速度可以再加快一些 * 程式碼不要擠在一起，字母與符號間隔一個空格，實做不同的功能時，可以適度空一行，像是宣告變數與迴圈，閱讀起來比較舒服 ```c= int* twoSum(int *nums, int numsSize, int target, int*) { int i, j; for(i = 0; i < numsSize - 1; i++) { for(j = i + 1; j < numsSize; j++) { // do somthing... } } } ``` #### 影片細節 * [02:38](https://youtu.be/oilMDfzOgx4?t=158) 如果想要在目前這一頁寫程式，建議游標將移動到 `int* twoSum` 那一行之後按下 `ctrl + shift + end` 選取程式碼，再用 `ctrl + shift + >` 放大選取的字體，這樣操作會比較順，也不會因為放大上面的範例讓 coding 的空間變少。 * [03:49](https://youtu.be/oilMDfzOgx4?t=229) 建議可以改成 `numsSize - 1 是因為 i 用來找出符合 target 的第一個 index，所以會從0掃到倒數第二個，而 j 是接在 i 之後的第二個 index，所以會從 1 掃到最後一個` * [03:57](https://youtu.be/oilMDfzOgx4?t=237) i 若掃到最後一個，j 會超出 nums 的範圍，因為 `j = i + 1`，C 語言的程式依然可以執行但是會得到不正確的答案。 * [04:55](https://youtu.be/oilMDfzOgx4?t=295) integer 的發音 [in-ti-jer](https://www.dictionary.com/browse/integer#) * [05:48](https://youtu.be/oilMDfzOgx4?t=348) 影片中 interviewee 的畫面太大檔到程式碼 sizeof(int) * 2 * [06:01](https://youtu.be/oilMDfzOgx4?t=361) 到 int* twoSum 那一行按下 `ctrl + Enter` 換到下一頁來寫，interviewer 閱讀起來比較舒服 * [10:30](https://youtu.be/oilMDfzOgx4?t=630) 有先講要寫 `addNode` ，而不馬上實作，接著講迴圈執行完後判斷答案的部份，這樣讓 interview 的過程能流暢進行，不會被實作的部份卡住。 * [11:40](https://youtu.be/oilMDfzOgx4?t=700) `else` 要接在 if 的大括號`}`後面，閱讀起來比較舒服 * [11:48](https://youtu.be/oilMDfzOgx4?t=708) 建議將游標移動到 `returnSize = 0;` 那行後按 `shift + ↓(下)` 選取兩行，接著按 `tab` 這樣比較流暢 * [11:57](https://youtu.be/oilMDfzOgx4?t=717) head 是指向 Node 的指標，[不可以說星號](https://www.youtube.com/watch?v=scLFY2CRtFo&t=3855s)，請參閱[你所不知道的 C 語言：開發工具和規格標準](https://hackmd.io/@sysprog/c-prog/%2Fs%2FHJFyt37Mx#ISOIEC-9899-%E7%B0%A1%E7%A8%B1-%E2%80%9CC99%E2%80%9D) * [14:17](https://youtu.be/oilMDfzOgx4?t=857) `curr -> next` 可以改成 `curr->next` 閱讀起來比較舒服，另外要判斷目前的節點是否為 NULL 也可以將判斷式改成 `if(!curr->next)` * [15:57](https://youtu.be/oilMDfzOgx4?t=957) `addNode` 的 do-while loop 的結束條件是 `while(curr)`，亦即 curr 還沒走訪完就一直執行下去，用 `while(1)` 而且沒有搭配 Jump statements ([C99規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) 6.8.6) 會變成無窮迴圈，還會不斷的把新節點的記憶體存放在 heap。 * [16:49](https://youtu.be/oilMDfzOgx4?t=1009) 跟 interviewer 有[良好的互動](https://youtu.be/ZOUE9zDsvK0?t=7448)，順便練習說客套話 :+1: * [22:36](https://youtu.be/oilMDfzOgx4?t=1356) 函數實作後忘記將參數 target 補上型態 int，interviewer 也沒有提醒 * [27:25](https://youtu.be/oilMDfzOgx4?t=1645) swap 的發音 [swop](https://www.dictionary.com/browse/swap#) ## 第三次作業 - 他評03 ### Interviewer #### 缺點 > [00:27](https://youtu.be/oilMDfzOgx4?t=28) * 不用特別說只有唯一解，留給 interviewee 去問，也可以看 interviewee 夠不夠細心去思考這些問題 > [07:16](https://youtu.be/oilMDfzOgx4?t=436) * 問完時間複雜度，應該要問如何改進之類的，直接跳到一個跟時間複雜度不相干的問題，很不流暢 > [15:47](https://youtu.be/oilMDfzOgx4?t=947) * 看到程式有錯沒有詢問 > [16:54](https://youtu.be/oilMDfzOgx4?t=1014) * 沒討論到優化的部分 * 突然跳第二題很不互動 > [23:35](https://youtu.be/oilMDfzOgx4?t=1415) * 問完時間複雜度，應該要問如何改進之類的，直接跳到一個跟時間複雜度不相干的問題，很不流暢 > [24:19](https://youtu.be/oilMDfzOgx4?t=1459) * 應該打斷問 `merge sort` 也很快，為啥不是用 `merge sort` > [30:53](https://youtu.be/oilMDfzOgx4?t=1853) * 突然結束沒互動 #### 優點 * 有進行延伸問題 ### Interviewee #### 缺點 > [00:43](https://youtu.be/oilMDfzOgx4?t=43) * 需要再詢問 `array` 裡數字的範圍，需不需要討論 `overflow` 的問題 > [01:33](https://youtu.be/oilMDfzOgx4?t=95) * `j.......` 意義不大 * 講解方法可以再更簡潔一些 > [02:10](https://youtu.be/oilMDfzOgx4?t=131) * ~~變數~~ 改成輸入參數 > [08:34](https://youtu.be/oilMDfzOgx4?t=514) * `typedef` 寫進去一開始的 `struct` ，行數越精簡越好 > [12:37][11:55](https://youtu.be/oilMDfzOgx4?t=712) * ~~Node 星號~~ 改成指向 Node 的指標 > [13:40](https://youtu.be/oilMDfzOgx4?t=820) * 思考指標的指標的運用 > [15:47](https://youtu.be/oilMDfzOgx4?t=947) * 這樣會是無窮迴圈吧? > [17:53](https://youtu.be/oilMDfzOgx4?t=1073) * 沒問數字範圍，或是會不會出現 array 裡面沒 element * `small` 沒用到? > [28:15](https://youtu.be/oilMDfzOgx4?t=1695) * 巨集使用好像怪怪的? (可能我功力不夠 XD #### 優點 * 想法闡述的算清楚 ## 第三次作業 - 他評04 ### 優點 >Google doc 使用流暢。 >有進行問題延伸及時間複雜度的討論。 ### 檢討 >盡量避免使用 "應該"、"吧" 等帶有不確定性的詞。 #### interviewer > [7:31](https://youtu.be/oilMDfzOgx4?t=451) 可以討論使用 Link list 的目的或優點。 > [16:03](https://youtu.be/oilMDfzOgx4?t=963) 可以與 Interviewee 討論一下，若只是請 interviewee 寫程式意義不大 > [23:45](https://youtu.be/oilMDfzOgx4?t=1425) 若只是想與面試者討論解題想法，可以請面試者不需寫下完整的 Quick Sort 演算法，以省下時間進行後續面談。 #### interviewee >視訊畫面可以縮小一點，有些時候會占用到程式碼的部分 (例如: [5:18](https://youtu.be/oilMDfzOgx4?t=318))。 >寫到一半時進行補充說明可能會使聽者分心，可以的話盡量避免。 >[24:06](https://youtu.be/oilMDfzOgx4?t=1446) 平均時間複雜度在 O(nlogn) 的排序演算法很多，可以的話應說明為何 Quick Sort 會比較快，並且在 Worst Case Quick Sort 有 O(n^2) 的時間複雜度。 ## 第三次作業 - 他評05 ### Interviewer #### 優點： * 16:03 有提示更好的解法，interviewee 也能從這個提示中學習。 * 有將原本題目做進一步的變化。 #### 可改進： * 建議可在 Approach 階段主動與 interviewee 互動，討論解題思路。 ### Interviewee #### 優點： * 口語表達流暢清晰。 * 一邊 Coding 時的說明很順暢。 * 16:49 收到提示且順利實作出來後，有適時與 interviewer 互動。 #### 可改進： * 可與 interviewer 多一點互動，例如：Repeat 和 Example 後停一下詢問這樣的理解是否正確，或是說明完 Approach 可以停一下看 interviewer 有什麼想法，也許 interviewer 不會想花太多時間在基本方法的實作上，就會直接將 interview 往變化題推進。 * Code 同一個括號的部分因爲換頁切斷，不斷上滑下滑跳來跳去會看得比較辛苦，建議如果同一個括號盡量在同一頁內完成，閱讀 code 時會比較順暢。 ## 第三次作業 - 他評 06 #### 優點 * google doc全螢幕且字體大小適中。 * Interviewee不疾不徐，按照REACTO方式順暢應答。 * 邊寫邊描述想法，有條有理很清楚。 * [16:04](https://youtu.be/oilMDfzOgx4?t=964) Interviewer在Interviewee提出方法後，馬上與他討論將解放前面是不是更好，很好的互動而不是一問一答像在演戲。 #### 可改進 * Interviewer一開始提到希望程式用document的方式把他寫下來，聽起來語意怪怪的。 * Interviewer在講解題目就按照稿唸，對於Interviewee可能幫助不大。 * loop, KK[lup] 可能發音要注意一下。 * [1:23](https://youtu.be/oilMDfzOgx4?t=83) ......j這樣的表示方式可能沒有實際幫助到了解，其實透過描述Interviewer應該就知道你的方法是什麼了。 * 指標的部分不應該講星號，老師應該會介意(?) * [5:14](https://youtu.be/oilMDfzOgx4?t=314) 視訊畫面切太大佔太大版面且導致擋到程式碼。 * [6:24](https://youtu.be/oilMDfzOgx4?t=384) Interviewer問到：你可以解釋一下他的時間複雜度及相對應的程式碼嗎？時間複雜度我們應該都是討論整個程式，不太懂相對應的程式碼想表達什麼，應該是要Interviewee去解釋為什麼是這個等級的意思吧(?) * [7:26](https://youtu.be/oilMDfzOgx4?t=446) Interviewer問了方法，Interviewee在描述完方法後一樣應先跟Interviewer討論，不要急著寫出來。 * [20:31](https://youtu.be/oilMDfzOgx4?t=1231) if不是loop可能習慣了還是緊張口誤，發音一樣要注意。 * 第二題的small記得小的裡面最大的，但後面都沒有用到。 * [24:07](https://youtu.be/oilMDfzOgx4?t=1447) quicksort時間複雜度 worst case 在資料大到小或小到大排列的時候會是O(n^2)，應該說 Average case 下的時間複雜度為O(nlogn)較適當。 * pivot, KK[ˋpɪvət] 唸法一樣要注意 * swap, KK[swɑp] 同樣是唸法問題 * Interviewer針對Interviewee提出透過qsort先排序再search的方法沒有給反饋突然就後續有消息會通知有點突兀。