# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS11ooE4Rh)」作業 1 > 貢獻者: 夾克-jacket > interviewer : 🐱 > interviewee : 🐭 > [模擬面試錄影(漢)](https://www.youtube.com/watch?v=hZGCMWOjzhE) > [模擬面試錄影(英)](https://www.youtube.com/watch?v=nkG86AooYUc) > [模擬面試錄影(漢)](https://www.youtube.com/watch?v=r78MISeher0) ## [338. Counting Bits](https://leetcode.com/problems/counting-bits/) ### 面試過程 🐱 : 給你一個整數 n ， 你必須回傳長度 n + 1 的陣列 ，陣列中的元素為 0 ~ n 個別的二進位表示中有多少個 1。 🐭 : 根據給定的 n ， 我必須求出 0 ~ n 個別的二進位表示中 1 的數量有多少，舉例來說若 n == 5 ，那 0 ~ 5 二進位中 1 的數量分別為 [0,1,1,2,1,2]，這就是我們要求的陣列。 ``` n = 5 0 => 0 => 0 1 => 1 => 1 2 => 10 => 1 3 => 11 => 2 4 => 100 => 1 5 => 101 => 2 ans =[0,1,1,2,1,2] ``` 🐭 : 我最直覺的方法是用暴力法去找出每個數字位元為 1 的數量有多少，以 5 為例子，每次去看最右邊的位元是否為 1，是的話就將此數字位元為 1 的數量增加，並目前的數字右移一位直到變為 0，就可以得到一個數字位元為 1 的數量。 ``` 5 => 101 => count++ => 10 => 1 => count++ => 0 ``` 🐭 : 接著來實作程式碼，我要回傳一個陣列，而我的函式叫 `CountBits` 輸入的參數為 `n` ， 那我先宣告我要回傳的陣列 `ans` ， 接著走訪 0 ~ n 的每個數字，這裡用整數 `num` 表示目前正在檢測的數字 、 `count` 表示位元為 1 的數量，當檢測的數字還大於 0 時，表示還有位元為 1，這時候去檢查最右邊的位元是否為 1，是的話就增加 `count`，並將檢測的數字右移一位，檢測完後就將 `count` 加入我要回傳的陣列，最後檢測完 0 ~ n 後就可以回傳陣列 `ans`。 ```c vector<int> CountBits(int n) { vector<int> ans; for(int i = 0; i <= n; ++i) { int num = i, count =0; while(num > 0) { if(num & 1) ++count; num >>= 1; } ans.push_back(count); } return ans; } ``` 🐱 : 好，看起來沒問題，那如果要進一步改進程式碼的話，你打算怎麼做? 🐭 : 我們可以思考一個數字位元為 1 的數量跟他前一個數字的關係，以下為例子，那可以發現我們先從右往左找第一次出現 1 的位元索引位置，索引位置的 1 是因為加一而從 0 變為 1 的，而索引位置前的 0 就是因為加一而從 1 變為 0，最後可以發現 `當前數字位元為 1 的數量` = `前一個數字位元為一的數量 + 1 - 索引位置`。舉個例子這邊的優化， 假如有一個數字 $11000011_2$，原來的方法需要跑 8 次才能求出位元為 1 的數量，新的方法則只需要跑兩次。 ``` 2 => 010 => 1 3 => 011 => 2 => 0 => 1 + 1 - 0 4 => 100 => 1 => 2 => 2 + 1 - 2 = 1 110000011 => 4 110000010 => 3 + 1 + 0 ``` 🐭 : 接著來實作程式碼，因為會用到前一個數字的結果，所以我們要先將 0 位元為 1 的數量存入 `ans` ， 接著便走訪 1 ~ n ，找出當前數字第一個位元為 1 出現的索引，找到之後就能透過前一個數字的結果及索引來算出當前數字位元為 1 的數量。 ```c vector<int> CountBits(int n) { vector<int> ans; ans.push_back(0); for(int i = 1; i <= n; ++i) { int num = i, index = 0; while(!(num & 1)) { ++index; num >>= 1; } ans.push_back(ans.back() + 1 - index); } return ans; } ``` 🐱 : 如果你去思考將數字分為 2 的倍數和不是 2 的倍數，你可不可以想出更好得解決方法。 🐭 : 當數字為奇數時，位元為 1 的數量會比前一個數多一；若為偶數，位元為 1 的數量與右移一位相同，因此我們只要判斷當前的數字是奇數還是偶數，就能用前面算出的值來求出此數位元為 1 的數量。 ``` 2 => 010 3 => 011 => 1 + 1 if num == odd dp[num] = dp[num] + 1 4 => 100 if num == even dp[num] = dp[num/2] 7 = 111 14 = 1110 ``` ```cpp vector<int> CountBits(int n) { vector<int> ans; ans.push_back(0); for(int i = 1 ;i <=n ;++i) { if(i % 2 == 1) ans.push_back(ans.back() + 1); else ans.push_back(ans[i >>1]); } return ans; } ``` ## [136. Single Number](https://leetcode.com/problems/single-number/) ### 面試過程 🐱 : Given a non-empty array of n integer ， every elements appear twice except for one ， find that single one. 🐭 : So there is one single number in this array ， and other number appear in this array will show twice. ``` [2,1,4,2,4] => 1 ``` 🐭 : OK ， here is my approach ， First ， I will traverse this array and use a hash table to record how many times a number appear ， then traverse the hash table to see which number appears only once. Since insert and find operation in hash table are $O(1)$ ， first step time complexity will be $O(n)$ ， and the second step will take $O(n + m)$ to traverse the hash table ， n is the number of integer and m is the number of bucket ， So total time complexity will be $O(n+m)$. ``` first =>traverse array => hash table => O(n) second => traverse hashtable => O(n+m) toal time complexity => O(n+m) ``` ```cpp int FindSingleNum(vector<int> arr) { unordered_map<int,int> m; for(auto &x : arr) { ++m[x]; } for(auto itr = m.begin(); itr != m.end(); ++itr) { if(itr->second == 1) return itr->first; } return -1; } ``` 🐱 : OK ， Can you avoid to use hash map to reduce memory usage，maybe you can think is it possible to solve it in $O(1)$ additional space complexity? 🐭 : emmm... ， since there's one single number and all the other number is in pairs ， we can use the xor to eliminate these pairwise number ， and finally get the single number. ```cpp int FindSIngleNum(vector<int> arr) { int ans = 0; for(auto &x : arr) ans ^= x; return ans; } ``` 🐱 : Does the sequence of number will affect the xor operation? 🐭 : No ， since xor operation obey the commutative and associative property ， sequence of number doesn't matter. ## [1584. Min Cost to Connect All Points](https://leetcode.com/problems/min-cost-to-connect-all-points/) ### 面試過程 🐱 : 給你一個陣列 points ，陣列中的每一個元素都是二維坐標系上的一個點，連接兩點的成本為他們的曼哈頓距離，我希望你求出讓所有點連接的最小成本。 🐭 : 好，所以我現在有一些二維座標上的點，我必須讓所有點連接，也就是說任兩點一定有一條路徑，並回傳最小成本。舉例來說，假設現在有三個點 [(0,0),(1,0),(0,2)]，那我有四種方式可以滿足條件，那成本分別為 [4,5,3,6]，那最小成本就是 3。 ``` [(0,0),(1,0),(0,2)] [4,5,3,6] => 3 ``` 🐭 : 這裡我們可以使用最小生成樹來解這個問題，首先我們要先算出點與點之間的成本當作邊，那我打算用 prim's algorithm 來求出 MST ，首先我們先隨機選一點開始，將這點的所有邊作為可選擇的邊，選出成本最低的邊，並將另一點的所有邊也加入可選擇的邊，若選到的邊的終點已被連接過，則重新再選一條邊，重複上述動作直到選出 n - 1 條邊 (n 為點的數量)。 ``` first: construct edge second: prim’s algorithm minheap: choosable edge start point: 0 add edge of point 0 to minheap take min edge of minheap => if end point connect repeat this toalcost += cost add edge of endpoint to minheap ++selectedge repeat until selectedge == n - 1 return toalcost; ``` 🐭 : 接著來實作程式碼，我們用 `E` 來建立每個頂點他所有邊對應的頂點及成本，那首先我們就任意兩點一組並建立對應的邊。再來我們就實作 prim's 演算法。首先我們要有一個 minheap `Q` 作為我們目前能選擇的最小邊，接著我們選定一個起始頂點，接下來我們取出最小的邊，若這個邊的終點已經被連結過了就重新再選一個，反之則將此點所連接的邊都加入 minheap 並將這個點標記為已連接，重複此步驟直到找出 n - 1 條邊(n 為頂點數)，就能求出最小成本。 ```cpp int MinCostConnPoint(vector<vector<int>> &points) { vector<vector<pair<int,int>>> E(points.size()); for(int u = 0; u < points.size(); ++u) { for(int v = u + 1; v < points.size(); ++v) { int cost = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]); E[u].push_back({cost,v}); E[v].push_back({cost,u}); } } priority_queue<pair<int,int>, vector<pair<int,int>,greater<pair<int,int>>> Q; Q.push({0,0}); bool con[points.size()]; memset(con,false,sizeof(con)); int edgeneed = points.size();; int cost = 0; while(edgeneed) { auto e = Q.top(); Q.pop(); if(!con[e.second]) { cost += e.first; –edgeneed; con[e.second] = true; for(int i = 0; i < E[e.second].size(); ++i) { if(!con[E[e.second][i].second]) Q.push(E[e.second][i]); } } } return cost; } ``` 🐭 : 時間複雜度為 $O(ElogV + VlogV)$。 ``` VlogE + 2ElogE =>O(VlogV+ ElogV) logE = logV E = V^2 logE = logV^2 => 2logV => logV ``` 🐱 : 好，那可以發現像 `selectedge.first` 及 `selectedge.second` 很難直接去知道這個值代表什麼，如果要改進程式碼的可讀性你打算怎麼做? 🐭 : 我會定義一個結構體 `edge` 來表示一個邊的終點及成本，因為我們要比較邊的成本大小，所以要做 operator overloading。 🐭 : 那我這邊直接用剛才的程式碼做修改可以嗎? 🐱 : 可以。 ```cpp struct edge { int cost, endpoint; bool >operator(const &y) const { return cost > y.cost}; } int MinCostConnPoint(vector<vector<int>> &points) { vector<vector<edge>> E(points.size()); for(int u = 0; u < points.size(); ++u) { for(int v = u + 1; v < points.size(); ++v) { int cost = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]); E[u].push_back({cost,v}); E[v].push_back({cost,u}); } } priority_queue<edge, vector<edge,greater<edge>> Q; Q.push({0,0}); bool con[points.size()]; memset(con,false,sizeof(con)); int edgeneed = points.size();; int cost = 0; while(edgeneed) { auto e = Q.top(); Q.pop(); if(!con[e.endpoint]) { cost += e.cost; –edgeneed; con[e.endpoint] = true; for(int i = 0; i < E[e.endpoint].size(); ++i) { if(!con[E[e.endpoint][i].endpoint]) Q.push(E[e.endpoint][i]); } } } return cost; } ``` 🐱 : 那你覺得這個問題適合用最小生成樹來解決嗎? 🐭 : 將剛分析的時間複雜度以 n 改寫可以發現是 $O(n^2logn)$，那如果以暴力法每次去找未連接的點最短邊並相連的話時間複雜度是 $O(n^2)$，所以生成樹並不是這個問題的最佳解。 ``` V = n E = n(1+n)/2 O(nlogn + n^2logn) => O(n^2logn) O(n^2) ``` ## 自我檢討 * 加強自己的語言組織能力，讓自己能將想表達的話有條理的說出 * 在邊寫 code 邊講解時很容易打錯字 * 口齒要更清晰、聲音要更清楚 * 跟面試官要再多一點互動 # 第二次作業-他評01: ## interviewer 優點： * 有把題目解釋清楚 可改進： * 不應該在interviewee一coding完馬上結束，可以再來回和interviewee互動 ## interviewee 優點： * 在coding之前把approach非常完整的講解清楚 * coding時解釋清楚 可改進： * 漢第(一)題，在interviewer提出有什麼改進方案之前，interviewee應該在做完程式後稍微分析一下時間和空間複雜度，不然interviewer說看起來沒什麼問題之後突然要你優化，這樣有些奇怪 ## 第二次作業-他評 02 - interviewer - 優點: - 題目列得很清楚 - 可改進地方: - 可以嘗試將題目轉換成現實中會遇到的問題，讓interviewee不會太快就知道你想考他什麼 - interviewee - 優點: - 會先用pseduo code來解釋流程 - 舉例清楚明瞭 ## 第二次作業-他評 03 ### interviewer - [ ] 優點 * 能夠非常明確清楚的說明題目，而且還能夠舉例給interviwee聽，過程聽起來非常的順滑且清楚，interviewee甚至能夠在聽題目的過程中就開始想要怎麼解。 - [ ] 可改進的地方 * 如果能夠在interviewee說明自己的想法的時候適時的提供反饋，說不定能激發他產生其他種解法。 ### interviewee - [ ] 優點 * 不著急於建構程式碼，而是一樣先舉例並且聽取interviwer反應後再開始撰寫。 - [ ] 可改進的地方 * 可以試著分析自己的程式碼的複雜度，這樣大概能想到下一個優化的算法大概是多少複雜度。