# 2023年「資訊科技產業專案設計」作業2
## 第一次作業檢討整理
### interviewee
#### 優點
- 使用與公司業務或是開發相關的經驗去包裝題目
- 延伸問題的設計恰當
- 如 : 將 [122.Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/) 延伸到 [53.Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)
- 詢問 interviewee 改進方案,並針對改進方案點評
#### 可改進的地方
- 不要直接指出問題,應讓 interviewer 自己思考優化方案、適時引導
### interviewer
#### 優點
- 解釋通順且流暢,咬字清晰
- 遵循 REACTO 步驟,詳細發問、確實測試程式碼
- 在 Repeat 階段先確立題目限制、corner case 與數值範圍
- 在寫成之前先完成註記,再填上,幫自己建立程式架構也方便對方理解
#### 可改進的地方
- 畫面顯示上的問題,如 : 字體太小、游標擋住文字等
- 語助詞過多
- 爭取思考時間的時候,也許重複問題、說出自己的思路會比直接說「我想一下」更好
### 心得
觀看別人的面試過程並給出點評比想像中的更耗費心力和時間啊 ! 不過看到他人不足會警惕、他人的長處會成為自己改進的目標,也是獲益良多了 ! 期許自己在這堂課中的經歷會成為成長的養分 :evergreen_tree:
## 模擬面試練習 : [1282. Group the People Given the Group Size They Belong To](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/)
> 瑪奇朵 - Macchiato
🧔:interviewer
👶:interviewee
[模擬面試錄影(漢)](https://youtu.be/95Vv2ivXlPU)
### Repeat
🧔:你好,歡迎參與敝公司的面試。請問你對公司開發的產品有沒有初步的了解呢?
👶:你好,有的,我知道公司目前有參與各項應用程式的開發,包含購物網站、遊戲平台等。
🧔:沒錯,那麼假設我們今天想要在購物網站上加入一個購物車分類功能,考慮消費者欲購買的商品分別屬於幾件組合優惠,並自動將這些商品分類,以利於結帳金額計算。針對這個問題,你有甚麼想法?
👶:請問組合優惠是一定要剛好符合數量,還是只要超過就可以? 例如說5件商品打折是一定要剛好5件嗎?
🧔:一定要剛好滿足數量才有優惠。
### Example
👶:(舉例說明)
```
[1,3,2,2,3,3]
[[0], [2, 3], [1,4,5]]
```
👶:請問有沒有可能出現匹配不全的狀況呢?
🧔:我們假設一定可以完全匹配。
### Approach
👶:好,那我的想法是用 hash map 去實作這個問題。key是需求人數,value則是待分配的玩家編號組成的vector。當我們取得一個玩家的資料時,就將他的需求人數設為key,玩家編號放入對應vector中。當人數滿了之後,就將該需求人數的資料移除,直到所有人都配成功分配為止。
🧔:聽起來很合理,你可以開始實作看看。
### Coding
```c++
vector<vector<int>> GroupTheItems(vector<int>& GroupSizes){
// create hash map
unordered_map<int> umap;
vector<vector<int>> res;
// for loop
for(int i = 0; i< GroupSizes.size() ; i++){
int s = GroupSizes[i];
// add into hash map
umap[s].push_back(i);
// the group is full : delete
if(umap[s].size() == s){
res.push_back(umap[s]);
umap[s].erase();
}
// return result
return res;
}
```
### Testing
👶:那我拿前面的舉例來測試程式是否能正確運行。
```
[1,2,3,3,2,3]
i = 0, umap = {1:[0]}, res = [[0]], umap = {}
i = 1, umap = {2:[1]}, res = [[0]]
i = 2, umap = {2:[1], 3:[2]}, res = [[0]]
i = 3, umap = {2:[1], 3:[2,3]}, res = [[0]]
i = 4, umap = {2:[1,4], 3:[2,3]}, res = [[0], [1, 4]], umap = {3:[2,3]}
i = 5, umap = {3:[2,3,5]}, res = [[0], [1, 4], [2,3,5]], umap = {}
```
🧔:你能不能分析一下上述做法的時間複雜度與空間複雜度?
👶:時間複雜度是 O(n),因為umap的加入和查找都是O(1),然後會遍歷所有的商品 n 次。空間複雜度也是 O(n),因為我是針對每一筆商品資料去建立map和裡面的vector。
### Optimize
🧔:你為甚麼會使用unordered map去實作,他跟map的差別在哪裡?
👶:unordered map的底層的資料結構是hash map,是沒有順序性的,他在查找資料的時候只需要 O(1),而 map 的資料結構則是一顆紅黑樹,查找資料的時候需要 O(logn) 的複雜度,所以我這邊選用的是unordered map,去降低時間複雜度。
🧔:好,聽起來你對 c++ 的資料結構有一定的熟悉度,這樣的選擇的確可以減低時間複雜度。
### 延伸題目
🧔:那麼現在把這個問題做延伸,基於前面這個購物車分組的設計,將優惠規則改成:如果使用i件優惠,就不能使用 i-1 件與 i+1 件的優惠,想讓系統自動算出最多有幾件商品可以獲得優惠,你會怎麼做呢?
👶:請問如果有多組i件商品組合的話,他們是不會互相影響使用的嗎?
🧔:對,只有限制不能使用 i-1 與 i+1 的優惠組合。
👶:這題和前面題目的差別是 : 使用 i 件商品組合會影響 i-1 與 i+1 件優惠的使用,因此我想先使用排序的方式,再使用動態規劃建立 list 去存取,當我遇到第 i 件組合的時候,我究竟是要使用、還是不使用,會使最終優惠商品的數量為最大。
🧔:好,那礙於時間關係,我們今天的面試就先到這裡,很開心有機會跟你聊聊天,麻煩靜候我們的消息,感謝你。
👶:好的,謝謝。
---
## 自評 : 待改進的地方
### Interviewee
- 被原本題目限制,想不到可以怎麼變更與修改題目。延伸題目幾乎可以開下一個問題了。
- 討論結束的很突然,應該可以針對作法給出一些點評或是更多的引導思考。
### Interviewer
- 解釋到卡詞,會使一句話的語速忽快忽慢,不如整體放慢步調能讓人更專心聽。
- 解釋精簡到位即可,每次都會想要再補充說明反而使內容很冗長。
### 第四次作業他評01
* 整個面試蠻擬真的,有包含情境,題目也有經過包裝。
* [0:21](https://youtu.be/95Vv2ivXlPU?t=20) interviewer的題目指示很不清楚,像是輸入是什麼都是interviewee自己想出來的。以這題來說我覺得interviewer可以快速的舉個小例子幫助interviewee理解題目。
* [3:20](https://youtu.be/95Vv2ivXlPU?t=200) interviewee有快速用pseudo code(或註解)帶過程式的架構,感覺不錯,可以提醒自己,也讓面試官更好懂程式碼的意思,不過也是因為這題程式碼不長,才有時間這麼做。
* [12:48](https://youtu.be/95Vv2ivXlPU?t=767)這邊延伸問題的說明都是用未知數的表示方法(i件、i+1、i-1件)很不直覺,如果interviewer用實際數字的例子(例如使用3件組合的優惠就不能使用2件和4件的組合優惠),感覺聽起來更好懂。
[00:54](https://youtu.be/95Vv2ivXlPU?t=54)
### 第四次作業他評02
- [1:34](https://youtu.be/95Vv2ivXlPU?t=94) 這邊的匹配不全指的是? 搭配例子感覺會更好理解一些
- [12:12](https://youtu.be/95Vv2ivXlPU?t=732) 影片中說**只需要O(1)的複雜度**,但實際上可會到O(n),比較嚴謹的說法應為**平均O(1)**
- [c++: unordered_map](https://en.cppreference.com/w/cpp/container/unordered_map)
## 第四次作業他評03
### 待改進
### Interviewer
[00:17](https://youtu.be/95Vv2ivXlPU?t=17): 在進入題目討論之前我們可以先有個開場白,說好那我們接下來來討論購物車的分類功能
[00:24](https://youtu.be/95Vv2ivXlPU?t=24) :「考慮消費者購買的商品分別屬於幾件的優惠組合,並自動將這些商品分類以利於金額的計算」,這樣的說法感覺沒有真的解釋清楚題目要如何分類到購物車,以及所謂的幾件商品的組合優惠是什麼?光是從文字去了解都有困難,當場口語的去聽可能就需要更多的釐清。
### Interviwee
[00:54](https://youtu.be/95Vv2ivXlPU?t=54): 就我的理解? 覺得與其這樣說其實應該說確定跟面試官討論清楚而非自我的理解
[01:10](https://youtu.be/95Vv2ivXlPU?t=70): 講一下每一個groupsize本身的index就是商品的編號,不然接下來直接講他們為什麼可以分在同一組的時候會有點搞混
[01:32](https://youtu.be/95Vv2ivXlPU?t=92): 給出的case裡面?在這邊的case會混淆,前面一開始是先提到說一個[1,2,3,3,2,3],然後也說了[[0],[1,4],[2,3,5]],所以他的case是指什麼應該在說明清楚。
[02:11](https://youtu.be/95Vv2ivXlPU?t=131):把這個商品的資料丟進hashmap中,首先商品的資料是指index嗎?丟進hashmap中是依照怎樣的規則應講清楚,是丟到value的陣列裡面嗎?比較有效的方法就直接用前面的的example就好了。
[02:35](https://youtu.be/95Vv2ivXlPU?t=155): 可以直接開始實作了,不需說我要開始實作了
[02:43](https://youtu.be/95Vv2ivXlPU?t=163): 「雙層陣列」應該說二維陣列比較精準
[04:03](https://youtu.be/95Vv2ivXlPU?t=243) 「unordered」唸成感覺像unorded
[06:07](https://youtu.be/95Vv2ivXlPU?t=367): “GroupSize[i]” typo, GroupSizes[i]
[12:59](https://youtu.be/95Vv2ivXlPU?t=779) :「如果使用i間的商品優惠」, i-1, i+ 1, i是index嗎?指的是相鄰編號的商品不能放在同一個優惠組合包裡面嗎?後續才在解釋中明白是優惠組合所需的商品數量。同樣,舉個簡單例子就可以解決困惑。
[14:26](https://youtu.be/95Vv2ivXlPU?t=866): 這邊針對最後面試者給出的想法後直接以「好因為時間關係來結束面試」顯得唐突,因為如果是時間關係,其實延伸題本身應該就不會問了。
### 優點:
寫程式碼之前有提出大致想法的comment,便於理解思路。
語速適中