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

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1 > 沐揚仁-sheep >[video](https://www.youtube.com/watch?v=DCdx849bjDQ) > :clown_face: : Interviewer > :japanese_goblin: : Interviewee ## [283. Move Zeroes](https://leetcode.com/problems/move-zeroes/) > Video:[00:59](https://www.youtube.com/watch?v=DCdx849bjDQ&t=59) ### 模擬面試過程 :clown_face: : 我們有一個系統是在火車軌道上偵測有無異物入侵，以台南車站為原點位置為0，我們用±來表示南北的方向，往北為正，往南為負，若偵測到異物入侵時，我們會記錄入侵的位置，方便工作人員排除狀況，那我們想要去處理這些紀錄的資料，入侵位置依照時間按照順序排出，但是當入侵位置為台南車站時，我們就將這筆資料挪到最後，因為我們想要去關注除了台南車站以外的其他入侵位置和時間的關係也就是說當我們收到五筆資料，依照時間順序為 0 11 0 3 -12 以陣列的方式呈現那我希望經過處理後可以得到 11 3 -12 0 0 :japanese_goblin: : 目前是希望經過處理後可以把0這個位置挪到最後方，但其他位子的順序依然保持不變對嗎 :clown_face: : 對 :japanese_goblin: : 那位子的紀錄最南和最北為多少以及表達位子的精確度到小數點幾位？ :clown_face: : 那麼表示位子的範圍是往南 $2^{31}$ 公里一直到往北 $2^{31}$ -1 公里，那位子的精確度表示到整數即可 :japanese_goblin: : 一次最多需要處理的資料會有多少呢？ :clown_face: : 需要處理的資料最多會收到 10,000 筆位置資訊最少會有 1 筆 :japanese_goblin: : 那對於處理方式有什麼要求嗎？ :clown_face: : 希望盡可能的減少記憶體空間，只能在原本的資料中操作，不能再複製一份資料去處理，並且盡可能減少操作的次數 ```c void moveZeroes(int* pos, int posSize){ //time complexity:O(n^2); //space complexity:O(1); int i=0,j=0; while(j<posSize){ if(pos[i]==0){ while(j<posSize){ if(pos[j]!=0){ pos[i]=pos[j]; pos[j]=0; break; } else{ j++; } } } i++; j++; } } ``` :clown_face: : 看起來確實能成功處理資料，那有更精簡的做法嗎? :japanese_goblin: : 我思考一下!若我們只專注在非0的位置去做交換，不特別紀錄0所在的位置，這樣我們只需掃過一次資料，就可以處理完資料 ```c void swap(int *a ,int * b){ if(*a!=*b){ *a=*a^*b; *b=*a^*b; *a=*a^*b; } } void moveZeroes(int* pos, int posSize){ //time complexity:O(n); //space complexity:O(1); int i=0,j=0,k; if(posSize>1){ int i=0,j=0; for(k=0;k<posSize;k++){ if(pos[j]!=0){ swap(&pos[i],&pos[j]); i++; j++; } else{ j++; } } } } ``` :clown_face: : 時間複雜度確實下降了!看來距離調查結果又更進一步了!謝謝你提出的方法! ## [122. Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/) > Video:[16:02](https://www.youtube.com/watch?v=DCdx849bjDQ&t=962s) ### 模擬面試過程 :clown_face: : 有買賣股票的經驗嗎？ :japanese_goblin: : 沒有 :clown_face: : 沒有的話也沒關係的，如果你今天有預知股價的能力，但是這個能力很不穩定，有時候可以預知三天，有時候可以預知七天，每次預知的天數都不固定，而且有個限制，你買入後，要賣出才能做下一次買賣，也就是說你手上沒有股票時才能買股票，那在每一次預知的期間你能算出你最大獲利是多少嗎？ :japanese_goblin: : 有限制購買股票的張數嗎？ :clown_face: : 有，一次只能買一張 :japanese_goblin: : 那預知能力最多能預知幾天呢？ :clown_face: : 最多30,000天最少為1天 :japanese_goblin: : 股價會落在什麼樣的區間範圍內嗎？ :clown_face: : 股價會落在 0到10000元之間 :japanese_goblin: : 有限制買賣的次數嗎？ :clown_face: : 沒有限制，可以做無限次買賣 :japanese_goblin: : 好的，我已經了解題目的基本要求，這邊我想舉一個簡單的例子，來確認我的題目的理解有沒有錯誤，如果今天預知六天的股價分別為 7 1 5 3 6 4 那我在第2天花 $1 買入，隔天以 $5 賣出，又在第4天 $3 買入，隔天以 $6 賣出 :japanese_goblin: : 總共賺了（5-1）+（6-3）=7，最高獲利為$7對嗎？ :clown_face: : 對的 :japanese_goblin: : 那我初步的想法是只看相鄰的兩天，只要前一天比較便宜後一天比較貴，我就做買賣 ### 程式碼 ```c //Time complexity=O(n) //Space complexity:O(1) int maxProfit(int* prices, int pricesSize){ int max=0,profit; for(int i=0;i<pricesSize-1;i++){ profit=prices[i+1]-prices[i]; if(profit>0){ max+=profit; } } return max; } ``` :clown_face: : 那如果今天加上了一個交易次數的限制，假設我們交易次數最多為1次，那你會怎麼去思考呢? :japanese_goblin: : 我會先求出相鄰兩天的利潤記錄在一個 profit 的陣列當中，然後我們在 profit 陣列中玄找總和最大的連續子陣列(maximum subarray) :clown_face: : 好的!那最後我們想以英文面試來看看你英語的溝通能力，之後也會有外國的同事加入，良好的溝通可以事半功倍 :japanese_goblin: : 沒問題! ## [202. Happy Number](https://leetcode.com/problems/happy-number/) > Video:[24:54](https://www.youtube.com/watch?v=DCdx849bjDQ&t=1494s) ### 模擬面試過程 :clown_face: : Please write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Finally,return true if n is a happy number, and false if not. :japanese_goblin: : First,I want to confirm if I am understanding the question right,let me repeat the question: If this number is happy number，I'll return true ,and false if not. And happy number means that it's an positive number and we calculate its sum of squares of all digits repeat this process until the number equlas 1 :clown_face: : Yeah, I think you are right. :japanese_goblin: : I want to start with an easy example and try to deduct from there. :clown_face: : OK! :japanese_goblin: : if the number is 19 :::spoiler Example:input=19 Input:19 1*1+9*9=82 8*8+2*2=68 6*6+8*8=100 1*1+0+0=1 ::: :clown_face: : Yeah,good example! :japanese_goblin: : Ok! I want to know the constraint about n and the n range. :clown_face: : It is only limited in its range.The n range will become 1~ $2^{31}$- 1 :japanese_goblin: : OK,I understand the problem now. :japanese_goblin: : Can I take several minutes to think about it? :japanese_goblin: : OK!First,I need to solve cycle detection . We can record the numbers that appear in the history and put them in an array. :japanese_goblin: : If any result is equal the number that appears in the history,and the result is not equal 1,we can confirm it has a cycle.Because of cycle,this number is not a happy number. First,we need an array to record history number,and we need to check that the result is in a history array or not.If not , we put the result in history,and calculate the sum of the squares of its digits.We also need a variable to record the size of history array. we repeat this process until the cycle is detected.That means some result is appear in the history array again. Finally, we check the result equals one or not How to get the sum of squares of its digits? If n is not zero,we take n mod 10 to take units digit.After,we need to update n. Finally, we can calculate the sum. ### 程式碼 ```c int next_n(int n){ int r,d; while(n!=0){ d=n%10; n/=10; r+=d*d; } return r; } bool contain(int* history,int size,int n){ for(int i=0;i<=size;i++){ if(history[i]==n){ return true; } } return false; } bool ishappy(int n){ int history[10000]={0}; int size=0; while(!contain(history,size,n)){ history[size]=n; n=next_n(n); size++; } if(n==1){ return true; } return false; } ``` :japanese_goblin: : This is my program ,which is $O(log {n})$ time complexity. Do you have any hesitation about my algorithm ? :clown_face: : I think this is a good method,but this method waste too much memory space ,like a history array. Do you have any idea to improve this problem? :japanese_goblin: : I think we can use floyd cycle detection algorithm to solve this problem. It can save memory and be more efficient. :clown_face: : It sounds like a good idea. :clown_face: : 那我們的面試就到此結束，很高興認識你沐揚仁，謝謝你的時間。 :japanese_goblin: : Elsa，謝謝你抽出時間與我面談。 ## 初步檢討 * 整體還是偏緊張，可以再放輕鬆一點 * 口頭說回傳值但沒有寫在程式碼中 * 在寫完程式碼後可以主動提及自己的時間複雜度、和空間複雜度 * 可以多解釋時間複雜度的計算 * 在股票題的延伸中有提到總和最大的連續子陣列(maximum subarray)可以再多敘述他的演算法和時間複雜度 * 在提到可以用 floyd cycle detection 的演算法時，可以主動去解釋一下演算法的原理，以及為什麼可以解決解省記憶體空間的問題 * 在寫程式碼的時候會有自言自語的情況，面試官會誤認為在對自己說話，要注意盡量避免自言自語的情況發生 --- ## 第二次作業-他評 01 ### 關於 interviewer - [ ] 優點 * 說話清晰且語速適當 * 將題目與實際生活例子結合的非常好，更能提高鑑別度 - [ ] 可改進的地方 * [10:38](https://youtu.be/DCdx849bjDQ?si=mBdOY4zoA8v2FUKJ&t=638): 詢問更精簡的做法時，能適時引導interviewee方向，例如修改重複性高的部分，或是減少時間與空間複雜度 ### 關於 interviewee - [ ] 優點 * repetetion 的部分把題目的細節釐清的很確實 - [ ] 可改進的地方 * [10:03](https://youtu.be/DCdx849bjDQ?si=s4jN23Kcw4OtMJK1&t=603): 這裡跟interviewer的互動方式應該可以從**有什麼疑問嗎**變成**這樣符合您的需求嗎**，能給interviewer更好親近的感覺 * [24:32](https://youtu.be/DCdx849bjDQ?si=Dvdoq1zxDsexEKjG&t=1472):更改後的程式碼少了test的步驟 --- ## 第二次作業-他評 02 ### 優點 * 每個題目都有給予適當合理的情境 :+1: * 說明都很清楚、沒什麼很明顯的停頓感 * 第一題 [15:00](https://www.youtube.com/watch?v=DCdx849bjDQ&t=59): 有特別將解法一的「assign 為 0」和解法二的「Swap 方式」去做比較，明確講出 Swap 的優點 ### 可改進之處 * 第一題 [0:59](https://www.youtube.com/watch?v=DCdx849bjDQ&t=59): 也可以使用快慢指標的寫法去解決，以下程式碼參考自 [LeetCode 刷题攻略 - 27. 移除元素](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.md) ```cpp void moveZeroes(std::vector<int>& nums) { int slow = 0; for (int fast = 0; fast < nums.size(); ++fast) { if (nums[fast] != 0) { nums[slow] = nums[fast]; // nums[fast] 往前挪即可 ++slow; } } // 此時 nums[0] ~ nums[slow - 1] 為非零元素，nums[slow] 往後就都是 0 了 for (int i = slow; i < nums.size(); ++i) { nums[i] = 0; } } ``` ## 第二次作業-他評 03 ### interviewer #### 優點 - 對題目的情境設定很用心 - [22:46](https://youtu.be/DCdx849bjDQ?si=AmPAUo0-FJ0js6in&t=1366) 第二題的延伸問題設計得很得當! #### 可改進之處 - 第三題結束的比較匆忙，時間允許的話可以再繼續追問優化做法 ### interviewee #### 優點 - [5:05](https://youtu.be/DCdx849bjDQ?si=M_m-AmJYy1850PiE&t=305) 舉例的時候，使用表格講解的方式很一目了然 - 講解清晰且通順，語速穩定 #### 可改進之處 - Repeat 的部分做得非常確實，不過如果題目要求多又繁雜的話，建議可以使用比較簡略的記錄法(或用英文)，可以省下打字的時間。如:`i 指向0的位置` 可記錄成`i -> position of 0` - [10:20](https://youtu.be/DCdx849bjDQ?si=QsfQSmIDXWVqfrLK&t=620) 程式碼放在同一個頁面中反而讓字變得太小，看得比較吃力。可以把字體、行距調大並去掉空行 - [12:32](https://youtu.be/DCdx849bjDQ?si=7V9GeRsGRBjLPl64&t=812) 這段寫程式的時候，聲音突然變很小、像是講給自己聽的，不如就直接講出來比較不會讓 interviewer 覺得自己是不是錯過什麼內容 - 第三題 history 陣列的尋找可以改用 unordered set，使查找的時間複雜度降到 O(1) 且使實作更簡潔 (用法參考 : [std::unordered_set](https://cplusplus.com/reference/unordered_set/unordered_set/)) ## 第二次作業-他評 04 ### interviewer #### 優點 - 從一開始的互動到題目的設計都相當用心，非常自然 #### 可改進之處 - 優化的部分可以沿神多一點討論 ### interviewee #### 優點 - 對題目的提問很非常關鍵 - E的部分解釋很清楚，甚至有附上表格 - 有注意排版 - 在書寫程式碼的過程中對程式碼的解釋也相當清楚 #### 可改進之處 - 英文口說可以更自信一點