# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 南瓜籽-Pepita
> 🎃：interviewer
> 🌱：interviewee
> [模擬面試錄影(漢)](https://www.youtube.com/watch?v=SeiO1c3v8ZE)
> [模擬面試錄影(漢)](https://www.youtube.com/watch?v=4VKr5Sp7xRo)
> [模擬面試錄影(英)](https://www.youtube.com/watch?v=f5sU7RvKbFo)
---
## [973. K Closest Points to Origin](https://leetcode.com/problems/k-closest-points-to-origin/)
### 模擬面試過程
🎃：請從題目給的座標點中，找出K個離原點歐氏距離最近的座標點。
🎃：座標點個數會介在$1\sim10^4$之間，座標點的數值則介在$-10^4\sim10^4$。
🌱：請問題目給的座標點會重複嗎？題目的座標系是3維還是2維的？
🎃：不會重複，是2維座標系
🌱：以[[3,3],[5,-1],[-2,4]]，K=2為例，目標是輸出離原點最近的[[-2,4],[3,3]]。
🎃：沒錯喔！
🌱：那我會將這個問題拆成兩個部分，一個是處理題目給的前K個點，用vector存位置與相距原點的距離，另一個則是處理剩下題目給的座標點，只要比儲存在vector裡的任一點距離原點更近，就可以取代儲存在vector裡，距離原點最遠的點
### 直觀
```cpp
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
vector<vector<int>> res;
vector<int> dist;
int index=0;
for(int i=0; i<k; i++){
res.push_back(points[i]);
int tmp = points[i][0] * points[i][0] + points[i][1] * points[i][1];
dist.push_back(tmp);
if(tmp > dist[index]){
index = i;
}
}
for(int i=k; i<points.size(); i++){
int tmp = points[i][0] * points[i][0] + points[i][1] * points[i][1];
if(tmp < dist[index]){
res[index] = points[i];
dist[index] = tmp;
}
int max=0;
for(int j=0; j<k; j++){
if(dist[j] > max){
index = j;
max = dist[j];
}
}
}
return res;
}
};
```
🎃：那你覺得這樣的實作方式，有什麼可以進步的地方？
🌱：在排序的部分可以優化，雖然quicksort在best case可以達到$O(NlogN)$，但是在worst case卻是$O(N^2)$，mergesort相對quicksort所有case都是$O(NlogN)$，但是題目的排序只須找到最大值就好，不需要每次有新的點就要那k個點重做排序，因此會選擇時間複雜度為$O(NlogN)$的max heap實作排序
### maxheap, priority_queue
```cpp
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
priority_queue<vector<int>, vector<vector<int>>, compare> pq;
for (vector<int>& point : points) {
pq.push(point);
if (pq.size() > K) {
pq.pop();
}
}
vector<vector<int>> ans;
while (!pq.empty()) {
ans.push_back(pq.top());
pq.pop();
}
return ans;
}
private:
struct compare {
bool operator()(vector<int>& p, vector<int>& q) {
return p[0] * p[0] + p[1] * p[1] < q[0] * q[0] + q[1] * q[1];
}
};
};
```
### 初步檢討
### 同儕檢討
---
## [733. Flood Fill](https://leetcode.com/problems/flood-fill/description/)
### 模擬面試過程
🎃：請你從一張圖中的起始點開始，將與起始點pixel值相同，也與起始點pixel是4-direction connected的pixel值轉成目標值。
🎃：圖的長寬會在$1\sim50$之間，圖的pixel值與目標值會在$0\sim2^{16}$。
🌱：以下圖為例，以$(1,1)$位置為起始點，換成目標值2。
```cpp
[[1,1,3],
[1,1,0],
[1,0,1]]
```
🌱：結果會是從起始點擴散出去，上下左右有相鄰的，換成目標值2。
```cpp
[[2,2,3],
[2,2,0],
[2,0,1]]
```
🎃：沒錯喔！
🌱：好的。那我會將這題分成兩個部份來解，一個是4-direction connected的搜尋，另一個是確認是否與起始點的pixel值相同，選擇要不要改成目標值。
🎃：那搜尋的部分你想怎麼做呢？
🌱：我會用DFS來實作，以遞迴的方式實現搜尋。
### recursive DFS
```cpp
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
if(image[sr][sc] == color)
return image;
funct(image, sr, sc, image[sr][sc], color);
return image;
}
void funct(vector<vector<int>>& image, int sr, int sc, int value, int color){
if(sr<0 || sr>=image.size() || sc<0 || sc>= image[0].size() || image[sr][sc]!=value)
return;
image[sr][sc] = color;
funct(image, sr-1, sc, value, color);
funct(image, sr+1, sc, value, color);
funct(image, sr, sc-1, value, color);
funct(image, sr, sc+1, value, color);
}
};
```
🎃：遞迴的缺點是對記憶體不友善，那你會怎麼做呢？
🌱：記憶體優化的部分，因為遞迴會堆積在記憶體stack的部分，所以可用iteration的方式來優化。
🎃：那你會想怎麼寫呢？
🌱：我會用資料型別stack來記錄迭代時，需要改pixel值的點。
### iterative DFS
```cpp
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
int oldColor = image[sr][sc];
if(oldColor == newColor) return image;
const vector<pair<int, int>> moves = {{-1,0}, {1,0}, {0,-1}, {0,1}};
stack<pair<int, int>> q({{sr, sc}});
while(q.size())
{
auto [row,col] = q.top();
q.pop();
image[row][col] = newColor;
for(auto& [R,C] : moves)
{
int r = row+R, c = col+C;
if(r < 0 || r >= image.size() || c < 0 || c >= image[0].size() || image[r][c] != oldColor)
continue;
q.push({r,c});
}
}
return image;
}
};
```
### 初步檢討
### 同儕檢討
---
## [232. Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/)
### 模擬面試過程
🎃: The next question is to implement a queue using stacks.
🌱: Okay, I need to implement push, pop, and empty. Is there anything else I need to implement?
🎃: Add a peek() function that returns the element at the front of the queue.
🎃: Object queue is instantiated and called as follows.
```cpp
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
```
🌱: Let's take this input as an example.
```cpp
["MyQueue", "push", "push", "peek", "pop", "empty"]
```
🌱: And the values are following.
```cpp
[[], [1], [2], [], [], []]
```
🌱: So, we have a queue called MyQueue. Push values 1 and 2 into the queue. Then peek at the front of the queue, and the value is 1. Pop the queue, and the value is 1. The remaining part of the queue is 2. The final step is to check if the queue is empty or not and return false.
🎃: That's right.
🌱: I will use two stacks to implement a queue. When a user calls push() or empty(), use them in the same way as we do with a stack. When a user calls pop() or peek(), pop all values except the target one from the first stack and push these values into the second stack as a buffer. Return the target value. Then, we will pop all the values from the second stack and push them into the first stack to maintain the correct order.
🎃: OK. Let's do it.
### 直觀
```cpp
class MyQueue {
public:
stack<int> st;
MyQueue() {
}
void push(int x) {
st.push(x);
}
int pop() {
stack<int> st2;
while(st.size()-1){
st2.push(st.top());
st.pop();
}
int tmp = st.top();
st.pop();
while(st2.size()){
st.push(st2.top());
st2.pop();
}
return tmp;
}
int peek() {
stack<int> st2;
while(st.size()-1){
st2.push(st.top());
st.pop();
}
int tmp = st.top();
while(st2.size()){
st.push(st2.top());
st2.pop();
}
return tmp;
}
bool empty() {
return st.empty();
}
};
```
🎃: What aspects do you think can be improved?
🌱: After we pop all values from the first stack and push them all into the second stack, we can use the second stack to pop the values in a queue-like order.
🎃: OK
### 優化
```cpp
class MyQueue {
public:
stack<int> st;
stack<int> st2;
MyQueue() {
}
void push(int x) {
st.push(x);
}
int pop() {
peek();
int tmp = st2.top();
st2.pop();
return tmp;
}
int peek() {
if(st2.empty()){
while(st.size()){
st2.push(st.top());
st.pop();
}
}
return st2.top();
}
bool empty() {
return st.empty() && st2.empty();
}
};
```
---
## 第二次作業-他評 01
* 我討論這一題 [973. K Closest Points to Origin](https://leetcode.com/problems/k-closest-points-to-origin/)
* 這一題範例給的是 (3, 3), (5, -1), (-2, 4), K=2的答案是 (3, 3), (-2, 4).
* 感覺這可能與圓錐曲線的[橢圓](https://zh.wikipedia.org/zh-tw/%E6%A4%AD%E5%9C%86)有關, e.g., 半短軸長 / 半長軸長 / 焦距的關係. 但我距離高中有點久遠, 還需要研究才能給建議.
* If 真與橢圓有關, 因為題目給的都是格子點, 就可先將點座標都先轉到第一象限. 然後或許可以透過單一點座標 (x, y)運算來省掉平方的運算.
* Sorry, 應用橢圓特性 or 畢氏定理可知道 x + y為定值時的各個格子點 (x, y)與原點的距離的最大值最小值, e.g., x + y = 0, 1, 2, ..., n 會各自構成一個類別, 單一類別內可以輕易排序得知與原點距離孰遠孰近. 但要進一步應用到這個問題的話, 還須處理 x + y為不同值的情況, 好像就沒那麼簡單了.
#### Both
- [ ] 優點
* 語速雖不快, 但聽得很清楚, 英文發音容易識別.
## 第二次作業-他評 02
* 我討論這一題 [973. K Closest Points to Origin](https://leetcode.com/problems/k-closest-points-to-origin/). 承上, 他評 01.
* 感覺這個問題很適合使用 dynamic programming方式來解這個問題, 尤其是平面上的點很多時.
* 以 (0, 0)開始建構平面上的各個格子點與原點的距離. 我試著用以下表格呈現.
| (y, x) | 0 | 1 | 2 | 3 | 4 | 5 |
| ------ | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 1 | 4 | 9 | 16 | 25 |
| 1 | 1 | 2 | 5 | 10 | 17 | 26 |
| 2 | 4 | 5 | 8 | 13 | 20 | 29 |
| 3 | 9 | 10 | 13 | 18 | 25 | 34 |
| 4 | 16 | 17 | 20 | 25 | 32 | 41 |
| 5 | 25 | 26 | 29 | 34 | 41 | 50 |
* 每個 column與前一個 column的差是固定的, 每個 row與前一個 row的差也是固定的.
* 這是因為計算 (y, x)到原點距離時使用的 y^2 + x^2. 當計算 (y + 1, x)到原點距離時, (y + 1)^2 + x^2只會比前一個點 (y, x)多出 2y + 1. 同理可證, (y, x + 1)與 (y, x)的關係.
* 已知平面上一點 (y, x), 平面上另有一點 (v, u), 其中 v >= y, u >= x.
* 則 (v, u)與原點距離的平方 = (y, x)與原點距離的平方 + (v - y)^2 + (u - x)^2.
* 基本上就會大量重複使用到 row 0, col 0的內容, 而 row 0與 col 0內容是一樣的, 感覺可以省下許多運算成本.
## 第二次作業-他評 03
- interviewer
- 優點:
- 題目清楚明瞭
- 有試著引導interviewee
- 可改進地方:
- 可以嘗試轉換題目，對應到真實生活的例子上
- interviewee
- 優點:
- 有做到利用問題來確認是否有理解錯題目
- 可改進地方:
- 遞迴改成迭代不一定會比較省空間(?
Sign in with Wallet
Connect another wallet