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

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1 > 貢獻者: 李一 Pear > [模擬面試錄影-1 (英)](https://www.youtube.com/watch?v=2e7edTpR3vc) > [模擬面試錄影-2 (漢)](https://www.youtube.com/watch?v=brz38rMKVfQ) > [模擬面試錄影-3 (漢)](https://www.youtube.com/watch?v=EHdy7qDeJoY) ## **自評** 1. 加強打字速度。 2. 加強同時打字跟說話的能力。 3. REACTO中的A(approach)可以同時在畫面中打字輔助說明。 4. 在開始實作程式之前，interviewee可以試著主動與interviewer討論改進方案。 5. 在REACTO中的T(test)過程中，可以使用一些edge case來驗證程式的可行性。 6. C++中有許多好用的函式，應該多多了解，能讓撰寫程式的過程更順利，也能讓程式更簡潔。 7. 善用一些語助詞以及肢體動作，爭取思考時間，也能透過這些東西傳達當前正在思考或是其他狀態。 8. 題目可以包裝成更應用的例子。 ## [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/) > [模擬面試錄影](https://www.youtube.com/watch?v=2e7edTpR3vc) ### 題目 **interviewer:** 今天你出門旅遊，遇到了一條河，你想要過去對岸，但是河的水很深，這時你看到旁邊有一座吊橋，吊橋的路是由一片一片的木板組成，你可以選擇一片一片走，或是跨一片走，那請問你總共有幾種不重複的走法到對岸? ### 解法 **interviewee:** 假設總共吊橋的路有n片地板的話，除了橋上的路以外還有現在踩的地方跟對岸，總共n+2個立足點，所以一開始我會先宣告一個長度為n+2的陣列，由於到達現在的位置和第一個木板的方法都是只有一種，所以陣列的第一個還有第二個元素都是一。第二片木板可以從起始點或是第一片木板到達，所以到達第二片木板的走法數量會是到達起始點跟第一片木板的走法數量的總和，依此類推，所以如果要算出到達第i點的走法數量，就需要將到達i-1以及i-2的走法數量加起來。 ```cpp int NumberOfWays (int n) { if (n == 0) { return 1; } vector<int> ways(n+2); ways[0] = ways[1] = 1; for (int i = 2; i <n+2; i++) { ways[i] = ways[i-1] + ways[i-2]; } return ways[n]; } ``` ### 改進 **interviewer:** 使用了一個陣列儲存了你到各個位置的走法的數量，但是好像不需要把他們全都記錄下來，是不是有更好的方法能降低你的空間複雜度呢? **interviewee:** 利用兩個變數current跟previous來取代陣列，一開始一樣先將current跟previous設為1，接著使用for迴圈，先讓temp=current，接著讓current=temp+previous，然後讓previous=temp，迴圈結束後再回傳current。 ```cpp int NumberOfWays(int n){ if(n==0) return 1; int current=1; int previous=1; for(int i=2;i<n+2;i++){ int temp=current; current+=previous; previous=temp; } return current; } ``` ## [1299. Replace Elements with Greatest Element on Right Side](https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/) > [模擬面試錄影](https://www.youtube.com/watch?v=brz38rMKVfQ) ### 題目 **interviewer:** 有一串正整數數列，將數列中的元素用這個元素後面的元素中的最大的元素取代。 ### 解法 **interviewee:** 從第一個元素開始找後面的最大元素。 **interviewer:** 每一步都要向後找最大的元素會不會太過於耗時? **interviewee:** 如果同時記錄最大元素的位置，直接將前面的元素替換成找到的最大元素，可以節省一些時間。 **interviewer:** 如果今天我給你一個遞減的數列，像是[5 4 3 2 1]，這樣你兩個方法所需要的時間其實是一樣的。 **interviewee:** 如果從數列的尾端開始，一開始先宣告一個變數，值為數列的最後一個數值，然後從數列到數第二個開始往前，比對當前數列位置的值與變數的大小，如果比變數小的話，就替換成變數的值，比變數大的話，就將變數的值變成該位置的值。 ```cpp vector<int> replaceElements(vector<int>& arr) { int n=arr.size(); int fill_in=arr[n-1]; for(int i=n-2;i>=0;i--){ int temp=arr[i]; arr[i]= fill_in; if(temp> fill_in) fill_in =temp; } arr[n-1]=-1; return arr; } ``` ### 改進 **interviewer:** 在處理數列最後一個數應該有更好的處理方法。 **interviewee:** 在程式中會先將數列中的數字替換掉，再去比對變數的大小，這樣的話，我一開始就可以將要替換進去的變數設為-1，這樣的話迴圈可以從n-1開始，程式最後將數列最後設為-1可以去掉。接下來也不需要一個變數n儲存數列長度，下面迴圈可以直接將n-1替換成arr.size()-1。 ```cpp vector<int> ReplaceElements(vector<int>& arr) { int fill_in =-1; for(int i=arr.size()-1;i>=0;i--){ int temp=arr[i]; arr[i]= fill_in; fill_in =max(temp, fill_in); } return arr; } ``` ## [62. Unique Paths](https://leetcode.com/problems/unique-paths/) > [模擬面試錄影](https://www.youtube.com/watch?v=EHdy7qDeJoY) ### 題目 **interviewer:** 有一個機器人，只能往右或往下移動，這個機器人有幾種方法移動到房間右下角呢? ### 解法1 **interviewee:** 可以簡化成一個排列組合的問題，由於機器人只能往下或往右走，加上這個房間是長方形的，假設這是個m*n的房間，機器人需要m-1步到達房間最下面，需要n-1步到達房間最右邊，那總共有m+n-2階層除以m-1階層再除以n-1階層這麼多種方法。 ```cpp int uniquePaths(int m, int n) { long long ans=1; int minn=min(m,n); for(int i=1;i<minn;i++){ ans=ans*(m+n-1-i)/i; } return ans; } ``` ### 解法2 **interviewee:** 先宣告一個 $m \times n$ 的二維陣列用來儲存機器人到各個位置的走法數，陣列的第一排跟第一列都先初始化為1，由於機器人到位置(i, j)只能從(i-1,j)或是(i, j-1)出發，所以機器人到位置(i, j)的走法數會是機器人到位置(i-1, j)跟(i, j-1)的走法數的和。 ```cpp int uniquePaths(int m, int n) { vector<vector<int>> ways(m, vector<int>(n, 0)); for (int i = 0; i < m; ++i) { ways[i][0] = 1; } for (int j = 0; j < n; ++j) { ways[0][j] = 1; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { ways [i][j] = ways [i-1][j] + ways [i][j-1]; } } return ways [m-1][n-1]; } ``` ### 討論 **interviewer:** 如果使用遞迴的方式會遇到什麼問題，以及如何改善呢? **interviewee:** 在遞迴的過程中，我可能會多次重複走訪過陣列的某一個點，為了避免這種情況，在一開始我可以將陣列中的值初始化成-1，這樣在遞迴的程式中，可以透過該點數值是否為-1，來判斷是否走訪過這個位置。 --- ## 第二次作業-他評 01 ### 關於 interviewer - [ ] 優點 * 會對 interviewee 的程式碼詢問一些問題或是提出可改進的部分 - [ ] 可改進的地方 * [00:04](https://youtu.be/brz38rMKVfQ?t=4): 建議將題目顯示在畫面上，較為方面理解 ### 關於 interviewee - [ ] 優點 * [00:49](https://youtu.be/brz38rMKVfQ?t=49): 詢問一些例外狀況的處理很不錯 - [ ] 可改進的地方 * [00:21](https://youtu.be/brz38rMKVfQ?t=21): 跳過了 REACTO 中的 R ## 第二次作業-他評 02 * 口條清楚，語速和聲音大小控制得當 ### interviewer * interviewer的開頭介紹很完整！不過如果可以說明自己是甚麼樣的公司，而接下來出的題目能依照工作時會可能遇到的情境來出題會更好！ * 感覺介紹題目的時候有圖片或是提供畫面會更好理解，尤其配合題目需要幾種走法類型的題目 * [06:33](https://youtu.be/brz38rMKVfQ?t=393): 在說處理最後一個數有更好的方法，可能可以再引導一下這個更好的方法可能的方向，不然感覺interviewee也很難直接突然想到。 ### interviewee * 能夠對題目給出例子和提出一些疑問和訊問可能出現的情況，增加討論，而不盲目開始寫code，使自己更好的理解題目的內容與限制。 * 可惜缺少repeat題目而直接開始做example的步驟。 * [00:27](https://youtu.be/EHdy7qDeJoY?t=27): 這部分在說明如何實作的時候看有沒有辦法打字出來說明，不然怕interviewer無法理解意思。 * [01:26](https://youtu.be/EHdy7qDeJoY?t=86): 可以說明為何設定這樣的變數型態，能讓內容更完整。 ## 第二次作業-他評 03 ### interviewer - [ ] 優點 * [00:06](https://youtu.be/EHdy7qDeJoY?si=CfCE6-Ja8c41lzhq&t=6): 題目有用情境題包裝，可以避免面試者背答案。 - [ ] 可改進的部分 * 面試官問問題時除了針對題目改善外，應該要想如何找出面試者的思維邏輯，譬如說，他是如何想到第二種解法，為什麼一開始想不到? ### interviewee - [ ] 優點 * 寫程式時的速度跟語速可以讓聽的人很清楚解題過程跟邏輯。 - [ ] 可改進的部分 * 有時候調整程式架構會太安靜，可以說些話，比如說接下來的步驟。 ## 第二次作業-他評 04 ### 關於 interviewer - [ ] 優點 * 講話通順，語氣自然 * (第二題)在REACTO的A適當引導interviewee去思考出更好的解法，協助interviewee把時間花在刀口上 - [ ] 可改進的地方 * [0:27](https://youtu.be/2e7edTpR3vc?si=NGIKEd5QfGl0XQLZ&t=27)：前面開場是中文，開始說明問題時突然切成英文有點突兀，可以設計過場環節，或是一開始就用英文會比較順 ### 關於 interviewee - [ ] 優點 * 打code的時候講話跟寫code的時間分配恰當不會有割裂感，而且解釋得很清楚，可以明確知道每一行code的邏輯為何 - [ ] 可改進的地方 * (第一題)REACTO的E跟T沒有做，在完全沒有實際例子的狀況下很考驗interviewer跟interviewee之間的默契，如果有舉例的話會更好理解 * (第一題)結束的有點倉促 * (第三題)比起用m跟n說明例子，用實際數字帶入m跟n會更好理解 ## 第二次作業-他評 05 ### interviewer - [ ] 優點 * 會包裝題目，是厲害的面試主持人。 * [6:38](https://youtu.be/brz38rMKVfQ?si=THsQnOiB-pLTvVka&t=398): 給面試者的引導力度拿捏的十分優秀，循循善誘不會直接給出答案。 - [ ] 可改進之處 * [3:44](https://youtu.be/brz38rMKVfQ?si=PInAWn55-I2BhUTV&t=224): 「聽起來快了很多」這句話感覺有點籠統。 ### interviewee - [ ] 優點 * 語速適當，口齒清晰，適當與面試主持人交換意見。 * 邊coding邊說明的部分也做得很好。 - [ ] 可改進的地方 * [3:25](https://youtu.be/brz38rMKVfQ?si=ucBHcXmWvM3NawuB&t=205): 在講解優化後的解法時感覺可以搭配舉例，更能清楚的表達想法，再進一步coding。而且這次也沒有像第一個舉例一樣說明時間複雜度來進行比較，感覺前後有點不統一。 * [6:13](https://youtu.be/brz38rMKVfQ?si=B2NqNQSGTUUEF5xx&t=373): 雖然答案很直觀，但感覺可以稍微說明時間複雜度是由程式碼的哪部分決定而來。 * [7:22](https://youtu.be/brz38rMKVfQ?si=YvkDttz0-3ephnhq&t=442): 改使用既定函數的步驟忘記口頭說明了。