2023 年「資訊科技產業專案設計」學員作業講評

• 自七七人

• 14. Longest Common Prefix 在 LeetCode 分類是 Easy，但其實不簡單，因為後續變形很多，例如 trie (也叫做 prefix tree)，我們在網頁瀏覽器和程式碼編輯器常用的 autocomplete 功能，就可用到，其空間效率會是關鍵。

  Auto-complete feature using Trie

• 參見〈隱藏在字典裡的數學〉
• 01:55: 避免說 size of the array，因為 sizeof 在 C/C++ 是保留字 (但 Java 裡頭不是)，考慮到英文面試時說話較慢，因此儘量一開始就避免講會讓人誤會的詞，可改說 "the length of the given array"。
• 特定的單音節的字，常用弱化母音 schwa 來唸，例如 to, at, for, can, of 等虛詞 (function words)。注意 of 要唸 /əv/，不唸為 /oʊf/

  推薦「英語兔」和「ST English」頻道

• 02:19: 程式碼 sort 出現於解說之前，應該避免，因為後者才是主體，程式碼只是產出的一環。後續可思考，如果不能呼叫標準函式庫的 sort，該怎麼做？

• 施新豐

• 避免一開始說要安排 3 題，面試首要「互動」，倘若狀況不好，題目再多也無益，反之，當互動狀況好的時候，由一題出發，做很多延伸討論，甚至可圍繞在公司專案的開發上，那是更好
• LeetCode 編號 1 的題目 Two Sum，貌似簡單，作為 LeetCode 的開篇之題，乃是經典中的經典，正所謂「平生不識 Two Sum，刷盡 LeetCode 也枉然」，就像英語單詞書的第一個單詞總是 Abandon 一樣，很多沒有毅力堅持的人就只能記住這一個單詞，所以通常情況下單詞書就前幾頁有翻動的痕跡，後面都是嶄新如初，道理不需多講，雞湯不必多灌，明白的人自然明白。

  以上說法取自 Two Sum 兩數之和
  mint condition: "mint" 除了薄荷的意思，還可指鑄幣廠，"mint condition" 裡的 “mint” 就與鑄幣廠有關。有些人收集錢幣會在錢幣剛開始發行時收集，因爲這樣的錢幣看起來很新，他們會用 "mint condition" 來形容這種錢幣的狀況，強調「像剛從鑄幣廠出來」，後來衍伸出「有如新一樣的二手商品」的意涵。

• Two Sum 題意是給定一個陣列 nums 和一個目標值 target，求找到 nums 的 2 個元素相加會等於 target 的索引值。題目確保必為單一解，且回傳索引的順序沒差異。例如給定輸入 nums = [2, 7, 11, 15], target = 9，相加變成 9 的元素僅有 2 及 7，因此回傳這二個元素的索引值 [0, 1]

  結合 Linux 核心 hash table 的使用案例: 2022q1 第 1 週測驗題

• Two Sum 在 C/C++ 程式語言的撰寫上，若使用 hash table，則該向 interviewer 溝通，確立能否使用現有的實作 (如 C++ STL 的 std::unordered_map) 或假設該實作已存在，則聚焦在「如何使用」。
• 螢幕的字體尺寸很重要，錄製的當下可能看不出來，但從最終的影片就可發現實在不好識別，特別是線上面試時，interviewer 可能不會用全螢幕模式來參與
• 07:35: 避免說「我暫時的想法」，這句話冗贅，且顯得沒自信，可直接跳過，或說「我想這樣做」
• 07:55: 撰寫程式碼時，應當一邊解說
• 10:34: 在面試的場合中，可能沒有辦法當場執行撰寫的程式碼，檢驗程式碼的正確性時，可使用 REACTO 階段舉出的輸入案例。螢幕滑鼠的移動會干擾視線。
• 10:50: algorithm 的翻譯是「演算法」，而非「算法」，後者是「計算的方法」(the way to calculate)，但 algorithm 更在意「預先定義」的明確步驟。探討 integer overflow 是很好的議題，但該在 REACTO 的 Approach 階段提出，而非程式碼撰寫完才進行，當然，interviewer 若觀察到 interviewee 缺乏對 integer overflow 的處理，可在 REACTO 的 Test 之後提出討論。
• 11:52: 不用提 LeetCode 的測試案例，目前的情境是面試，測試案例其實是「討論」過程中產生的。這是面試，不是進行「例行報告」，著重在「討論」，而非「獨白」

• 新鮮柿

