--- ###### tags: `資訊科技產業專案設計` --- # 資訊科技產業專案設計課程 作業4 > 貢獻者: 霸佛羅 Buffalo ## 第一題 > [**影片連結**](https://youtu.be/d74vuI-Xc6c) #### 題目 Design a class: 1. Inserting a value (no duplicates) 2. Removing a value 3. GetRandom a vlue that is already inserted(with equal probability) #### 過程 :dog:: interviwer :cat:: interviwee :dog:: / * question statement * / :cat:: Is there any limit for the range of the inserting values? :dog:: You can assume that will be a resonable amount, so you can ignore that problem. :cat:: What should I do if the removing value doesn't exist? :dog:: Okay, if there isn't exist in the class, you can just ignore it. :cat:: I think I will use an array to store all exist elemnets, and also use a hash map to store each element's index. Everytime inserting a value, I will find whether the value is inside the hash map or not. If it is inside, it means it's the duplicate element, so I could ignore it. However if it is not inside the hash map, I will append it into the end of the array, and store the index inside the hash map. On the other hand, while removing, I will get the element's index and swap it to the end of the array then pop it. And I also have to update the information inside the hash map. And for the getRandom function, I could just randomly pick an element in the array. All there operations' complexity will be in O(1). :cat:: / * Coding * / :dog:: That's the end of our coding interview today, thanks. #### 程式碼 ```cpp= class A{ public: A(){ srand((unsigned int)time(NULL)); } void insert(int x){ if(mp.count(x)) return; arr.push_back(x); mp[x] = arr.size() - 1; } void remove(int x){ if(!mp.count(x)) return; int idx = mp[x]; swap(arr[idx], arr[arr.size()-1]); arr.pop_back(); mp.erase(x); mp[arr[idx]] = idx; } int getRandom(){ int idx = rand() % arr.size(); return arr[idx]; } private: vector<int>arr; unordered_map<int,int>mp; }; ``` #### 改進方案 - 忘記要分析空間複雜度 - 命名盡量取有意義的命名，不要用A命名 - 講解做法時的英文口說要再練到更流利 ## 第二題 > [**影片連結**](https://youtu.be/d74vuI-Xc6c?t=1043) #### 題目 1 g of protein provides 1 calorie. 1 g of oil provides 5 calories. Nutritionists recommend that we consume exactly $x$ calories a day. Now we have $a$ g of protien and $b$ g of oil. Could you figure out is it possible to achieve the goal? Example: ```c++= input: a = 2 // 2g of protien b = 2 // 2g of oil x = 7 output: True // 2g of protien and 1g of oil input: a = 2 // 2g of protien b = 2 // 2g of oil x = 8 output: False ``` #### 過程 :dog:: interviwer :cat:: interviwee :dog:: / * question statement * / :cat:: Ok, I will like to repeat it again. In the example, if we take 2g of protien which provides 2 calories, and 1g of oil which provides 5 calorires. So the total sum up to target value which is 7. :dog:: Yeah, that's right. :cat:: The first way come to my mind is there will be a protien array which store all posible calories. Then we also do oil the same way. Then we can do bruce force. We can iterate over all poisble calories provide by protien and calories, and check whether it could sum up to target value or not. :dog:: Could you tell me what is the time complexity for your appraoch? :cat:: Time complexity will be O(a * b) and space complexity will be O(a + b). :dog:: Ok, I think you can start your coding now. :cat:: /* Coding */ :dog:: Ok, it looks like there is no problem of your code. However the complexity is really high. Could you come up with another soution that is better? :cat:: Ok, I think I can use a hash map for getting the value we want. So the time complexity will be O(a+b). :dog:: So I think you can start your coding now. :cat:: / * Coding * / :dog:: Ok, it looks great. However it can still be much more faster by using some mathematical skills. So could you come up with another faster solutions? :cat:: Ok, so I could just take as much oil as I could. Then we can check whether the remainder is smaller than protiens we have or not. :dog:: Sounds great. You can start your coding. :cat:: / * Coding * / :dog:: That's the end of our coding interview today, thanks. #### 程式碼 ```python= # Time complexity: O(ab) # Space complexity: O(1) def brute_force(self, a, b, x): ### BRUTE FORCE ### protien = [] oil = [] for i in range(a + 1): cal = i * 1 # each of the protien have 1 cal protien.append(cal) for i in range(b + 1): cal = i * 5 # each of the oil have 5 cal oil.append(cal) for i in range(a + 1): for j in range(b + 1): if (protien[i] + oil[j] == x): return True return False # Time complexity: O(a+b) # Space complexity: O(1) def hashing(self, a, b, x): hash_map = set() for i in range(a + 1): cal = i * 1 # each of the protien have 1 cal hash_map.add(cal) for i in range(b + 1): target = x - i * 5 if target in hash_map: return True return False # Time complexity: O(1) # Space complexity: O(1) def constant(self, a, b, x): n = x // 5 n = min(n, b) x -= n * 5 return x <= a ``` #### 改進方案 - 可以在面試官詢問之前，就主動分析自己所想的方法的時間與空間複雜度 ## 第三題 > [**影片連結**](https://youtu.be/d74vuI-Xc6c?t=1890) #### 題目 We have a car located at the starting city $u$. We are planning a trip to the city $v$. The car will burn 1L of fuel per kilometer. Each time when we arrive at any city, we could fuel our car up to a safe amount $L$. Given the roads connecting each other cities, could you please figure out what is the minimum safety amount $L$, so that we will not find ourselves run out of fuel and stuck in the mid of a road? Note that all the roads are biconnected. Example: ```c++= input: u = 0 v = 3 roads = [ [0,1,10] // a road that connects cities 0 and 1 with a distance of 10km [0,2,20] [1,3,30] [2,3,20] ] output: 20 ``` #### 過程 :dog:: interviwer :cat:: interviwee :dog:: / * question statement * / :cat:: For a given specific route from starting point to end point, the safety amount will equal to the maximum weight of all the edges on the route. Is that right? :dog:: Yes. :cat:: Because the answer will be exactly equal to the weight of one of the edge, I could get all of the weights first and try to examine all of the possible answers. Each time to examine, I will have to run one time of DFS or BFS. The complexity will be O(E*(V+E)). :dog:: Ok, you can start coding. :cat:: / * Coding * / :dog:: Ok, so is it possible for a better solution? i think I can give you a hint for binary search. :cat:: For the approach now, we just examine all possibilities. We could exmaine the answer by binary seach, so the time complexity will come down to O(lg(E)*(V+E)). :dog:: Yes, that's right. :cat:: / * Coding * / :dog:: So could you come up with a better solution? :cat:: Will there be any hint? :dog:: Yes, of course, so the problem is related to shortest path algorithm, which is the single source one. :cat:: Ok, I think I could modify the method of Dijkstra algorithm. The array to store current shortest distance in Dijkstra will change to store the minimum safety amount from source to current vertex. :cat:: / * Coding * / :dog:: That's the end of our coding interview today, thanks. #### 程式碼 ```cpp= #include <bits/stdc++.h> using namespace std; int f(int u, int v, vector<vector<int>> roads){ // O(V^2) vector<vector<int>> adj; // adjacency matrix for(auto r : roads){ adj[r[0]][r[1]] = r[2]; adj[r[1]][r[0]] = r[2]; } vector<int> ans(adj.size(), INT_MAX); vector<int> vis(adj.size(), false); ans[u] = 0; for(int i = 0; i < adj.size(); i++){ int p = -1; int minimum = INT_MAX; for(int j = 0; j < ans.size(); j++){ if(vis[j]) continue; if(minimum > ans[j]){ minimum = ans[j]; p = j; } } if(p == -1) break; vis[p] = true; for(int j = 0; k < ans.size(); j++){ if(j == p || vis[j]) continue; ans[j] = min(ans[j], max(ans[p], adj[p][j])); // change compare to dijkstra } } return ans[v]; } ``` #### 改進方案 - 有時候會過於專注在寫程式碼以至於忘記要邊講邊寫 - 要記得主動分析複雜度 --- ## 檢討自我整學期的表現 目前是大四雙主修生，暑假再查詢課程時發現老師有在開面試課，就覺得很新鮮想趁這個機會好好學習，雖然功課花的時間之多，要和其他科好好分配時間，不過得到的資訊與收穫確實讓我很慶幸沒有退選！ 產出部分，第一次寫 CV，其實遇到了許多困難，從一開始用 CakeResume 排版製作，雖然方便但字體及間距有許多加強空間，因此經由爬文及詢問朋友後決定使用 google doc。文字內容部分，從一開始不知道有甚麼專題可以放，到後來用具體且可量化的方式呈現成果，並經由詢問老師以及主動聯繫美國朋友加以改善，並於後來也有參考一些 Champ 學長的建議，成功完成了出版履歷；Linkedin 部分，一直都知道需要經營並整理自己的作品，之前會都覺得自己沒什麼東西，不過在老師邀請那麼多學長來過後，發現是個跟別人 connect 的好工具，目前已經把現在做的事放上去，也有把握機會跟學長 connect 並且也有做交流，期待日後還能夠持續有所連結，期待日後能在職場上有所人脈！ 關於這堂課作業涵蓋最多的模擬面試，真的比我想像中不容易許多，除了要邊寫邊打更要充分的展現溝通能力，不是只是把題目解出來就好，這部分覺得自己還有很大的進步空間不過在這學期也有自己看蠻多其他創作者的模擬面試影片，會繼續努力進步。除此之外，follow up question 也是日後還要多加練習的，因為很多題目可以有很多種變化，因此不能只是背該題目最佳解而已，因此這段過程中也大大的意識到自己的不足，意識到後期待日後成長。