---
title: 2021 年資訊科技產業專案設計課程面試範例
tags: INFO2021
---
# 2021 年「資訊科技產業專案設計」
> 貢獻者: 姜西難 JohnCena
> ==[video](https://youtu.be/mVaY4qcUhHI)==
## Leetcode P108 Convert Sorted Array to Binary Search Tree (Easy)
> link: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
### Problem
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
### My Answer
這次主要做出變化的就是在這一題。
1. 改成 C++
2. 有讓面試者提要求，希望能增加 function 的參數，使我們不需要額外定義helper function.
3. 面試官額外再問了如果要forloop的話，stack的element要怎麼定義。
- recusion code:
```cpp=
TreeNode* sortedArrayToBST(vector<int>& nums, int l=0, int r=INT_MAX) {
if(l>r) return NULL;
if(r==INT_MAX) r = nums.size() - 1;
int mid = (l + r) / 2;
return new TreeNode(
nums[mid],
sortedArrayToBST(nums, l, mid-1),
sortedArrayToBST(nums, mid+1, r)
);
}
```
- define struct for stack element
```cpp=
class stackElement{
public:
TreeNode* parent;
int direction;
int leftBoundary;
int rightBoundary;
stackElement(TreeNode* parent, int dir, int l, int r):
parent(parent), direction(dir), leftBoundary(l), rightBoundary(r) {}
};
```
## Leetcode P2 Add Two Numbers(Medium)
> link: https://leetcode.com/problems/add-two-numbers/
### Problem
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.
### MyAnswer
這次去掉了面試者一開始前面用比較爛方法寫的橋段，而是從寫錯code開始，基本上跟上一次大同小異。
- ```python=
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummyhead = ListNode()
curr = dummyhead
while l1 or l2:
num = (l1.val if l1 else 0) + (l2.val if l2 else 0)
curr.next = ListNode(num%10)
if l1: l1 = l1.next
if l2: l2 = l2.next
curr = curr.next
return dummyhead.next
```
被面試官指出過後
- ```python=
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummyhead = ListNode()
curr = dummyhead
carry = 0
while l1 or l2 or carry:
num = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
curr.next = ListNode(num%10)
carry = num // 10
if l1: l1 = l1.next
if l2: l2 = l2.next
curr = curr.next
return dummyhead.next
```
## 第二次檢討
- 主要變化是在 array_to_bst 的部分，讓面試者不只是問問題，還有提要求希望可以改這個function的definition，不過蠻久沒寫c++，也不常寫，所以不知道寫法好不好。
- 剩下兩題其實直到最後我還是沒法選出一個比較好再做更進階的題目，本來有想加面試官要求將程式碼縮得更短的橋段(如下方code)，不過**縮短真的有比較好嗎**? 這我真的不知道，所以沒有加。
- ```python=
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummyhead = curr = ListNode()
carry = 0
while l1 or l2 or carry:
num = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
curr.next, carry = ListNode(num%10), num // 10
if l1: l1 = l1.next
if l2: l2 = l2.next
curr = curr.next
return dummyhead.next
```
# 資訊科技產業專案設計 HW1
## Leetcode P70 Climbing Stairs(Easy)
> link: https://leetcode.com/problems/climbing-stairs/
>
### Problem
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
### My Answer
我自己所能想到的其實就四種，其中在影片中使用的方法一開始是 第一種，接著被面試官問完後才改成第二種方法。
1. for loop with dp
- Time: $O(N)$
- Space: $O(N)$
- 雖然兩種複雜度看起來都跟遞迴一樣，但實際上每一次的iteration少了一些判斷跟function call的動作，所以實際上會比較快，記憶體量也比較少
- ```python=
def climbStairs(n: int) -> int:
if n < 3: return n
dp = [1, 2]
for i in range(3, n+1):
dp.append(dp[n-1] + dp[n-2])
return dp[n-1]
```
7. for loop
- Time: $O(N)$
- Space: $O(1)$
- ```python=
def climbStairs(n: int) -> int:
if n < 3: return n
a, b = 1, 2
for i in range(3, n+1):
a, b = b, a+b
return b
```
## Leetcode P108 Convert Sorted Array to Binary Search Tree (Easy)
> link: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
### Problem
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
### My Answer
這個問題我寫完以後，原以為會有別種解法，不過我想不太到，在LeetCode上翻來覆去大家也都差不多，所以就這一種吧。
```python=
def sortedArrayToBST(nums: List[int]) -> Optional[TreeNode]:
def create_tree(l, r):
if l > r: return None
mid = l + (r - l) // 2
return TreeNode(
nums[mid],
create_tree(l, mid-1),
create_tree(mid+1, r)
)
return create_tree(0, len(nums)-1)
```
- Time: $O(N)$
- Space: $O(N)$
- code中的 `mid = l + (r - l) // 2` 可以替換成 `mid = (l+r)//2`
## Leetcode P2 Add Two Numbers(Medium)
> link: https://leetcode.com/problems/add-two-numbers/
### Problem
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.
### MyAnswer
在影片中，我使用了兩種寫法
2. 直接在一個for迴圈讀取兩個LinkedList的值並建造我們回傳的LinkedList，且不能忘了要做進位的運算
- Time: $O(N)$
- Space: $O(N)$
- ```python=
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummyhead = ListNode()
curr = dummyhead
carry = 0
while l1 or l2 or carry:
num = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
curr.next = ListNode(num%10)
carry = num // 10
if l1: l1 = l1.next
if l2: l2 = l2.next
curr = curr.next
return dummyhead.next
```
兩者都是 $O(N)$，但可以看到第二個寫法較為簡潔，且不會做到大數的運算，以及 call function。
## 初步檢討
1. 錄製品質先不管的話我覺得我表現還不錯
2. 影片寫code的部分似乎太冗長了
3. 英文真的要多加練習，講話超卡
# 第三次作業 他評
* 影片整體節奏很快，建議放慢速度，增加 interview 雙方的互動
* interview 雙方對於題目的共識取得過於容易，建議增加溝通過程
* 解題過於快速，沒有展現出思路，建議透過圖例以及放慢解說過程來進行解題。
# 第三次作業 他評2
* 在講解的時候邊說邊有搭配著手勢，更容易能夠理解想表達的概念
* 3:54的時候因為後製擋住部分程式碼，不過還是可以清楚理解，且實際面試的過程中應該不會遇到這個問題
* 於Stack的撰寫上，可以用一個舉例會比較容易理解程式碼是如何運作
* 在addTwoNumbers的題目中，interviewee和interviewer的互動還不錯，不過可以舉一些例子來讓程式的想法更加清晰，也可以用於驗證程式碼是否正確
# 第三次作業 他評3
## 面試過程檢討
### 總體
* 人物有經過變裝，口吻也稍有改變，容易看出差別。
* 人家中文叫做[趙喜那](https://www.youtube.com/watch?v=TBR0wEWmx2U)，不是江西難。
* 依照課堂需求應該使用如Google document來增加撰寫程式碼的困難度，影片中使用 **sublime** 不符合要求。
* 影片內容簡潔，不會硬要把程式寫完，概念說明完整便結束。
* 片尾有彩蛋
* 應該要有三題，可是只有兩題。
### **Interviewer**
* 題目講解快速，沒有浪費過多時間舉例而浪費面試時間。
* 直接回答『應該是歐。』聽起來不太專業。
* [2:15](https://www.youtube.com/watch?v=mVaY4qcUhHI&t=135) 在撰寫程式時建議可以再說明清楚一點，因為使用遞迴方式若沒有說明不易明白。
* [3:12](https://www.youtube.com/watch?v=mVaY4qcUhHI&t=192) 這裡詢問面試者改成非遞迴的形式，不應該直接說可以用 **stack** 來實作，應該用引導的方式跟 **Interviewer** 互動。
* [6:58](https://www.youtube.com/watch?v=mVaY4qcUhHI&t=418) 這裡 **Interviewer** 適時提點程式所缺漏所缺漏的部分關於數值上的限制，很不錯。
### **Interviewee**
* 有先跟 **Interviewer** 進行討論，而非埋頭寫程式，看得出思考的脈絡。
* [2:15](https://www.youtube.com/watch?v=mVaY4qcUhHI&t=135) 在撰寫程式時建議可以再說明清楚一點，因為使用遞迴方式若沒有說明不易明白。
* [5:28](https://www.youtube.com/watch?v=mVaY4qcUhHI&t=328) 提到解題用到 **Dummy Head** 的部分，可以再說清楚一點使用的原因會更佳。
# 第三次作業 他評4
### 整體
[3:48](https://youtu.be/mVaY4qcUhHI?t=228) 馬賽克遮到程式碼了
### Interviewer
[0:49](https://youtu.be/mVaY4qcUhHI?t=49) 避免使用「應該是哦」的回答來回應 interviewee，這樣會讓別人覺得 interviewer 不夠專業
[2:28](https://youtu.be/mVaY4qcUhHI?t=148) 沒有對 `(l + r) / 2` 潛在 overflow 的問題提出疑問
[3:17](https://youtu.be/mVaY4qcUhHI?t=197) 應該避免直接將解法於出題時一併說明，這樣會減少與 interviewee 互動的機會，也無法確認 interviewee 關於資料結構相關的認知
[4:26](https://youtu.be/mVaY4qcUhHI?t=266) 可以針對 interviewee 提出的要加上 direction 的變數的說明進行詢問
### Interviewee
[0:27](https://youtu.be/mVaY4qcUhHI?t=27) 避免過度依賴手勢來說明想法
[3:08](https://youtu.be/mVaY4qcUhHI?t=188) 完成程式碼後，可以利用一些邊界的測資來檢驗程式碼的正確性
[4:07](https://youtu.be/mVaY4qcUhHI?t=247) interviewee 可以針對 interviewer 提出的情境進行進一步的討論，而不需要急著將程式碼寫出來，而錯失了與 interviewer 互動的機會
# 第三次作業 他評5
### 總體
節奏掌握得還蠻好的，並且口條清晰，整個面試過程非常迅速
interviewee應該全程同時存在電腦畫面以及攝影機鏡頭畫面，這樣講解也會比較方便
### interviewer
[0:48](https://youtu.be/mVaY4qcUhHI?t=48) interviewer的口吻太不確定，可能會被interviewee看不起
[3:16](https://youtu.be/mVaY4qcUhHI?t=196) 可以不用主動提示stack，詢問如果不用遞迴該如何實作
[4:51](https://youtu.be/mVaY4qcUhHI?t=291) 講解題目時感覺是直接將英文題目翻譯成中文，敘述上有點不清楚，讓人難以理解。
[5:20](https://youtu.be/mVaY4qcUhHI?t=320) interviewee說的approach沒有很清楚，可以追問interviewee時做細節
### interviewee
[0:48](https://youtu.be/mVaY4qcUhHI?t=48) 可以加上圖示的Example，後續說明較為清楚
[3:08](https://youtu.be/mVaY4qcUhHI?t=188) 可以再用一組測試資料說明程式是如何運作的
[4:24](https://youtu.be/mVaY4qcUhHI?t=264) 可以再簡單地說一下測試資料進入for迴圈會如何運作
[5:00](https://youtu.be/mVaY4qcUhHI?t=300) 優點，有追問interviewer沒有說清楚的細節
[5:13](https://youtu.be/mVaY4qcUhHI?t=313) 可以舉一些不同的例子來確認題目該如何運作，並方便後面講解
[5:20](https://youtu.be/mVaY4qcUhHI?t=49320) 解釋approach的部分沒有很清楚，可能需要搭配例子來做說明會更好
[6:08](https://youtu.be/mVaY4qcUhHI?t=368) 之前應該先寫上一組例子，這樣寫程式的時候可以對照著例子來寫，程式邏輯會更為清楚。
# 第三次作業 他評6
### Interviewer
1. 第二題interviewer應該避免直接點出沒有處理進位這個問題，應讓interviewee自己去發掘程式碼的潛在問題
2. 沒有對 (1+r) / 2 存在潛在overflow問題提出質疑
### Interviewee
1. 程式碼簡潔，口條清晰
2. 講解Example 及 Approach 可以帶入例子，會更加清楚
Sign in with Wallet
Connect another wallet