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

黑衣: Interviewer.
白衣: Interviewee.
影片: 施新豐-Crazy: Homework1 (漢/英)

作業目標

透過 Leetcode練習來模擬面試過程中可能發生的情境. 期望學員不能只會背 code, 身為一個 Engineer, 思考的能力尤其重要, 然後才是找解決的方法.
學習過程的呈現則要求以影片錄製與 HackMD筆記來完成.

Leetcode No. 1 Two Sum (Easy)

過程討論

黑衣:
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

在老師的作業要求中有看到面試範例影片提到可以使用 Hash來改進, 猜測可以這樣進行 implementation.
在 enumerate完所有與 element 0, e.g., nums[0], 若都沒找到等於 target value的 pair的話, 進行 element 1的 enumeration時, 同樣需要再次存取 nums[2], …, nums[size-1]. 因此, 或許可以在第一次讀取陣列時進行這些動作.

記錄下 difference(i, j) = nums[j] - nums[i] 的內容.
即 difference(0, 1), difference(0, 2), …, difference(0, size - 1).
進行比對 pair sum與 target value時, 一定需要 traverse陣列 nums[],
for nums[i], __target = target - nums[i], 這時 __target 就需要在其他 nums[j] 中尋找, where j != i.
If 第一 round的 traversal沒有找到 target pair sum的話, 進行比對 nums[i + 1] 時, __target += difference(i, j), 然後使用這一 round的 __target 與陣列內容作比對即可. 這樣一來, 就不用再讀取 enumeration element i時已讀取過的 element value.
面試範例影片中所提到的 Hash實作可能就是把陣列內容 insert到 Hash table. 但我還不確定 Hash Table的實作.

表現自評

太晚開始做作業, 時間很趕. 第一次接觸 Leetcode, 比想像中的還有挑戰性. 有時間的話, 會想完成 Other proposal, 然後比較不同設計的優缺點.

Leetcode No. 119 Pascal's Triangle II (Easy)

過程討論

黑衣:
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的問題.

觀察 Pascal's Triangle後可發現, 每個 row的結果是左右對稱的. 因此, 每個 row的 element只需計算前半, 後半與前半是對稱的, 可以不用再計算一次.
計算每個 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)

過程討論

黑衣:
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.

    if (dividend < 0) 
        sign--; 
    if (divisor < 0) 
        sign--;

這就使得可以使用 sign == 0來判斷最終 quotient會是負數.
但這邊還會有另一個問題, int型別的正負數不對稱, 負整數有多一個 -2^31. 我目前的解法是將 dividend, divisor的絕對值都使用 long type來儲存.

然後, 不知道 Leetcode是不是會將 Medium難度的答案增加執行時間的標準. 以下這幾個 special case其實可以有更快的判斷方法.

dividend == 0, return 0;
dividend == divisor, return 1;
abs(dividend) < abs(divisor), return 0;
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有想辦法改進，觀察出帕斯卡三角形只需要算一半就好。
- 25:38改進除法的特殊案例，和不斷相減的過程，很棒。
可改進的地方
- 如果能遵循 REACTO framwork 會更好。
- 02:00抱歉，畫質可能要提升，看不清楚作答時的程式碼內容，或是可以將程式碼附在HackMD上。
  - 老師說撰寫簡潔的程式碼比較好，像是21行和20行可以進行合併，變成if((nums[i]+nums[j]) == target){...}
- 03:08可能有影片剪輯錯誤，在第一題時interviewer詢問是否能改進程式碼後，畫面直接進入第二題面試。
- 13:00 可以拿掉在16行進行是否能整除的判斷，直接都用19行的運算就好。
- 三題沒有做到再改進的部份，感覺都還停留在通過測試的階段而已。

第二次作業-他評 02

關於 interviewee

可改進的地方

07:35: 避免說「我暫時的想法」，這句話冗贅，且顯得沒自信，可直接跳過，或說「我想這樣做」
07:55: 撰寫程式碼時，應當一邊解說
10:34: 在面試的場合中，可能沒有辦法當場執行撰寫的程式碼，檢驗程式碼的正確性時，可使用 REACTO 階段舉出的輸入案例。螢幕滑鼠的移動會干擾視線。
10:50: algorithm 的翻譯是「演算法」，而非「算法」，後者是「計算的方法」(the way to calculate)，但 algorithm 更在意「預先定義」的明確步驟。探討 integer overflow 是很好的議題，但該在 REACTO 的 Approach 階段提出，而非程式碼撰寫完才進行，當然，interviewer 若觀察到 interviewee 缺乏對 integer overflow 的處理，可在 REACTO 的 Test 之後提出討論。
11:52: 不用提 LeetCode 的測試案例，目前的情境是面試，測試案例其實是「討論」過程中產生的。這是面試，不是進行「例行報告」，著重在「討論」，而非「獨白」

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

作業目標

Leetcode No. 1 Two Sum (Easy)

過程討論

Proposal驗證

Other proposal

表現自評

Leetcode No. 119 Pascal's Triangle II (Easy)

過程討論

Proposal驗證

Other proposal

表現自評

Leetcode No. 29 Divide Two Integers (Medium)

過程討論

Proposal驗證

Other proposal

表現自評

作業心得與討論

待學習與研究的主題

第二次作業-他評 01

關於 interviewer

關於 interviewee

第二次作業-他評 02

關於 interviewee

Read more

淺談 Microkernel 設計和真實世界中的應用

並行程式設計: 概念

並行程式設計: Lock-Free Programming

2025 年 Linux 核心設計課程期末專題