---
title: 2021 年資訊科技產業專案設計課程面試範例
tags: INFO2021
---
# 2021 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2021)」面試範例
> 貢獻者: 林宇庭-Austin
> ==[video](https://youtu.be/zokVE4RUmmU)==
# Homework 2
## (E) [167. Two Sum II - Input array is sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)
Given an array of integers `numbers` that is already ***sorted in non-decreasing order***
Find two numbers such that they add up to a specific `target` number.
Return *the indices of the two numbers (**1-indexed**) as an integer array `answer`*
* The tests are generated such that there is **exactly one solution**
### Solution 1: Brute Forece
```cpp=
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> answer(2, 0);
for (int i = 0; i < (numbers.size()-1); i++) {
for (int j = (i+1); j < numbers.size(); j++) {
if (numbers[i] + numbers[j] == target) {
answer[0] = (i+1);
answer[1] = (j+1);
return answer;
}
}
}
return {};
}
};
```
Time complexity: $O(n^2)$
:::danger
Time Limit Exceeded
:::
### Solution 2: Two Pointers
```cpp=
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> answer(2, 0);
int left = 0;
int right = numbers.size() - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
answer[0] = (left + 1);
answer[1] = (right + 1);
break;
} else if (sum > target) {
right--;
} else { // sum < target
left++;
}
}
return answer;
}
};
```
Time complexity: $O(n)$
【想法】
左右夾擠
## (E) [69 Sqrt(x)](https://leetcode.com/problems/sqrtx/)
Given a non-negative integer `x`, compute and return the square root of `x`.
### Solution 1: Brute force
```cpp=
class Solution {
public:
int mySqrt(int x) {
if (x == 0 || x == 1)
return x;
for (long root = 0; root <= x; root++) {
if (root*root > x) {
return (root - 1);
}
}
return -1;
}
};
```
Time complexity: $O(\sqrt{x})$
### Solution 2: Binary search
```cpp=
class Solution {
public:
int mySqrt(int x) {
long begin = 0;
long end = static_cast<long>(x);
while (begin <= end) {
long middle = (begin + end)/2;
if (middle*middle > x) {
end = middle - 1;
} else {
begin = middle + 1;
}
}
return (begin - 1);
}
};
```
Time complexity: $O(logx)$
【想法】
1. binary search: 找出最小的正整數 $c$，使得 $c^2 > x$
2. 則 $\sqrt{x} = (c - 1)$
## (E) [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)
Given `head`, the head of a linked list, determine if the linked list has a cycle in it.
### Solution1: HashTable (`unordered_set`)
```cpp=
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> record;
ListNode* current = head;
while (current) {
if (record.count(current)) {
return true;
}
record.insert(current);
current = current->next;
}
return false;
}
};
```
Time complexity: $O(n)$
Space complexity: $O(n)$
【想法】
看過的建築物又再看到一次，肯定是繞圈了
### Solution2: Fast + Slow pointers
```cpp=
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast) {
if (!fast->next)
return false;
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
return true;
}
return false;
}
};
```
Time complexity: $O(n)$
Space complexity: $O(1)$
【想法】
跑操場才有倒追，否則跑比較快的會先到終點
## (M) [102. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)
Given the `root` of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
### Solution 1: BFS
```cpp=
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root)
return {};
vector<vector<int>> levelOrder;
vector<TreeNode* > currentLevel, nextLevel;
currentLevel.push_back(root);
while (!currentLevel.empty()) {
levelOrder.push_back({});
for (TreeNode* node : currentLevel) {
levelOrder.back().push_back(node->val);
if (node->left)
nextLevel.push_back(node->left);
if (node->right)
nextLevel.push_back(node->right);
}
currentLevel = nextLevel;
nextLevel.clear();
}
return levelOrder;
}
};
```
Time complexity: $O(n)$
### Solution 2: DFS
```cpp=
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
DFS (root, 0);
return result;
}
private:
vector<vector<int>> result;
void DFS (TreeNode* root, int level) {
if (!root)
return;
while (result.size() <= level)
result.push_back({});
result[level].push_back(root->val);
DFS (root->left, level + 1);
DFS (root->right, level + 1);
}
};
```
Time complexity: $O(n)$
# 第三次作業-他評01(林宇庭-Austin)
**Interviewer**
- 優點
1. 有提出進階的問題
- 缺點
1. 和interviewee的對話偏少
2. 說明題目時，不知為何聽者好像沒辦法一次瞭解題目的意思
**Interviewee**
- 優點
1. 有執行REACTO的步驟
2. 第一題第一段的Repeat,Example和Approach所佔的時間很少，大概30秒就進入打code
3. 第一題第二段思考改進方法時，依然有記得按照REACTO的步驟
4. 邊打code也有邊解釋
5. 第二題第一段有解釋定義變數值域的原因
6. 第二題有考慮到邊界值的問題
- 缺點
1. (個人觀點)不喜歡看到簡體字：）
2. "應該是"的口頭禪聽起來不太肯定
3. 第一題沒有考慮到輸入為空的情況
4. 第一題第二段作改進時都是口頭解釋作法，可以在電腦上舉例說明會讓人更容易了解改進的方法
5. 第二題第一段講解Approach時可以在電腦上舉例說明會讓人更容易了解方法
6. 第二題第一段考慮邊界值的問題時有點不太清楚
7. 第一題第二段思考改進方法時，講解的不太清楚，如果使用REACTO會比較清楚
# 第三次作業-他評02
**Interviewer**
- 優點
1. 有follow up 問題給interviewee
- 缺點
1. 題目規範可以模糊一點，供interviewee藉由提問方式去清楚定義問題
2. coding 過程中未針對interviewee未講解清楚部分做提問
3. 缺少不同方法的比較及優缺點問題
**Interviewee**
- 優點
1. 有執行REACTO的步驟
2. Code 編寫能力流暢
- 缺點
1. 程式碼可以寫得簡潔些，多餘的變數不須額外定義
2. 第二題題目並未解釋清楚為何使用long
3. Repeat, Example 步驟未提供清楚的例子進行講解
4. 與interviewer 互動太少
# 第三次作業-他評03
+ **寫 Code 的部分非常流暢，也幾乎沒有完全安靜的空間，非常方便 Interviewer 理解 Intervieree 想做什麼。**
+ 通篇來說，Interviewer 幾乎只有朗誦問題的用處，說實話就算刪掉感覺也不構成大礙，下面會補上我認為可以問受試者的問題。
+ 我覺得頗有趣的是，在中國因為翻譯作的足夠完善，(雖然不是在程式界的經驗)我通常不會聽到名詞轉用英文的情形。但是這裡出現了中國用詞『數組』等等，卻又不用中國單詞的『索引』之類的。
+ Interviewer 的朗讀感非常重。我認為即使是 Interviewer 也應該會用比較口語的方式去敘述一個題目，又考慮到在敘述題目時應該 Interviewee 也該能看到文字說明，倘若還是複述的話其實根本沒必要。
+ Interviewee 與 Interviewer 有相同的問題，REACTO 裡的 "R" 應該指的是整理題目後清晰的說明自己的理解，而不是照著重念一次。
+ Interviewee 舉例的時候，應該要打在右方程式碼區域，而不是用滑鼠指。錄成影片都有點難跟了，如果是 LIVE 一定更困難。
## 第一題 Sorted Two Sum
### Interviewer
+ 『可以讓這個程式變得更快嗎』我覺得實在太明顯，或者說 $O(n^2)$ 本來就根本不可能是最佳解。一開始就限定解答的時間複雜度可以節省時間去問更有意義的問題，或讓 Interviewee 不『裝弱』。
+ 假設這個面試是指定使用 C++ 作答，我認為 Interviewer 應該同時會想知道 Interviewee 對 C++ STL 的理解，因此在撰寫 `for` 迴圈的時候我認為可以要求受試者使用 iterator 作答(殘酷一點順便叫他說明 iterator 的好處壞處)等等，看看 interviewee 到底有沒有對 C++ STL 有深入的理解。
+ 最後的統計上，使用的記憶體空間只贏過 35% 的使用者；可以問 Interviewee 到底輸給 65% 的使用者的原因為何？
### Interviewee
+ 1:38, 這裡又變成 "vector"，不是『數組』了XD
+ 超時的理由如果可以自己提出更好一點。
+ 6:00 左右說明時，『右邊的 pointer 往中間靠』『左邊的 pointer 往中間靠』不太精準，比如說 `[1, 2, 3, 5, 6], target = 3` 的狀況，答案的左右 pointer 都會存在『中間』的左側。應該說『往左/右靠』。
## 第二題 sqrt(q)
### Interviewer
+ 『請在不使用內建的函數或運算符號的情況下，撰寫一個求平方根整數部分的函數』就行了。
+ 這題的 $O(n)$ 到 $O(\log n)$ 的優化實在太明顯，和上一題有一樣的問題。
+ 在計算平方根的時候，乘法計算其實也會花掉許多時間。或許可以問問 Interviewee 『如果可以維持 O(n)的時間複雜度，你可以不用乘法，也不用迴圈模擬乘法，一樣解決問題嗎？』來考考 Interviewee 有沒有從 $n^2$ 求 $(n+1)^2$ 的數學能力。
+ `static_cast` 都出來了，當然可以問問『`const_cast` `dynamic_cast` `reinterpret_cast` `static_cast` 的差異』在哪裡之類的問題，一樣考驗 Interviewee 對 C++ 的認知。
### Interviewee
+ 更嚴重，說明的時候連滑鼠都不動了。假設 Interviewer 像我一樣聽人說話無法專心，但是看影像專心到不行，Interviewee 直接完蛋。
+ 很多『應該』，自信一點。
+ 11:05，`long` 的使用原因很奇怪。`long` 就是那個在各個 CPU Architecture 跟 OS 上會有不同大小的奇葩人，在 『Windows』 和 『IA-32 的 Linux』 上是 4 Bytes, 在 『Intel-64 的 Linux 和 max OS』 上是 8 Bytes，僅僅說『因為我們要把 int 平方所以我們用 long』反而會讓人暴露自己不太懂的東西。
- Standard 只規定 `int` 需 $\geq 16$ bit，`long` 需 $\geq 32$ bit，但 `long` 不一定比 `int` 大。
Sign in with Wallet
Connect another wallet