[心得] 國外各大公司面試經驗

背景：4~7年經驗(anonymized), 求學背景是純商, 程式100%從0自學來的
Leetcode去年訂了一年Premium之後開始刷，累積到目前700題，Medium + Hard佔約70%
2020年2月開始陸續投遞履歷，全部都是投英國/日本的職位
只有Google例外是台北辦公室（GCP）

投遞：Stripe, Yelp, Microsoft, Apple, Indeed, Google,
Facebook, Spotify, TikTok, Twitter, Lyft, Yelp, SmartNews
無聲卡: Microsoft, Lyft, Twitter, GitLab

以下面試經驗照面試時間順序排列

------
＊ Spotify - Software Engineer (Data)
- 透過LinkedIn投遞履歷

[ Phone - Feb ]
- coding: Valid Parentheses, 給定一字串，寫一個function來辨認是否為valid
- follow-up: 多幾個不同的Parentheses, 例如{} [] ()
- follow-up: 寫成map reduce的形式, 怎麼設計mapper & reducer
- 有沒有聽過prabalistic data structure? 給一個例子 （我給Bloom Filter）
- 一些簡單的SQL問題

[ Onsite - Mar]
早上兩面，下午兩面，中午在spotify london的飯廳跟兩個工程師吃飯，
飯後閒聊順便玩一下飛鏢，再繼續面試

- System design問題，設計一個Top 10 tracks API與實時計算系統
- Behavioural問題，tell me a situation when ....STAR類問題,
就照著過往經驗回答即可, 隨時要跟hiring manager做eye contact爭取感情加分
- Case analysis, 給一個line chart是三個國家的DAU,
並發現US DAU nose-diving, 問題出在哪？跟面試官交互討論出問題成因
主要考察邏輯分析，溝通能力
- Coding: 暖身題Fizzbuzz, 迅速寫完之後給了一些簡單的follow-up
- Coding: Longest Session.
給定一個List of 4-tuple [user_id, track_id, timestamp, time_played],
找出最長的session. -> 類似LC 56. Merge Intervals, 最佳解O(NlogN)
Follow-up: 如果input塞不進memory, 怎麼解？
我簡短回答有Disk-based or Mapreduce approach
然後我深入講了一下MapReduce怎麼寫

Spotify這職位有意思的地方是會考Case Analysis,
通常這比較常用來考data/business analyst, 還好我唸過商學院XD

[ Result ]
三天後通知結果, offer get. ￡105K GBP/year

------
＊ Indeed - Senior Software Engineer
- 透過japan-dev.com投遞履歷

[ Phone - Feb ]
使用Karat面試，可以在週末面(加分！！)
- coding: 類似LC 1143. Longest Common Subsequence, 給定兩個字串
找出最長公共子字串. 另外兩個問題我忘了，都是LC easy. 掌握好基本學理，
好好溝通你的解法並迅速implement出來就好
- 系統問題：Thread v.s. Process, thread exhaustion,
memory leak, Java GC (SOTW). container的優點...等等

[ Result ]
本來安排要3月中飛日本on-site，因為武漢肺炎爆發突然宣布hiring freeze
無限期on hold, sad

------
＊ Google - Software Engineer
內推, 原本推日本的缺，Recruiter說日本沒有我的專業
(日本office主要做Mobile及NLP Research), 台北/倫敦比較多GCP/Data的缺

