# Info2023-homework2
# 模擬面試
貢獻者：迪奧 Dio
[video](https://youtu.be/ef43Yj8wvzk)

interviewer:🥵
interviewee:😈

🥵：我們是一家AI的新創公司，在我們研發部門目前有建立幾個模組需要測試他們的準確度，還有和其他模組搭配的成效如何。因此，我們希望同學可以幫我們排出這些模組的可能性。當我們給予`n`個模組，還有一組需要`k`個模組的時候。

😈：好的。所以您的意思是，當我們現在有`n`個模組，需要一次取出`k`個模組時，排出他們的可能性。

🥵：對。

😈：舉例來說當 n = 4，k = 2，這樣可排出這樣嗎？

[1, 2][1, 3][1, 4]
[2, 3][2, 4]
[3, 4]

🥵：對。就是這樣。

😈：好的。那如何有效排出這個算法，我覺得可以使用dfs深度優先演算法來解決這樣的問題。

🥵：為什麼是dfs，而不是bfs呢？可以請你解釋一下嗎？

😈：好的。我們可以把這個排列的問題想像成一棵樹狀結構。以這個 n = 4，k = 2來舉例的話，我們可以從樹的根節點往下有1、2、3的節點。

😈：我們先從1的節點往下可以走到2，然後發現 [1, 2] 的combination可以達到 k = 2 的條件。所以就回傳它，然後回去1這個節點再往下發現3這個節點。然後發現 [1, 3] 這個組合完成 k = 2 的條件。所以說又把3給pop掉，回到1。

😈：繼續延伸找到4，[1, 4]這個組合也同樣達到條件以後，再回去1這個節點。然後發現1下面的234已經走完了。所以從1再回去根節點來到2，依序走完[2, 3] [2, 4]。最後到[3, 4]。

😈：那他就是一個深度優先演算法。我們先走到最深後，再往回看有沒有其他路可以走。

😈：而bfs則是廣度優先演算法，那他則是有點像是波紋擴散。會把1同樣層級的234一起搜尋到後，在繼續擴散到他們的子節點。這樣就不符合我們搜尋的方式。

😈：所以說我們這個應該使用dfs的算法。而照我剛剛的講法，他其實蠻適合使用遞迴的方式來解決。

🥵：ok。那可以請你撰寫程式碼來實作你的想法嗎？

😈：好的我現在馬上使用python code來實作。首先，定義一個combination的function。那我把它取名叫做combine，他需要有n和k兩個參數。而我們需要一個回傳的list。所以我們把回傳的list給定義好了之後。

😈：接著我們來建立dfs function。根據我剛剛的說法，他需要一個⋯⋯我們需要依序把點加入到combination當中，然後根據combination和加入的點來判斷他現在是不是已經達成長度等於k的條件。

😈：如果是的話，就把comb加入res當中。要注意的是需要把它copy一份加入進去，而不是直接把combination加入進去。因為，在操作當中會重複使用comb，如果這時候冒然把還不是最終答案的comb加入進去的話，那很容易導致後續發生錯誤。

😈：接著，當comb長度未達k時，我們要持續把點加入combination當中，所以我們需要for回圈。從start point開始到n+1。

😈：為什麼是n+1呢？因為range 是取頭不取尾，所以使用n+1才可以把尾也考慮進去。而在for回圈當中，首先要做的事情是在comb當中去 append第i個點，也就是從start開始，到n+1加入到comb中。加完之後，使用dfs演算法來判斷是否這次加完之後長度就夠了。

😈：足夠的話，就把comb加入res當中，若不足的話，又會繼續加入下個點進來。當把一種組合都加完後，我們會把最後加入的給pop出去，讓他可以持續加入新的組合進來。

😈：完成dfs演算法之後，我們可以從1 start point開始，搭配空的res list開始。最後，就可以return res。

🥵：那可以請你舉例一下嗎？

😈：好那一樣使用 n = 4，k = 2 來舉例。當dfs一開始從1和空的傳入，因為發現comb長度不為k，所以會加入點i，也就是1。

😈：接著進入dfs，變成dfs(2, [1])。接著，因為又進入第二次dfs，且comb長度仍未達k，所以又進去for loop中，加入2的點成為comb: [1, 2] 然後到dfs算法當中dfs(3, [1, 2])。

😈：這時發現comb長度等於k，所以把comb給append到res當中。然後將最後的值pop出去，回到for loop加入3，然後依序執行dfs和pop。

😈：就會發現它持續把[1, 2][1, 3][1, 4][2, 3][2, 4]最後[3, 4]找到。這樣他就完成找到n = 4，k = 2的方式。

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

🥵：ok。你的演算法和舉例已經非常完善。但是，當使用遞迴方式時，如果今天要排列的數非常大，那就代表遞迴需要重複呼叫許多次。那可能電腦記憶體不足。所以有沒有其他的方式，不使用遞迴重複呼叫的方式來完成？

😈：恩，有的。如果不使用遞迴的方式時，我覺得可以使用stack來儲存遞迴時所需的東西。而程式碼大概可以是combine⋯⋯不好意思，口有點渴，喝口水。

😈：我的想法是說，可以使用stack來取代遞迴的方式。也就是持續把點和comb append到stack當中。美次去檢查start point和comb。如果長度夠的話，就把comb append 到 res list當中。其他時候就是持續加入到stack當中。差不多是這樣子的想法。

🥵：好，請你繼續實作。

😈：ok。同樣一開始需要result list儲存結果。因為使用stack所以定義一個stack。接著，當stack非空，每次我們會把start和comb從stack中pop出，讓我們可以去檢查長度是否足夠。

😈：若足夠則res.append(comb.copy())，其他時候就for i in range(start, n + 1)把comb append到 stack當中。這裡使用comb + [i]只是方便寫而已，當然也可以使用comb.append(i)。

😈：最後，return res。那我們可以直接在stack當中加入第一種組合，這樣就可以簡潔程式碼同時達成while stack非空的條件。

def combine(n, k):
	res = []
	stack = [(1, [])]
	
	while stack:
	start, comb = stack.pop()
	if len(comb) == k:
		res.append(comb.copy())

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

return res

🥵：ok，我理解你程式碼運作的原理及想法。這樣子的實作已經很完善。另外，我想問這兩種演算法，哪種時間複雜度比較好，哪種空間複雜度比較好呢？

😈：首先看到第一個演算法，因為他使用dfs他的時間複雜度是O(Cn取k)，空間複雜度因為使用到一個list操作comb因此是O(k)。

😈：而不使用遞迴的方式，他的空間複雜度一樣操作在comb所以是O(k)，時間複雜度則是O(Cn取k)。因為，每次都會把東西append到comb當，所以是取決在Cn取k的上面。

🥵：好哦。看來你知道這兩種演算法的時間、空間複雜度是一樣。只是差在是否遞迴，而使用stack的方式可以解決當數字很大時，遞迴可能造成記憶體不足的問題。

😈：是的。

🥵：這次的inerview就到這裡。謝謝你。

😈：謝謝。

總共評論五位：
1. [布撥 Pawmi](https://hackmd.io/@sysprog/S1ZLuL616)
2. [呆呆獸 Slowpoke](https://hackmd.io/@sysprog/Sy2E1d6yp)
3. [牙塑 Wind](https://hackmd.io/@sysprog/r1JYgOakp)
4. [瑪奇朵 Macchiato](https://hackmd.io/@sysprog/r1WoJGleT)
5. [奧黛麗 Audrey](https://hackmd.io/@sysprog/rJ5V1Ip16)

# 簡介對同儕評論
## [布撥 Pawmi](https://hackmd.io/@sysprog/S1ZLuL616)
- **優點**：聲音溫和好聽、第2, 3題interviewer和interviewee的互動性蠻好的，有來有往。
- **可改進的地方**：雜音很多、聲音可以更加強壯與抑揚頓挫來提升自信心和吸引人、邊打程式碼時應該邊解釋。

## [呆呆獸 Slowpoke](https://hackmd.io/@sysprog/Sy2E1d6yp)
- **優點**：說明自己的想法後再開始實作。
- **可改進的地方**：打字有異音很躁、聲音可以增加抑揚頓挫會更吸引人、邊打程式碼時應該同時解釋，不然打很慢、又很安靜。

## [牙塑 Wind](https://hackmd.io/@sysprog/r1JYgOakp)
- **優點**：說明python底層邏輯讓interviewer眼睛為之一亮，也明白你是有料的。此外，撰寫程式碼時邊說明用途，邏輯也非常清晰有條理。
- **可改進的地方**：當interviewee提出一些做法時，interviewer可以提出質疑使interviewee思考，並說明自己的看法。這樣interviewer可以更加理解interviewee是不是真的理解。

## [瑪奇朵 Macchiato](https://hackmd.io/@sysprog/r1WoJGleT)
- **優點**：詳細說明程式的演算法優缺點、打程式碼邊解說。
- **可改進的地方**：使用情境題來包裝leetcode原題、聲音有時候變很小聲。

## [奧黛麗 Audrey](https://hackmd.io/@sysprog/rJ5V1Ip16)
- **優點**：英文好聽、部分題目有用情境帶入。
- **可改進的地方**：interviewer可以引導interviewee做更多的延伸，以及適時質疑interviewee讓他思考。

# 我所學習到的點
## interviewer
- 避免直接使用leetcode原題。配合公司方向的情境題會更好。
- 適時地質疑interviewee來確認他是否真的理解亦或是背答案。
- 引導interviewee說明自己的看法。

## interviewee
- 先清楚說明自己的想法後再開始實作。
- 聲音要更有自信與抑揚頓挫，才更能展現個人自信心與魅力。
- 說明自己的做法有哪些優缺點。