Try   HackMD

2021 年「資訊科技產業專案設計」面試範例

貢獻者: 高爾夫-Golf
video1, video2

35. Search Insert Position

video

題目描述

給一個已經排序過 ( 升冪 ) 的數列，並且此數列每個數字都不同，再給一個目標數。如果目標數在此數列中，請回傳此數字位置；如果目標數不在數列中，請回傳目標數應該要安插的位置。

程式碼解說

方案一 : 暴力解

由於此數列已經排序過了，因此直接用一個 for 去把數列中每個位置都去跟目標數比較，即可以得到答案。特別注意，如果跑完整個迴圈都還沒找到，就代表目標數大於整個數列，所以直接回傳最後一個位置即可。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i]>=target) return i;
        }
        return nums.size();
    }
};

方案二 : 二分搜尋法

二分搜尋法就是利用數列中間的數字跟目標數比較，一直切成更小等分，直到切不了就代表結束。

  • 中間數「大於」目標數
    • 中間數以後也都大於目標數，因此可以不用再看
  • 中間數「小於」目標數
    • 中間數以前也都小於目標數，因此可以不用再看

結束二分搜尋法會有幾種可能性

  1. 目標數被夾在 left and right
    • 直接回傳 right
  2. 目標數不在 left and right 中
    • 代表目標數大於整個數列或小於整個數列
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums[0] >= target) return 0;
        if(nums.back() < target) return nums.size();
        int left = 0;
        int right = nums.size() - 1;
        while (right - 1 != left) {
            int mid = (right + left) / 2;
            if (nums[mid] == target) return mid;
            else if(nums[mid] > target) right = mid;
            else left = mid;
        }
        return right;
    }
};

面試過程檢討

Interviewer

  • 00:14: 說話避免中英混用，「目標值」和 "index" 擺在一起，無助於理解，而且也缺乏對應的名詞定義，儘量改為口語方式表達 (甚至設計另一種情境)，也可避免 interviewee 死背答案。關於輸入的數值範圍和行為，都該清楚說明
    • 例如：考慮成大資訊系只錄取 45 名學生，已知現有成績造遞減排列，給定分數 x，我們可以如何判斷是否篤定錄取或者列入「危險但有機會」(考慮有 y 人放棄的狀況) 呢？
  • 01:41: 避免說「聽起來這方法還可以」，也不該直接問「時間複雜度」(interviewee 很容易背誦或猜測)。今天公司安排 interviewer 用上班時間跟 interviewee 互動，是為了「找人做事」，要儘量藉由互動來確認應徵者的能力和溝通方式是否對公司有助益。這裡可改提出 interviewee：「打算要用策略來實作？」「演算法是否需要額外配置空間？」等問題，這些需要基本的論述
  • 02:05: 避免說「我覺得
    O(n)     可能太慢」這種話，一來聽起來很沒把握 (所謂的「可能」，要看用在哪裡)，二來「太慢」的前提是輸入資料的量，既然 interviewer 沒有清楚說明條件，這個「太慢」也未必會成立。這樣的提問，會讓 interviewee 覺得對方沒有好的準備，也缺乏適度的關注及互動
  • 04:58: 避免說「幫我把 code 實作出來」，一來很不專業，二來中間應該要有討論，例如「如何找位於中間的元素」，甚至在題目加上額外條件，像是「考慮到原本的輸入中存在負整數，但給定的目標值必定大於零，那可以怎樣改進？」。interview 的重點是「互動」，不要讓 interviewer 可僥倖背誦答案
  • 06:35: 當 interviewee 寫出語法不正確或者可能沒思考周全 (如 + 帶來的overflow) 時，即可打斷 interviewee，提醒他修改或者討論
  • Binary search 衍生 很多變形，如果 interviewee 作答後可充分解釋程式碼，可引導 interviewee 去思考上述變形，甚至論文 Modified Binary Search Algorithm，提出改進手段
  • 沒有後續的問題和程式碼討論，interviewer 沒做出足以鑑別一個人能力的舉措

Interviewee

  • 01:59: 既然講了最差的時間複雜度，那也該提平均和最佳的案例
  • 02:15: 進行 REACTO 步驟時，就可說明自己將採用 binary search，不用拖到現在才說，注意時間！
  • 02:23: 之前所舉出的案例，不用急著刪去，一樣留意時間，儘量騰出有效的互動時間
  • 02:37: 舉例時，應先列出奇數個元素，才可沒爭議地指出「中間」，否則就需要定義
  • 05:13: 打字太慢，要練！
  • 05:16: 「兩個 input」不易識別，改為「二個參數」，注意: 中間若說不清楚，無助於溝通，最後只是浪費自己的寶貴時間
  • 05:25: STL 的 vector 發音要確實: [vek-ter]，不要偷懶忽略 [k] 的發音，寧可說得慢，不要讓人誤解
  • 06:01: 不要說「接下來我們就進入 while 迴圈的部分」，會讓人感覺你是背誦答案，應該要一邊解說 binary search 的演算法，一邊敲打程式碼 (要練!)
  • 06:54: 提到「第二種可能性」時，沒有說到「第一種可能」(不需要加「性」)，應該在撰寫程式碼之前，就列舉三種可能
  • 07:50: 中間停頓過久，如果要移動游標，過程中請說話，化解尷尬，也能讓 interviewer 的注意力集中
  • 08:46: 判斷式 if (nums.back() < target) 和後續的程式碼可精簡，例如事先求值 (evaluate) nums.size()
  • 環境採光儘量柔和，避免過白

