Coding Problems - Google 工程師 Coding 面試範例

How to: Work at Google — Example Coding/Engineering Interview

LINK： https://www.youtube.com/watch?v=XKu_SEDAykw

從影片中學到什麼

這個影片主要介紹 Google 在 coding interview 環節的模擬情況，最大的重點在於如何解題，可以用什麼樣的流程清楚展現自己如何解決問題，除了題目結果外，最重要的是解題過程中如何思考，整個流程可以細分成：

1. 面試官闡述問題，在上面（i.e. sorted array）寫下 key points，確保所有細節，展示組織能力

2. 在次確認 inputs outputs

3. 思考問題重點是什麼，有時間空間內存的限制嗎

4. 用最簡單/暴力解法開始解題，口頭描述，表明出你善於思考與批判

5. 說明這個解法不是最佳解，它的 bigO，readable

6. 說明 code 有什麼地方是多餘的，重複的，可以怎麼去解決

7. 在真正開始寫下代碼前，先在問題上寫下我要怎麼做

8. 開始將代碼模塊化，把代碼分成小片段，需要時寫下註解

9. 真正寫下解法，前面準備得越多，能寫下的代碼就越好，千萬不要不確定怎麼寫就開始

10. 思考程式什麼情況下會出錯，假設有人想要破壞你的程式碼，什麼樣的 inputs 會導致程式出錯，告訴面試官我會怎麼測試這段程式碼

11. 命名盡量用人看得懂的

12. 告訴面試官你會怎麼加強你的代碼，有沒有辦法更 readable，會怎麼使用 google 來幫助你

在這個範例題目我用 JavaScript 實作一次

Question：
輸入數列，裡面的數字兩兩相加，等於8的話回傳 true
[1,2,3,9] if sum = 8 return false
[1,2,4,4] if sum = 8 return true

1. 釐清問題後首先以暴力解法 run 一遍，完全遍歷整個陣列

const arr1 = [1, 2, 3, 9];
const arr2 = [1, 2, 4, 4];

function checkSumEqual(arr) {
  for(let i = 0; i < arr.length - 1; i++){
    for(let j = 0; j < arr.length - 1; j++){
      if(arr[i] + arr[j] == 8)
        return true
    }
  }
  return false
};
console.log(checkSumEqual(arr2));

2. 可以發現這種解法的時間複雜度是 Ｏ(n^2)，而且會有重複相加的情形，開始思考有什麼方式可以不會重複相加，可能會想到使用類似 Selection Sort 把第二層迴圈 j 初始值從 0 改為 i，解決了重複相加的問題，相比原本來說好了一點，但是還是一樣使用了兩層的迴圈，時間複雜度一樣是 Ｏ(n^2)，所以在思考看看有沒有其他方法。在影片裡被面試者想到的是縮小範圍的方式，最大值加最小值，如果大於 8，最大值 index - 1，反之如果小於 8 就讓最小值 index + 1，如果中間遇到相加等於 8 就直接回傳 true，迴圈到最小值 > 最大值為止

const arr1 = [1, 2, 3, 9];
const arr2 = [1, 2, 4, 4];

function checkSumEqual(arr) {
  let min = 0;
  let max = arr.length - 1; 

  while(min < max){
    let s = arr[min] + arr[max];
    if(s == 8){
        return true
    }else if(s > 8){
        max--;
    }else{
        min++;
    }
  }
  return false
};
console.log(checkSumEqual(arr2));

3. 看似完美的解決問題，只有使用到一個迴圈，時間複雜度 Ｏ(n)，但是在這裡面試官丟出一個難題，不保證輸入的值有經過排序，所以這個解法行不通了，如果還要做排序那可能效能還沒有暴力解好，所以還要再看看有什麼方式，可能會想到 hash table 的方式，做一次遍歷，把 8 減掉現在遍歷到的數字放到 hash 表中，如果現在遍歷到的數字匹配到 hash 的數字，就代表有一對數字相加為 8，回傳 true

const arr1 = [1, 2, 3, 9];
const arr2 = [1, 2, 4, 4];

function checkSumEqual(arr) {
  let hashTable = new Set();
  for(i = 0; i < arr.length; i++){
    if(hashTable.has(arr[i]))
      return true
    hashTable.add(8 - arr[i])
  }
  return false
}
console.log(checkSumEqual(arr2));

4. 這樣解決了遍歷一次，時間複雜度O(n)，而且不會有排序問題，因為 HashTable 是慢慢把前面遍歷的值處理後加進去，也不會有自己加自己的狀況產生，很好的解法。

5. 最後到這裡就告一段落了，可能還會再問一些相關問題，比如輸入的數字太多，無法負荷，你會用什麼方法解決，這邊就是把自己的想法講出來就好了，可能是把輸入分段處理，分段處理又會遇到什麼問題……