---
title: 2021 年資訊科技產業專案設計課程面試範例
tags: INFO2021
---
# 2021 年[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2021) 作業
> 貢獻者: Ellie
> ==[video](https://youtu.be/kjn-XAKecHk)==
## 自問自答紀錄
> :male-office-worker: : interviewer
> :female-student: interviewee
### [1. Two Sum](https://leetcode.com/problems/two-sum/)
:male-office-worker: : Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.(給你一個陣列 nums 和一個整數target，回傳兩個元素的index, 使得兩元素相加為 target)
:female-student: : 好的，所以是找出是哪兩個元素相加會等於整數 target，需要回傳兩個元素的index,我會將元素兩兩配對，檢查兩個數字相加後是否等於target
> 復誦問題 & 提出解法
:male-office-worker: : ~~寫出你的程式碼~~ 寫下你的程式碼並**解釋**
> **程式碼更簡潔:**
> 如果是要常用到 `nums.size()` 可以用變數 n 儲存陣列的大小 `int n = nums.size()`
> interviewee 要有測試範例，並提出特殊情況的測資，ex: 沒有找到答案
> interviewee 在寫程式碼時，可以解說最好以及最壞的情況下，會花多少時間得到答案
```cpp=
vector<int> twoSum(vector<int>& nums, int target) {
for(int i=0;i<nums.size()-1;i++) {
for(int j=i+1;j<nums.size();j++) {
if(target == nums[i]+nums[j]){
return {i, j};
}
}
}
return {0,0};
}
```
:male-office-worker: : 有更快的解法嗎?
:female-student: : 我認為可以將每個元素需要再加多少才會等於target的資訊儲存在 `hash table` 中，在之後的檢查中若發現有相符合的數字，即可兩兩配對，時間複雜度為 $O(n)$
:male-office-worker: : 為什麼這樣做比較快? 為什麼是 $O(n)$?
> 讓對方說明原因
:female-student: :
> 解釋 hash table 的特性，可以寫個例子來解說 hash table
:male-office-worker: : 寫出程式碼並解釋
```cpp=
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;// target-num, index
for(int i=0;i<nums.size();i++) {
if(map.find(nums[i]) == map.end()) {
map[target-nums[i]] = i;
}else {
return {map[nums[i]], i};
}
}
return {0,0};
}
```
### [169. Majority Element](https://leetcode.com/problems/majority-element/)
:male-office-worker: Given an array nums of size n, return the majority element.(給定陣列，回傳majority element)
The majority element is the element that appears more than ⌊n / 2⌋ times.You may assume that the majority element always exists in the array.(出現次數超過 n/2 次就是 majority element)
:female-student: : ok, 所以是找出出現次數大於n/2的元素，我會使用 `hash table` 紀錄每個數字出現的次數，再檢查是否大於 n/2, 時間複雜度為 $O(n)$
> 解說解法!
```cpp=
int majorityElement(vector<int>& nums) {
unordered_map<int,int> m;
int upper = nums.size()/2;
for(int i=0;i<nums.size();i++) {
if(m.find(nums[i]) == m.end())
m[nums[i]]=1;
else
m[nums[i]]+=1;
if(m[nums[i]]>upper) {
return nums[i];
}
}
return 0;
}
```
:male-office-worker: : ~~有沒有比較節省空間的方法呢?~~ 那有沒有其他可以改進的地方?
> 避免直接提出"節省空間的方法"
:female-student: : 有的，可以分成眾數以及其他數字，眾數的個數一定會大於其他數字的個數，ex: [1,1,1,2,3]，所以可以假定眾數為-1，計數器設成0，如果接下來的元素等於眾數，則計數器加一，如果不是則減一，但如果計數器等於零，表示這個數字並不是眾數，所以需要將眾數假定成跟他比較的數字，結束時，就可以得到真正的眾數。
> 節省空間: 需要提到原本的hash table需要花多少空間 & 解說摩爾投票演算法
```cpp=
class Solution {
public:
int majorityElement(vector<int>& nums) {
int ans=nums[0], cnt=1;
for(int i=1;i<nums.size();i++) {
if(nums[i] == ans) {
cnt++;
}else{
if(cnt==0) {
ans=nums[i];
cnt=1;
} else {
cnt--;
}
}
}
return ans;
}
};
```
### [229. Majority Element II](https://leetcode.com/problems/majority-element-ii/)
:male-office-worker: : find all elements that appear more than ⌊ n/3 ⌋ times.(如果我要能夠得到出現次數超過 n/3 次的元素呢?)
:female-student: : 恩... 我認為我需要一些提示
:male-office-worker: 你認為回傳的 element 會有幾個?
:female-student: : 有可能是一個、兩個或是都沒有，最多就是兩個，那我知道了，我可以先找出前兩個出現次數最多的元素，再檢查這些候選元素的個數是否大於 n/3
```cpp=
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int a1=-1, a2=-2, c1=0, c2=0;
for(auto& x:nums){
if(x==a1) c1++;
else if(x==a2) c2++;
else if(c1==0) {
a1=x;
c1=1;
}else if(c2==0) {
a2=x;
c2=1;
}else{
c1--;
c2--;
}
}
c1=0,c2=0;
for(auto& x:nums){
if(x == a1) c1++;
else if(x == a2) c2++;
}
int n=nums.size();
vector<int> v;
if(c1>n/3) v.push_back(a1);
if(c2>n/3) v.push_back(a2);
return v;
}
};
```
---
## 第三次作業 - 他評01
### Interviewer :
#### 優點 :
[06:26](https://youtu.be/kjn-XAKecHk?t=386) 有對改進的方法做出適當的提問。
#### 缺點 :
[00:00](https://youtu.be/kjn-XAKecHk) 面試官應先自我介紹，並敘述面試的流程，而不是直接開始問題的敘述。
[10:16](https://youtu.be/kjn-XAKecHk?t=616) 可以在多問一些問題，而不是直接跳到下一道題。
### Interviewee :
#### 優點 :
[12:12](https://youtu.be/kjn-XAKecHk?t=733) 明確的表示要對演算法哪個部分做改善。
[12:47](https://youtu.be/kjn-XAKecHk?t=767) 舉多個例子來解釋改進的演算法，可以很快地了解改善的方法。
#### 缺點 :
[02:35](https://youtu.be/kjn-XAKecHk?t=155) 函式的輸入應該為是 vector<int>，而不是 vector<int, int>; 再者回傳值不太適合用 vector <int, int>，應為 vector<int>。
[16:10](https://youtu.be/kjn-XAKecHk?t=970) 撰寫程式碼的時候，適當調整行距及頁面，使得程式碼能夠完整出現在畫面上，解說得效果會更好。
---
## 第三次作業 - 他評02
### Two Sum
#### Interviewer
* [0:02](https://youtu.be/kjn-XAKecHk?t=2) 可以舉出情境題，例:某次化學老師為了做實驗，想幫同學分組，又不希望每組的平均實力相差太大，因此想找一組2人，並且2人的化學期中考的分數加總為80(target)，於是老師從化學成績單的1號學生開始找起。
* [1:43](https://youtu.be/kjn-XAKecHk?t=103) 若找不到兩數和等於 target，應該先講要回傳 {-1,-1}。
* 可以試問若答案不只有1個的情況，或是重複的答案如何解決?
* 可以試問 Two Sum 的變形題，並問解決 Two Sum 的方法是否能套用? ex: 15. 3Sum, 18. 4Sum。
#### Interviewee
* [1:04](https://youtu.be/kjn-XAKecHk?t=64) 有舉出淺顯易懂的例子，並詳細說明。
* [2:55](https://youtu.be/kjn-XAKecHk?t=175) 避免「要寫兩條迴圈」，會讓人感覺在背答案。試著邊解說演算法，邊寫出程式碼。
* [4:33](https://youtu.be/kjn-XAKecHk?t=273) 有討論到暴力解在最好和最壞的情況所花的時間。
* [6:47](https://youtu.be/kjn-XAKecHk?t=407) 直接說 hash table 找值花的時間為 O(1) 即可。
### Majority Element
#### Interviewer
* [10:18](https://youtu.be/kjn-XAKecHk?t=618) 一樣可舉出情境題，例:某天班會，洛克班上要選班長，投票規則如下:班上每人在紙上寫一名同學名字，並放入投票箱，最後開票票數超過班上人數的一半的同學，即為班長，假設必有一人的票數必超過班上人數的一半。
* [11:43](https://youtu.be/kjn-XAKecHk?t=703) 在問到優化的部分，要 Interviewer 思考哪個地方可改進，不會立刻提醒 Interviewer 空間複雜度可改，使兩者之間的互動更頻繁。
#### Interviewee
* [12:25](https://youtu.be/kjn-XAKecHk?t=745) 講解摩爾投票演算法時，若能把例子裡面所有元素全部跑過一遍，可使人更容易了解。
---
## 第三次作業 - 他評03
### 針對 interviewer :
優點：
* 明確指出自己的期許
缺點：
* 沒有說清楚題目要求(例如會不會有重複的值、會不會有負值等)
* 沒有追問其他的相關問題(如3sum或其他變化)
### 針對 interviewee :
優點：
* 有完整使用到 REACTO
* 舉例時講到的東西都有記下來，讓聽的人更容易理解
缺點：
* 應針對投票演算法的時間複雜度做更多說明
## 第三次作業-他評04
### interviewer
優點
- 有詢問interviewee為什麼改進方式能更好。
缺點
- 沒有針對 interviewee 的程式碼做檢討。
- [11:43](https://youtu.be/kjn-XAKecHk?t=703) 「有沒有可以改善的地方 」會給 interviewee 不太明確的方向，建議可以換成「針對時間(or空間)複雜度，有沒有可以改善的地方」。
### interviewee
優點
- 將重點程式碼完成並詳細解說，沒有花過多的時間寫細節。
- 在講解的時候有使用簡單的 example 讓 interviewer 了解想法。
- 整體面試的過程流暢，邏輯清晰，沒有贅詞。
缺點
- [14:00 - 15:30](https://youtu.be/kjn-XAKecHk?t=880) 這段講解的很清楚但太細節，在上面講解演算法，interviewer應該已能理解你的想法了，大約15行程式碼，花了1分半。
- 沒有詢問 interviewee 題目有沒有constraints，可能會造成寫完發現沒有滿足interviewer的要求。
## 第三次作業-他評05
### interviewer
優點
- 有對 Hashmap 提出延伸性的問題
缺點
- 和 Interviewee 的互動偏少，可針對程式碼做提問
- [11:43](https://youtu.be/kjn-XAKecHk?t=703)只說有沒有可改進的地方比較籠統，可提出式想對空間或時間複雜度等級做改善
### interviewee
優點
- 再做題目時有做到 REACO
- 第一題給出第二種解法時沒有急著寫code，而是先把想法說清楚
缺點
- 解題前可先問問看有沒有其他要注意的部分，例如 array 範圍等等，解完題目後沒有 Test
- [6:45](https://youtu.be/kjn-XAKecHk?t=405) 說明 hashmap 的時間偏長
- [13:45](https://youtu.be/kjn-XAKecHk?t=815) Interviewee 說完兩種方法，可分析優缺點，再問 Interviewer 想要看到哪一種後再開始寫 code
---
## 第三次作業-他評05
### interviewer
* 面試官開頭應先確認interviewee是否已經準備好或是確認姓名等等，而不是一開始就直接講題目。
* 針對題目的敘述可以再多做說明，比如是否有唯一解、值是否會重複等等。
* 第二題interviewer說: 那有沒有可以改進的地方。偏籠統，可以具體說明一點，比如時間或空間複雜度，
### interviewee
* 可以表現得再更有自信一點，講話有點虛。
* 舉出的例子都有完整寫下來且易懂。
* 語速可以再快一點點，因為一次解釋的東西很長，但語速太慢的話可能interviewer會不耐煩。
---
Sign in with Wallet
Connect another wallet