想請教 Google Interview 要注意的事項 - 面試

※ 引述《RockLee (Now of all times)》之銘言：
: 上週跟美國那邊進行了第一輪電話面試,
: (第一次跟國外面試就是魔王等級 Orz...)

說老實話 Google 的面試早就不是魔王等級...
井字遊戲輸贏有很魔王嗎? 我覺得最近大多都是出木樁王, 就是考驗基本功而已.
個人經驗是 Square 跟 Palantir 的面試問題都有趣得多.

: 今天 HR 打電話來說 interviewer 的 feedback 沒有很好,
: 會再通知我第二輪電話面試的時間.
: 根據 HR 的說法,
: interviewer 認為我的 code 雖然正確,
: 但是一些 follow up 的問題,
: 例如複雜度的分析沒有做的很好.
: 其實我感到有點訝異, 回想一下上次面試過程,
: 一開始是問一些過去的學經歷(我的背景是本土碩士 六年台廠工作經驗),
: 然後只出了一道coding的問題(我寫完離預定的interview結束時間還有20分鐘, 時間上應
: 該夠再出一題),
: 題目是給一個 array 代表 3 X 3 的井字遊戲狀態(1:O, -1:X, 0:空格),
: 輸出一個數字代表結果(1:O win, -1:X win, 0:還沒人贏).
: 我只想不到一分鐘就開始 coding,
: coding 完 interviewr 也說 code 看起來應該正確,
: 然後問如果輸入不是 3 X 3 而是 N x N 我的 code 是否依然正確,
: 我回答只要把 3 改成相對的 N 即可.
: (一開始我相關code中都直接用3, 此時我有說若一開始設定N=3並在相關code中用N會更容
: 易擴充)
: 然後他問我複雜度的部分,
: 我也有回答出 time complexity: O(N^2), space complexity: O(1),
: 對這個問題應該也已是最佳解.
: 然後他問我若 N 大到無法在一台機器運算怎麼辦,
: 我也有大概講一下用 row index 當 key, 每一行 row 當 value,
: 如何用 map-reduce 架構運算.
: 不好意思寫得很亂, 我想板上應該不乏在 Google 及其它好公司工作的強者, 想請教一下
: (1) Coding 問題會在 constant factor 上計較嗎?
: 因為我覺得我遇到的問題input size就是N^2了,
: 我的coding頂多只能就 constant factor 作改進.

Short answer: Yes constant factor matters.

Long answer:
個人覺得敝公司的電話面試越來越鬆了,
這種 fizz buzz 等級的問題只要 code 會動, 複雜度不要太誇張, 基本都會給過.
我最近還看到一個 tail recursion 轉 loop 寫壞掉的也讓他濫竽充數混進來.
所以個人傾向相信是你推論的時候犯了一些錯誤而不自覺.
你也沒有電話錄音, 很難從片面之詞推斷出你到底哪裡答得不好.
另一種可能是這個 interviewer 很嚴格, 他用 onsite 的標準在檢視你的答案.

話說回來 constant factor 重不重要, 你如果 constant factor 比較低當然有加分啊.
你會這樣問, 然後答案的 space complexity 又是 O(1), 我大概已經猜出你怎麼做的,
多半就是為了省暫存空間, 所以直的掃一次, 橫的再掃一次.
嗯, 勤儉是不錯的美德啦, 不過這樣做多半 code 跑比較慢. 理由是因為:

1. Memory bandwidth 很貴. 整個 N^2 的矩陣能只掃一次你就不會想掃第二次.
相反的, memory space 很便宜, 你都可以存一個 N^2 的矩陣了,
再多拿 O(N) 存一個 column sum 是有多貴?

2. Cache locality 的問題. 橫著掃矩陣很快,
因為 CPU 讀記憶體不是一次只讀一個 byte, 而是一次讀一條 L1 cache line,
在近代 CPU 上面一般而言是 64 bytes 或更多.
這代表的是, 你讀矩陣第一格的時候可能因為 cache miss 而 stall 數百個 cycle,
可是你讀接下來 63 格的時候, 資料都還會在 L1 cache 裡面.
相反的, 當你直著掃的時候, 這多讀的 63 bytes 根本完全沒有用到,
因為下一個 row 的資料已經在不同 memory block 上,
而當你掃完一整個 column 回來要掃下一個 column 的時候,
L1 早已經被刷新, 全部的資料都得重讀.

這個原則不只對於 L1 cache 適用, 對於整個 memory hierarchy 都適用.
資料放在雲端, 硬碟存不下? 那就要注意存取的 locality, 儘量少 network request.
資料放在硬碟, 記憶體存不下? 那就要注意存取的 locality, 儘量少 swap.
資料放在記憶體, L2 存不下? 那就要注意存取的 locality, 儘量少 cache fault.

結論是, 省暫存空間這個勤儉的行為就像是為了撿路上的銅板而被十八輪大卡壓過去.

: (2) 會希望先跟 interviewr 描述想法再開始 coding 嗎?
: 我在 interview 的時侯是先 coding 完才描述我的方法,
: 我在想會因為這樣被扣分嗎?

會不會扣分因 interviewer 而異, 不過你是應該先描述想法再 coding. 理由:

1. 這是 interview 很重要的一部分, 我們想聽的不只是問題的答案,
更重要的是了解你的思路, 了解你是如何解決這個問題.
我們要用的不是知道所有問題答案的人, 而是知道如何解決新問題的人.

2. 先確認對於題目的理解沒有錯誤, 以免你都寫完了才發現是聽錯題目.

3. 先說明你的 approach, 之後 interviewer 也比較容易理解你的 code.

其實綜合 2. 3. 點, 就是我們想知道你的溝通能力如何,
實際在工作的時候也不會是一個人死幹蠻幹,
更多時間其實是花在 code review 上說服你的同儕.
因此事前溝通很重要, 你才不會 code 寫完了才發現 code review 不會過,
事後溝通也很重要, 讓別人懂你的 code 才有人能繼續修改你的 code.

: (3) 通常 coding 正確還有哪些原因會得到 negative feedback 呢?

最常見的是溝通能力問題, 或是人看起來陰陰沈沈很難相處,
或是看起來對寫程式沒有熱情.

--
「ふ…ふざけるな！そんあ短い咒文で、魔法を起動できるわけないだろうが！
お前わマウゼルの神に逆らう氣なのか？！傲慢な～」

「失禮致しました、誠實に全力でお相手致します。
第一戰術級‧軍用攻性魔法‧出よ、武雷神〈トール〉！」
〈スクラップド‧プリンセス〉

--