# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業2
---
黑衣: Interviewer.
白衣: Interviewee.
影片連結: [施新豐-Crazy: Homework2 (漢)](https://youtu.be/E3-tv6w8lBY)
---
## 作業目標
* 「這是一個最好的時代, 這是一個最壞的時代.」from 雙城記 by [狄更斯](https://zh.wikipedia.org/zh-tw/%E6%9F%A5%E5%B0%94%E6%96%AF%C2%B7%E7%8B%84%E6%9B%B4%E6%96%AF). 活著雖然不易, 既然陰錯陽差讀了 engineering, 也許不是個稱職的 engineer, 但還是要試著學習 engineer的精神, 試著找到出路養活自己.
* 養活自己就要找工作, 需要在 interview中脫穎而出. 然而, interview本身充滿著一定程度的**主觀且不透明**, 課程期望透過**同學互評**來減低不透明程度讓學員提早瞭解自身優缺點及可以改進的方向.
## HW1的 interview練習可改進的部份實在太多, 需要循序漸進的練習, 在此列出 HW2預計完成的目標
* 學會調整螢幕錄製畫質字體尺寸讓觀眾可清晰觀看影片.
* 練習 follow 「REACTO」framework, 學習減少說話時的贅字或語助詞.
* 完成 HW1提及的部份 Optimization.
* HackMD附上程式碼供學員討論.
---
## [Leetcode No. 1 Two Sum (Easy)](https://leetcode.com/problems/two-sum)
### 過程討論
***黑衣:***
有個男孩每天都會將辛苦打工賺的錢存入銀行, 但某天接到一通陌生來電告知過去有二天銀行帳戶交易發生錯誤, 可能會平白損失那些賺來的辛苦錢. 已知過去 N天的交易記錄, 希望你能幫忙想方法幫男孩找出是 N天中的哪二天可能發生交易錯誤.
另外, 若電話通知訊息屬實, 也只會有一組正確的答案. 否則, 該電話可能為詐騙電話.
```
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.
```
int* twoSum(int* nums, int numsSize, int target) {
int i, j;
int *pair = (int *)malloc(2 * sizeof(int));
// enumerate all possible results
// once encounter the result matching the target
// return their indices
// Otherwise, return NULL
for (i = 0; i < numsSize - 1; i++) {
for (j = i + 1; j < numsSize; j++) {
if (nums[i] + nums[j] == target) {
pair[0] = i;
pair[1] = j;
return pair;
}
}
}
return NULL;
}
```
***黑衣:***
男孩每天還是很努力打工賺錢, 但三年後, 再次接到類似來電, 這就代表可能累積了 1000多筆交易記錄. 原本方法隨著交易天數增加所需的運算成本 scale得很快. 請問還有沒有其他可以改進的部份呢?
***白衣:***
在 enumerate完所有與 element 0, e.g., nums[0], 若都沒找到等於 target value的 pair的話, 進行 element 1的 enumeration時, 同樣需要再次存取 nums[2], ..., nums[size-1]. 因此, 或許可以在第一次讀取陣列時進行這些動作.
1. 把 nums[0]與其他 nums[j]的加總結果順便記錄下來, 也記錄下 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 第 0 round的 traversal沒有找到 target pair sum的話, 進行比對 nums[i + 1]時, __target += difference(i, j), 然後使用這一 round的 __target與陣列內容作比對即可. 這樣一來, 就不用再讀取 enumeration element i時已讀取過的 element value.
```
int* twoSum(int* nums, int numsSize, int target) {
int i, j;
int *pair = (int *)malloc(2 * sizeof(int));
int *sums = (int *)malloc(numsSize * sizeof(int));
int *diffs = (int *)malloc(numsSize * sizeof(int));
pair[0] = -1;
i = 0;
for (j = 1; j < numsSize; j++) {
if (nums[0] + nums[j] == target) {
pair[0] = 0;
pair[1] = j;
goto out;
}
sums[j] = nums[j] + nums[0];
diffs[j] = nums[j] - nums[0];
}
for (i = 1; i < numsSize - 1; i++) {
for (j = i + 1; j < numsSize; j++) {
if (diffs[i] + sums[j] == target) {
pair[0] = i;
pair[1] = j;
goto out;
}
}
}
out:
free(sums);
free(diffs);
if (pair[0] >= 0)
return pair;
return NULL;
}
```
驗證過後發現方法一與方法二的執行時間沒有明顯差異, 探究之下發現方法二在第 0 round之後的 pair sum比對所需的資料存取次數並沒有比較少, e.g., 方法二(diffs[i], sums[j]) V.S. 方法一(nums[i], nums[j]). 並無法有預期的減少資料存取的效果. 而且還多了 diffs, sums的額外的記憶體空間配置與 maintain的成本.
### Other proposal
在老師的作業要求中有看到[面試範例影片](https://youtu.be/kVgy1GSDHG8)提到可以使用 Hash來改進, 但 C程式語言中沒有內建的 STL, 還需要研究 Hash Table的實作.
## [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). 這樣一來, 這個問題就可簡化成排列組合的問題.
另外, C(n, m)與 C(n, m + 1)有這樣的關係.
* C(n, m + 1) = C(n, m) * (n - m) / (m + 1)
* 這代表每次都可從前一項 C(n, m)分子分母乘以對應的數值來算出 C(n, m + 1)的值.
```
int* getRow(int rowIndex) {
int *row = (int *)malloc((rowIndex + 1) * sizeof(int));
int i;
row[0] = 1;
for (i = 1; i < rowIndex + 1; i++) {
row[i] = row[i - 1] * (rowIndex - i + 1) / i;
}
return row;
}
```
排列組合的 Proposal雖可直接算出 Pascal's Triangle任一列的任一 element的值. 但是其運算過程會牽扯到 n!的計算, 程式語言的數值類資料結構都有值域限制, 當 n值一大, 這個 proposal就面臨數值 overflow挑戰.
我試著採取這個 action來減緩數值 overflow的問題.
* 觀察 Pascal's Triangle後可發現, 每個 row的結果是左右對稱的. 因此, 每個 row的 element只需計算前半, 後半與前半是對稱的, 可以不用再計算一次.
```
int* getRow(int rowIndex) {
int *row = (int *)malloc((rowIndex + 1) * sizeof(int));
int i;
row[0] = 1;
for (i = 1; i < rowIndex / 2 + 1; i++) {
row[i] = row[i - 1] * (rowIndex - i + 1) / i;
}
for (; i < rowIndex + 1; i++) {
row[i] = row[rowIndex - i];
}
return row;
}
```
可惜 rowIndex == 30時還是會發生 int overflow, 目前採取 dirty fix的解法. 轉成較大型別的 data type, e.g., long, 避掉 int overflow的發生. 但此方法的延展性不高.
```
int* getRow(int rowIndex){
int *row = (int *)malloc((rowIndex + 1) * sizeof(int));
int i;
row[0] = 1;
for (i = 1; i < rowIndex / 2 + 1; i++) {
row[i] = (long)row[i - 1] * (rowIndex - i + 1) / i;
}
for (; i < rowIndex + 1; i++) {
row[i] = row[rowIndex - i];
}
return row;
}
```
### 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 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.
```
if (dividend < 0)
sign--;
if (divisor < 0)
sign--;
```
這就使得可以使用 sign == 0來判斷最終 quotient會是負數.
但這邊還會有另一個問題, int型別的正負數不對稱, 負整數有多一個 -2^31. 我目前的解法是將 dividend, divisor的絕對值都使用 long type來儲存.
```
int divide(int dividend, int divisor) {
long remaining;
char sign = 1;
long abs_dividend = dividend;
long abs_divisor = divisor;
long count = 0;
if (dividend == 0)
return 0;
if (dividend < 0) {
abs_dividend = 0 - (long)dividend;
sign--;
}
if (divisor < 0) {
abs_divisor = 0 - (long)divisor;
sign--;
}
remaining = abs_dividend;
while (remaining >= abs_divisor) {
remaining -= abs_divisor;
if (sign == 0)
count--;
else
count++;
}
return count;
}
```
然後, 不知道 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; // 須注意正負號, 以及超出正負整數極值的 int overflow問題.
* sign == 0, 答案為 0 - abs(dividend), 而 abs(dividend)的最大值為 -(INT_MIN), 0 - abs(dividend)最小值就會是 INT_MIN, 不需處理 int overflow的問題.
* sign != 0, 答案為 abs(dividend), 因為 abs(dividend)的最大值為 -(INT_MIN), 所以需要額外處理 int overflow的問題.
```
int divide(int dividend, int divisor) {
long remaining;
char sign = 1;
long abs_dividend = dividend;
long abs_divisor = divisor;
long count = 0;
if (dividend == 0)
return 0;
if (dividend == divisor)
return 1;
if (dividend < 0) {
abs_dividend = 0 - (long)dividend;
sign--;
}
if (divisor < 0) {
abs_divisor = 0 - (long)divisor;
sign--;
}
if (abs_divisor > abs_dividend)
return 0;
if (abs_divisor == 1) {
if (sign == 0)
return 0 - abs_dividend;
return abs_dividend > INT_MAX ? INT_MAX : abs_dividend;
}
remaining = abs_dividend;
while (remaining >= abs_divisor) {
remaining -= abs_divisor;
if (sign == 0)
count--;
else
count++;
}
return count;
}
```
再來, 我 submission時還是被回覆 Time Limit Exceeded! 因此, 會需要來處理 dividend >> divisor而使得 while loop需要跑多 round的問題.
我希望當 remaining還很大時, while loop中每次可以直接扣掉多次的 divisor, 節省 while loop執行次數. 因此我預先設計了數個 2的冪次方倍數 divisors, while loop會先從最高冪次的 divisor對 remaining進行扣除, 之後依序使用低冪次的 divisor.
```
int divide(int dividend, int divisor) {
long remaining;
char sign = 1;
long abs_dividend = dividend;
long abs_divisor = divisor;
char seeds = 8;
int weights_seed[9] = {1};
long __abs_divisor[9] = {0};
long count = 0;
int order;
if (dividend == 0)
return 0;
if (dividend == divisor)
return 1;
if (dividend < 0) {
abs_dividend = 0 - (long)dividend;
sign--;
}
if (divisor < 0) {
abs_divisor = 0 - (long)divisor;
sign--;
}
if (abs_divisor > abs_dividend)
return 0;
if (abs_divisor == 1) {
if (sign == 0)
return 0 - abs_dividend;
return abs_dividend > INT_MAX ? INT_MAX : abs_dividend;
}
remaining = abs_dividend;
__abs_divisor[0] = abs_divisor;
weights_seed[0] = 1;
for (order = 1; order <= seeds; order++) {
__abs_divisor[order] = __abs_divisor[order - 1] + __abs_divisor[order - 1];
weights_seed[order] = weights_seed[order - 1] + weights_seed[order - 1];
}
order = seeds;
while (order >= 0) {
while (remaining >= __abs_divisor[order]) {
remaining -= __abs_divisor[order];
if (sign == 0)
count -= weights_seed[order];
else
count += weights_seed[order];
}
order--;
}
return count;
}
```
### Other proposal
感覺對於 while loop中 divisor的設定可以更 smart一點, abs(dividend)與 abs(divisor)無法預先知道時, 就會有 over-provision, under-provision的問題. 目前做法的缺點是會 always計算出 divisor的二的冪次方倍數 divisors.
* 遇到 abs(dividend) >> abs(divisor)時, 當然可以發揮預期效果.
* 但若 abs(dividend)與 abs(divisor)相近的話, 這些預先準備的 divisors就會是個 overhead了, 這個 overhead有二個, e.g., 預先算好 divisors以及使用 2的高羃次方倍數 divisors與 remaining的比較.
所以這樣的作法雖可避免 under-provision使得計算時間拉長, 但卻可能造成 over-provision的浪費. 我認為可以透過 abs(dividend), abs(divisor)的 MSB來動態決定 divisor的大小. 但我目前對 bit operations還不熟悉, 還沒有對此進行研究.
## 作業心得與討論
### HW2未完成的目標
* For many reasons, 我向來不太會 interview, 所以在我看來, 課程其他學員的表現都很不錯, 我實在沒有什麼立場來做評論. 只能勉強寫了一些 critics.
* For presentations, 中英文口說都亟需改進.
* 沒有演算法 Complexity Analysis.
* HackMD Markdown語法, LATEX排版不會使用.
* Leetcode選題以及使用的解題方式與數學背景高度相關, 實際面試時不一定能剛好都與數學相關, 可以多多練習其他題型.
* For [Leetcode No. 1 Two Sum](https://leetcode.com/problems/two-sum), Week6課程老師有附上 C程式語言的 Hash Table實作, 還沒研究.
* For [Leetcode No. 119 Pascal's Triangle II](https://leetcode.com/problems/pascals-triangle-ii), 可以僅針對分母進行質因數分解, 但還未實作.
* For [Leetcode No. 29 Divide Two Integers](https://leetcode.com/problems/divide-two-integers), 有關 bit operation來找出 MSB的方法還沒研究.
### 其他心得
* 每個人都有盲點, 老師想出的同學互評的方式, 一來可以讓同學點出彼此的優缺點. 二來, 也是一個促進課堂互動的方式.
* 我的心得是「老師難當」, 尤其評分的時候.
* Sorry, 我沒有看很多其他同學的 interview錄影. 我也還沒時間欣賞 Leetcode同題目的 submissions.
* 我的時間管理還是有待改進, 每次都被許多身旁的事情追著跑, 啥時才能羽扇綸巾, 談笑以對呢?
* 我還是需要時間, 一步一步來, 要相信自己, 每個人的旅程都不一樣.
## 待學習與研究的主題
* 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的檢討
* [06:11](https://youtu.be/E3-tv6w8lBY?si=VZmoOCTNCFmwDWmh&t=371) OMG! 男孩每天賺的錢可多達 10^9耶! 感覺這個條件可以放在延伸問題時再點出來, 改成"30年後, 男孩長大在證券交易所上班, 再次接到不明來電時, 每天的交易量為 ..."就較有可能符合這個 order的數字.
* interviewee的檢討
* 針對 Two Sum這個問題, HackMD上介紹影片中優化的解法在驗證後沒有預期的效能改善. 仔細思考這個問題的背景後, 我認為這個問題設計上很特別, 輸入整數陣列索引範圍在[0~9999], 但這 10000個陣列元素的內容卻是散佈在[-10^9~10^9]. 許多解法 based on Hash Table, 但我認為在 Hash Table之前應該還有一個可能的解法, e.g., 建立 inverse array以陣列元素內容 map到其陣列索引. 這個 inverse array會是一個非常稀疏的陣列, 其陣列索引範圍會有[0~10^9 + 10^9], 陣列元素數值就為 [0~9999]. 理解上, 不確定作業系統中每個 task的 page table是否會是類似這樣的 mapping關係. 於是, 我有嘗試以這樣的概念進行以下實作.
* 先以原始陣列來建構出 inverse array.
* traverse原始陣列的每個 element, 在每個 iteration, 可以用 target扣除 element value後, 在 inverse array中找尋是否有對應的內容, 有的話, 該內容就是所求的另一索引. 沒有的話, 就進行下一 iteration.
* 然而, 這樣的解法會需要許多空間, 且目前我並沒有實作成功. 以下有我的簡單實作.
* 另外, 我認知的 page table會是以 radix tree進行實作, 這個還需要研究. 另外, 有關 sparse mapping引發配置空間卻沒有實際使用到的問題, 也凸顯出使用 radix tree, hash table等資料結構的必要性.
* 其他
* HackMD中程式碼的部份可以選擇程式語言種類來 highlight keywords.
```clike
#define BALANCE 100
int* twoSum(int* nums, int numsSize, int target) {
int i, j;
int *pair = (int *)malloc(2 * sizeof(int));
int *pos1 = (int *)malloc(100 * 2 * sizeof(int));
int *pos2 = (int *)malloc(100 * 2 * sizeof(int));
memset(pos1, 0, sizeof(pos1));
memset(pos2, 0, sizeof(pos2));
char flag = 0; // not found
// establish the nums mapping array firstly
for (i = 0; i < numsSize; i++) {
if (pos1[nums[i] + BALANCE] <= 0) {
pos1[nums[i] + BALANCE] = i + 1;
} else if (pos2[nums[i] + BALANCE] <= 0) {
pos2[nums[i] + BALANCE] = i + 1;
}
}
// according to the mapping array, find out whether the pair exists
for (i = 0; i < numsSize - 1; i++) {
if (target == nums[i] + nums[i]) {
if (pos1[nums[i] + BALANCE] > 0 && pos2[nums[i] + BALANCE] > 0) {
pair[0] = pos1[nums[i] + BALANCE] - 1;
pair[1] = pos2[nums[i] + BALANCE] - 1;
flag = 1;
goto out;
}
} else {
if (pos1[target - nums[i] + BALANCE] > 0) {
pair[0] = i;
pair[1] = pos1[target - nums[i] + BALANCE] - 1;
flag = 1;
goto out;
}
}
}
out:
free(pos1);
free(pos2);
if (flag)
return pair;
return NULL;
}
```
Sign in with Wallet
Connect another wallet