---
title: 2021 年資訊科技產業專案設計課程面試範例
tags: INFO2021
---

# 2021 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2021)」面試範例

> 貢獻者: 捷安森
> ==[video](https://youtu.be/-taEse-rviU)==

### 測驗 `1` LeetCode `226`

一棵樹的結構定義為:

 struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
  };

### 方法一
* 使用 recursive
* 先反轉 root 的左邊和右邊
* `invertTree`: 反轉剩餘尚未反轉的子樹
* Time complexitty:O(N)

對應的程式碼如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* invertTree(struct TreeNode* root){
if(root==NULL)
    return NULL;
struct TreeNode * temp=root->left;
root->left=root->right;
root->right=temp;
invertTree(root->left);
invertTree(root->right);
return root;
}

### 方法二

* 使用 iterative
* 檢查root是否為NULL，是的話直接回傳NULL
* 建立一個 queue
* 將root放入queue中
* 每次從queue中取出一個節點，將其左右位置互換，
並分別將左右節點中非NULL的節點放入queue中
* 重複直到queue中沒有節點
* 回傳root
* Time complexitty:O(N)

### 測驗 `2` LeetCode `237`

一個點的結構定義為:

struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };

### 方法1
* 單向linkly list
* 將被刪除節點的下一個節點的值複製並蓋掉被刪除節點的值
* 將被刪除節點的 next 連結指向下一個再下一個的節點
* Time complexity O(N)

對應的程式碼如下:

  struct ListNode {
      int val;
      struct ListNode *next;
  };
 
void deleteNode(struct ListNode* node) {
    node->val=node->next->val;
    node->next=node->next->next;
}

### 方法2
* 雙向linkly list
* 有 previous & next pointer 可以指向想指的 node
* Time complexity O(1)

### 測驗 `3` LeetCode `215`

* 使用Quick Sort方法，找第k大的數字。依Quick Sort原理，會將陣列做部分排序，這裡從大排到小。把陣列最左邊的值當作 pivot 值，從左邊與從右邊分別找出比pivot還小 / 還大 互相交換，會分成2個區塊，再判斷k位置繼續往左邊或右邊尋找。

* ex:

對應的程式碼如下:

 void swap(int *a ,int *b)
{
    int temp=*a;
    *a=*b;
    *b=temp;
}
 int quickSelect(int  *nums,int k, int left ,int right)
{
    int pivot=nums[left];
    int i=left;
    int j=right;
    while(i<=j)
    {
        while(nums[i]>pivot)
            i++;
        while(nums[j]<pivot)
            j--;
        if(i<=j)
        {
            swap(&nums[i],&nums[j]);
            i++;
            j--;
        }
    }
    if(left<j && k<=j)
        return quickSelect(nums,k,left,j);
    if(right>i && k>=i)
        return quickSelect(nums,k,i,right);
    return nums[k];
}

int findKthLargest(int* nums, int numsSize, int k){
  return quickSelect(nums,k-1,0,numsSize-1);
}

## 第三次作業-他評01(捷安森-Johnathan)
**Interviewer**
- 優點
1. 有嘗試和interviewee互動

- 缺點
1. 說話避免中英夾雜
2. 和interviewer的互動較少
**Interviewee**
- 優點
1. 第一題開頭在電腦上將所舉的例子打出來，讓人更好理解

- 缺點
1. 講話有點"顫抖"的感覺，聽起來很緊張
2. 打字和說話的間隔太久，空氣凝結了
3. 輪到interviewee表現時，因為沒有使用REACTO所以沒辦法一次聽完Approach，不好理解
4. 對齊程式碼花了太多時間
5. 第一題第二段改進時，僅口頭講解，對聽者來說很難完全理解
6. 因為沒有一次講完Approach所以Coding到一半會停下來繼續講解Approach，會讓人很難理解方法和看懂code
7. 第二題第一段結束時說"這就是我目前的寫法"，聽起來很像我已經準備好更好的寫法等你來問了：）
8. 第二題最後好像是interviewee"我們這題討論到這邊"，好像怪怪的

