# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS11ooE4Rh)」作業 2

>貢獻者: 芋頭-Taro
> [video(漢)](https://youtu.be/XNtt8YAk_B8)

> 👨‍💻：interviewer
> 🦝：interviewee

## [14. Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/)

👨‍💻： 這個…芋頭先生齁，歡迎來到 **Macrohard** 的面試，我是瀏覽器部門的香菇，你可以先做個簡單的自我介紹一下，我先將 google doc的連結放在聊天室裡

🦝： 好的，我是芋頭(下略)

👨‍💻： 好的，芋頭，很高興認識你，那我這邊有個小問題想請教你齁，就是你有聽過 trie 嗎?

🦝： trie? 你是指 prefix tree 嗎?

👨‍💻： 沒錯，他常被用於網頁瀏覽器等功能，如你所知，我們公司的部分業務就是網路瀏覽器，所以我希望你撰寫一個小程式作為資料建檔的一部分，根據資料名稱，找出多個資料中，其名稱中最長的相同字首，以利後續處理

🦝： 所以我要處理多個輸入字串，並找出所有輸入字串的最長相同字首，並且回傳，像是輸入 app, apple, approach，要回傳 app 這樣對嗎

👨‍💻： 沒錯

🦝： 那我可以假設輸入的資料型態為 `vector<string>` 形式嗎? 還有回傳的資料型態用 `string` OK嗎

👨‍💻： 都可以

🦝： 那需要區分大小寫嗎? 畢竟如果是要用在搜尋引擎上，應該需要忽略大小寫

👨‍💻： 這是個不錯的問題，我覺得你說的有道理，的確該忽略大小寫的影響，你可以另外寫個預處理函式來將大小寫的差異消除

🦝： 那我的想法是利用 ASCII 判別大小寫，如果資料是 pass by reference 的話，將所有輸入轉換成小寫並存於新的 `vector<string>` 中，並傳入主要函式，將輸入的陣列利用 `std::sort` 依據字母做排序，這樣第一個和最後一個就會是相差最大的字串，這樣一來只要比較這兩個就好了，找到最長字首字串後回傳小寫的字串，這樣的時間複雜度會是 $O(m * n log n)$，這樣沒問題吧

👨‍💻： 看起來沒甚麼問題，那假設無法使用 `std::sort` 你還可以怎麼做呢，可以不用全部打出來沒關係，先用Pseudo Code就行

🦝： 如果無法使用 sort 的話嗎…，(OS:如果不能呼叫sort 這樣不就要手動自幹一個排序函式出來嗎，也太麻煩了吧，還是說有除了利用 sort 還好的方法，問問看吧)

🦝： 我想想喔，我想和你比對一下想法，可以告訴我你那邊會怎麼處理嗎?

👨‍💻： 我這邊不太會用 sort 去做這件事，就像我剛剛說的，我們公司的部分業務就是網路瀏覽器，求common prefix string 只是這個整體結構的一小部分，而其整體資料架構才是我們重視的

🦝： (OS: 阿幹對阿，prefix tree，他剛剛就講過了，我只要建立 prefix tree ，並且從 root 沿途確認子節點數量是否大於一，直到有子節點數量大於一，就可以求出 common prefix string 了阿)

🦝： 我理解你的意思了，謝謝你，我這邊的想法也差不多，就是先建立 prefix tree，建立完後再從 root 尋訪子節點，確認子節點的數量是否為一，直到找出子節點大於一的節點，就可求出 common prefix string。因為 insert 所有字串的時間複雜度為 $O(n*m)$，這樣比起 sort 所花費的$O(m * n log n)$ 還要來的快，同時還可以建立 prefix tree 以利後續做使用

👨‍💻： 很好，我蠻喜歡這個方法的，你可以把它寫出來嗎

🦝： 沒問題

👨‍💻：不用全部寫出來，這個架構看起來沒問題，這樣就可以了，時間也剩不多了，你表現得不錯，剩下的一點時間你有想要問甚麼嗎?

🦝： 就是你可以告訴我，你認為這個部門最好與最壞的部分嗎?

👨‍💻： 這個嘛，先講壞的好了，就是我們常常會收到急件，會要去做一些 hotfix，然後時間會很趕，就會有一段時間特別忙，好處就是上層不太會去干涉專案，我們算是有著專案的很大一部分主導權。還有甚麼想問的嗎?

🦝： 沒有了，謝謝

👨‍💻： 那今天的面試就到這邊，期望未來能和你共事，掰掰。

## 筆記(給自己看的)
### 面試官要點
* 面試官不要使用上對下的用詞，因為不確定對方上來的職位與自己的關係，有些企業會讓工程師面試他的主管
* 不要一開始透漏題目，這樣而外加題或是覺得對方步行要提早結束面試都方便
* 時間控管

### 面試者要點
* 關鍵提問
* 「我是否可以假設…」
* 對於商業目標的定義
* 期望結果的形式
* 資料缺失、或者雜訊
* 資料表之間的 JOIN 方式（Primary Key & Foreign Key）
* 極端情況
* 利用 Pseudo Code 與口頭描述提升溝通效率
* 先講解在打程式碼
* 滑鼠不要亂晃
* REACTO
* Repeat: 重複提問，確認自己理解原本的要求
* Examples: 針對題目條件，舉出符合的案例，不限於特例
* Approach: 說明自己打算採用的方案
* Code: 撰寫程式
* Test: 若不能實際測試，那說明驗證程式的方案
* 在寫出程式後，需要主動提出你寫的程式有哪些優劣勢、可以怎麼改進
* 用 Unit Test 說明程式可行性，以及因為面試時間太短沒有解完的是哪些 Edge Cases
* 說明此程式碼所做的權衡（Trade-off）：空間 v.s. 時間、可讀性 v.s. 效能、等等
* 提出 Coding Style 改進方向，例如哪裡值得 重構（Refactor）

### 企業面試概念
* 重點在溝通，而非閉嘴寫程式，企業寧願收會溝通程式70分的，也不要程式90但不溝通不知道她在幹嘛的
* 面試是種表演，要與面試官交流，相互面試
* Google recuirter 提供的準備文件會建議第一題花 10 - 15 分鐘，其中五分鐘確認題意，五分鐘思考並表達解法，最後五分鐘實作與測試；第二題花 20 - 25 分鐘，五分鐘確認題意，十分鐘想解法與表達，最後十分鐘實作與測試。其理由是第一題通常比較簡單而第二題會比較困難
* 一般自我介紹是拿來給面試者暖身用的，一般不太會太認真聽，時長大概一分鐘
* 自我介紹要準備 1 / 3 / 5 分鐘的版本

### 反問問題
在反問問題這個階段同樣不計入評比，但可以透過機會多多了解公司甚至是部門或這個職缺，或者單純閒聊人生。我比較喜歡問的問題有:

* What is your favorite part working here?
* What is the team culture like?
* What makes a successful PE / SRE / SWE?
* What do you think are the most important qualities for someone to be really successful in this position?
* What are the common career paths in this department?
* What are the biggest challenges the company / team is facing right now?
* Can you tell one of the best part and one of the worst part of your company or team?
* What do you learned most in your position?
* What is your daily work flow? / What is the tipical days looks like?
* 是否可以從頭到尾參與 Project，亦或 Project 容易受客戶影響而終結

## 第四次作業-他人評論-01
- Interviewer：
- 優點：
- 題目改寫成實際需求
- 缺點：
- 口齒比較不清晰
- Interviewee：
- 優點：
- [1:15](https://youtu.be/XNtt8YAk_B8?t=75) 明確給出資料儲存格式，並且詢問特殊案例
- [5:57](https://youtu.be/XNtt8YAk_B8?t=357) 先用註解寫出程式操作並且給出時間複雜度很棒
- 缺點：
- [2:05](https://youtu.be/XNtt8YAk_B8?t=125) lowwer 拼寫錯誤應該為 lower