# info2023-homework2 Ken
## Homework2
### [322. Coin Change ](https://leetcode.com/problems/coin-change/description/)
>[video](https://youtu.be/kTCO4kCgSbE)
A - Interviewer
B - Interviewee
A: Hello, I'd like you to design a memory management system similar to the cloud storage we use in our daily lives. Imagine there are various memory blocks of different sizes. For example, users may want to store documents or photos. Our goal is to efficiently utilize memory without wasting any space. Do you have any prior experience with this?
B: Yes, when I worked at for lab, I was responsible for image processing, and we also needed to allocate resources efficiently. I do have some relevant experience, especially in dealing with resource constraints and a high volume of requests.
B: (Repeat)The primary objective is to solve this problem: Given a set of blocks, each with its specific size, how do we use the least number of blocks to compose a specific amount of memory?
(Examples) If memoryBlocks = [1,2,5] and requestedMemory = 11, the output should be 3, because 11MB = 5MB + 5MB + 1MB.
(Approach) I'm thinking of a recursive method. The broad idea is that for each block, we have two choices: either use it or don't. Through recursion, we explore all possible combinations until we find the required minimum number of blocks or determine it's not achievable.
A: Great. First, our system will have a large number of users, and these users may simultaneously request storage space. Considering this, how would you architect this system? You've broken the original problem down into several subproblems, and there's overlap among these subproblems. Meaning, some subproblems will be computed multiple times. Can you handle these overlapping subproblems?
B:
(Repeat) Regarding the overlapping subproblems,
(Approach) we can use memoization: By creating a table (usually a one-dimensional or two-dimensional array) to store the solutions of the subproblems, we can avoid redundant calculations.
(Example) This is a typical step in Dynamic Programming (DP):
1. Define the states, which are typically the various parts of the problem that need solutions.
2. Establish the transition equation to determine how to obtain the solution for the main problem from the solutions of one or more subproblems.
3. Identify boundary conditions, determining both initial and termination conditions.
4. Compute and store the results, starting from the most basic subproblems, using the transition equation, and store the results in a table.
5. Return the final result based on the problem's requirements.
We can first check if the desired result is in the table, and if not, compute and store it.
(coding)
This code is a dynamic programming problem, aiming to find the minimum number of blocks from a given block array such that their sum equals or exceeds a desired amount.
**findLowestBlocks function**:
1. Uses a strategy combining recursion with dynamic programming to solve the problem.
2. For the current block, there are two choices: to use it or to skip it.
3. If deciding to use the current block, the memory requirement decreases by the size of the block.
4. If deciding to skip it, the memory requirement stays unchanged, but the next block is considered.
5. The dp array is used to store computed results, avoiding redundant calculations.
6. The function returns the minimum number of blocks needed to achieve the desired memory size.
**memoryAllocation function**:
1. Initializes the dp array first.
2. Calls the findLowestBlocks function to compute the solution.
3. If the computed result is INT_MAX - 1, it indicates there's no viable combination to meet the memory requirement, thus returns -1. Otherwise, it returns the calculated block count.
```ccp=
class Solution {
public:
int dp[12 + 1][10000 + 1]; // Dynamic programming array used to store previously computed results
int findLowestBlocks(vector<int> &blocks, int cur, int amount) {
// Base case: Current index is beyond the size of blocks or amount is less than or equal to 0
if (cur == blocks.size() || amount <= 0)
return (amount == 0) ? 0 : INT_MAX - 1;
// If the result for this state already exists in the dp array, return it directly
if (dp[cur][amount] != -1)
return dp[cur][amount];
int res = -1;
// If the current block is greater than the required amount, we cannot use it
if (blocks[cur] > amount) {
// We can only choose not to use the current block and recursively call itself to process the next block
int doNotTakeBlock = findLowestBlocks(blocks, cur + 1, amount);
dp[cur][amount] = res = doNotTakeBlock; // Record the result in the dp array
}
else {
// We have two choices: use or not use the current block
// Choose to use the current block
int takeBlock = 1 + findLowestBlocks(blocks, cur, amount - blocks[cur]);
// Choose not to use the current block
int doNotTakeBlock = findLowestBlocks(blocks, cur + 1, amount);
// Get the minimum result from the above two choices and store it in the dp array
dp[cur][amount] = res = min(takeBlock, doNotTakeBlock);
}
return res;
}
// Main function that calls the recursive function and handles the result
int memoryAllocation(vector<int>& blocks, int amount) {
// Initialize the dp array with -1
memset(dp, -1, sizeof(dp));
int res = findLowestBlocks(blocks, 0, amount);
// If the result is INT_MAX - 1, return -1 to indicate no solution, otherwise return res
return (res == INT_MAX - 1 ) ? -1 : res;
}
};
```
B: The time complexity is O(n.m), and the space complexity is O(n.m).
A: Considering large systems, if we have numerous requests and a vast amount of memory blocks, do you think recursion is still a good choice?
B:
(Repeat & Example) That's an excellent point you raise. For larger systems, recursion could lead to stack overflow.
(Approach) In such cases, I'd lean towards using the Tabulation method of DP, where a table is used to store answers for subproblems. We then reference this table to get all the necessary information to solve the parent problem. Once solved, the result is also added to the table, and this continues until the table is complete. This bottom-up approach can avoid recursion entirely by only using loops.
(codding)
This code offers a dynamic programming approach to solve for a given set of blocks, aiming to achieve or exceed a certain amount using the minimum number of blocks.
**findLowestBlocks function**:
1. **Initialize the DP table**: For every possible subset and each potential target value, initialize base cases.
2. **Populate the DP table**: Consider each block and each target value. There are two choices: to use the block or not. Based on these choices, compute the minimum number of blocks required to achieve the target value.
3. **Return the result**: Return the final result from the DP table.
**memoryAllocation function**:
1. Calls the `findLowestBlocks` function passing `blocks` and `amount`.
2. Checks the result, if it's `INT_MAX - 1`, this implies that there's no solution, so it returns -1. Otherwise, it returns the result.
```ccp=
class Solution {
public:
int dp[12 + 1][10000 + 1];
int findLowestBlocks(vector<int> &blocks, int arraySize, int amount) {
// 1. Initialize the dynamic programming table
for (int i = 0; i < arraySize + 1; i++) {
for (int j = 0; j < amount + 1; j++) {
// Initialize base cases if i or j is 0
if (i == 0 || j == 0)
dp[i][j] = (j == 0) ? 0 : INT_MAX - 1;
}
}
// 2. Fill the dynamic programming table
for (int i = 1; i < arraySize + 1; i++) {
for (int j = 1; j < amount + 1; j++) {
// If the current block size is greater than the memory to allocate
if (blocks[i - 1] > j)
dp[i][j] = dp[i - 1][j]; // Do not use the current block
else
// Choose the minimum between not using the current block or using the current block
dp[i][j] = min(dp[i - 1][j], 1 + dp[i][j - blocks[i - 1]]);
}
}
// 3. Return the result
return dp[arraySize][amount];
}
// Main function: Calls findLowestBlocks and handles the result
int memoryAllocation(vector<int>& blocks, int amount) {
int res = findLowestBlocks(blocks, blocks.size(), amount);
// If the result is INT_MAX - 1, return -1 to indicate no solution, otherwise return res
return (res == INT_MAX - 1) ? -1 : res;
}
};
```
B: The time complexity is O(n.m), and the space complexity is O(n.m).
A: Now, I'll introduce a constraint. Let's assume the system can only handle 10 requests at a time. This could be due to backend limitations or other technical issues. How would such a constraint affect your solution?
B: If there's such a limitation, I would consider introducing a request queue system. Only 10 requests would be processed at a time, while others would wait. At the same time, I would inform users on the frontend that they might need to wait, or create some funny image to reduce users's boredom.
A: Understood. Now, from a business perspective, if users are not satisfied with our service efficiency, they might turn to competitors. From your experience and the perspective of this system, how would you balance efficiency and user satisfaction?
B: Based on my past experience, I would recommend increasing backend resources or using more efficient algorithms. Additionally, we can provide a more user-friendly interface, informing users of expected wait times, and even offering priority processing for regular users. These methods can all enhance user satisfaction.
### 初步檢討
- [ ] 要加強測試
- [ ] coding過程感覺可以再更順一點，不然好像有點尷尬
- [ ] 測試完要多點延伸，不是直接說我打好code了，可以分享想法之類的
- [ ] 說話可以加強，還是會黏在一起，唸英文不順
- [ ] 程式碼講解可以更通順
- [ ] 加強互動
- [ ] 面試官應當更多問題，探索面試者，不是考試機器人
- [ ] 面試者感覺不夠積極，要更活躍，證明自己的價值
## 對其他同學的批評 (正反面都有)
### 1. [朱舞花-Flowey 144, 1791, 287](https://hackmd.io/@sysprog/ByN0NI8kp)
**Interviewer**
- [ ] 優點
- [ ] 指示清晰，明確要求要達到甚麼條件
- [ ] 缺點
- [ ] 我認為通常主管面試是找未來會一起工作很久、要相處一陣子的人，感受不出主管有在確認這種方面
- [ ] 可能題目可以變換下，多出點應用超出leetcode 的codeing範圍，更應用到商品的想法，比如二元墅連接到ubuntu的記憶體控制，找東西順序，或著商品排序找些
**Interviewee**
- [ ] 優點
- [ ] 咬字真的很清晰，我用兩倍速聽都很清楚，不會誤會
- [ ] 有遵守確認，舉例，說明方案，撰寫程式
- [ ] 缺點
- [ ] 感覺互動有點少，可能coding過程可以多點閒聊
- [ ] 可能多點驗證程式的方案，例如舉例套進去看看
- [ ] 感覺說這題就做完好像不太好
### 2. [曉榕-Dawn](https://hackmd.io/@sysprog/HJFjrhC1a)
**Interviewer**
- [ ] 優點
- [ ] 問答清晰，點到問題
- [ ] 面試官友善
- [ ] 缺點
- [ ] 感覺要變形下題目
**Interviewee**
- [ ] 優點
- [ ] 咬字清晰，2倍速下可聽，好評
- [ ] 每行都有清晰講解code的功能
- [ ] 片頭片尾好讚
- [ ] 缺點
- [ ] 直接進入coding好像太快，可能可以遵守"確認，舉例，說明方案，撰寫程式，驗證程式"，延長時間，多點展現自己，不然好像考試刷提，特別是驗證程式
### 3. [沙西米-Sashimi](https://hackmd.io/@sysprog/S1hhirak6)
**Interviewer**
- [ ] 優點
- [ ] 說明清晰
- [ ] 缺點
- [ ] 面試官感覺有點冰冷
- [ ] 題目可能要變形
**Interviewee**
- [ ] 優點
- [ ] 很確實的落實確認，很好的互動
- [ ] coding過程的說明，很好避免尷尬
- [ ] 咬字清晰
- [ ] 驗證程式碼做的很確實
- [ ] 缺點
- [ ] 感覺說明方和可以多點，多解釋下整體思路，不然直接進入coding可能跟不上
### 4 [卑鄙葛摟-Babygirl](https://hackmd.io/@sysprog/rk9g0BpJa)
**Interviewer**
- [ ] 優點
- [ ] 指示清晰
- [ ] 缺點
- [ ] 要變換題型
- [ ] 互動太少，感受不到面試官有想認識面試者
- [ ] 感覺就很順的放水受試者
**Interviewee**
- [ ] 優點
- [ ] 咬字清晰，2倍速可聽
- [ ] 解釋有邊打字，有個圖示很棒
- [ ] 邊coding的解釋很棒，不會尷尬，還會再用簡單文字表示，避免面試官恍神很棒
- [ ] 缺點
- [ ] 要遵守"確認，舉例，說明方案，撰寫程式，驗證程式"，可能要多確認下問題
- [ ] 測試可能要再多一點
### 5 [查理-Charlie](https://hackmd.io/@sysprog/HyEYCSpyp)
**Interviewer**
- [ ] 優點
- [ ] 說明清晰
- [ ] 缺點
- [ ] 面試官很冰冷，感覺比電我的教授還兇，我老師電我幾句還會說點好話或著笑一下安慰之類的。
**Interviewee**
- [ ] 優點
- [ ] 有落實"確認，舉例，說明方案，撰寫程式，驗證程式"
- [ ] 咬字很乾淨，可用2倍速聽
- [ ] 邊coding有編說明，不會尷尬
- [ ] 缺點
- [ ] 聲音有點小，我得用外掛軟體放大音量才聽得道(600%音量欸)
- [ ] 驗證程式可能要更確實
### 學到什麼
1. 題目變形太少
- 目前大家都還是用原本的題目，沒有多變化題目，這樣在面對真實問題時很難想像可以解決
2. 說話很重要
- 咬字清晰的人優勢很大，有些不清楚的我直接跳過懶得聽，很難2倍速的也是，得多練習口條
- 有些對話很冰冷、尷尬，我自己如果是主管要看面試錄影決定用人可能會想把面試官、面試者都辭退，很難想像要長期與這些人相處
3. 很少談到後續
- 很少人能把這個題目延伸下去，多說說接續的應用，延長話題，多點發揮來應對此問題。基本上都是你問我答，我自己很喜歡computer vision 大師takeo的對話，你可以感受到熱情，很多想法聊不完的感覺。充分展現他對於這一行的熱愛。或著黃老師他們那股熱情講解，一直延續話題的感覺。
整體而言大家都不太熟悉面試，並且對coding好像熱情不高沒有很多話題的尷尬感。很不親切，沒有那種大師風範。
Sign in with Wallet
Connect another wallet