[ Phone - Apr ]
LC Medium難度，實作time_delta函數，就是給你一個Date class跟一個正整數，
例如(2020-01-01, 5)，要回傳2020-01-06. 一開始給了一個naive的O(N)解，
面試官提示問有沒有更好的解，然後我解釋了一個O(logN)的解 (但沒時間implement
還好最後有pass，感覺是溝通跟邏輯推理很重要(即使沒寫出完整的最佳解)

[ Virtual On-Site - May ]
全部都是coding interview 沒有system design

- LC Hard矩陣題, finding the size of largest submatrix sum to 0.
看過這題目的variation (LC 1074)
花了20分鐘實作O(N^3 using Kadane's algorithm)解法，寫完之後閒扯了一些
test corner cases. 這題你沒看過最佳解法的話
能想到並實作O(N^4)的prefix sum解法已經很猛了, 多做點題還是有幫助的
- LC Medium有向圖題, 這題在Leetcode上沒看過類似的，給你一個樹，
可以視為Direct graph及一個想delete的節點，找出所有detached的節點。
花了20分鐘討論，10分鐘用DFS寫了一個解答
(然後面試結束我想了一下發現了一個bug, 扼腕)
- 2題LC Easy~Medium字串題，這題也沒看過，
概念上類似finding palindromes in a list of strings,
例如mow在轉置後會等於原字串mow。第二題是follow-up,
要找出轉置後不等於原字串的，例如loom -> wool
- 2題LC Medium，N-ary tree尋找兩個node的共同祖先，
答出第一題後給了一個follow-up (如果兩個node很靠近該怎麼最佳化?)
給了一個錯誤的解法(錯把有向圖當無向圖來解)，算是GG
- Behavioural, 無難度，就問一些你遇到XX狀況會怎麼做，
之前遇到甚麼衝突的情況之類的，照真實情況回答即可，
但盡量touch到Googlyness讓面試官找到signal幫你加分，
例如be friendly and approachable, focus on customer,
do the right thing之類的

[ Result ]
On-site 5天後通知表現fairly well送package到HC,
10天後通知沒過HC, 自己評估是兩個hire, 兩個leaning(hire/no-hire),
Google標準很高所以....Reject
我側面了解是要拿到三個hire以上? 這部分如果有熟悉的Googler為我解惑
我感激不盡

------
＊ Facebook - Software Engineer - Infra
內推（感謝Brian Hsu大大）

[ Phone - Apr ]
一題LC Medium, LC 146. LRU cache的變體
用Doubly-linked-list & Hashmap實現
被面試官提醒非常多次一些小地方有bug，感覺GG

[ 2nd Phone - Apr ]
上一個Phone interview雖然有寫出最終解答，不過中間提示太多
面試官覺得需要加麵一次, 這次是一題Easy, 不在LC上,
是tax bracket calculation (我在LC discuss中有看到)，給出O(N)最佳解
另出一題Hard, LC 42. Trapping Rain Water的變體，給出3-pass O(N)次佳解,
中間卡了非常多次, 面試官不停給hint. 這輪我遇到很有意思的面試官，
寫出的feedback精細到我幾分幾秒的時候說了甚麼話都記錄下來, 簡直人體Logger

[ Virtual On-Site - June ]
On-site前recruiter説E4已經額滿，所以我要拿Offer就必須直接拿E5(Senior) offer,
不然就算表現有E4水準也不發offer，搞得我壓力很大...
面試前把所有FB tag的leetcode題刷好刷滿 每題至少刷三次

- 2 LC mediums, 實作bisect.insort_right 跟
在一個NxN矩陣尋找最長連續數字. 皆給出最佳解
- 2 LC mediums, 一題LC 3.的變形，一題LC 398.的變形,
皆給出最佳解(linear time & constant space)
- 系統設計，給幾個constraint下設計一個分散式爬蟲系統，自認表現沒有E5水準. GG
- Behavioural問題，就一般聊天，一邊看著FB的評分標準
一邊把該講的點全部都講到讓面試官好給分，因為我面E5，
需要大量強調領導經驗跟跨團隊合作，例如以下這幾點：
- INTRINSIC MOTIVATION
- BEING PROACTIVE
- PERSEVERANCE
- CONFLICT RESOLUTION
- EMPATHY
- GROWTH
- WORKING IN AN UNSTRUCTURED ENVIRONMENT
- COMMUNICATION

[ Result ]
禮拜二面試，隔一個禮拜收到結果，表現不到E5水準，
兩關coding跟system都得到hire recommendation for E4,
但behavioural面試沒有回答好，有點borderline
Recruiter的feedback是solid E4
但今年度E4已經沒有head count了 所以算reject吧
Recruiter也提到如果今年或明年的E4 head count再開可以送HC
但目前一切都還很難講，建議我不要等待，累積實力等到明年再試一次E5

------
＊ Stripe - Machine Learning Engineer
- LinkedIn獵頭找上

[ Phone - Jun ]
- coding: 兩題，input是一個DB table, 以JSON來表示。
一題尋找table中最小的column, 一題尋找table中最小的數個columns（tie-breaker） e.g.
table = [{‘a’: 1, ‘b’: 2, ‘c’: 3}, {‘a’: 2, ‘b’: 1, ‘c’: 2}]
minCol(table, ‘a’) -> 回傳{‘a’: 1, ‘b’: 2, ‘c’: 3}
minCol(table, ‘b’) -> 回傳{‘a’: 2, ‘b’: 1, ‘c’: 2}
一畝上有很多Stripe面經提到一樣的題目，看來是高頻題一直重複出

[ Virtual On-Site - Jul ]
Stripe喜歡用pair programming來測試面試者，
我個人很喜歡這種面試方式，
比FB那種一個session固定給你兩題LC類型的題目要有意義多了
就算最後沒拿到offer也可以學到很多東西。

- Behavioural: 直接跟用人主管面試，可以趁機問一些組的方向跟個人成長
- Machine Learning Coding: 給一個dataset，生出一個model,
並談到各種model類型，imputation strategy, evaluation metric的選擇,
precision-recall trade-off等等
建議面試前可以到kaggle下載dataset來練習並多讀別人做機器學習的經驗
- Bug Squash: Debugging練習，給一個github codebase及幾個會報錯的test,
並寫出bug fix, 這題我當下太緊張沒寫出來, 面試完後一下就解出來了
- Coding: 寫一個class, 拿schedule當input,
產出什麼時間點要寄送什麼subject的email.
- Machine Learning System Design:
設計一個end-to-end fraud detection系統
40% ML design, 40% system design, 20% business metrics. 答的不知所云

[ Result ]
一個禮拜後通知rejection, 估計是最後一關Machine Learning System Design
我在溝通方面表現不夠好，Stripe的bar也非常高
(recruiter說這個role是EMEA區的first hire, 標準特高)

------

＊ TikTok(Bytedance) - Software Engineer
- 透過LinkedIn投遞履歷，妙的是面試官全是中國人，直接中文面試XD，瘋狂中英加雜

[ Phone - Jul ]
- coding 1: 給一個MxN的布林矩陣, 1代表有一個人在該位置上
如果同一個行或列上有兩個以上的人就代表他們都是非alone
最後回傳有幾個人是非alone
[0 1 1 0]
[0 0 0 1] -> return 5
[1 1 1 0]
最後給出最佳解，two pass scan
time complexity O(M*N) & space complexity O(1)

[ Phone 2 - Aug ]
- coding 2: 給一個array [5 2 1 1 2 5],
必須使用所有的元素來形成任意個subset
每個subset的和是一樣的, 尋找最大的subset數量 (依這個例子答案為2).
這題可以視為LC.698的變體(不指定k)。一開始我覺得可以用greedy,
後來討論得到counter-example後改用sort + backtracking暴力解.

[ Phone 3 - Aug ]
- 針對履歷問了非常多問題也非常細，舉幾個例，API gateway的好處是什麼
(SSL termination, throttling blah blah..),
API rate limiting具體怎麼實現(token bucket algorithm)，
CAP theorem，怎麼樣避免S3上eventual consistency的問題，
訓練出來的模型怎麼存放/versioning，evaluation metric怎麼挑選，
做什麼trade-off，怎麼debug Spark jobs...等等
可以感覺出來面試官知識量很夠
- 順便問了一題coding 3: LC 56. Merge intervals
你能寫錯嗎? 練到爛了閉著眼睛都能寫出來

[ Result ]
前三輪我聽recruiter説都是得到很好的評價，
剩下應該還有一到兩關面試，
但大概是最近抖音美國被川普搞得雞犬不寧
recruiter直接ghost我，我也懶得follow-up了

＊ Yelp - Senior Software Engineer
- 2019年11月網路上投遞，2020年8月才收到OA邀請orz

[ Online Assessment - Aug ]
- 一題，給一連串的Review，有公司id跟使用者id，算公司間的jaccard similarity

[ Phone interview - Aug ]
- 不記得問啥了，很簡單就是

[ Onsite - Sep ]
- Behavioural interview: 過去的失敗，最驕傲的project，最困難的project等等
- System design: 設計distributed cache system
- Behavioural interview: 遇到衝突如何處理，最好給出實際例子，不然他們一律當你是掰的
- Coding interview: 非常簡單的問題，兩個follow-up，LC easy那種

[ Result ]
面試完兩個禮拜後通知verbal offer for IC3, ￡125k GBP/year
優點是可以fully remote 完全不用進辦公室也沒關係
而且拿到offer之後所有的面試官都寄信給我恭喜我...汗

＊ Apple - Software Engineer
- 內推，當初內推選了四個職位，其中一個是AI/ML組，這是JG的組
（JG是Jeff Dean很久以前在Google的上司，2018年join Apple)
算是Apple頗具未來潛力的組，專門做Machine Learning的
- Apple組與組之間的面試風格差異非常大，僅供參考

[ Phone - Aug ]
- 針對履歷問一些問題，包括機器學習/分散式系統，都是基礎知識，
但可以感覺出來面試官知識量很夠
- coding: 給一串文本, 及兩個字, 回傳最小的距離
e.g. text = [cat dog cat dog mouse],
word1=cat word2=mouse, output為2
e.g. text = [cat dog mouse dog mouse],
word1=dog word2=mouse, output為1
e.g. text = [cat dog mouse dog mouse],
word1=mouse word2=mouse, output為2(不是0喔!!)

[ Phone 2 - Aug ]
- coding: LC 200. 加問了幾個follow-up但都很基本
太熟了，時間還沒到就結束面試了

[ Onsite - Sep ]
總共五輪面試，分成兩天，面試官幾乎都是同team或隔壁team的，
看LinkedIn發現這些人背景一個比一個兇猛，還沒join就開始有imposter syndrome了...

- 第一輪Behavioural：問了一堆技術上的問題，怎麼trade-off，怎麼lead，
怎麼解決衝突，怎麼面對同team的人的challenge等等

- 第二輪Coding: 先花了半小時討論怎麼設計一個fault-tolerant的資料處理系統，
watermark，idempotency，一些實務上會遇到的巨量資料處理問題等等
然後花十五分鐘問了一個基本的Linked List問題，把A-B-C-D反轉成B-A-D-C，
再follow-up一下如果寫成recursive call要多少個node才會產生stackoverflow
(1MB stack總共可以裝16k個call,每個call有return address/3 local variables
/1 arg/1 function reference pointer)

- 第三輪Coding: 非常模糊的問題，給一個array of log entry, 類似下面的格式
LogEntry {
user_id
query
timestamp
session_id. // NEW
reformulation_type // NEW
}
要寫出兩個function, 一個是怎麼產生reformulation type，
就是query跟query之間的關係
可以是add/delete/modify/same 等等 (這些都要自己去定義，面試官完全不說話)
一個是要你在這個log entry裡加兩個新的field.
給了一個O(NlogN)的做法，並用Jaccard similairty去產生reformulation type
這題非常新穎，我運氣好剛好想到jaccard similarity的解法
過後聽feedback說是讚譽有加

- 第四輪System design: 設計多人線上井字遊戲系統

- 第五輪Machine Learning: 問了很多簡歷上的東西，怎麼最佳化model training
之前是怎麼改善模型, 一些技術細節怎麼實現等等，
然後就開始轟炸我機器學習相關問題
例如假設今天我是蘋果工程師，會怎麼做federated learning on 1 billion devices GBDT要取哪些模型輸出送往中央伺服器，每個epoch要多少個參數
怎麼對模型輸出動手腳以免被attacker逆向工程出真的模型（鬼才知道）
後來沈思一下，隨便亂回答一個加入Gaussian noise進去參數裡面，
結果竟然矇對了(汗)
話說這個職位並不是做ML的，所以這一輪本來是coding interview
但是因為我過去背景以及面試官背景的關係
我猜他面到一半就改弦易轍想全部都問我ML,
不愧是蘋果，夠random
面完後好奇看了一下面試官LinkedIn, 嗯劍橋PhD in ML

[ Result ]
面試完過了一個禮拜通知verbal offer for ICT4,
Fuzzy offer for anonymity: ￡140K ~ ￡170K GBP/year

總結：
Reject: Indeed(?), Google, Facebook(?), Stripe,
TikTok(?), SmartNews(做完OA就被reject了）
Offer: Spotify, Apple, Yelp

對凡人(Non ACMer/Non奧賽)而言刷題很重要，
我Leetcode買了premium後大概花11個月時間陸陸續續刷了約700題，
每天下班後穩定1~3小時左右無壓力慢慢刷，
輔佐以Elements of Programming Interviews的解題觀念。

Coding interview最重要的就是problem clarification沒有之一，
你沒有搞清楚輸出輸入跟邊界條件根本不可能寫出好的解答,
另外我強烈推薦找一兩個人幫你mock interview,
我自己透過mock解掉了很多解題面試上的盲點
結果就是除了Google之外
我今年沒有fail過任何一個coding interview.

System Design準備上我只有在Youtube上看看一些影片，
再加上一本Design Data-Intensive Application (DDIA, 軟體工程師必讀聖經本)，
以及一本Streaming systems(有點太專門了), 其他都是平常設計系統的實戰經驗累積。我有看Gro-k-k-ing the system interview, 但我覺得有些deep dive不夠深，
deep dive部分還是要靠DDIA，
system design primer
(https://github.com/donnemartin/system-design-primer)
以及follow一個大神的頻道
(https://www.youtube.com/channel/UC9vLsnF6QPYuH51njmIooCQ)

經常看LC以及一畝三分地的面試經驗有很大幫助，讓我理解各個公司面試風格的不同
(例如FB愛出LC原題每輪要解完兩題，G幾乎不考原題，
重視溝通 problem solving與逐步優化，
Amazon極重視Leadership principle,
Apple基本無法準備，完全不按牌理出牌等等).

TC(total compensation)在Blind & levels.fyi上可以找到一些參考
(但台灣幾乎沒有任何樣本可供參考, 嘆)，
negotiation也是必要的，上網看看人家怎麼做，
例如這傢伙https://haseebq.com/my-ten-rules-for-negotiating-a-job-offer/

希望這些面經對大家有些幫助!

--