疫情間的面試 (3)
Image generated by Copilot
TLDR
- Google的面試過程包括四關程式面試和一關行為面試，資深工程師還需進行系統設計面試。
- 通過每天解決十個練習題進行了一個月的準備，面對困難時會尋找解答並反思解題過程。
- 通過面試後，進入了選擇Team的階段，最終選擇了負責YouTube整合測試的小組。
Google的正式面試有五關，像我等級比較低的會有四關程式面試，跟一關行為面試（Behavioral Interview）。行為面試會給你一些公司裡發生的情境，然後問你如何處置。譬如你的同事希望你幫他完成一個計畫，可是你本人也有工作，要如何婉拒等。如果是資深工程師就會有一關是系統設計，譬如問你要如何設計一個像YouTube的網站。我經過三十天的訓練，大約每天十題練習題，還是覺得十分不安心，偶而還是有題目會卡住。我卡住的時候，我就會假裝是真的在面試，看看自己能不能夠吱吱嗚嗚，在短時間內找到解法。如果真的不行，我就會花五到十分鐘，安靜地想怎麼解。如果還想不出來，我就不浪費時間，直接看解答，看完解答後再反思為什麼當初想不到這個解答。通常有幾種可能：一種是這種題型的我練習不夠多，那就多找些類似的練習。一種是我想得太複雜，簡單暴力法其實就是解答，那就要提醒自己，解題要從簡單的想法開始做起，再慢慢改進。一種是題目沒看清楚，譬如輸入範圍其實有限制，輸入數量其實很小，那就要提醒自己面試一定要看好限制，不清楚要問問題。最後一種是自己才智不夠，就是沒有那種解題「啊哈！」的那種靈感，那就要想靈感是怎麼來的，要靠什麼觀察來觸發它。
舉一些例子，最常見的我叫它 「互補觀察」：如果題目要找集合A，然而比較好算的集合B與集合A互補，或知道集合B可以輕易推算集合A，那不妨先算集合B再求答案的集合A。譬如題目求圖形的海洋面積，但其實陸地面積更好算，那不如計算陸地面積，再總面積減掉陸地求海洋面積。或者題目求排列組合有幾種，那不仿先算不成立的排列組合有幾種。藉由這些互補的觀察，可能就會有這些「啊哈！」的發現。還有一種我稱它 「隱形限制」，就是題目沒講但要自己知道的限制。譬如英文字母只有26的字母，用三個迴圈求三個英文字母的排列組合只有26^3，不到兩萬的組合，但很多人看到三個迴圈就想到複雜度O(N^3)，而去避免使用它。
11月大約每天十題練習題
面試的過程中，依據網路上以及我自己的心得，也有一些重點要掌握比較容易拿高分：
- 一開始要先儘量問問題
把題目要問什麼搞清楚，請考官多給些例子，包括輸入變數的範圍，要不要考慮特別奇怪的輸入等，再依據自己的了解，給些例子，請考官檢查自己的了解有沒有錯誤。不要一開始就一股腦的解題，好的考官就算了，不好的就看你解半天卡關，才悠悠然的說，你題目搞錯了，請重新來過。
- 不停自言自語
要把腦袋中解題的想法講出來。如果都放在腦袋裡想，考官無法判斷你是在發呆還是在思考，沒有評分依據，只能給你低分。把想法講出來，考官也可以給你適當提示。我一開始會把最顯而易見的解法分享出來，這種解法通常效率是最差的，但講出來不花30秒鐘，先拿個基本分也好。但要注意的是，講完這種最笨的解法後，一定要在考官批評你解法差前，趕快補一句：我覺得還有更好、更有效率的解法。這時考官就會倒吸一口氣，發現原來你只是深藏不露，第一個解法只是鋪陳而已，吊吊胃口，現在才是主菜上桌。
- 從複雜度求演算法
這時如果你還不曉得最佳解是什麼，千萬不能跟考官瞎扯，要提供有邏輯性的思維。我的解題經驗是，從演算法的複雜度下手。如果最差解是O(N2)，那就試試看O(NlogN)，通常就是迴圈裡面再一個二分法搜尋(Binary Search)或使用二元堆積(Heap)搜尋。譬如這時就可以說，我看到這邊有一個未知變數，讓我試試看可不可以用二分法搜尋找到它。如果這是正確的方法，考官通常會興奮地引導你。不好的考官可能會默不吭聲，但你要放棄這個演算法時，通常還是會忍不住問你確定嗎，要不要再試試看。
當然大部分的時候並沒有O(NlogN)的解法，那就要朝O(N)的方向想。複雜度O(N)的演算法有很多，最簡單的就只需要運用到基本的資料結構，譬如字典(Hash map)、連結串列(Linked list)、樹(Tree)、佇列(queue)等。難一點的需要運用字典數(Trie)、堆疊(Stack)、雙指標(Two pointers)、滑動窗口(Sliding window)等比較進階的演算法與資料結構，這些類型的題目都可以在Leetcode網站上搜尋的到。如果題目很明顯的是圖形問題，譬如兩點最短路徑與花費等，那常見演算法就只有深度優先搜尋(Depth-First Search,DFS)與廣度優先搜尋(Breadth-First Search, BFS)。運氣不好的話就會出現很少見的拓樸排序(Topological Sort)。它其實也是圖形問題，藉由圖形的相關位置、位址深淺等方式來排序。還有使用到聯合尋找(Union Find)資料結構的題目，通常題目會牽扯到分類，譬如一群人要分組或一堆球要分類上色等。這些比較少見的題型如果面試前沒練習到，面試中實在不容易想出來。
- 考慮「動態規劃」演算法的可能性
如果上面的演算法都不行，也不像是圖形的問題，那只能倒抽一口氣，怪自己的運氣不好，出現了比較困難的演算法。我最怕的演算法有兩種，一種是比較不常出現，運用到賽局理論(Game Theory)的題目。這種題目通常會有兩個人要比賽，在兩方都不放水的情況下，判斷誰會贏。這種題目很像腦筋急轉彎，與其考程式，更像是在考數學。另外一種是面試常常出現的動態規劃(Dynamic programming，簡稱DP)。這種演算法通常學校不會教，工作上更是不會用到，但面試很喜歡考，因為大部分的人很難會想到用ＤＰ去解，想到也很難寫出來。要判斷是不是ＤＰ 的題目，就要觀察問題是不是能夠被切割。譬如，如果題目是問「長度為20的字串有幾種排列組合？」，那就把題目改成，「如果已知長度為19的字串有幾種排列，長度為20的字串有幾種排列組合？」。如果能夠推算得出來，那我們就可以進一步從已知長度為18的答案，推得長度為19的答案，再推算長度為20的答案，以此類推。最後我們只需要知道長度為1的字串有幾種排列組合，長度為20的字串的排列組合就可以推算出來了。所以，解決DP問題的關鍵是，觀察能不能把複雜的問題，化成比較簡單可以解的問題，再從簡單的問題得到的解答一步一步推回來。雖然講是很容易，但要化成數學式子，再用程式把它寫出來卻十分困難。
壓力大到睡不著覺在我人生中發生過幾次，分別是國中學測跟高中指考的前一晚，第一次當助教要帶普通物理的時候，剛開始上班不知道怎麼開始的失眠症，以及Google面試的前一晚。想到練習了一個月，結果因為失眠隔天表現不盡理想，更睡不著覺了。到面試當天，五題的面試題有一題簡單，兩題普通，兩題困難，困難的題目都是DP的問題，但因為我知道自己DP比較弱，所以考前有特別準備，雖然一開始有稍微卡了一下，但最後還是都有解出來。兩題普通的，一題是圖形問題，解法如之前所述就只有幾種。另一題是遞迴問題，是比較常見的題型。考完後就知道自己應該上了，如釋負重。
被通知錄取以後，就進入了選老闆的階段。Google人事會寄給我三個正在招人的小組，以及他們的聯絡方式，我一個個跟他們面談後，再跟Google人事說自己想要的組別。當然老闆也會決定要不要收，所以就是有一點像相親一樣，當兩廂情願後，就可以簽下合約了。最後我選了YouTube負責做整合測試(Integration testing)的小組，正式從硬體轉成軟體工程師。