---
# System prepended metadata

title: '2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業2'

---

# 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;
}
```
