# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS11ooE4Rh)」作業 2
# [竹間-Maggie](https://hackmd.io/@sysprog/HJmI6rpy6)
> video: [模擬面試影片(中+英)](https://www.youtube.com/watch?v=Il3nIsxQWTM&feature=youtu.be)
# 第二次作業-他評02
## interviewer
### 優點
- 流程清晰，且三題連貫
-
### 可改進的地方
- 建議以情境題帶入題目，也可以跟面試者討論題目進而引導出想要解決的問題
- 雙向溝通的占比比較少，建議多加一些互動
## interviewee
### 優點
- 一步一步地講解程式碼，可以讓面試官帶入思考面試者的想法
- REACTO都有涵蓋在裡面並且流程明確
### 可改進的地方
- 如果可以，建議討論時間複雜度與空間複雜度之間的比較與取捨，並與面試官溝通是要使用哪一種導向的演算法進行實作
- 建議在撰寫程式碼時減少中間沉默的時間，在這期間可以嘗試與面試官互動或者重複表達你的想法，讓注意力不容易散掉
- 建議在理解題目時多詢問題目變數的限制與範圍，這樣可以多將一些邊界條件納入思考
# [盲狗-Mango](https://hackmd.io/er8SqLuPTSqPz7Fa33PV6g?both)
> [模擬面試錄影(漢)](https://youtu.be/sqPCM6ESEZg)
> [模擬面試錄影(漢)](https://youtu.be/-ul6w3t3rgw)
> [模擬面試錄影(英)](https://www.youtube.com/watch?v=QEG4Gdv7aho)
# 第二次作業-他評01
## interviewer
### 優點
- 面試過程輕鬆不會太上對下
### 可改進的地方
- 可以將變數限制交給面試者來詢問，一方面看看他是否有在思考邊界條件，另一方便也可以促進溝通
- 面試者的答案都全肯定，建議面試官可以明知故問，給面試者解釋的機會，也可更加理解對面試者的想法
- 建議可以用實際例子來包裝問題
## interviewee
### 優點
- 懂得適時求助面試官給予引導
- 口齒清晰
### 可改進的地方
- 可以把程式碼放在REACTO中的最後一步，coding階段可以先思考最直觀且最暴力的解法，給面試官一個「我可以在短時間內優化」的印象
- repeat(R)階段與example(E)階段同時並行，建議先理解題目意圖再進行舉例
# [優嬉兔-UCII](https://hackmd.io/@sysprog/rJ7cZOpka)
> [影片(漢語)](https://youtu.be/q6-oFMhfYX0)
> [影片(英語)](https://youtu.be/qHEQXp0NO2U)
# 第二次作業-他評 02
## interviewer
### 優點
- 從面試者做過的相關經驗著手，而不是單純提問，可以引導面試者從有他經驗的問題開始了解想法
### 可改進的地方
- 建議影片上面試官與面試者還是要做一些區隔，例如上名子之類的
- 第一題Fib的部分可以在最後引導能不能再減少時間，進而提出建表的概念，因為fib數列是固定值，因此可以利用建表的方式讓數列只需做一次，之後查表即可，以此來減少時間成本，而不是每次都重新run一遍
## interviewee
### 優點
- 口齒清晰，且流程簡潔俐落
### 可改進的地方
- 建議example階段直接自行創造簡單的example與面試官進行確認，先行把範例做好不太符合現實
- 在撰寫程式碼時可以避免一段時間的沉默，可以一邊打程式碼一邊跟面試官分享自己的想法，目前都還停留在解說一段之後沉默直到一段打完在接下一段的狀況
- 在與面試官討論做過的經驗時可以包裝一下題目，從實務延伸到問題避免直接用演算法問題起頭，以免面試官產生「他只會刷提」的觀感
- REACTO中的test階段不太明顯，建議可以在撰寫完程式碼之後使用之前創造的example trace code 讓面試官了解整體的流程
# [靈魂程式手-Soul Coder](https://hackmd.io/pBfvjKMqTH6jKDGxmUtgwA?view)
> [mock interview (Chinese)](https://www.youtube.com/watch?v=hLgU4ySRzQQ)
> [mock interview (English)](https://www.youtube.com/watch?v=Rx4HqiT76FU)
# 第二次作業-他評 01
### 文檔建議
- 錯別字偏多 (「回圈」=>迴圈,「准備」=>準備)另外bigO()通常是n(N) 這邊打h(H)應該沒差但要注意
- 文案只是給觀看者看個大意，不用連失誤也一起打出來，心裡話也不用打，演算法部分可以把code省略掉，這樣比較精簡
- 建議先在這邊擬一個大綱再去拍影片
## interviewer
### 優點
- 未面試者準備文檔也有圖例很用心可以省略時間
### 可改進的地方
- 建議從實例來包裝問題，給文檔應該可以敘述的比臨時構思的還要好
- 建議適當的明知故問一下來溝通彼此的想法
## interviewee
### 優點
- code寫完有簡單帶過之前舉的例子做驗證
- 做錯了懂得及時修正並向面試官道歉
### 可改進的地方
- REACTO中的O(optimizition)階段需要加強建議一開始先向面試官展示暴力解或次優解，在optimizition階段再展示最優解，會給人一種「我可以在短時間內進步」的正向觀感
- coding部分相信很多地方都可以做優化，像Add Two Numbers的部分可以直接用其中一種的link list做加法即可，省下名為sum 的link list 的空間，Get Maximum in Generated Array部分如果是用C語言撰寫程式的話他的除法(/)就已經是整數型態了不用再外面包一層int type
- 在R(repeat))可以先詢問邊界條件向面試官展示我有考慮到邊界案例
# [瞧滷肉-GIOGIO](https://hackmd.io/@sysprog/ByfdoSp1T)
> [模擬面試影片1(漢)](https://www.youtube.com/watch?v=PnLzfA89Bu8)、[模擬面試影片(英)](https://www.youtube.com/watch?v=zdfKiC64hJs)、[模擬面試影片2(漢)](https://www.youtube.com/watch?v=SmPKBypc4vs)
# 第二次作業-他評 02
## interviewer
### 優點
- 直接畫圖給面試者看，好心的面試官
- 面試氛圍輕鬆，用畫的給人一種自由發揮的感覺
### 可改進的地方
- 可用實例來包裝問題，讓問題往實際層面延伸，測試面試者在面對實際情況時如何將其化為簡單的演算法問題
## interviewee
### 優點
- 口齒清晰，且流程簡潔俐落，可以編寫程式碼邊講解，帶領面試官了解其思考
- 即使REACTO的流程順序不太對但解說連貫不突兀所以無傷大雅
### 可改進的地方
- leetcode解題記錄不要露出來，因為面試一定不會想考你已經做過的題目，就算你做過也要假裝沒做過
# 總評
- 大部分的同學一開始都直接點名題目，應該要學會包裝題目
- 寫程式整體的流暢感包括速度落差蠻大的，我是屬於比較寫的慢的一邊應該要多加練習
- 可能是因為自言自語尷尬，大家包括我在內在交談時都會有許多不明的冗言贅字，應該要注意並加以省略
- 我是菜英文，對比其他同學的英文程度還是要多加努力
[39. Combination Sum](https://leetcode.com/problems/combination-sum/description/)
---
> 貢獻者:
> 太陽🌞:interviewer 章魚🐙:interviewee
🌞: 你好，從我手上這份簡歷，我感受到您對程式設計的熱情和專業，但在我們談及工作內容前，我想幫公司同仁先認識你在程式開發的想法和風格
🌞:假設本公司現在獲得一筆採購經費，現在我們想要下單購買不同的零件，每樣零件有不同的價格，你可以重複購買同一樣材料，但需要注意經費需要徹底花費，你能幫我列出所有購買可能嗎?
🐙:請問這題的經費範圍大概多少?
🌞:為了面試效率的問題我們先把所有數字同時除以十萬，所以本來面試的金額是十萬到四百萬變成了1到40
🐙:那零件的價格呢?
🌞:零件的價格是我們已知的，但他的範圍至少是2，當然他也不可能超過經費上限，所以我們只需要求出所有可能即可
🐙:那就是2到40囉
🌞:是的並且我們假設每個零件的價格都是不同的，且最多只有30種零件
🐙:那我把問題理解成我們有一筆經費k與一列零件價格表，我們只需要求出所有可以重複購買的可能就好了吧
🌞:你可以舉個例子說說看你的想法
🐙:那假設現在經費是7，零件有三種價格分別是2,3,6,7，那我們的購買可能是[2,2,3][7]
🐙:在假設經費變成8，零件同樣是2,3,6,7，那我們的購買可能就會變成[2,2,2,2][2,3,3][2,6]
🐙:我第一個想到的是用Recursion的方式來實做，我們可以迭代每個零件價格，接著再Recursion 經費-當下迭代的零件價格當成新的經費遞迴下去即可，但需要注意如果[2,3]已經是其中一種可能了，則[3,2]則視為同一種可能所以不應記錄，為了避免這種情況發生所以迭代過後的零件就不納入後續的零件選擇上
🌞:你可以嘗試用程式碼時做出來嗎?
🐙:當然可以
### 面試過程
#### ***方案一 : Recursion***
```python!
# Time: O(N^N)
# Space: O(N^2)
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
#如果經費小於最小的零件價格，買不起
if target<min(candidates):
return []
ans=[]
#迭代整個零件價格表
for i in range(len(candidates)):
#當經費等於零件價格時可以
if target==candidates[i]:
ans.append([candidates[i]])
tmp=self.combinationSum(candidates[i:],target-candidates[i])
for j in tmp:
ans.append([candidates[i]]+j)
return ans
```
🌞: 那這個演算法的時間複雜度為何?
🐙: 由於使用Recursion計算所以時間複雜度非常龐大，會到O(N^N) ，另外空間複雜度只需要用ans去記錄所以會是O(N^2)
🌞: 沒錯這個演算法的複雜度非常之大，當我們的數字越來越大時會非常耗時，那有沒有更好的演算法幫助降低計算呢?
🐙:那我會改用Dynamic programming的方式去實做他，對每一筆經費都做一次建表，這樣之後加入的只要對照經費表上面的資料再去做增加即可
🐙:所以我會用一個for迴圈去迭代所有經費的額度，我們只需要在裡面逐個檢查零件金額列表，將經費減掉零件金額之後去查找之前Dynamic programming表內的對應金額並加其加入即可，最後只要輸出最後一個項即可
#### ***方案二 : Dynamic programming***
```python!
# Time: O(M*N^2)
# Space: O(M*M)
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
dp=[[] for i in range(target+1)]
for i in candidates:
for j in range(i,target+1):
if j==i:
dp[j].append([i])
else:
for k in dp[j-i]:
dp[j].append(k+[i])
return dp[-1]
```
🌞: 你覺得這個演算法的優勢在於哪邊呢?
🐙:除了時間複雜度變為較優的O(M*N^2) 之外，雖然我們犧牲了一點空間複雜度就是從O(N^2) 變成O(M^2) ，這邊N代表零件種類的數量，M代表經費，因為零件金額的數字是固定的，所以N最多也頂多到經費額度本身而已，所以我們可以之道N<=M，所以O(N^2) 變成O(M^2) 成本市增加的，但因為我們已經建立經費Dynamic programming表了，所以之後只要零件金額列表不便，我們只須要查表即可，就逤之後需要增加經費額度，也之需要從Dynamic programming表往後建即可，不需要再重新算起，大大減少第一次做計算之後的所需時間
🌞:不錯的想法，那今天的面試就到這裡結束，有問題歡迎聯絡我們，那我會跟同仁討論之後再告知結果，謝謝你的參與
## 總體初步檢討
***交談過程***
* 整體節奏偏慢
* Coding完之後面試官除了問時間複雜度跟能不能再變快之外就不會問其他問題了
* REACTO 的Test部分講太長了
* 遞迴方法run程式碼篇幅太冗長應該加速，面試官有問題再細講就好了
* 交談一直吃螺絲，廢話也偏多
***程式過程***
* 變數命名還需要加強
* 程式打的還是太慢了
* 思路不夠清晰寫程式一直卡住
Sign in with Wallet
Connect another wallet