Re: [北美] 想請教 Google Interview 要注意的事項

[Freak1033 (金が信念! XD)]

※ 引述《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 呢?

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

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

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

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 173.228.125.35
→ pest:不過剛畢業的沒事就丟一個hashmap出來說O(1)跟勤儉無關啊...
推 RockLee:井字遊戲本身確實不是魔王等級 我只是訝異原本以為在 time
→ RockLee:complexity都是O(N^2)的情形下, 用space complexity O(1)
→ RockLee:應該是較好的選擇 沒想到feedback是複雜度分析沒做好
→ RockLee:看了F大的說明發現interviewer重視的確實跟我想的不一樣
→ pttnoguest:難怪狗家的東西 越來越難用
→ kruz:我覺得自從G社變成誰都會輪到當面試者以後運氣成份就變得很重
→ kruz:要..以前因為那堆面試者經驗很多所以至少結果比較consistent
推 smi1e:我用的面試題都比這些難多了@_@
推 RockLee:我練習CareerCup上的考古題也有發現較近的題目平均難度確
→ RockLee:實有下降 不過如果沒有F大的說明可能連蛋糕等級的題目都會
→ RockLee:把我砸死我還不知道為什麼
→ RockLee:看了以前的文章也有人覺得他遇到的明明都是蛋糕等級的題目
→ RockLee:也很快寫完卻不知為何被淘汰 或許他也沒有釐清interviewr
→ RockLee:重視的是什麼吧
推 RockLee:其實也有其它在Google工作的板友回信說他一般不會計較
→ RockLee:constant factor 有需要的話他會明講
→ RockLee:所以重點可能要先釐清每個 interviewr 重視的是什麼
→ RockLee:希望下次遇到的題目難一些吧
→ RockLee:不是很理解P大的意思 是說不要常用HashMap嗎?
→ pest:問題不大的話用hashmap就有點太簡單了,通常也對這個O(1)太樂
→ pest:觀了一點,往往處理hashmap的code比要解的問題還複雜 XD
推 pest:舉個例子,不過就是要寫個function把陣列順序互掉,也丟個hash
→ pest:map出來嚇人,是說記憶體這模便宜也不是這樣用的啊...
→ RockLee:下篇有板友提到NDA的疑慮 我原本以為分享phone interview
→ RockLee:的資訊應該還好 因為on-site之前也不可能簽NDA
→ RockLee:HR也沒特別提這個 不過既然有板友提醒保險起見還是刪除吧
推 shaopin:我後來也有想到phone interview好像也還好
→ shaopin:不過就是稍微提醒一下, 因為以前我也是這麼過的...
推 thanksyou:太強大了各位，這題目我只能傻眼完全無法討論怎麼解
→ thanksyou:至少要 close book回家想個三天才會有初步解法...
→ thanksyou:感覺是樹狀搜尋法
推 forwind:lol
→ RockLee:結果昨天 on-site 還是沒有人拿 NDA 給我簽啊~
推 landattack:謝謝Freak1033! 這篇有好多interviewer 分享喔! ^Q^
推 Dav12345:了解了 開一個另方向的N arrays 把掃過加上去檢查
→ Dav12345:row的掃過一次 column也檢查完了