###### tags: `course`, `homework`
# Mock interview Record - Homework1
> 古道梅子-Gudao
> 🐶: Interviewer, 🐱: Interviewee
> [mock interview video](https://youtu.be/Dtahq75FuCo)
## 1779. [Find Nearest Point That Has the Same X or Y Coordinate](https://leetcode.com/problems/find-nearest-point-that-has-the-same-x-or-y-coordinate/)
### Problem Description
:::warning
You are given two integers, `x` and `y`, which represent your current location on a Cartesian grid: `(x, y)`. You are also given an array `points` where each `points[i] = [ai, bi]` represents that a point exists at `(ai, bi)`. A point is **valid** if it shares the same x-coordinate or the same y-coordinate as your location.
Return the index **(0-indexed)** of the valid point with the smallest Manhattan distance from your current location. If there are multiple, return the valid point with the smallest index. If there are no valid points, return `-1`.
The Manhattan distance between two points `(x1, y1)` and `(x2, y2)` is `abs(x1 - x2) + abs(y1 - y2)`.
:::
🐶: We need to create a **recommendation system**, where users will use keywords for searching. We want to *return the product that **best matches** the keywords entered by the user*.
🐶: To achieve this, we have assigned a unique ID to each item, creating a 2-dimensional array with the item's ID and the brand's ID. We will also **automatically** convert the user's *input text into ID format*.
🐶: Please find at least one product from the database that matches *either its **brand** or **product name***. *If there are **no matching products** in the database, please return `null` to inform the system*.
🐱: Today, I will cerate a recommendation system. Users can type some text into searching box. want to return the best match product that in ours database.
🐱: We hava a function that can convert text into id format: [brand, name]
🐱: We can convert this problem into find a point that closest in ours database and it start from (x, y).
🐱: All if points in ours database can be [brand id, name id] this format.
🐱: Dose it make sence?
🐶: Yap! It's make sence.
---
### Examples
ex1:
database: [[0, 1], [2, 3], [0, 2], [1, 0]]
users: [0, 0]
// brand 0 : google, 1 : sony, 2 : samsung
// name 0 : phone, 1 : watch, 2 : speaker, 3 : microphone
// find closest [0, 0]
return [0, 1];
ex2:
database: [[0, 1], [2, 3], [0, 2], [1, 0]]
users: [2, 3]
return [2, 3];
ex3:
database: [[0, 1], [2, 3], [0, 2], [1, 0]]
users: [9, 9]
// brand 9 : logi, name 9 : keyboard
return null;
### Solutions
```cpp=
class RecommendationSystem {
vector<int> searching(int brand, int name, vector<vector<int>>& database) {
int min = INT_MAX;
vector<int> res;
for (vector<int> p : database) {
if (p[0] == brand || p[1] == name) {
// our database have same brand or same name
int dist = abs(p[0] - brand) + abs(p[1] - name);
if (dist < min) {
min = dist;
res = p;
}
}
}
return min == INT_MAX ? null : res;
}
};
```
:::success
- **Time Complexity: $O(n)$**
- **Space Complexity: $O(1)$**
:::
---
 
## 973. [K Closest Points to Origin](https://leetcode.com/problems/k-closest-points-to-origin/) (*Follow up*)
🐶: We want to make a slight adjustment to our current system. Users should be able to specify how many (k) top relevant products they want to receive, and these products do **not necessarily** need to be an exact match with the keywords.
🐱: Using min-heap, and pop it k-times.
### Example
database: [[0, 1], [2, 3], [0, 2], [1, 0]]
users: [0, 0], k = 2
return [[0, 1], [1, 0]];
### Solutions
```cpp=
class RecommendationSystem {
vector<vector<int>> SearchingKItems(int brand, int name, vector<vector<int>>& database) {
priority_queue<pair<int, vector<int>>, vector<pair<int, vector<int>>>, greater<pair<int, vector<int>>>> min_heap;
for (vector<int> p : database) {
// calculate euler distance
min_heap.push({(p[0] - brand) * (p[0] - brand) + (p[1] - name) * (p[1] - name), p});
}
vector<vector<int>> res;
for (int i = 0; i < k; i++) {
auto p = min_heap.top(); min_heap.pop();
res.push_back(p.second);
}
return res;
}
};
```
- 註: 拍片時忘記是要計算**Euler距離**，這在邊已做更正。
:::success
- **Time Complexity: $O(klogn)$**
- **Space Complexity: $O(n)$**
:::
🐶: Thank you for participating in the interview today. We will notify you of the results via email in the near future. Have a wonderful day!
### 自評
- 雙方互動還是偏少
- 若抓到interviewee的錯誤應該要及時的去更正他
## 作業二-評比
- [評比一](https://hackmd.io/CEeb2K3pRLimtpLxZsrpdA?both)
- interviewer:
- 優點
- 不會一開始就直接切入題目
- 引導interviewee來猜出原本的題目是什麼
- 會轉換題目，不會讓interviewee一聽到題目就知道要考什麼
- interviewee:
- 優點
- 有隨著interviewer的引導來猜出題目
- 可改進地方
- 第二部影片(14:05): 使用`defaultdict`前應該要先`import collections`，兩種應該都需要把值取出來，與一般dict的差別應該是會自動幫新的key對應的value做初始化，若已經先做完初始化，兩邊的用法應該會是一樣的。
---
- [評比二](https://hackmd.io/4W0nTeYsT_iTZ--yG_aQdA?both)
- interviewer
- 優點:
- 咬字清楚
- 有延伸題目到不同的情境
- 可改進地方:
- 可能需要將題目轉換一下，才不會讓interviewer一聽到關鍵字就知道今天要考的題目是什麼
- interviewee
- 優點:
- 註解很清楚
- 咬字清楚
- 打字速度快
- 可改進地方:
- 第一題的第一個解法，將字串翻轉後直接比對兩字串是否相同即可`return input == reverse_s`
- isalnum的用法可能要與interviewer做一下簡短的說明
- 第二題的部分程式可以更精簡:
```cpp
if(list1)
{
tail->next= list1;
}
if(list2)
{
tail->next = list2;
}
// 上面的兩個if可以改成:
tail->next = list1 ? list1 : list2;
```
- 第三題程式碼可以再精簡一些
```cpp
bool Search2DMatrix(vector<vector<int>>& input,int target)
{
int n = input[0].size();
int m = input.size();
int left = 0,right = m*n-1;
int mid, mid_row, mid_col;
while(left<=right)
{
mid = (left+right)/2;
mid_row = mid/n;
mid_col = mid%n;
if(input[mid_row][mid_col] == target)
return true;
else if(target>input[mid_row][mid_col])
{
left = mid+1;
}
else
{
right = mid-1;
}
}
return false;
}
```
---
- [評比三](https://hackmd.io/LGDvF7z6QraooiVkwhKAqA?both)
- interviewer
- 優點:
- 題目列得很清楚
- 可改進地方:
- 可以嘗試將題目轉換成現實中會遇到的問題，讓interviewee不會太快就知道你想考他什麼
- interviewee
- 優點:
- 會先用pseduo code來解釋流程
- 舉例清楚明瞭
---
- [評比四](https://hackmd.io/2W0cu9uFS8udA3Jw4zL9Gw?both)
- interviewer
- 優點:
- 題目清楚明瞭
- 可改進地方:
- 題目給的線索太多，好處是interviewee可以很清楚知道要考什麼，但對於有刷過leetcode的人可能鑑別度不會太高
- 可以嘗試轉換題目，對應到真實生活的例子上
- interviewee
- 優點:
- 一邊打code一邊講解還蠻流暢的
---
- [評比五](https://hackmd.io/cqmdfZxVQsqJGvTeaTS4lw?both)
- interviewer
- 優點:
- 題目清楚明瞭
- 有試著引導interviewee
- 可改進地方:
- 可以嘗試轉換題目，對應到真實生活的例子上
- interviewee
- 優點:
- 有做到利用問題來確認是否有理解錯題目
- 可改進地方:
- (第一題)如果已經確定大小(vector可以轉換成pair來增快整體時間)
- 遞迴改成迭代不一定會比較省空間(?
Sign in with Wallet
Connect another wallet