之前在台灣面試時一直都沒怎麼遇過需要 coding interview，而且我也一直對於在別人面前寫程式感到害羞，還以為自己可以就這樣逃過 coding interview 的關卡。
殊不知在英國面試時就常常遇到 coding interview，雖然有時候會是 online test, assignment，但果要進比較大的公司，coding interview 幾乎是必備。
還記得我第一次 coding interview 時，面試開始時我想說我會寫我會寫欸然後我就直接寫完了，還以為自己表現不錯題目有解出來 : )
結果得到 feedback 是 "感覺面試者沒有想跟面試官溝通"。
起先覺得困惑，後來才知道原來 coding interview 不是只是解題就好，部分也是因為我自己這部份沒做好資料查詢。
所以痛定思定後，上網詳盡搜尋了相關資訊包括如何準備、面試時需要從哪些方面下手，並運用範例寫下 coding interview 過程，同時也請 MANGA 經過面試官訓練的朋友幫忙檢查內容。
我試圖把 coding interview 的流程寫成可以以較有結構式的方式執行；這篇會分為平時練習時、面試前和面試過程中去解釋。
一、平常練習時
1. 解題順序 & 技巧
⇒ 理解 & 釐清問題
平時練習時就可以假裝自己在面試，先看題目後改用自己話再敘述一次，並想像你會問面試官哪些問題去釐清題目，這時再去看 examples 和 constraints，訓練自己看懂題目的速度和正確性。
⇒ 列舉
試著想一些實例幫助你思考，也可以用來做之後的驗證。
有時候題目舉例太複雜，可以先用簡單的例子去推想和分析題目，再改用複雜的例子去補足沒想到的部份。
⇒ 想解法 (Pseudocode)
敘述出自己的思路，可以的話多舉幾種方法，並寫下 pseudocode；重要的是要表現出你如何拆解問題，比如像可以用到 recursion 的題目，是如何把大題目拆解成一個個小題目進而解決原本複雜的問題。
有時候很難一下就想到最佳解，又想要寫出 bug free 的程式，又想要兼顧 time and space complexity，這時候不如先寫出你覺得現行可用的解法，再去進行優化。
有時候用腦袋想的沒有畫圖來得清楚，像是 linked list 用畫圖的方式就可以相當有效的幫助理解。
⇒ 實作
在要實際寫程式前先說明自己目前要做什麼事，就你想到會有哪些情況，再繼續寫下去，寫完後也可以說明這些程式分別對應到剛剛提出得哪些情況。
在平時就要注意有意義的變數名稱、換行縮排等等。
⇒ 測試案例
寫完後可以用剛剛列舉時舉出的實例來驗證、使用一些特例或是極端一點的實例，描述這個測試案例按照程式跑結果會是什麼。
跑測試很容易犯錯的是，自己覺得寫得對就跳過行數，沒有真正一行行跑，但在面試容易緊張時，有時候就可能犯一些小錯誤，況且一行行跑可以幫助自己找到程式中得 bug。
⇒ 優化
說明這個算法的 time and space complexity，並想想還可以怎麼優化你的程式。
⇒ 看其他人怎麼解題的並學習
可以點 discuss 看其他人的解法和自己的解法有什麼不同，檢討很重要! 也許可以自行解出來，但是有可能時間或空間複雜度很高，或是還有更好的解法、寫好你沒想到，這時候是很棒的時機跟其他人學習，然後再利用在下次解題上。
如果沒有你熟悉的語言解題，看其它語言也是可行的，在這方面演算法結構不會差太多。
2. 解題時盡量不要使用 auto-completion 和 syntax highlight
有些公司的測試是不提供使用者使用 IDE 或 Editor 的，可能會用比如說 Coderpad、Google documents 等，所以平常就要練習自己能直接寫出程式；剛開始用習慣的 auto-completion 會覺得有點辛苦，但也是練久就會習慣了。
當然也有公司是要你使用自己電腦，架設好環境和自己習慣使用的 IDE coding interview。
3. 解題時間安排
解題時可設定如卡住半小時，則可以考慮參考解答，不需要糾結在非自己解出來不可，有時候是卡住時就是需要提醒，況且花個幾小時卡住在同一個題目效益不大，除非你只是寫興趣而不是為了求職用的。
若半小時可解一題，接下來就嘗試讓自己半小時可以解兩題，以此類推。
面試解題會有時間限制，尤其是在高壓下更有可能因為緊張而腦袋短路；所以平時就要限制時間解題，有助於減少在面試時思路卡住。
4. 刷題在精不在多
LeetCode 的題目至少有上千，拼一拼也是有機會全部刷完，但與其刷多題都但不懂其意，還不如好好刷個 100 題徹底了解資料結構和演算法，有效的最大化解每一提的效益，讓自己之後遇到各種變形題都能迎刃而解。
如果是新手建議從 easy 開始刷，一下就刷 medium 以上的可能會覺得很挫折，循序漸進可以讓自己更有信心去解題。
5. 複習題目
當寫完一個題目之後可以過一天、一週之後再回來看同一個題目，除了看自己有沒有辦法再解出來外，也可以再想想還有沒有別的解法，或是試著解類似題。
6. 練習打字速度
解題速度很重要，但打字速度也很重要。面試的時間說長不長說短不短，如果你已經有構思卻卡在打字速度是件很可惜的事情。
7. 找人幫忙 Mock interview
自己練習和實際上場時又會有差異，所以最好的辦法就是找人練習面試，Facebook 上有很多程式相關社團可以在上面徵人互相 Mock interview，如果可以找到自己想應徵的公司的工程師幫忙面試最好，如果可以的話多找不同人練習，除了可以訓練自己聽不同口音外，也可以讓自己能快速的適應不同人的面試思考方式。
二、面試前
2.1 設備準備
確認所有你所需的設備都可正常運作且有備援，網路穩定環境安靜。比如無線耳機、滑鼠、鍵盤是不是電源都足夠，如果突然電量不足有沒有替代方案。
2.2 心態準備
看到沒看過的題目不要驚慌，相信自己根據過往的練習和經驗可以推理的出來解法。面試過程中就算解不出來、講得不順都盡量堅持下去，不管怎樣都想辦法可以在這次面試中學到東西
三、面試時流程
1. Clarify (0 ~ 10 mins)
1.1 Understand the question
不要聽完 / 看完題目就直接開始解題，除了技術能力，溝通和合作能力也很重要，如果沒有跟面試官討論就開始解題，會讓人覺得你會不會其實沒有思考清楚? 就算你思考清楚，這樣是不是以後都會自己單幹，不跟未來同事合作?
再來如果對於題目理解不清，整個解題方向可能都會有問題。所以當面試官提出題目後，首先你可以先用自己的話描述，以你的理解題目是這樣對嗎?
Interviewer: Given a string s, find the first non-repeating character in it and return its index.
Candidate: Okay, so according to my understanding, if there is a string "Egg”, the unique character in it is "E”, so the return value will be "0”?
Interviewer: Yes, exactly.
1.2 Ask clarifying questions
確定對於題目理解無誤後，開始問幫助釐清題目的問題，比如詢問
- 數據範圍限制 (constraints) 是什麼?
- 能不能給個範例?
- 如果輸入值是這個，那輸出值會是什麼?
- 能不能舉一個邊界範例 (edge cases) 說明這個 output 會是什麼?
- ...
這時候詢問時可以在白板上打下相對應的 input, output, constraints 等，除了幫助說明避免歧異，也讓自己有筆記可以看幫助思考，也可以避免之後面試官忘記自己講過什麼。
如果在思考時，可以跟面試官說你正在想比如 "I'm just thinking about what else could be relevant to know...”，盡量避免直接沉默不講話。
Candidate: May I ask some questions to clarify this interview question?
Interviewer: No problem, go ahead.
Candidate: If there are two alphabets, both appear once, and what we are looking for is the first one character, right?
Interviewer: Yes, we only want to get the index of the first unique alphabet.
Candidate: What if all the alphabets in string are duplicate?
Interviewer: If the unique character doesn't exist, then return -1.
Candidate: Great, thank you. I'm thinking, are there any other relevant questions I would like to ask?
Interviewer: No worries, take your time.
Candidate: How about the edge cases, what if the input is 0, null or empty?
Interviewer: The constraints of the string length is greater than one.
1.3 Specify assumptions
告訴面試官你的假設是什麼，比如說 input format, range 等等，主要是消除歧異點，避免比如說 input string 可能帶有空白或是大小寫敏感。
Candidate: Can I assume that there will be no whitespace?
Interviewer: Yes, you can make that assumption.
Candidate: Can we assume that there is no case sensitivity?
Interviewer: Yes, It can be case insensitive.
2. Plan (10 ~ 20 mins)
2.1 Find a solution
提出說你覺得有什麼解法，然後你覺得哪個比較適合。和面試官確認思路是否合理是很重要的，一個是在解釋過程中，思路會變得更清晰；再來就是如果思考方向有問題，面試官也可以及時提示你問題所在。Coding interview 不只是測試技術能力、也是測試解決問題的能力還有如何和團隊合作的能力。
Candidate: Okay, so I can think about two ways to solve this question.
The first one is using indexOf and lastIndexOf to find the index of the alphabet, if the return value of these two are equal which means this alphabet is unique, then return the index. But the time complexity will be O(n) for using the for loop to go through the string, and using indexOf and lastIndexOf will make time complexity as O(n^2).
for (let i = 0; i < s.length; i++) {
if (s.indexOf(s[i]) === s.lastIndexOf(s[i])) {
return i;
}
}
return -1;
The second one is a hash map to store every key and value, the alphabet can be the key, and how many times the specific alphabet shows up can be the value. The time complexity for creating the hash map will be O(n), but once we build it, then every time we look up it will be O(1).
Considering the time and space complexity I will use hash map to implement it, does it make sense to you?
Interviewer: The hashmap solution sounds good to me, please go ahead to code it.
2.2 Explain your solution
把面試官當作你合作的同事，一邊寫 pseudocode 一邊講解每一步，詢問說這樣的假設和想法是否合理，除了讓面試官更清楚你的思路外，之後實際實作時也有筆記可以看，更可以把複雜的問題拆成一個個小 tasks。
Candidate:
- Create a hash map, use the alphabet as the key, and counts of key as value
- Return the index of key if value is 1
- Return -1 if it doesn't exist
3. Implement (20 ~ 35 mins)
3.1 Write the code
說明你解題時會使用的語言，寫的過程和面試官保持交流，告訴面試官你在實現什麼功能，不用試圖第一次就可以寫出最佳解，先嘗試可以解出題目就好，並跟面試官澄清這還不是最佳解，再繼續接著優化。
如果對於某些解題相關的知識不是很確定時，不用假裝你全部都知道，可以比如說 "I'm not sure, but I believe that XYZ is the case.”
如果卡住可以尋求協助，面試官給予提醒或方向。不用害怕問問題，再厲害的工程師也會有卡住的時候，要適當的尋求協助；絕大部份面試官都不會想刻意為難你的，所以如果他們嘗試在導引你方向，抓住對方給予的提示。
Candidate: First, I use the split method to split the string then store the data to an array. Then I use a JS built-in method to create a map, then using a for loop to build a hash map, use the value as the key, and counts of the alphabet show up as the according value, and I give the initial value as 1.
let arr = s.split("");
let arrLength = arr.length;
let map = new Map();
for (let i = 0; i < arrLength; i++) {
map.set(arr[i], 1);
}
Through the loop processing, if the map has the same key, then add 1 to the value.
for (let i = 0; i < arrLength; i++) {
if (map.has(arr[i])) {
map.set(arr[i], map.get(arr[i]) + 1);
} else {
map.set(arr[i], 1);
}
}
After building the map, we are going to find the unique alphabet. Here I use the for loop to go through the map, if the value equals to 1, then return the index, otherwise return -1.
// Return the index of key if value is 1
for (let l = 0; l < arrLength; l++) {
if (map.get(arr[l]) === 1) {
return l;
}
}
// Return -1 if it doesn't exist
return -1;
};
Interviewer: All look reasonable, could you verify the implementation by running through some tests?
3.2 Test
測試一來是有助於自己找到 bug 並改正，一來是讓面試官知道你很重視測試。
可以先從基本的案例開始跑，舉例後用游標一邊告訴面試官現在跑到哪一行，寫下目前 input 是什麼 output 是什麼；接著開始測試比較複雜的案例；最後舉出 edge cases，比如 input 是數字，那就可能要測試當數字是負的、零和浮點數的時候。
如果在 debug 過程中發現有程式寫錯也不用驚慌或是洩氣，解釋為什麼會錯和你應該要如何改正，詢問面試官是否願意給你時間修正。
Candidate: The first test let me start with a simple one such as "eye”, then we will have a hash map likes {'e' => 2, 'y' => 1} after execution this code block. Then I use the for loop to look up the hash map, since the y is the only non-repeating value so the return value will be the index of y which is 0;
If the string is "cat”, then we will have a map likes {'c' => 1, 'a' => 1, "t” => 1}, although all the alphabets are only show once, but we only need the first non-repeating alphabet, so the return value will be the index of c which is 0.
If the string is "loveleetcode”, the map will be {'l' => 2, 'o' => 2,'v' => 1, 'e' => 4, 't' => 1, 'c' => 1, 'd' => 1}, the return value will be the index of v which is 2.
If the string is "aabb”, then we will have a map likes {'a' => 2, 'b' => 2}, none of these
alphabets are unique, so the return value will be -1.
Interviewer: Good good so could you describe the complexity of your solution?
4. Optimize (35 ~ 50 mins)
4.1 Trade-off For Time And Space Complexity
提出說你對於時間 v.s. 空間、可讀性 v.s. 效能的 trade-off，讓面試官知道你的思考過程和為什麼做出這個選擇，證明自己有分析程式的能力。
Candidate: About the time complexity, first I used the for loop building the hash map so is O(n), then I use the for loop to look up which alphabet is unique, here is O(1), I used two for loop here however it's not nested so the whole time complexity is O(n).
About the space complexity, I used one array to store the input data, so it's O(n).
Interviewer: Cool, it all makes sense.
4.2 Optimize (35 ~ 50 mins)
提出說你覺得程式有哪些地方可以優化、是不是還有更好的解法，如果面試官還願意提供你時間，把握機會優化你的程式。
如果沒寫完或沒寫出來也還是可以向面試官說明已經完成多少，還沒解的問題有哪些，如果你有時間你會怎麼做，經由這種方式讓面試官從別的方式知道你還是有能力能解決問題的。
(因為這題是簡單題，沒有太多可以優化的地方，故此處就不寫範例。)