2023年「資訊科技產業專案設計」作業2

第一次作業檢討整理

interviewee

優點

• 使用與公司業務或是開發相關的經驗去包裝題目
• 延伸問題的設計恰當
  • 如 : 將 122.Best Time to Buy and Sell Stock II 延伸到 53.Maximum Subarray
• 詢問 interviewee 改進方案，並針對改進方案點評

可改進的地方

• 不要直接指出問題，應讓 interviewer 自己思考優化方案、適時引導

interviewer

優點

• 解釋通順且流暢，咬字清晰
• 遵循 REACTO 步驟，詳細發問、確實測試程式碼
  • 在 Repeat 階段先確立題目限制、corner case 與數值範圍
• 在寫成之前先完成註記，再填上，幫自己建立程式架構也方便對方理解

可改進的地方

• 畫面顯示上的問題，如 : 字體太小、游標擋住文字等
• 語助詞過多
• 爭取思考時間的時候，也許重複問題、說出自己的思路會比直接說「我想一下」更好

心得

觀看別人的面試過程並給出點評比想像中的更耗費心力和時間啊 ! 不過看到他人不足會警惕、他人的長處會成為自己改進的目標，也是獲益良多了 ! 期許自己在這堂課中的經歷會成為成長的養分

模擬面試練習 : 1282. Group the People Given the Group Size They Belong To

瑪奇朵 - Macchiato
🧔：interviewer
👶：interviewee

模擬面試錄影(漢)

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

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 interviewer的題目指示很不清楚，像是輸入是什麼都是interviewee自己想出來的。以這題來說我覺得interviewer可以快速的舉個小例子幫助interviewee理解題目。
• 3:20 interviewee有快速用pseudo code(或註解)帶過程式的架構，感覺不錯，可以提醒自己，也讓面試官更好懂程式碼的意思，不過也是因為這題程式碼不長，才有時間這麼做。
• 12:48這邊延伸問題的說明都是用未知數的表示方法(i件、i+1、i-1件)很不直覺，如果interviewer用實際數字的例子(例如使用3件組合的優惠就不能使用2件和4件的組合優惠)，感覺聽起來更好懂。

00:54

第四次作業他評02

• 1:34 這邊的匹配不全指的是? 搭配例子感覺會更好理解一些
• 12:12 影片中說只需要O(1)的複雜度，但實際上可會到O(n)，比較嚴謹的說法應為平均O(1)
  • c++: unordered_map

第四次作業他評03

待改進

Interviewer

00:17: 在進入題目討論之前我們可以先有個開場白，說好那我們接下來來討論購物車的分類功能
00:24 :「考慮消費者購買的商品分別屬於幾件的優惠組合，並自動將這些商品分類以利於金額的計算」，這樣的說法感覺沒有真的解釋清楚題目要如何分類到購物車，以及所謂的幾件商品的組合優惠是什麼？光是從文字去了解都有困難，當場口語的去聽可能就需要更多的釐清。

Interviwee

00:54: 就我的理解? 覺得與其這樣說其實應該說確定跟面試官討論清楚而非自我的理解

01:10: 講一下每一個groupsize本身的index就是商品的編號，不然接下來直接講他們為什麼可以分在同一組的時候會有點搞混

01:32: 給出的case裡面？在這邊的case會混淆，前面一開始是先提到說一個[1,2,3,3,2,3]，然後也說了[[0],[1,4],[2,3,5]]，所以他的case是指什麼應該在說明清楚。

02:11:把這個商品的資料丟進hashmap中，首先商品的資料是指index嗎？丟進hashmap中是依照怎樣的規則應講清楚，是丟到value的陣列裡面嗎？比較有效的方法就直接用前面的的example就好了。

02:35: 可以直接開始實作了，不需說我要開始實作了

02:43: 「雙層陣列」應該說二維陣列比較精準

04:03 「unordered」唸成感覺像unorded

06:07: “GroupSize[i]” typo, GroupSizes[i]

12:59 :「如果使用i間的商品優惠」， i-1, i+ 1, i是index嗎？指的是相鄰編號的商品不能放在同一個優惠組合包裡面嗎？後續才在解釋中明白是優惠組合所需的商品數量。同樣，舉個簡單例子就可以解決困惑。

14:26: 這邊針對最後面試者給出的想法後直接以「好因為時間關係來結束面試」顯得唐突，因為如果是時間關係，其實延伸題本身應該就不會問了。

優點：

寫程式碼之前有提出大致想法的comment，便於理解思路。
語速適中