## 第三次作業 - 他評02

* 語調太過低沉，講話看起來並沒有什麼活力，可以試著提高音量或語調來改善。
* 第二題 時間複雜度講錯，並不是 O(N)，而是O(1)。
* 雙方並沒有太多的其他互動。

### Interviewer :

* 每次提問都是時間複雜度，應該可以問其他的更深入的東西。
* 面試者提出改進的方法後，並沒有提出相關的問題。
* 第二題的問題描述敘述有點問題，題目是直接給予要被刪除的節點，並非給予鏈結串列。

### Interviewee :

* REACTO 步驟並沒有確切的完成。
* 第一題改進的方法，其實可以用舉例來說明，會更加的清楚。
* 影片最後 "這題的討論目前到這"，這句話應該不是面試者該講的東西。

## 第三次作業 - 他評 03

### 針對 interviewer :
* 不應該只問有沒有其他方法可解，也要提出自己期待的解法，例如希望使用 iterative 的方式，或者希望對哪方面做優化
* 沒有追問其他的相關問題
* 在討論時直接問「針對這題有沒有其他想法」，但沒有給出方向，可能會讓 interviewee 不知如何回答、導致雙方在原地轉圈
* 直接接受 interviewer 提出的雙向連結做法，沒有做更深入的討論

### 針對 interviewee :
優點：
* 有使用 REACTO
* 有提出雙向連結的改進方式

缺點：
* 花太多的時間在舉例
* 有提到說使用 queue 可以只用一個，使用 stack 需要兩個，因為 queue 是先進先出，stack 是後進後出。但反轉二元樹應該無關先後順序，使用一個 stack 也可以做到（？

## 第三次作業 - 他評 04

### interviewer :