371. Sum of Two Integers

video

題目描述

給兩個整數，回傳相加的結果。不能使用 + and -

程式碼解說

方案一 : 把每個 bit 去 Run 過一遍，特別注意 carryout

class Solution {
public:
    int getSum(int a, int b) {
        if (!a || !b) return a == 0 ? b : a;
        int result = 0;
        int carryout = 0;
        for (int i = 0; i < 32; i++){
            int A = (a >> i) & 1;
            int B = (b >> i) & 1;
            switch (A + B + carryout){
                case 1:
                    result |= 1 << i;
                    carryout = 0;
                    break;
                case 2:
                    carryout = 1;
                    break;
                case 3:
                    result |= 1 << i;
                    carryout = 1;
                    break;
                default:
                    break;
            }
        }
        return result;
    }
};

getSum 的參數是兩個整數

  1. 首先利用第四行去判斷「是不是有其中一個為零」，假如有就可以直接回傳非零的數字。
  2. 透過 for 迴圈去看每個 bit 是 0 還是 1 ，並且利用 A and B 來存
  3. 緊接著用 switch 將每種可能性找出來，並做出對應的事情。
    • 如果 A + B + carrout = 3 代表要進位並且還要存 1 進去 result
    • 如果 A + B + carrout = 2 代表要進位並且還要存 0 進去 result
    • 如果 A + B + carrout = 2 代表「不用」進位只要存 0 進去 result
  4. 回傳 result

方案二 : 利用 XOR 把不用進位的 bit 直接存起來，再將要進位的左移，直到沒有 carryout

class Solution {
public:
    int getSum(int a, int b) {
        unsigned carry;
        while (b != 0) {
            carry = a & b;
            a = a ^ b;
            b = (carry << 1);
        }
        return a;
    }
};

while 迴圈的結束條件是沒有 bit 需要進位

  1. 首先程式碼第七行，把需要進位的 bit 存進 carryout 起來。
  2. 程式碼第八行，將 a XOR b 就可以找到不用進位的 bit ，直接存進去 a
  3. 將 carryout 往左移一個，就代表進位後的 bit
  4. 重複 1 ~ 3 ，直到沒有 bit 需要進位
  5. 回傳 result

面試過程檢討

Interviewer

  • 接下來要測驗 Interviewee 能不能用不同的方法來進行，並且降低記憶體的使用；然而在影片中講的不夠精準，不應該說空間複雜度，而是要說降低記憶體的使用。
  • 00:15: 提及不能用 + 和 - 這二個運算子，但沒說「為何要給這樣的限制」，只會讓背誦答案的人有幾可趁。可以順著題目意思，說「我想知道你能否組合邏輯運算子，達到運算電路的模擬，也能得知你在位元層級的掌握度」
  • 02:46: 避免說「可以麻煩你把 code 打出來嗎？」這種話，原因是:
    1. 沒有討論
    2. 沒有正面回應
    3. 給背誦答案者過多的空間
    4. 這種說法過於「台式」(乍聽以為是《深X保健室》來賓的對話)
  • 02:59: 「不用考慮 (overflow)，沒關係」無助於互動，這其實是理解 interviewee 對二補數和相關數位邏輯認知的好機會，應該在此停下
  • 03:50: 敘述 for (int i = 0; i < 32; i++) 值得討論，應該打斷，讓 interviewee 回顧 64-bit data model
  • 07:22: 看到 interviewee 寫出較長的程式碼，應該停下來討論，不僅要確認程式碼正確，也要思考程式碼能否精簡，例如 if (!a || !b) return a == 0 ? b : a; 可簡化為 if (!a || !b) return a | b; (減少分支且更直觀)
  • 07:31: 避免說「這個 code 看起來是沒什麼問題」，這樣很不專業，只會讓 interviewee 覺得自己只是換個地方默寫 LeetCode，而不是一個重視技術內涵的公司該有的表現
  • 07:34: 避免只是說「你能寫得更精簡嗎？」，卻沒有給予方向和思維，這不是好的「互動」
  • 沒有後續的問題和程式碼討論，interviewer 沒做出足以鑑別一個人能力的舉措

