---
# System prepended metadata

title: '佛萊迪 Freddy : info2023-homework2'

---

# 佛萊迪 Freddy : info2023-homework2
## 學員間檢討
* 檢討學員 : 
    * 失去倪 RBIN: [他評 - 02](https://hackmd.io/CLjwjs3xRDGz5B0qctDymw?both)
    * 蕭卡辰 James: [他評 - 02](https://hackmd.io/VgHxI04KRK-8hjUeQo-lzg?both)
    * 真蝦 shrimp: [他評 - 02](https://hackmd.io/U_wjs0I7Tgic6avc362YmA?both)
    * 沐揚仁 sheep: [他評 - 02](https://hackmd.io/QF6s3PDjR6akM1lO0rcASw?both)
    * 鋒美食 Tastii: [他評 - 01](https://hackmd.io/7_bOiFhNTVyUhQjOmiOG_Q?both)
* 檢討簡介 : 
    1. 是否有更精簡的寫法(我知道的)
    2. Interviewee 與 Interviewer 之間的互動
    3. Interviewee 敘述的邏輯與清晰度
    4. Interviewee 在解釋程式時，是否有哪些重點有特別提到 or 沒提出來
* 從中學習到什麼 : 
    1. 若 coding 時遇到需要寫副程式的時候(e.g., `GCD()` 或 `swap()`)，應先寫主程式，後續再補完副程式
    2. 自己邊寫程式邊說明時，要再多注意說的內容與語氣
    3. 遇到遞迴題目時，可以先將主要遞迴的部分提出來，後續再處理 Edge cases
* 課堂許願 : 
    * 每次面試結束後都會被問「還有什麼問題嗎?」，我總是不知道要從什麼角度去問(e.g., 薪水?加班?制度?)，希望老師可以些微提點一下 :smiley: 
---
# 第二次模擬面試練習
>[video](https://youtu.be/srL6Uy0-P6Q)
* 對話代表 : 
    * :nerd_face: : Interviewee
    * :bearded_person: : Interviewer
## [278. First Bad Version (漢)](https://leetcode.com/problems/first-bad-version/description/)
:::info
這題目情境是我上禮拜在面試時被問到的，因此找了 Leetcode 上類似的一題。
:::
### 測驗說明、問答與程式碼實作
* :bearded_person: : 哈囉 Freddy，我是Jack。那今天的面試交由我來主持，題目的部分已經放在共享的文件中了。
* :bearded_person: : 假設你在開發專案的時候需要時常使用 `git commit`，但有一天你發現最新 commit 是有著嚴重 Bug 的。由於每個 commit 都是基於前一個 commit 所開發的，因此代表第一次出現該 Bug 的 commit 可能會出現在你提交數個 commit 之中。
* :bearded_person: : 現在你提交過 `n` 次 `[1, 2, ..., n]` 的 commit，你需要找出第一次出現該 Bug 的 commit。過程中，你可以呼叫 `bool isBadCommit(commit: int)` 去判斷該 commit 是否有誤。
* :nerd_face: : (重複題目)(舉例)
    ```
    n = 5
    1 2 3 4 5
    F F T T T => return 3
    ```
* :nerd_face: : (描述解法)(開始 Coding)
    ```python
    def findBadCommit(n: int) -> int:
        for i in range(1, n + 1):
            if isBadCommit(i):
                return i
        return -1 # 皆為 correct
    ```
* :bearded_person: : 測試是否正確? 時間/空間複雜度為何?
* :nerd_face: : (驗證) Time complexity: $O(n)$、Space Complexity: $O(1)$
* :bearded_person: : 要如何改善這解法?
* :nerd_face: : 用 Binary Search
    ```python
    def findBadCommit(n: int) -> int:
        left = 1
        right = n
        while left <= right:
            mid = (left + right) // 2
            if not isBadCommit(mid): # correct
                left = mid + 1
            else: # wrong
                right = mid - 1
        return left
    ```
* :bearded_person: : 測試是否正確? 時間/空間複雜度為何?
* :nerd_face: : (驗證) Time complexity: $O(\log{n})$、Space complexity: $O(1)$
* :bearded_person: : 提醒 `mid` 計算上可能會有潛在問題
* :nerd_face: : 需要改成避免 Overflow 的寫法
    ```python
    # mid = (left + right) // 2
	mid = left + (right - left) // 2
    ```
* :bearded_person: : 現在不能使用 Array，改用 Linked List
* :nerd_face: : Time complexity : $O(n)$
    ```python
    class ListNode:
        def __init__(self, val = 0, next = None):
            self.val = val
            self.next = next
            
    def findBadCommit(head: ListNode):
        cnt = 1
        while head:
            if isBadVersion(head.val):
                return cnt
            head = head.next
            cnt += 1
    ```
* :bearded_person: : 感謝你的參與
### 初步自我檢討
#### Interviewee :nerd_face:
* 卡詞太多了，`那、這個、然後`等贅詞也過多
* 思考與敘述太過沒有脈絡，思考途中也容易腦袋當機
* 「版本」與「Commit」兩個詞容易使人混淆
* 每當在說明判斷 `isBadCommit` 時都會卡住
* 最後沒有提到 Linked List 解法的 Space Complexity
* 有時候講 `Binary` 這個字時會糊在一起
#### Interviewer :bearded_person:
* 一樣，`那、這個、然後`等贅詞太多
* 講解題目不順
* 提示 `mid` 那邊可能有點太明顯