* [5:55](https://youtu.be/-taEse-rviU?t=355), [11:00](https://youtu.be/-taEse-rviU?t=660) 提問可以更加具體，並明確具有考驗受試者的目的性，例如: 是否可以不使用遞回的方式解題。
* [7:05](https://youtu.be/-taEse-rviU?t=425) 可以進一步詢問如何使用兩個 Stack 達到與 Queue 同樣的效果，或討論其他資料結構的延伸問題。

### interviewee :

* [0:28](https://youtu.be/-taEse-rviU?t=28), [7:38](https://youtu.be/-taEse-rviU?t=458) 可以先說明現在正在舉例，否則聽者可能一頭霧水。
* [0:28](https://youtu.be/-taEse-rviU?t=28) 畫 binary tree 的時間有點久，聽者可能失去耐心。
* 可以先大致講解解題流程再開始寫程式。
* 盡量避免使用 "覺得"、"應該" 等具不確定性的詞。
* 寫程式過程的沉默可能讓聽者坐不住，可以嘗試邊寫邊解說，或盡量加快打程式的速度。

## 第三次作業 - 他評 05

### 總體
interviewee常常不說話只打字，應該要邊說話邊打字
interviewee說話時不太清晰且有點小聲，像在碎碎念，可以讓咬字清楚一點
[7:06](https://youtu.be/-taEse-rviU?t=426) 原始題目有提到一個假設，給定的node不會是最後一個node，interviewer跟interviewee討論時應該將這個假設加進去，否則解法會有問題

### interviewer
[1:08](https://youtu.be/-taEse-rviU?t=68) 應該先詢問interviewee準備如何實作
[8:21](https://youtu.be/-taEse-rviU?t=661) 應該詢問interviewee要如何實作的細節

### interviewee
[0:28](https://youtu.be/-taEse-rviU?t=28) 花了快30秒寫例子，時間有點太長了，可能可以在寫例子的同時敘述問題以及interviewer的思路
[1:13](https://youtu.be/-taEse-rviU?t=73) 應該先敘述準備如何實作
[7:40](https://youtu.be/-taEse-rviU?t=460) 例子中的箭頭可以簡化，原本是------>，可以改成->，這樣不會花太多時間在打字上
[8:15](https://youtu.be/-taEse-rviU?t=495) 只說了利用這種作法，應該詳細說明自己準備要做甚麼(例如本篇作者在hackmd中寫到的 "將被刪除節點的下一個節點的值複製並蓋掉被刪除節點的值
將被刪除節點的 next 連結指向下一個再下一個的節點")
[10:45](https://youtu.be/-taEse-rviU?t=645) 這份程式由於沒有將預訂要刪除的node delete掉，可能會產生memory leak的問題，interviewee可能需要講清楚
[11:05](https://youtu.be/-taEse-rviU?t=665) 本題input是要刪除的節點，不用一個個搜尋，所以不論哪一種方法，時間複雜度都應該是O(1)

## 第三次作業 - 他評 06

### interviewer

#### 可改進的地方
- 聲音有點悶，會讓人聽不清楚在講什麼，可能音量要提高一點或是講清楚一點。
- 只是單純講述題目，沒有後續延伸或是變化題型，有點可惜。

### Interviewee

#### 優點

- 舉例完整，也用實際打出來讓interviewer知道例子的運作。

#### 可改進的地方

- 程式概念是清楚的，但是一樣聲音沒辦法讓人知道是在講什麼，所以讓人無法清楚知道要表達的意思。
- 不確定的口頭禪要有點多了，應該、也許這種會讓人感覺你自己也不確定。

{%hackmd 2eMtcAv6R4ax6MC71u_XMQ %}

## 第三次作業 - 他評 08

#### 優點
- 看得出捷安森很緊張，但是仍然保持邏輯，舉出例子輔以解釋。
- 一邊撰寫程式一邊解釋想法。

#### 可改進
- 語調低沈無力，在視訊面試中透過麥克風收音又更為明顯，不僅是沒有活力的問題，也會造成理解上的困難。
- google doc應該調整為全螢幕，縮放可以縮到150畫面會更為清楚。
- 老師上課提到的在畫面上透過打字表達二元樹還是需要再練習才能更流暢明確。
- 在撰寫程式碼時，程式碼的縮排不一會讓Interviewer看得不太舒服。
- [5:35](https://youtu.be/-taEse-rviU?t=335) Interviewer問到：你使用方法的時間複雜度是什麼呢？ 老師上課說過這樣的問法不太適當，應該問時間複雜度是什麼等級。
- 應避免太多模稜兩可(可能、應該)之類的贅詞
- [5:54](https://youtu.be/-taEse-rviU?t=354) Interviewer問到：這題，你還有其他的方法可以解嗎？ 應該在討論時間複雜度後認為這樣方法還不夠好，那有沒有其他可以改善效能的方法，直接這樣問感覺就是雙方在套招演出一樣。
- [6:01](https://youtu.be/-taEse-rviU?t=361) Interviewee瞬間就提出要用queue去迭代，既然你這麼快就有想法，這本身就有問題，這表示你一開始在遇到題目時就應該先確認方法是不是Interviewer要的，根據REACTO的步驟，就可以避免一些無意義的討論跟時間。
- 第一題，針對Interviewee提出的方法，Interviewer完全沒有討論或是給出想法建議，突然就切掉蠻錯愕的。
- 應該大部分面試比較少會說鏈結串列，某些term還是直接說英文大家會比較理解，可以直接用Linked List。
- 根據REACTO的步驟，在確認題意後給出方法描述，可以先和Interviewer討論是否ok，在開始實作也不遲．
- [10:48](https://youtu.be/-taEse-rviU) Interviewer問到：針對剛剛使用的方法，你認為時間複雜度是多少呢？ 一樣的問題，這樣的問法還是不太適當。
- 後面在問其他解法時可以看出搞錯題目了，這題刪除是直接給你欲刪除的節點，不給你head去讓你搜尋節點位置再刪除，相對是比較簡單的問題，時間複雜度的分析應該也是錯的，應為O(1)，可以更簡潔不去更動val，直接指向下一個node即可。

    *node = *node->next;