之前有幸有被 Google / Facebook 的招募團隊看上，有過幾次 Phone / Coding interview （雖然結果都是沒錄取....）

但是不管是在事前準備，閱讀招募團隊提供的一些參考、準備資料，其實過程中也都對自己的寫 code 或是思考既能有一定的成長。

這裡就分享一下關於 Coding interview 中遇到最大的問題：解題，如何應對以及思考方向。

當然面試過程中可能還有一些技巧（與面試者的互動，溝通方式等），但是這篇主要是介紹跟實際解題有關的技巧與訓練。

通常在面試過程中，面試官都會拋出一個程式問題，然後讓你在時間內解決。

當然這類型的問題，在 LeetCode 之類的網站其實都很多了，但是撇除掉已知題型的那種直覺性解題。一來通常面試官都會針對那些常見題型做一些變形，或是好死不死就是遇到了從來沒見過的問題。

很多時候第一次聽到這種問題都會手忙腳亂。加上跟外國人面試已經夠緊張了，很多時候會腦袋一片空白。

所以 https://careercup.com 網站裡面有一本蠻有名的書 Cracking the Coding Interview

f:id:mouseface99:20191129180547j:plain

（台灣好像也有中譯版：提升程式設計師的面試力）

裡面有提供了一個很不錯的思考方向

注意！ 不是「解題」方法，而是「思考」方向

裡面提到了一個 7步驟的流程，讓你不管遇到什麼樣的問題都能夠透過這個流程，慢慢抽絲剝繭的解決問題

步驟

1. 確認問題（Listen）
2. 列舉 (Example)
3. 暴力破解 (Brute Force)
4. 優化 (Optimize)
5. 再次檢視 (Walk Through)
6. 實作 (Implement)
7. 測試/驗證 (Test)

1. 確認問題（Listen）

聽到問題後，首先先別急著動手寫 code（這是台灣工程師最常犯的習慣），先好好地聽完問題描述，以及所有可能的線索。然後從中確認是不是該有的條件/需求都已經拿到了。沒有的話要再詢問，或是跟面試官二次確認。

有時候面試官也會故意隱藏一些必要資訊，來考驗應試者是不是足夠細心

2. 列舉 (Example)

聽完問題後，第一步不是開始思考解法，而是先試著想一些實例，這些例子一來可以用做驗證解法，另一部分是可以透過在產生實例的時候可以幫助你思考

這些實例是不是有什麼共同點？
這些實例的量是否足夠代表性？還是只有侷限在某一個特定條件？

3. 暴力破解 (Brute Force)

正常人遇到稍微困難一點的問題，很難一開始就能夠想到一個很好的解法（除非這題目剛好是你做過的考古題，或是以前遇過很類似的問題）

所以一開始與其在那邊發呆想一步到位，其實還不如先快速想一個可以暴力破解的方式。通常在第二步列舉的時候，或多或少就已經有了暴力破解法的一些想法與方向。這時候就先把這些暴力解法整理一下，是否這個解法能夠解決之前列舉的問題。

這個步驟有幾個目的：

不要讓你的思考停擺，畢竟要想一個足夠完整的解法，還不如先找一個暴力解法，然後再慢慢優化
如果好死不死面試時間走完了，至少你會有一個能交差的 soluition（60分還是比0分強！）

4. 優化 (Optimize)

這一步就是關鍵了，如何把你的暴力破解法，優化成最終的解法！

這裡有幾個優化的思考方向：

檢視你手邊有的線索與資訊，你是否全都用上了？（通常面試官給你的資訊應該要全用上！）
試著先不要用程式邏輯思考，先動手用紙筆試圖針對幾組實例來解決，通常可以從中發掘出如何用 coding 的方式把手動解法程式化。
試著故意用「錯誤」的方式解決，然後檢視為什麼錯誤？哪裡錯了？哪部分修正後是不是可以變成正確解？
試著用最佳時間 vs 最佳空間的兩種方式來評估，是否哪種做法比較適合當前的問題（或是符合面試官給出的限制條件）

注意！ 剛剛提出的暴力解，跟現在優化後的優化解，都還只是邏輯，想法階段。頂多只有一些 Pseudocode level 的 approach / algorithm，還不要花太多時間寫正式的 code

5. 再次檢視 (Walk Through)

在實際動手前，再花一點點時間重新檢視這個優化後的解法，確定整體流程與邏輯是沒問題的（有時候在微調階段可能會把一些前後邏輯，或是不同模組間的溝通/資料交換格式打亂）

6. 實作 (Implement)

接下來才是正式開始寫 Code 了！

這時候的目的就是要寫出 Beautiful Code，這裡講的 Beautiful 可能不一定指的是排版上的「美觀」，而比較像是「完整」及「注意細節」

既然已經知道解法了，這時候在實作的時候除了把 Solition 的流程/結構建構出來之外，也可以花點時間去留意一些小細節，比方說：

是否某些地方會出現一些 null-pointer exception？
While-loop / 遞迴中的初始/終止條件是否完整？
是不是有考慮到一些 corner case 與一些極端的狀況？
是否用了適合的資料結構？

雖然這些細節對於單純解決問題來說可能影響不大，但很多有名的公司（Google / Facebook）在面試的時候，其實都會去看這些細節。因為他們不單純只是希望你具有解決問題的能力，而是在揣摩你未來工作時是否對一些小細節足夠細心

書中也提到一個優化的方向 BUD Optimization

Bottlenecks：程式中是否哪部分會造成效能/記憶體瓶頸？
Unnecessary Work：是否有哪些部分是多餘的，不必要的？
Duplicated Work：是否有哪些流程/功能可以被模組化，重複使用？

7. 測試/驗證 (Test)

最後就是交卷前檢查/驗證的步驟，可以從以下幾點下去驗證：

先用眼睛走過你的程式流程，有點像是在幫自己做 code review 一般，檢查流程是否完整
是否有可能會出現一些 null-pointer / 無窮迴圈 / 分母為0 的狀況？
用剛剛步驟 2 所產出的一些實例來驗證。有時間的話再根據目標問題的定義，產出更多實例
試著使用一些特例，或是極端一點的實例，確認目標有被正常處理或是有被適當的異常處理

當發現 Bug 在修復時，可以的話最好再修復完之後再跑一次驗證流程，確保不會發生 side-effect

實例

本來想在這裡列出一個具體例子，並且給出實際的解題過程與思考流程，但是後來發現這樣會讓這篇文章太長..... 所以後來決定另外寫一篇具體實踐的例子，之後再寫另外一篇然後會把連結貼過來～

最後心得

雖然這幾次 interview 最終都沒被錄取，但是在這幾次的準備過程中，其實自己也學到很多。

不管是在面對 coding interview 的流程，還是對外國面試官的應對技巧。

尤其是本篇所寫的思考方式，這個流程其實不只是在 coding interview，其實在工作上遇到的任何問題都可以透過這個流程，系統性的分解/解決問題。

比起傳統的遇到問題就馬上動手寫 code，然後在 QA 階段或甚至是產品上線後才遇一個問題解一個問題，然後解一個問題卻又爆出另一個問題....

MF99 coding 💻

keep learning; keep coding;

Code interview：Coding 面試與思考訓練

步驟