# 2023 年「資訊科技產業專案設計」作業 1
> 貢獻者：迪奧-Dio
> [video](https://www.youtube.com/watch?v=QWrjL0TQtRI)
> interviewer:🥵
> interviewee:😈

## [1337. The K Weakest Rows in a Matrix](https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/)
### 測驗說明與回答
> 影片：[0:00](https://www.youtube.com/watch?v=QWrjL0TQtRI)

🥵：同學你好，我是Jojo。今天就由我來代表公司的同仁和你簡單的聊聊天，對你有更深入的認識，不需要覺得有壓力，這沒什麼的，只是單純聊聊天來認識彼此。可以請同學先自我介紹一下嗎？謝謝。

😈：好的妳好～我是Dio，目前是國立成功大學資訊工程學系碩二的同學，預計明年會畢業。對於貴公司的職缺非常有興趣，因此前來應徵，希望未來可以在貴公司工作。

🥵：哦～原來你是成大的學生，我們也有一些公司同仁也是來自成大資工。這樣剛好大家互相有個照應。那既然是成大的同學，相信你程式的能力也是相當不錯。稍微問一些簡單的題目來更加了解你齁，不用覺得有壓力。

🥵：假設我們現在有一個 **`matrix`**，在這個 **`matrix`** 上面呢有 **`1`** 代表著士兵， **`0`** 代表著公民。每個士兵都會站在公民的前面，也就是 **`matrix`** 的最左邊。

🥵：在這樣的規則之下，**`matrix`** 有好幾個rows，每個row士兵的數目各不相同。今天我們想在這樣的規則中找到 **`k`** 個最弱的rows。

🥵：怎麼樣去比較rows的強弱呢？就是看每個row士兵的數目，士兵少的row便是較弱的row。如果士兵數目一樣的話，則較靠上的row視為比較弱的row。

😈：ok所以說你的意思是，如果我們現在有一些士兵和市民，士兵會站在市民的前面，而我們的目標是回傳k個最弱的rows。計算rows的強弱是看那個row的士兵總數，而如果士兵數目一樣的話，則比較上面row的位置，就是比較weak比較弱的row。沒問題，我現在就馬上開始實作給你看看。

😈：好的，我現在開始定義一個 **`function`** 叫做 **`kWeakestRow()`** ，他的input就是我們的 **`matrix`** 還有要回傳的`k`個rows。

😈：接著呢，我們要先定義一個 **`sum_list`** 去紀錄每個row的士兵數目，對於每個row我們去計算有幾個士兵數目，我們使用 **`enumerate`** 這個函式來同時紀錄現在是第幾個row，還有他士兵的數目。而我們把這個結果給紀錄在 **`sum_list`** 當中。

😈：接著，對於 **`sum_list`** ，我們把他排序一下取出最弱的rows，我們使用python內建的 **`sort`** 方式，而sort key就是 **`sum_list`** 的第0項，使用 **`lambda`** function指定一個x function對 **`sum_list`** 中的第0項進行sort，排完之後我們可以得到最弱到最強的row index順序。

😈：接著我們回傳前k項就是我們的k weakest rows。

def kWeskestRow(mat, k):
    sum_list = []
    for i, row in enumerate(mat):
        sum_list.append((sum(row), i))

    sum_list.sort(sum_list, key=lambda x: x[0])

    return [ret[1] for ret in sum_list[:k]]

🥵：非常好，你現在已經完成了一種方式來去解決k weakest rows的問題。恩......但是我在想，會不會其實有更好的做法可以讓他表現的更好。可以請你試試看嗎？

😈：我心中確實有些想法可以讓這個程式碼變得更加優化、效能更好。但是不知道你想要我嘗試的是哪種，不知道我們可不可以來進行一個比對看看嗎？就是你心中的想法是哪種？

🥵：歐我覺得你要不要嘗試看看使用heap這個方式？

😈：哦～heap我確實是有想到這個方式。那的確是可以提升我們的速度，那我馬上來使用heap來實作。

😈：對於heap的方式呢，其實和原本的程式碼相差不了多少，只需要改進一些地方。

😈：首先我們先 **`import`** 一個套件 **`heapq`** ，然後建立一個 **`heap`** 的空的list。

😈：接著把原本的 **`sum_list`** 改成 **`append`** 到 **`heap`** 當中來紀錄每個row的士兵。在這個步驟基本上都是一模一樣的。

😈：接下來，不一樣的地方是我們sort的方式改成使用heap的sort方式，也就是heapify來排出他的順序。

😈：排完之後，我們就得到一個sort好的 **`heap`** ，而最後我們回傳的就是 **`heapq`** 的前 **`nsmallest`** 項，也就是我們的前 **`k`** 項，來得到我們最後的正確答案。

import heapq

def kWeskestRow(mat, k):
    heap = []
    for i, row in enumerate(mat):
        heap.append((sum(row), i))

    heapq.heapify(heap)

    return [ret[1] for ret in heapq.nsmallest(k, heap)]

🥵：做得非常好，接下來我可能還會想在更加的了解你。再問你一些別的比較有趣的問題。

## [1. Two Sum](https://leetcode.com/problems/two-sum/)
### 測驗說明與回答
> 影片：[7:22](https://www.youtube.com/watch?v=QWrjL0TQtRI)

🥵：Now, let's move on to the second question.

🥵：Given an array of integers **`nums`** and an integer **`target`**, please return the *indices of two numbers that add up to **`target`***.

🥵：You can assume that each input will have *exactly one solution*, and you may not use the *same* element twice.

🥵：You can return the answer in any order.

😈：Oh, you mean, for example, if we have an array [1, 2, 3, 4, 5], and the target is 8, then I should return [2, 4] because they are the indices of 3 and 5, which, when added together, equal 8?

🥵：That's correct.

😈：There is a straightforward way to solve this problem - Brute force. We simply loop through the array and add the numbers together to find the correct pair. Here is the implementation:

😈：First of all, we define a fucntion called **`twoSum`**. The input of the function is numbers and the target. Then, we get the length of numbers called **`n`**.

😈：Please note that the first loop stops at n-1 because there is no second number on the right side of the last number to pair with. Additionally, the second for loop starts from i + 1, as we cannot pair a number with itself.

😈：if we find sum of the two numbers equals the target, we return the indices of this two numbers. Else, we return nothing.

def twoSum(nums, target):
    n = len(nums)
    for i in range(n - 1):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]

    return []

🥵：You've done a great job. However, could you optimize your solution? Brute force consumes a significant amount of time and space.

😈：Of course! By using a hash table, I can store the values that I have encountered before.

😈：The key point is to let **`pre = target - current`**, which represents the second number. Then check if **`pre`** is in the hash table or not. If it is, return the current number's index and the index of **`pre`**. If it's not, store **`pre`** in the hash table.

def twoSum(nums, target):
    table = {}
    for i in range(len(nums)):
        current = nums[i]
        pre = target - current
        if pre in table:
            return [table[pre], i]
        table[current] = i

🥵：Correct! Now, I see that your ability is excellent. I underestimated you. Let's move on to a slightly more challenging question. Don't worry; it won't be too difficult.

## [77. Combinations](https://leetcode.com/problems/combinations/)
### 測驗說明與回答
> 影片： [11:27](https://www.youtube.com/watch?v=QWrjL0TQtRI)
🥵：接著這題是簡單的排列組合問題。給予 **`n`** 和 **`k`** 兩個數字，回傳從 **`[1, n]`** 的 **`k`** 種排列方式。

也就是說，如果當 **`n = 4`**，**`k = 2`**，那output就是 **`[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]`** 嗎？

🥵：嗯哼

😈：照這個想法的話，最直接的方式可以使用暴力法解題

🥵：歐～有沒有暴力法以外的呀？

😈：嗯嗯當然有的。有蠻多方式可以解決這個排列問題，我腦中已經有許多想法，請讓我試著整理這些想法，來使用比較簡潔明瞭的方式。

🥵：好的～

😈：我認為可以使用backtracking的方式來解題

🥵：嘿！怎麼說呢？

😈：排列可以將其轉化為tree，以剛剛 **`n = 4, k = 2`** 舉例，樹大概長成這樣。我們每次會選取一個數字放入排列之中，如果排列的總數不到k的話就繼續放數字進去，反之就得到一種組合。當完成後排列後要移除數字然後再做新的組合。

🥵：說的不錯，可以請你寫code示範嗎？

😈：好的沒問題。首先我定義一個function叫做 **`combine`**，input為 **`n`** 和 **`k`**。接著定義最後的result，他是一個list。然後我們需要一個輔助function來檢查combination是否符合條件，條件就是他的長度達到 **`k`**。有的話把他加到答案之中。

😈：注意使用 **`copy`** 是因為我們目前還需要 **`comb`** 來取得更多的組合，因此如果直接把 **`comb`** 加進去list會發生錯誤。

😈：接下來，如果長度不到 **`k`**，那就把其餘的數字依序加到 **`comb`** 中，用一個for loop來實現，從我們的 **`start`** 開始，到 **`n+1`**，這樣才有包含 **`n`**。我們把 **`i`** 給 **`append`** 進去 **`comb`** 中，然後跑遞迴，最後再 **`pop`** 出去。

😈：這樣就完成我們的遞迴function。最後我們從 **`1`** 開始跑，然後 **`return res`**。

def combine(n, k):
    res = []

    def dfs(start, comb):
        if len(comb) == k:
            res.append(comb.copy())
        else:
            for i in range(start, n + 1):
                comb.append(i)
                dfs(i + 1, comb)
                comb.pop()

    dfs(1, [])
    return res

🥵：非常好，很明確的解說如何使用遞迴來完成。那如果不用遞迴呢？

😈：不用遞迴的話……可以使用一個 **`stack`** 來完成我們剛剛遞迴時所做的事情。首先定義回傳的 **`res`** 還有建立一個 **`stack`** ，其中先把第一個case給加入其中。使用一個while loop來迭代，每次從 **`stack`** 當中取出目前的組合來看是否有達到條件，有的話就加入到 **`res`** 當中。沒有的話，一樣跑for loop把剩下的數字給依序加入到 **`comb`** 中然後添加到 **`stack`** 中儲存。最後再 **`return res`** 即完成不用遞迴的方式。

def combine(n, k):
    res = []
    stack = [(1, [])]

    while stack:
        start, comb = stack.pop()
        if len(comb) == k:
            res.append(comb)

        for i in range(start, n + 1):
            stack.append((i + 1, comb + [i]))

    return res

🥵：很好，看來你對各種方式都相當熟悉，這次的談話到這邊就結束了，很高興認識你，Dio。

😈：我也是，很高興認識你，謝謝。

## 總體初步檢討
**針對interviewer的部分：**
- 第一題應該引導interviewee慢慢說出自己的想法，而不是立刻實作。
- 說明題目時配合舉例會讓人比較好理解內容。
- 第一題也許不要直接說使用heap，而是用提示的方式說有某種方式蠻好用的。讓interviewee自己想出來。
- 在interviewee提出自己的想法時，適時的質疑他的想法，讓他思考自己提出來的想法會更好。

**針對interviewee的部分：**
- 第一題應該先說明做的想法，而不是馬上說「我馬上實作。」如同第三題的對話模式就比較不錯。
- 第一題function的名稱寫錯，應該是kWeakestRow。
- 第一題row和「弱」唸起來很像，row可以改成說中文橫列或是「弱」改成說英文weak可以有效避免別人聽不懂、混淆。
- 注意避免口頭禪一直說「我們」和「呢」。
- 說明優化的方法時，應該具體的說他的優點，而不是只是說他效能更好。

---

## 第二次作業-他評 01

### 關於 interviewer
- [ ] 優點
* 有適度的用手勢以及肢體去做動作。
* 對話過程舒適不會給面試者很有壓力的感覺。

- [ ] 可改進的地方
* 提問可以改為情境題。
* [4:53](https://youtu.be/QWrjL0TQtRI?t=293): 這邊說的"更好的做法"有點抽象，可以改說想要時間或空間的優化，或是程式更精簡等等。
* [5:31](https://youtu.be/QWrjL0TQtRI?t=331): 避免直接講 "用heap的方式實作" 這種關鍵字，可以改為用別種方式引導interviewer來想出如何改善程式碼。

### 關於 interviewee
- [ ] 優點
* 打code時都有邊講解清楚。

- [ ] 可改進的地方
* 通常面試時不要用會有提示字元出來的編譯器打code比較好。
* 沒有做到Testing的流程
* [2:34](https://youtu.be/QWrjL0TQtRI?t=154): 沒有做到REACTO中Examples跟Approach的部分就開始打程式。
* [2:12](https://youtu.be/QWrjL0TQtRI?t=132): 發音的部分聽起來很容易混淆，像是"row"跟"弱"避免在同一句話裡面講出來，聽得有點吃力。

## 第二次作業-他評 02
### 關於 interviewer
- [ ] 優點
* 加入背景音樂，讓整體聽感十分輕鬆。

- [ ] 可改進的地方
* 讀音相近的詞可以用其他語言來代稱，避免聽者被混淆。

### 關於 interviewee
- [ ] 優點
* Coding 與表達能同時順暢進行。
- [ ] 可改進的地方
* [11:40](https://youtu.be/QWrjL0TQtRI?t=700)：在與 interviewer 討論時，舉例(Example)應該搭配**畫面**才能使人更好理解，雖然問題 [77](https://leetcode.com/problems/combinations/) 並不複雜所以還可以讓人很快進入狀況，要是遇到更複雜的問題可能會導致溝通的效率降低。

## 第二次作業-他評 03
### 關於 interviewer
- [ ] 優點
* 對於題目描述得很具體，舉例也相當清楚
* 提示的適當

- [ ] 可改進的地方
* 手勢對我而言有點過多，反而像是沒準備

### 關於 interviewee
- [ ] 優點
* 回答有自信，對於interviewer要求也能及時理解

- [ ] 可改進的地方
* 少了舉例以及驗證的部分

## 第二次作業-他評 04
### Both
- [ ] 優點
* 影片開場白, Ending四平八穩.
* 語速雖不快, 但聽得很清楚, 英文發音也容易識別.

- [ ] 可改進的地方
* REACTO階段的 R, E, A可以搭配圖片介紹.

- [ ] Miscellaneous
* 帶著塑膠袋錄影會不會很悶呢?

## 第二次作業 - 他評 05
### Interviewer
- [ ] 優點
* 英文講得很好

- [ ] 可改進部分
* 背景音樂會干擾聲音

### Interviewee
- [ ] 優點
* 英文講得很好
* 第三題跟面試官討論的部分很好

- [ ] 可改進部分
* repeat 問題的時候可以把問題打出來
* 可以增加 REACTO 階段的 Testing