2023 年「資訊科技產業專案設計」作業 1

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1 > 貢獻者: 奇諾-Cino 🧔：interviewer 👶：interviewee > [中文影片](https://www.youtube.com/watch?v=NSkmwm80SW4) > [英文影片](https://www.youtube.com/watch?v=t9BU5bpO8jo) ## 面試過程-中文 🧔：你好，感謝你接受敝公司的面試邀請，我看過你的簡歷，你是因為喜歡遊戲進而想要實際參與遊戲開發過程，所以決定來面試敝公司的對吧？ 👶：是的，我在大學時期也有嘗試寫過幾個小遊戲。 ### [1282. Group the People Given the Group Size They Belong To](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/) 🧔：既然如此，在談及工作內容之前，我們先交流一下在遊戲開發上的想法。以常見的多人匹配系統為例，假設玩家可以自由選擇匹配人數，伺服器端將玩家的人數要求依照提交時間先後順序放入數列當中，你能否做出一個系統讓所有玩家匹配到希望匹配人數的團體中呢？ 👶：恩...我先舉個例子，假設我今天拿到： ``` input: [1, 2, 2, 1] output: [[0], [1, 2], [3]] ``` 每個玩家所在的團體的人數等於玩家自己要求的匹配人數對吧？但是可能出現團體湊不全，或者多重答案。 🧔：形容的很棒，我們就先忽略掉湊不全的問題，你就列出一種答案就好。 👶：好的，那麼我會使用map來解決這個問題。 🧔：請你具體解釋一下。 👶：用key代表要求的匹配人數，value代表group，將玩家一個個放入對應的group當中，一旦滿人了就將group放到result裡面，並清空map原本的group。 🧔：好，那請你實作看看 ```cpp vector<vector<int>> groupThePeople(vector<int> & groupSizes) { // map {key = req: value = group} map<int, vector<int>> mp; // res vector<vector<int>> vector<vector<int>> res; // for loop for (int i = 0; i < groupSizes.size(); i++) { // size int size = groupSizes[i]; // add player id into group mp[size].push_back(i); // if group full if (mp[size].size() == size) { // 這行影片中打錯了!!!! // add group into result res.push_back(mp[size]); // group clear mp[size].clear(); } } return res; } ``` 🧔：我們拿之前你提出的範例來驗證看看吧。 (code tracing...) 🧔：你能評估這段程式碼的時間複雜度和空間複雜度嗎？ 👶：時間複雜度是$O(n)$，空間複雜度是$O(n)$ 🧔：恩...不太對，c++的map類別是一顆紅黑樹，而不是雜湊函數。 👶：咦?是這麼一回事嗎？那麼時間複雜度應該是$O(nlogn)$才對囉？ 🧔：如果你要用雜湊函數，可以試試unordered_map，跟map的差別在於它沒有排序，但是檢索的時間複雜度是$O(1)$。 👶：好的，我會回去查查看。 ### [2140. Solving Questions With Brainpower](https://leetcode.com/problems/solving-questions-with-brainpower/description/) 🧔：另外還想問你一個關於遊戲數值規劃的問題，現今的遊戲常常推出限定活動道具，假設公司設計好一整季的活動安排，每個活動所能獲取的資源量都相等，但限定道具的取得成本不一，價值(強度等等)也不一，玩家可以預付資源取得道具，但是在還清成本之前不能再次取得道具，公司想用一套系統去計算每種活動安排最大可獲得的價值，對此你有甚麼看法。 👶：既然每個活動的資源量都相同，那就以此為標準化單位假設: ``` input = [(1, 2), (3, 4), …] output = the most gain can get ``` 每次活動都可以選擇取得道具或跳過道具，一旦選擇取得道具就要跳過相應的活動次數。這樣設計的邏輯你覺得如何。 🧔：恩，差不多是這樣。 👶：既然如此，每次活動都有兩個分支，利用遞迴函數function去比較兩種選擇的優劣，函數回傳在該次活動之後所能得到的最大價值(gain)，如此一來function(0)就會是答案了。 🧔：好，那請你把它實作出來。 ```cpp long long innerFunction(vector<vector<int>> & events, int e, int N) { // end if e not in events if (e >= N) { return 0; } // compare buy or skip long long point = max(events[e][0] + innerFunction(events, e + events[e][1] + 1, N), innerFunction(events, e + 1, N)); //return return point; } long long mostPoints(vector<vector<int>> & events) { // call function(0) return innerFunction(events, 0, events.size()); } ``` 🧔：但是你這個程式碼當i越大，被重複計算越多次，你有甚麼解決方法嗎？ 👶：既然每次計算f(i)都不會改變回傳值，不如分配一個空間將f(i)的結果儲存起來，重複讀取就好了吧。 🧔：聽起來你似乎有想法了。但這邊我有個建議，你有辦法將遞迴給拿掉嗎？ 👶：有趣，所有的回傳值都是由後面活動推導而出的，那不然乾脆從最後一個活動計算起。 🧔：你試著寫寫看。 ```cpp long long getMostPoint(vector<vector<int>> & events) { int N = events.size(); // dp [index = event, value = mostpoint] long long* dp = new long long[N+1] (); // for for (int i = N -1; i >= 0; i--) { //compare buy or skip dp[i] = max(events[i][0] + dp[min(i+events[i][1]+1, N], dp[i+1]); } return dp[0]; } ``` 👶：如此一來，時間複雜度就從原本的$O(2^n)$降到$O(n)$。空間複雜度看似變成$O(n)$，但考慮到每次遞迴的空間成本，之前的程式碼甚至可能stack overflow。 🧔：恩，時間也差不多了，很高興能和你討論這些議題，也還請留意一下電子信箱，如果有需要你參加第二次面試，我們會在下星期通知你，祝你有個美好的假期。 👶：我也十分樂在其中，也感謝貴公司給了我這次的機會，期待貴公司的通知。 ## 面試過程-英文 ### [9. Palindrome Number](https://leetcode.com/problems/palindrome-number/description/) 🧔：Hello, welcome to the interview.I'm Brid, a software engineer. Nice to meet you. 👶：Hi, I'm Cino, a new graduate from National Cheng Kong University. Nice to meet you too. 🧔：Okay, let's start our discussion. Do you know palindrome numbers? 👶：Uh...I'm not quite sure. Can you give me an example? 🧔：Okay, palindrome means the words that reads the same backwards and forwards. 👶：Do you mean like racecar or rotator? 🧔：Yes, you got it. So, palindrome numbers are the number which are palindrome, like 11 or 121. 👶：But how about negative numbers? 🧔：That a good question. Negative numbers are not palindrome number because minus sign doesn't exist at the end of the number. 👶：Okay. I got the point. 🧔：Today, you need to create a function which parameter is an integer x, and the function has to return true or false depands on whether integer x is a palindrome number or not. Any questions? 👶：Uh..., so if I input a number 121, it will return true, right? 🧔：Yes, of course. 👶：And if I input 123, it return false. 🧔：Absolutely. 👶：Okay, in this case, I will try to convert the input to string first. Then, I can use two pointers to compare front and bottom charactors. If they are different, I will return false, otherwise, the pointers will step close to the middle, and compare the charactors again. 🧔：Sounds great. Let's start coding. ```cpp bool isPalindrome(int x) { // convert x to string string str = x.to_string(); // imple right, left int right = str.size() - 1, left = 0; // compare while (left < right) { if (str[left] != str[right]) return false; left ++; right --; } return true; } ``` 👶：Let's make an example. If I input 12321 into the fuction, then... 👶：And the time complexity is $O(n)$, space complexity is $O(n)$ since we create a copy string of x. 🧔：It do work, but I think there is a possible way to remove the converting, can you try it? 👶：Okay, maybe we can create an integer 'y', then copy unit digits one by one to 'y', after copying the while digits of x, 'y' will become the reverse of x. ```cpp bool isPalindrome(int x) { // convert x to string string str = x.to_string(); // imple right, left int right = str.size() - 1, left = 0; // compare while (left < right) { if (str[left] != str[right]) return false; left ++; right --; } return true; } ``` 🧔：Well done, and that the whole interveiw today. Keep an eye out for the schedule of the next interveiw. Hope your have a nice day. 👶：Thank you, you too. --- ## 第二次作業-他評01 ### Interviewer - [ ] 優點 [0:00](https://www.youtube.com/watch?v=NSkmwm80SW4?t=0): 在開頭的地方很尊重面試者，和面試者小聊一下也是面試中認識一個人重要的環節，面試模擬這樣感覺也比較真實。 [0:24](https://www.youtube.com/watch?v=NSkmwm80SW4?t=24): 將題目包裝成實際應用不使用原題讚 - [ ] 可以改進的部分 [12:05](https://www.youtube.com/watch?v=NSkmwm80SW4?t=605): 這邊既然提到unordered map，其實可以繼續問說在本題的情況下，剛剛你是用map實作，現在有了unordered map你會在兩者之間選擇哪種作法? 考量的點是什麼? ### Interviewee - [ ] 優點 * Reacto做得詳細 * 先利用comment部分說明自己的想法approach，在實際寫code的方式值得學習 * [5:13](https://www.youtube.com/watch?v=NSkmwm80SW4?t=313): 編寫程式邊說明做的很棒，不會只念自己在打的東西 * 實作速度快 - [ ] 可以改進的部分: * [13:51](https://www.youtube.com/watch?v=NSkmwm80SW4?t=831): 問完「對不對」應該給面試官時間確認理解是否正確。 ## 第二次作業-他評02 ### Interviewer - [ ] 優點 * 出題包裝很用心，擬真實際面試情境 * 和 interviewee 的對談和問題討論都展現出面試「溝通」的本質，不會很像考試，而像在針對該情境交換想法 ### Interviewee - [ ] 優點 * 解題節奏很快且通順，先註記再完成程式的方法很棒 * 能夠一邊寫程式一邊講解，中間幾乎沒有卡住，讓人很享受解題過程 - [ ] 可以改進的部分 * 第二題直接使用 long long 去定義，範圍可以先問 interviewer 取得 ## 第二次作業-他評03 ### Interviewer - [ ] 優點 * 從實際的應用情境描述出題很棒，不只考驗面試者解決問題的能力，還能測試面試者定義問題的能力 * 引導面試者進行 REACTO 的流程很棒 ### Interviewee - [ ] 優點 * 解題過程流暢，能夠一邊撰寫程式碼，一邊解釋自己的想法 * 口齒清晰、語速適中 * 在討論 map/unordered_map 的複雜度時，在被面試官糾正後，能夠及時反應，並給出正確答案，顯示面試者具有臨場反應能力 - [ ] 可以改進的部分 * 在 Google Docs 上使用 Arial 字型呈現程式碼看起來較為凌亂不易閱讀，可以加上一些空行，並改用其他等寬字型如 Roboto Mono、Comfortaa、Verdana * 第三題似乎想嘗試使用註解寫 pseudocode 來解釋想法，但寫得太像程式碼，有太多不必要的細節，應該聚焦在更高層次的想法