• 請詳閱第二次的作業規範，關於「經過HW1以及HW2他評後學習到了什麼?」應該寫在「新建立」的 HackMD 筆記中，不然怎麼隱匿自己的身份呢？
• 0:30: 針對 104. Maximum Depth of Binary Tree，開頭的 "I need to find the maximum depth" 很突兀，應該先描述應用場景 (最好跟公司專案有關)，然後才講需求。打開 YouTube 字幕，觀察自動辨識出的單字和口說的差異。
• 詢問 ChatGPT，得到 "maximum depth of binary tree" 的應用場景，interviewer 也可利用本題目，跟 interviwee 討論更多已知的應用場景。
  • Efficient Data Storage: In computer science, binary trees are commonly used to implement data structures like binary search trees (BST) or balanced binary trees (e.g., AVL or Red-Black trees). The maximum depth of such trees directly impacts their performance. A balanced tree with a lower maximum depth ensures that search, insertion, and deletion operations are more efficient, as the depth of the tree is a key factor in determining the time complexity of these operations.
  • Algorithms and Searching: Algorithms like binary search and various tree traversal algorithms rely on understanding the depth of a binary tree. For example, binary search in a balanced binary search tree is a highly efficient way to search for an element, with a time complexity of O(log N) for a tree with N nodes. The logarithmic nature of this time complexity is due to the balanced tree structure and its limited depth.
  • Database Indexing: In databases, B-trees and B+ trees are commonly used to index and manage large datasets. The maximum depth of these trees affects query performance. A shallower tree means faster access to data, which is crucial for efficient database operations.
  • Network Routing: In computer networks, binary trees can be used to represent routing tables. A shallow tree means quicker routing decisions, reducing latency in data transmission.
• 0:39: 對照看 YouTube 自動辨識的字幕，原本的 depth 被判定為 "death"。提問的 "Is root node included in depth calculation?" 可改為 "Is the root node counted in the maximum depth of a binary tree? 會更明確，而且這也是 REACTO 的 "Repeat" 階段。
• 0:54: 不用說 "I want to give the example to confirm whether my understanding is correct."，若真的在意禮貌，可改說 "To validate my understanding of the requirements, I would like to go through some examples. Please advise if I make any mistakes."
• 1:11: "like this binary tree" 聽起來很突兀，特別是前面你沒有發話，不易猜出到底是「像誰」。可改說 "Consider a binary tree constructed with 1 as the root node, to which we then add two children nodes, 2 and 3."。「口語化」很好
• 1:24: 作為 interviewer 不該急著說 "That's right. Do you have any idea for this question?"，這無助於溝通，可請對方準備其他案例，像是 skewed binary tree，注意，原本的題目沒有要求要平衡 (balanced)
• 1:31: 托腮講出 "I would like to use …" 好嬌貴啊，"DFS with recursion" 無法完整解釋你如何解決問題，寧可多用幾句話來描述。例如: "Based on the definition, to find the depth, we should determine the path length from the root to the deepest leaf node, which may be in either the left or right subtree. In other words, the longest path from the root to the deepest leaf can traverse either the left or right child of the root. Therefore, the best approach is to calculate the depth of the left and right subtrees recursively. We take the maximum depth from either subtree and add 1 to obtain the depth of the tree.
• 1:41: 注意手勢，看起來就像在耍帥 若有所思但又不針對隻字片語進行互動，就喪失討論的效果。
• 4:11: 既然強調遞迴，可先寫遞迴式，也就是畫面中的敘述，然後再補上 max 和 root == NULL 等敘述

• 奧黛麗

• 針對 169. Majority Element，這題目暗示可用投票法 (過半元素出現的次數比其他所有元素的次數之和還多，所以最後保留下來的候選元素必定是過半元素)，這只能用於確保陣列 majority element 一定超過陣列大小的一半，如果是要找出現次數最多的則不適合。

  布爾什維克（俄語: большевик）在俄語的意思是「多數派」

• 0:40: 這裡的 "Other questions?" 太突兀，應該先舉例說明，而且 "other" 暗示之前已有問題，但顯然在這場景不存在。
• 0:47: 當 interviewee 提問 "Is the array sorted?"，除了回覆 "No, it is not sorted."，可帶入實際場景來說明，例如 "You can think of the data distribution as an election, where some people vote for the majority candidate, and others don't. The array represents the original voting data."
• 3:58: 不該急著說 "It's a nice solution"，畢竟你沒說到底好在哪裡。