# 資訊科技產業專案設計 HW5
###### tags: `資訊科技產業專案設計`
[影片連結](https://www.youtube.com/watch?v=BueZafPr04s)
# 作為 Interviewer
## [Problem: Find The Duplicates](https://www.pramp.com/challenge/15oxrQx6LjtQj9JK9XlA)
Given two sorted arrays arr1 and arr2 of passport numbers, implement a function findDuplicates that returns an array of all passport numbers that are both in arr1 and arr2. Note that the output array should be sorted in an ascending order.
Let N and M be the lengths of arr1 and arr2, respectively. Solve for two cases and analyze the time & space complexities of your solutions: M ≈ N - the array lengths are approximately the same M ≫ N - arr2 is much bigger than arr1.
### Example:
```
input: arr1 = [1, 2, 3, 5, 6, 7], arr2 = [3, 6, 7, 8, 20]
output: [3, 6, 7] # since only these three values are both in arr1 and arr2
```
Constraints:
[time limit] 5000ms
[input] array.integer arr1
1 ≤ arr1.length ≤ 100
[input] array.integer arr2
1 ≤ arr2.length ≤ 100
[output] array.integer
## Solution1:
先以一個 for loop iterate arr1, 將 arr1 的所有 element 存入 set 中, 接著再以另一個 for loop iterate arr2, 檢查 arr2 的 element 有沒有存在在 set 中, 如果有就將此 element 加入要 return 的 vector 中, 最後回傳此 vector.
```c=
vector<int> findDuplicates( const vector<int>& arr1, const vector<int>& arr2)
{
set<int> s;
for(int i = 0; i < arr1.size(); i++) {
s.insert(arr1[i]);
}
for(int i = 0; i < arr2.size(); i++) {
if (s.count(arr2[i])) {
ret.push_back(arr2[i]);
}
}
return ret;
}
```
### Time Complexity:
分別使用了兩個 for loop 去 iterate arr1 和 arr2, 所以為 O(M + N), if N > M , the time complexity is O(N). Otherwise, the time complexity is O(M) (N and M be the lengths of arr1 and arr2), 取 size 較大的那個 array.
### Space complexity:
O(N), 而外建立了一個 set 來存 arr1 中的所有 element ( N and M be the lengths of arr1 and arr2), 以及 return vector
### 缺點：
如果 M ≈ N - the array lengths are approximately the same, 這個方法的效率還可以接受, 但如果 M ≫ N - arr2 is much bigger than arr1, 這個方法的效率就相對較差, 而且要配置額外的記憶體空間.
## Solution2:
```c=
vector<int> findDuplicates( const vector<int>& arr1, const vector<int>& arr2)
{
vector<int> ret;
int i = 0, j = 0;
while(i < arr1.size() && j < arr2.size()) {
if (arr1[i] < arr2[j]) i++;
else if (arr1[i] > arr2[j]) j++;
else {
ret.push_back(arr1[i]);
i++;
j++;
}
}
return ret;
}
```
### Time Complexity:
while loop 會在 size 較小的那個 array 被完整遍歷後終止, so if N > M , the time complexity is O(M). Otherwise, the time complexity is O(N) (N and M be the lengths of arr1 and arr2), 取 size 較小的 array
### Space complexity:
O(N), 只額外配置 return vector
### 比較 solution 1:
即使 M ≫ N - arr2 is much bigger than arr1, 這個方法的時間複雜度是看 size 較小的那個 array. 且方法二無配置額外一個 set
## Interviewer 檢討:
在 interviewee 寫出解法後, 沒有問太多的細節, 就請他直接開始寫 code
# 作為 Interviewee
## [Problem: Array of Array Products](https://www.pramp.com/challenge/7Lg1WA1nZqfoWgPbgM0M)
Given an array of integers arr, you’re asked to calculate for each index i the product of all integers except the integer at that index (i.e. except arr[i]). Implement a function arrayOfArrayProducts that takes an array of integers and returns an array of the products.
Solve without using division and analyze your solution’s time and space complexities.
### Example:
```
input: arr = [8, 10, 2]
output: [20, 16, 80] # by calculating: [10*2, 8*2, 8*10]
input: arr = [2, 7, 3, 4]
output: [84, 24, 56, 42] # by calculating: [7*3*4, 2*3*4, 2*7*4, 2*7*3]
```
Constraints:
[time limit] 5000ms
[input] array.integer arr
0 ≤ arr.length ≤ 20
[output] array.integer
## Solution1: 暴力解
用 nest for loop, 外層 for loop iterate 整個 array, 內層 for loop iterate 整個 array 並算出除了外層 for loop 所指向的 element 以外, 所有 element 的 products
```c=
vector<long> arrayOfArrayProducts(const vector<int>& arr)
{
vector<long> res = {};
if(arr.size() <= 1)
return res;
for(int i = 0; i < arr.size(); i++) {
int count = 1;
for(int j = 0; j < arr.size(); j++) {
if(i == j) continue;
count *= arr[j];
}
res.push_back(count);
}
return res;
}
```
### Time Complexity:
使用了 nest for loop, 內外層 for loop 都去 iterate arr, 所以為 O(N^2), N is arr size.
### Space complexity:
O(N), 只額外配置 return vector, N is arr size.
### 缺點：
暴力解的效率很差.
## Solution2:
此用一個 for loop 去計算當前 index 的左邊所有 element 的積, 再以另外一個 for loop 去計算右邊所有 element 的積, 將這個相乘即可獲得答案。
```c=
vector<long> arrayOfArrayProducts(const vector<int>& arr)
{
vector<long> res = {};
if(arr.size() <= 1)
return res;
int count = 1;
res.push_back(count);
for(int i = 0; i < arr.size() - 1; i++) {
count*= arr[i];
res.push_back(count);
}
count = 1;
for(int i = arr.size() - 1; i >= 1; i--) {
count *= arr[i];
res[i - 1] *= count;
}
res[arr.size() - 1] *= 1;
return res;
}
```
### Time Complexity:
用了兩個 for loop, 且這兩個 for loop 都是 iterate arr, 所以 time complexity is O(N), N is arr size.
### Space complexity:
O(N), 只額外配置 return vector, N is arr size.
### 比較 solution 1:
較有效率, 從 O(N^2) 降到 linear time.
## Interviewee 檢討:
* 太執著於一步完成答案, 而沒有細心地去猜分題目
* 太急著去 run test, 沒有細心檢查 edge case, 也沒有細心檢查自己 code 中的 bug
* 思考的時候停頓了很久, 有很大一段沒有和 interviewr 對話
* 卡了很久, 讓 interviewer 一直給 hint, 有點變成 interviewer 在作答
## peer 回饋
---
# Behavior Question
* Tell me a bit about your professional experience in 2-3 minutes.
OK, I was an intern in galaxy Software Service Corporation for one year. During the internship, I learned a lot about the concept of software testing and how to improve the quality of my code. Also, I am a research assistant in software engineering laboratory in my university. During the research, I got the experience about cooperating with teammates to develop software products, we keep conversating with others and use git to control the version, and we have a meeting per week to check the schedule. Furthermore, I often need to find out problems which feedback from customers and trying to fix these bugs.
* What are you looking for in your next role?
As a new graduate student, I want to join a team that I can learn a lot skill from my teammate, because I hope they can lead me to become a better engineer. Also, I hope I can make some contribution to my team and my company.
* How about being a leader in next few years?
I hope I can be a leader in next three years
* tell an example of a difficult problem you solved?
Next month, I had a problem feedback from the cutomer that used our products. The problem is that a funciton not work in some websites with React framework, but it is still work in the website with other framework. Also, this function is work in old version React website, but it is not work in new version. Therefore, I diagnosed the problem is resulted from changing version of React framework. My solution is that, I consulted the React document to knew what has changed in new version and found out a important change was related to the porblem I wanted to solve. Finally, I follow the change to modify the function. So, that's the processes I try to diagnose the problem and find a solution to fix it.
* This kind of solution is determined by yourself or discussed with tour teammates?
This solution is found out by myself, because this task is assigned to me.
* Can you tell me about your team’s decision-making process? What do you like and not like about it?
When my teammate come up with an new idea, we would discuss with our professor in a meeting, the professor would listen other member's comments and make the decision. I like about it, because we make the decesion before discussing. So, this decision is made by all members.
## 檢討
* 被問到未來有沒有想成為 leader 時, 只有簡短地回答道未來會想成為 leader, 但後續檢討覺得可以講說成為 leader 前會想培養一些能力, 例如管理能力以及溝通能力等。
* 在被問到有沒有遇到什麼困難的問題以及如何解決時, 把困難的問題敘述得太過冗長, 覺得可以簡短的說因為改版問題就好了, 然後後續可以補上解決問題後, 有為程式碼註解問題發生原因及修改了什麼來加速未來成員遇到同樣問題時能更有效率的解決。
Sign in with Wallet
Connect another wallet