# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 2 > 夾克-jacket > interviewer : 🐱 > interviewee : 🐭 > [模擬面試錄影(漢)](https://youtu.be/lLUHwtwS-os) ## [2251. Number of Flowers in Full Bloom](https://leetcode.com/problems/number-of-flowers-in-full-bloom/) ### 面試過程 🐱: 旅遊公司有一系列旅遊行程，每個行程都有開始及結束時間，而旅遊公司也服務了許多遊客，每位遊客會選定一個時間出遊，你必許求出各遊客分別有多少旅遊行程可以選擇。 🐭(Repeat): 好，所以我現在有一堆旅遊行程及遊客，而我要幫這些遊客找出他們分別有多少旅遊行程可以去。 🐭(Example): 請問我的理解正確嗎? ``` travels: [1,3],[2,4],[3,5] people: [3,4] available scedule: [3,2] ``` 🐱: 沒錯，這正是我要的。 🐭(Approach): 那我最直覺得方法是，對於每位遊客去檢查每個旅遊行程他可不可以去，就可以求出沒位遊客可選擇的旅遊行程數量。 🐱: 好，那請你開始實作它 🐭(Code、Test): 時間複雜度會是 $O(nm)$ ```c vector<int> DetermineTravelScedule(vector<vector<int>> & travels, vector<int> &people) { int ans[poeple.size()]; memset(ans,0,sizeof(0)); int index = 0; for(auto &x : people) { // n for(int i = 0; i < travels.size(); ++i) { // m if(x >= travels[i][0] && x <= travels[i][1]) ++ans[index]; } ++index; } return ans; // [3,2] } ``` 🐱: 你有想到什麼方法去優化時間複雜度嗎? 🐭(Optimize、Approach): 若分別將旅遊行程的開始及結束時間排序好，我們可以透過二分搜來找出遊客出遊前，有多少行程已經開始和結束，將兩者相減就是可選擇的旅遊行程數量，時間複雜度為 $O(n \log{m})$ ``` travel start time: [1,2,3] // start => 3 travel end time: [3,4,5] // end => 1 People: [4] => 3 - 1 = 2 (available scedule) O(n * logm) ``` 🐱: 好，你可以開始時做了 🐭(Code、Test): 最後時間複雜度變為 $O(m \log{m} + n \log{m})$ ```c vector<int> DetermineTravelScedule(vecotr<vector<int>> &travel, vector<int> &people) { int ans[people.size()], start[travel.size()], end[travel.size()]; for(int i = 0; i < travel.size(); ++i) { start[i] = trave[i][0]; end[i] = tarvel[i][1]; } sort(start,start+sizeof(start)); // mlogm sort(end,end + sizeof(end)); for(int i = 0; i < people.size(); ++i) { // n int l = 0, r = travel.size() - 1, s ,e; // l = 0, r = 2 while(l < r) { logm int mid = (l + r) / 2; // mid = 1 if(start[mid] > people[i]) r = mid; // r > people[i] else l = mid + 1; // l <= people[i] l = 2 } s = r + (start[r] <= people[i]); // s = 2 + 1 = 3 l = 0, r = travel.size() - 1; // l = 0, r = 2 while(l < r) { logm int mid = (l+r) / 2; // mid = 0 if(end[mid] >= people[i]) r = mid; // end[r] >= people[i] // r = 1 else l = mid + 1; // end[l] < people[i] // l = 1 } e = l + (end[l] > people[i]); // e = 1 + 0 = 1 ans[i] = s - l; // 3 - 1 = 2 } // nlogm return ans; } ``` 🐱: 如果今天遊客出遊的時間是在一個範圍內，你該怎麼做呢? 🐭(Example): 請問是像這樣嗎? ``` travels: [1,3],[2,4],[3,5] people: [[3,4]] available scedule: [3] ``` 🐱: 沒錯! 🐭(Approach): 那變成要找出遊客最晚出遊時間前有多少行程已經開始以及遊客最早出遊時間前有多少行程已經結束。 ``` travel start time: [1,2,3] // start find less 4 => 3 travel end time: [3,4,5] // end find less 3 => 0 People: [3,4] => 3 - 0 = 3 (available scedule) ``` 🐱: 好，請你去實作它。 🐭(Code): ```c vector<int> DetermineTravelScedule(vecotr<vector<int>> &travel, vector<vector<int>> &people) { int ans[people.size()], start[travel.size()], end[travel.size()]; for(int i = 0; i < travel.size(); ++i) { start[i] = trave[i][0]; end[i] = tarvel[i][1]; } sort(start,start+sizeof(start)); // mlogm sort(end,end + sizeof(end)); for(int i = 0; i < people.size(); ++i) { // n int l = 0, r = travel.size() - 1, s ,e; // l = 0, r = 2 while(l < r) { logm int mid = (l + r) / 2; // mid = 1 if(start[mid] > people[i][1]) // people[i][1] = 4 r = mid; // r > people[i][1] else l = mid + 1; // l <= people[i][1] l = 2 } s = r + (start[r] <= people[i][1]); // s = 2 + 1 = 3 l = 0, r = travel.size() - 1; // l = 0, r = 2 while(l < r) { logm int mid = (l+r) / 2; // mid = 0 if(end[mid] >= people[i][0]) // people[i][0] = 3 r = mid; // end[r] >= people[i][0] // r = 0 else l = mid + 1; // end[l] < people[i][0] // l = 1 } e = l + (end[l] > people[i][0]); // e = 0 + 0 = 0 ans[i] = s - l; // 3 - 0 = 3 } // nlogm return ans; } ``` 🐱: 好，那今天的面試到此結束，感謝你的參加，掰掰 🐭: 謝謝，掰掰。 # 對同學的指教 ## 柯基-Corgi ### interviewer - [ ] 可改進的地方 * [8:05](https://youtu.be/hRWTy91fQ_c?si=xk-8gwPaEMBR4YHb&t=480) 可以嘗試要求 interviewee 分析 memory limit exceeded 的原因 ### interviewee - [ ] 優點 * 方法解說得很清楚並且有一步步的去優化 - [ ] 可改進的地方 * [4:50](https://youtu.be/eHdCI2ooSdM?t=290) 可以改成沒有分支的形式 `bulbs[j-1] = !bulbs[j-1];` * [14:48](https://youtu.be/hRWTy91fQ_c?si=Xv5zYZ-8tOj0RNVW&t=888) mod 念法 mäd ### 從中學到的 我覺得這位同學解說很淺顯易懂，且也會一直與面試人員互動。 ## 拉鍊-Zipper ### interviewer - [ ] 可改進的地方 * interviewer 可以在 interviewee 實作完程式碼後看看有沒有問題或可優化的地方 ### interviewee - [ ] 優點 * 問題條件問得很清楚 * 撰寫程式碼的同時也講解得很清楚 - [ ] 可改進的地方 * [0:44](https://youtu.be/MDoIdWNAIGs?si=fDZiZpX0xE8ssJp7&t=44) 口誤 Array 是陣列不是矩陣 * [15:35](https://youtu.be/MDoIdWNAIGs?si=3CEFVwhPbNr4z8z3&t=935) 沒有考慮到 first 超出陣列大小的非預期狀況 ### 從中學到的 這位同學開始前有向面試人員一一確認題目的條件，這是我自己沒有做到的。 ## 從其他同學中學到的 * 有些同學的肢體動作非常豐富，我也應該要在解釋方法時多加些機體動作 * 可以透過放慢說話數度來減少卡詞或說錯話的情況