Interviewee

  • 00:38: 避免說「探討每個 bit，並且把每個 bit 看過就可以知道答案」這種話，因為沒有任何資訊量可言 (一堆演算法都會「看過每個 bit」)，應該要推敲出題者的期待，特別是限制來自什麼。不要忘記「互動」，也該避免說「答案」，今天公司是要找人「解決工程問題」，而非「找人背誦答案」
  • 00:45: 與其急著寫出 carryout，不如將你知道的半加器、全加器，甚至二補數原理說出來

    解讀計算機編碼 科普讀物

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

    組合邏輯

  • 延伸閱讀: 使用遞迴和 bit-wise operator 來實作乘法運算
  • 02:00: 若將位元操作的行為說清楚，也不用特別去列真值表，除非被要求
  • 07:42: 既然你不是實力派女歌星，沒人想聽你的氣音，尤其透過視訊會議，會更明顯，務必避免
  • 09:32: 可以先用邏輯電路的觀點去解釋 carry，除非 interviewer 明確要求你舉實際的案例，這體整體來說，花費太多時間，卻又看不出 interviewee 具備的程式設計技巧
  • 11:01: 由於前面舉例根本沒歸納 XOR 和 AND 位元操作的行為，此處寫出程式碼，就像是死背程式碼，可能會引起 interviewer 拿出更多的變化來「挑戰」
    • 例如：不用遞迴、用更少的位元運算

參考實作:

int getSum(int a, int b)
{
   return (!a | !b) ? (a | b) :
                      getSum(a ^ b, ((unsigned) a & b) << 1);
}

延伸閱讀:

第三次作業 - 他評01

優點

  • 有重複問題和舉例討論。

缺點

35. Search Insert Position

00:18 Interviewer應該避免中英混用，以索引值取代index。
00:56 Interviewer在00:05只有說題目給定已經排序過的數列，Interviewee不能自己假設排序就是升冪(或降冪)，應該在重複Interviewer之問題後先確認再舉例。
01:41 Interviewer應該避免直接問Interviewee時間(空間)複雜度等，容易流於制式化的問答。如果想考驗相關想法，應該等Interviewee實作完程式碼還是沒有提到時，再以其他方式詢問並啟發思考是否能再更精進。
02:08 Interviewer不能直接說

O(N)可能太慢，因為到目前為止並未提到輸入的資料量，因此也不該在沒有補充說明條件的情況用可能這樣的字眼。
02:15 舉例只佔了一小部分空間，Interviewer不需要刪掉重打，才能節省討論時間。
04:13 Interviewer的舉例和後面實作二分搜尋法的程式碼不一樣，舉例是right = mid - 1或left = mid + 1，但是程式碼是直接將mid賦值到條件下對應的變數。
06:39 Interviewee用二分搜尋法前(或更早)就應該先向Interviewer確認給定陣列的長度，因為在int mid = (right + left) / 2;這邊可能會發生溢位。Interviewer發現寫法上的問題時也應該適時打斷並給予提示，觀察Interviewee能否做適當的修改。
07:47 Interviewee應該一開始就先針對較極端的情況(出現在頭或尾)進行舉例討論，比較能節省時間。
08:55 這題可以改寫二分搜尋法的程式碼，就不用前面那些判斷。另外整個過程到最後只有改進程式碼的時間複雜度，Interviewer沒有做問題的延伸或出變化題。

371. Sum of Two Integers

00:15 Interviewer只說條件是不能用＋或-太單調了，可以說要使用位元運算符實作兩整數加法，考驗Interviewee對位元運算的掌握度等等。
01:01 Interviewee不用將之前的舉例刪除重打，節省後續的討論時間。
04:05 Interviewer應該先向Interviewee確認題目是否有規定整數型別是幾個位元，不能自己假設是32bit。
07:23if (!a || !b) return a == 0 ? b : a;是要在a或b其中一個變數為0時，回傳不為零的變數，可以改成直接回傳a | b即可。
07:30 Interviewer給的評語(看起來是沒甚麼問題)太表面，接著如果想要求Interviewee寫得精簡一點時，也許應該提示是哪個部分，Interviewee最後也沒有在簡化程式碼，而是直接換了其他作法。
08:47 Interviewee舉例加法結果與進位時，就應該帶入自己對位元互斥或(^)以及位元且(&)的想法，避免後續的程式碼看起來像背答案。
09:50 Interviewee的舉例可以留著不要刪掉，後面解釋程式碼的作法時比較容易讓Interviewer理解。

第三次作業 - 他評02

35. Search Insert Position

  • 6:28 overflow problem
  • 7:31 可以提出 loop invariant 驗證 binary search 正確性
  • 8:52 array 中含有重複 element 的情況也該討論

371. Sum of Two Integers

  • 0:22 應先詢問整數範圍
  • 4:49 用到 operator +，與題目要求不符
  • 7:24 輸入測資
    a=231−1, b=231−1     會出錯
Last changed by 
 
sysprog
System Software Programming
4750
Published on HackMD