# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 黑衣: Interviewer.
> 白衣: Interviewee.
> 影片: [施新豐-Crazy: Homework1 (漢/英)](https://youtu.be/uw-vLLJ5t6A)
## 作業目標
* 透過 **Leetcode練習**來**模擬面試**過程中可能發生的情境. 期望學員不能只會背 code, 身為一個 Engineer, 思考的能力尤其重要, 然後才是找解決的方法.
* 學習過程的呈現則要求以**影片錄製**與 **HackMD**筆記來完成.
---
## [Leetcode No. 1 Two Sum (Easy)](https://leetcode.com/problems/two-sum)
### 過程討論
***黑衣:***
Function input有三個.
- nums, 一個 int陣列.
- numsSize, 此陣列 size.
- target, target value for pair sum.
Function需要回傳陣列中任二個 element的 index, 使此二 element的加總結果剛好為 target value.
(假設 input陣列中只會有一組 element的加總結果會等於 target value, 另外, 不能將陣列中一個 element加總二次.)
```
Example 1:
Input: nums = [2,7,11,15], size = 4, target = 9
Output: [0,1]
Explanation: 因為 nums[0] + nums[1] == 9, 所以 function需要回傳 [0, 1].
Example 2:
Input: nums = [3,2,4], size = 3, target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], size = 2, target = 6
Output: [0,1]
```
***白衣:***
我將這個問題 formulate成以下.
| | nums[0] | nums[1] | ... | nums[size - 2] | nums[size - 1] |
| -------------- | ------- | --------- | --- | ---------------- | ----------------------- |
| nums[0] | N/A | sum(0, 1) | ... | sum(0, size - 2) | sum(0, size - 1) |
| nums[1] | N/A | N/A | ... | sum(1, size - 2) | sum(1, size - 1) |
| ... | N/A | N/A | ... | ... | ... |
| nums[size - 2] | N/A | N/A | ... | N/A | sum(size - 2, size - 1) |
| nums[size - 1] | N/A | N/A | ... | N/A | N/A |
這樣是為了 enumerate陣列中任意二個 element的加總結果, 而就在每個 pair的加總過程中順便比對是否有與 target value相同, 找到的話就 return. 若是所有 pair在 enumerate過後都沒有等於 target value的結果, 就代表陣列中找不到符合條件的 element pair.
### Proposal驗證
有通過 Leetcode whole test cases的驗證.
### Other proposal
在老師的作業要求中有看到[面試範例影片](https://youtu.be/kVgy1GSDHG8)提到可以使用 Hash來改進, 猜測可以這樣進行 implementation.
在 enumerate完所有與 element 0, e.g., nums[0], 若都沒找到等於 target value的 pair的話, 進行 element 1的 enumeration時, 同樣需要再次存取 nums[2], ..., nums[size-1]. 因此, 或許可以在第一次讀取陣列時進行這些動作.
1. 記錄下 `difference(i, j) = nums[j] - nums[i]` 的內容.
即 `difference(0, 1)`, `difference(0, 2)`, ..., `difference(0, size - 1)`.
2. 進行比對 pair sum與 target value時, 一定需要 traverse陣列 nums[],
for nums[i], `__target = target - nums[i]`, 這時 `__target` 就需要在其他 `nums[j]` 中尋找, where j != i.
3. If 第一 round的 traversal沒有找到 target pair sum的話, 進行比對 `nums[i + 1]` 時, `__target += difference(i, j)`, 然後使用這一 round的 `__target` 與陣列內容作比對即可. 這樣一來, 就不用再讀取 enumeration element i時已讀取過的 element value.
4. 面試範例影片中所提到的 Hash實作可能就是把陣列內容 insert到 Hash table. 但我還不確定 Hash Table的實作.
### 表現自評
太晚開始做作業, 時間很趕. 第一次接觸 Leetcode, 比想像中的還有挑戰性. 有時間的話, 會想完成 Other proposal, 然後比較不同設計的優缺點.
## [Leetcode No. 119 Pascal's Triangle II (Easy)](https://leetcode.com/problems/pascals-triangle-ii)
### 過程討論
***黑衣:***
Function input只有一個.
- rowIndex, 一個大於等於 0的 int.
Function需要回傳第 rowIndex列的 Pascal's Triangle的內容.
(0 <= rowIndex <= 33)
```
Example 1:
Input: rowIndex = 3
Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0
Output: [1]
Example 3:
Input: rowIndex = 1
Output: [1,1]
```
***白衣:***
By definition, Pascal's Triangle中每個 element的值可從其前一列的 element的值來決定. 但這就代表要得知第 n列的內容, 需要把第 n-1列~第 1列的內容都算完. 我想知道有沒有其他的方法可以直接算出第 n列的內容, 回想起高中數學介紹排列組合的問題. Pascal's Triangle中第 n列的 element內容其實就是 (a + b)^n的結果中按升冪或降冪排列後的, 各項次的係數. 分別是 C(n, 0), C(n, 1), ..., C(n, n). 這樣一來, 這個問題就可簡化成排列組合的問題.
排列組合的 Proposal雖可直接算出 Pascal's Triangle任一列的任一 element的值. 但是其運算過程會牽扯到 n!的計算, 程式語言的數值類資料結構都有值域限制, 當 n值一大, 這個 proposal就面臨數值 overflow挑戰.
目前我採取這二個 action來減緩數值 overflow的問題.
1. 觀察 Pascal's Triangle後可發現, 每個 row的結果是左右對稱的. 因此, 每個 row的 element只需計算前半, 後半與前半是對稱的, 可以不用再計算一次.
2. 計算每個 row的 element時, 不要把分子分母的階層運算都乘開再做除法, 階層運算過程逐項可以整除的話, 就先做除法.
### Proposal驗證
有通過 Leetcode whole test cases的驗證.
### Other proposal
計算機科學與數學還是存在一些差異, 且計算機科學起步之時, 往往是計算資源非常侷限的時代, 難怪會需要有 dynamic programming等演算法, 時至今日, 這些演算法也許不能一步將結果計算出來, 但卻較有延展性, 即便 n值怎麼改變, 較不會引發數值 overflow的問題, 而能逐步將結果算出來.
時間夠的話, 我會想要完成這些.
* 實作出 dynamic programming的方法與排列組合的 proposal做比較.
* 排列組合的方法或許也有其他方式將 n!的計算造成的數值 overflow給避掉. 觀察了一下 Pascal's Triangle後發現 C(n, i)的結果一定能整除, 我認為在計算每個 element的結果時, e.g., C(n, i) = (n * (n - 1) * ... * (n - i + 1)) / i! 先不要乘開, 而使將依序將分子的 n, (n - 1), ..., (n - i + 1)都 insert到一個 list entry, 分母則是進行 list entry remove, 可以搭配質因數分解來完成 list entry insert / remove. 最後才是將 list entry讀出來做計算乘積. 至於這個 list要使用什麼資料結構來實作, 則可以再討論.
* 也許真的有可以避掉數值 overflow的解法, 但我對怎麼處理數值 overflow的議題也感興趣, 或許有天也會遇到不得不處理的狀況. 數值型別的 type casting內部是怎麼轉換的, 我也想要多瞭解.
### 表現自評
太晚開始做作業, 時間很趕. 第一次接觸 Leetcode, 比想像中的還有挑戰性. 有時間的話, 會想完成 Other proposal, 然後比較不同設計的優缺點.
## [Leetcode No. 29 Divide Two Integers (Medium)](https://leetcode.com/problems/divide-two-integers)
### 過程討論
***黑衣:***
Function input有二個.
- dividend, 被除數, or 分子, int型別.
- divisor, 除數, or 分母, int型別.
Function需要回傳 dividend除以 divisor的商數 quotient.
(divisor不會是 0. 若 quotient大於 2^31 - 1, 回傳 2^31 - 1. 若 quotient小於 -2^31, 回傳 -2^31.)
```
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.
```
***白衣:***
我的想法很簡單, 先從 dividend與 divisor都是正數的情況下做思考, 這個情況下, 設計一個 while loop, remaining的初始值設定為 dividend. if remaining >= divisor, 就進入 while loop中把 remaining扣掉 divisor得出新的 remaining, 當 while loop終止時, while loop的執行次數就是 quotient的值.
接著考慮正負號的問題. 我會希望計算時都是以正整數來執行, 所以會需要將 dividend, divisor都轉成絕對值.
我設計一個 sign變數, 初始值為 1.
```c
if (dividend < 0)
sign--;
if (divisor < 0)
sign--;
```
這就使得可以使用 sign == 0來判斷最終 quotient會是負數.
但這邊還會有另一個問題, int型別的正負數不對稱, 負整數有多一個 -2^31. 我目前的解法是將 dividend, divisor的絕對值都使用 long type來儲存.
然後, 不知道 Leetcode是不是會將 Medium難度的答案增加執行時間的標準. 以下這幾個 special case其實可以有更快的判斷方法.
1. dividend == 0, return 0;
2. dividend == divisor, return 1;
3. abs(dividend) < abs(divisor), return 0;
4. abs(divisor) == 1, return dividend; // 但須注意正負號, 以及正負整數極值的問題.
再來, 我 submission時還是被回覆 Time Limit Exceeded! 因此, 會需要來處理 dividend >> divisor而使得 while loop需要跑多 round的問題.
我希望當 remaining還很大時, while loop中每次可以直接扣掉多次的 divisor, 節省 while loop執行次數. 因此我預先設計了 1~8倍的 divisor, while loop會先從 8倍的 divisor對 remaining進行扣除, 之後才是小於 8倍的 divisor.
### Proposal驗證
有通過 Leetcode whole test cases的驗證.
### Other proposal
感覺對於 while loop中 divisor的設定可以更 smart一點, 我認為可以透過 abs(dividend), abs(divisor)的 MSB來動態決定 divisor的大小. 但我目前對 bit operations還不熟悉, 且時間很趕, 就沒有對此進行研究了.
### 表現自評
太晚開始做作業, 時間很趕. 第一次接觸 Leetcode, 比想像中的還有挑戰性. 有時間的話, 會想完成 Other proposal, 然後比較不同設計的優缺點.
## 作業心得與討論
* COVid-19疫情之後, 國內企業陸續採用視訊面試. 即便疫情過後, 視訊面試似乎仍被許多企業採用. 很高興老師在課堂上點出一些需要注意的細節, 但重點還是在練習.
* 我知道真正面試時不會有這麼多時間讓我們思考, 且可能也會更緊張, 但有練習應該會有所幫助.
* Leetcode設計出許多 test case能驗證 Engineer的 implementation, 這讓我從中不斷的思考和重新檢視我的 proposal design.
* 我知道任何設計都不會是完美的, 我的 code submission雖有被 Leetcode accepted, 但當 problem constraint一有變動時, 這個 implementation就可能不再是 bug-free.
* 另一方面, Leetcode也會對 submission的 Runtime與 Memory Consumption做評估, 並對所有 submission做評比, 看到我 submission的 ranking之後, 我會想要知道怎麼才能寫出更精進的 code.
* 而 Runtime與 Memory Consumption的 ranking有時不一定客觀, 那是反映這個 problem constraint的比較, 我認為一個好的 code還更需要能夠在不同 constraint下也都能夠運作, 讓 maintain effort降到最低.
* 我不喜歡在寫題目前看答案, 但寫完 submission之後, 有時間的話, 會看一下其他門派的武功招式.
## 待學習與研究的主題
* Leetcode No. 1: Hash Table的實作.
* Leetcode No. 119: dynamic programming的 proposal, numerical type casting的原理, big number problem.
* Leetcode No. 29: numerical type casting的原理, bit operations.
## 第二次作業-他評 01
### 關於 interviewer
- [ ] 優點
- 黑帽子和眼鏡特效超酷的。
- [ ] 可改進的地方
- 可以減少語助詞(e.g., ㄜ)
- 希望可以使用情境題。
- 可以增加探討時間和空間的複雜度。
### 關於 interviewee
- [ ] 優點
- [11:15](https://www.youtube.com/watch?v=uw-vLLJ5t6A&t=675s)有想辦法改進，觀察出帕斯卡三角形只需要算一半就好。
- [25:38](https://www.youtube.com/watch?v=uw-vLLJ5t6A&t=1538s)改進除法的特殊案例，和不斷相減的過程，很棒。
- [ ] 可改進的地方
- 如果能遵循 REACTO framwork 會更好。
- [02:00](https://www.youtube.com/watch?v=uw-vLLJ5t6A&t=120s)抱歉，畫質可能要提升，看不清楚作答時的程式碼內容，或是可以將程式碼附在HackMD上 。
- 老師說撰寫簡潔的程式碼比較好，像是21行和20行可以進行合併，變成`if((nums[i]+nums[j]) == target){...}`
- [03:08](https://www.youtube.com/watch?v=uw-vLLJ5t6A&t=188s)可能有影片剪輯錯誤，在第一題時interviewer詢問是否能改進程式碼後，畫面直接進入第二題面試。
- [13:00](https://www.youtube.com/watch?v=uw-vLLJ5t6A&t=780s) 可以拿掉在16行進行是否能整除的判斷，直接都用19行的運算就好。
- 三題沒有做到再改進的部份，感覺都還停留在通過測試的階段而已。
## 第二次作業-他評 02
### 關於 interviewee
- [ ] 可改進的地方
* [07:35](https://youtu.be/uw-vLLJ5t6A?t=455): 避免說「我暫時的想法」，這句話冗贅，且顯得沒自信，可直接跳過，或說「我想這樣做」
* [07:55](https://youtu.be/uw-vLLJ5t6A?t=475): 撰寫程式碼時，應當一邊解說
* [10:34](https://youtu.be/uw-vLLJ5t6A?t=634): 在面試的場合中，可能沒有辦法當場執行撰寫的程式碼，檢驗程式碼的正確性時，可使用 REACTO 階段舉出的輸入案例。螢幕滑鼠的移動會干擾視線。
* [10:50](https://youtu.be/uw-vLLJ5t6A?t=650): algorithm 的翻譯是「演算法」，而非「算法」，後者是「計算的方法」(the way to calculate)，但 [algorithm](https://en.wikipedia.org/wiki/Algorithm) 更在意「預先定義」的明確步驟。探討 integer overflow 是很好的議題，但該在 REACTO 的 Approach 階段提出，而非程式碼撰寫完才進行，當然，interviewer 若觀察到 interviewee 缺乏對 integer overflow 的處理，可在 REACTO 的 Test 之後提出討論。
* [11:52](https://youtu.be/uw-vLLJ5t6A?t=712): 不用提 LeetCode 的測試案例，目前的情境是面試，測試案例其實是「討論」過程中產生的。這是面試，不是進行「例行報告」，著重在「討論」，而非「獨白」
Sign in with Wallet
Connect another wallet