2023 年「資訊科技產業專案設計」作業 1

貢獻者: 朱舞花-Flowey
🧔：interviewer
👶：interviewee

模擬面試錄影: 漢)
模擬面試錄影: 英

144. Binary Tree Preorder Traversal

面試過程

🧔：第一題我們給一個二元樹，請寫一個程式回傳這個 Binary Tree 的 Preorder Traversal (前序追蹤)，並請說明時間複雜度。
👶：好的，那麼 Preorder Traversal 的走訪順序是 root

$\to$ 左子樹

$\to$ 右子樹，那我先撰寫描述節點的結構體，再用另一個結構體來配置記憶體空間給節點最後是印出 Preorder Traversal 的程式，以root

$\to$ 左子樹

$\to$ 右子樹的順序讓程式遞迴直到走訪所有節點，這樣因為所有的節點都走過一遍所以時間複雜度是

$O(n)$。

struct node {
	int data;
	struct node *left;
	struct node *right;
};

struct node* new_node(int data){
	struct node* node = (struct node*)malloc(sizeof(struct node));
	node->data=data;
	node->left=NULL;
	node->right=NULL;
	return(node);
};

void printPre(struct node *node){
	if(node == NULL) return;
	print(“%d”,node->data);
	printPre(node->left);
	printPre(node->right);
}

int main(){
	printPre(root);
}

🧔：請再寫出非遞迴的方式。
👶：那麼非遞迴的方式，代表node和配置空間用的struct不動，修改印出Preorder Traversal的程式就好，我用stack來實作，使用stack時要注意一下處理node的順序變成先印出root→將右子push進stack→將左子push進stack，且每次印出node之後就把該node給pop掉，直到stack為空(沒有node)。

struct node{
	int data;
	struct node *left;
	struct node *right;
};

struct node* new_node(int data){
	struct node* node = (struct node*)malloc(sizeof(struct node));
	node->data=data;
	node->left=NULL;
	node->right=NULL;
	return(node);
};

void printPre(struct node *node){
	if(node == NULL) return;
	stack <node*> nodeStack;
	nodeStack.push(root);
	while(nodeStack.empty()==0){
		struct node *node=nodeStack.top();
		printf(“%d”,node->data);
		nodeStack.pop();
		
		if(node->right)nodeStack.push(node->right);
		if(node->left)nodeStack.push(node->left);
    }
}

int main(){
	printPre(root);
}

1791. Find Center of Star Graph

面試過程

🧔：第二題我們給一個Star Graph，請寫一個程式回傳這個Star Graph的Center(中心點)，另外希望這個程式盡量簡短。
👶：我的想法是因為Star Graph的中心點會出現在圖中每一條edge連接的兩個node其中之一，所以任選兩條edge中他們重複連接的node必定就是Center，這樣也可以盡量精簡程式。

int findCenter(int[][] edge){
	int a=edge[0][0];
	int b=edge[0][1];
	if(a==edge[1][0]||a==edge[1][1])return a;
	else return b;
}

287. Find the Duplicate Number

面試過程

🧔：Hello, I am your interviewer, now I have a question for you, please provide your solution.
Given you an array of integers nums containing n + 1 integers, each integer is in the range [1, n]. There is only one repeated number, please return this repeated number.
👶：Ok, I want to contrast them one by oneby using two for loops.

int findDup(int[] nums){
	int len=num.length;
	for(int i=0;i<len;i++){
	    for(int j=i+1;j<len;j++){
	    if(nums[i]==nums[j]) return nums[i];
        }
    }
    return len;
}

🧔：Your solution is Brute Force, the time complexity is

$O(n^2)$. Can you write a better solution for this question?
👶：Ok,umm…let me think about it…
I think I can use Floyd cycle detection algorithm to solve this problem, The idea of this algorithm is we use two integers, slow and fast. They go forward one and two steps respectively, then if only one integer is repeated, it must has a cycle in this array, so we mention above, the two integers slow and fast must met each other at the same point.
So the first loop we can finally find the repeated number.
In the last loop, first we move slow to the initial position, then we start moving slow and fast until they met again, finally we can return slow or fast as answer. The time complexity can be reduced to N.

int findDup(int* num,int numSize)
{
    int slow=num[0];
    int fast=num[0];

    while(1){
        slow=num[slow];
        fast=num[num[fast]];
        if(slow==fast) break;
    }
    
    slow=num[0];
    
    while(slow!=fast){
	 slow=num[slow];
	 fast=num[fast];
    }
    return slow;
}

初步檢討

• 程式的撰寫過程可以再解釋得更清楚一些，將思路跟使用的實作方式描述得更具體。
• 回答問題時有點太過口語化且停頓太久。
• 可以在寫程式時多善用註解，讓interviwer更便於理解。
• 避免冗言贅字和過多的語助詞。
• 等到interviwer確實了解interviwee的解題方法後再開始撰寫程式。
• 使用的引數、陣列、變數等等的功能應該要更清楚地解釋給interviwer。
• 英文口說需要再加強。
• 英文面試題程式部分忘了講下面return len才是正確的答案回傳值。
• interviwer發問不精簡。

改善方法

• 先將思考過程告知interviwer再開始撰寫程式。
• 語助詞可以適度使用以爭取思考時間，但不宜太頻繁出現。
• 可將思考方向先當作註解寫在程式上，減少混淆也能解釋程式。
• 多練習英文聽力及口說。
• 可與interviwer交流確認題意，並解釋程式的功能、使用的變數等等。

---

第二次作業-他評 01

關於 interviewer

• 優點

• 說話清晰
• 說話速度中等
• 08:58: 適度推眼鏡，留白的藝術

• 可改進的地方

• 0:05: 不該自稱是「面試官」，這有「上對下」的隱含意思，大家日後可能會是同事，而且說不定應徵者一開始的職等就比自己高^{台灣很小，你永遠很難想像記仇會多久}，interview 是得知「相互」的「觀點」的途徑，不是讓你施展官威的場合。可改說「感謝你的時間，接下來由我主持這場面試」或「你好，從我手上這份簡歷，我感受到您對程式設計的熱情和專業，但在我們談及工作內容前，我想幫公司同仁先認識你在程式開發的想法和風格」
• 0:08: 不用強調面試有「幾題」，可改說「我從你遞交的簡歷中，發現若干經典演算法的素材，想趁面試跟你交流」
• 0:11: 「希望用 Document 的方式」乍聽之下很費解，可改說「請你在事先分享的 Google Docs 上答覆，過程中你若有想法，就直接寫下，便於後續討論」
• 0:16: 避免直接講 binary tree 和 preorder traversal 這些關鍵字，因為總會有人背誦參考程式碼就上場，從而缺乏鑑別度。可改用情境敘事來跟應徵者互動，例如：「考慮到敝公司的主要業務是廣告推送，商務邏輯 (business logic) 不乏會有多個因子經由特定運算，來調整廣告露出和效益的需求。就算只考慮四則運算，也會有多個變數經過加減乘除和小括號成為多種表示式，倘若我們直接將這些運算式用字串的方式儲存，一來佔用較多記憶體空間，二來執行時期成本較高，於是我們可將前述加減乘除和小括號，在某種操作後，轉為二元樹，之後用更精簡的方式來運算。對此，你有什麼想法呢？」
  • 提示: Polish notation
  • Pre-order traversal 可將 expression tree 轉換為 Polish notation，參見 Tree traversal: Applications
• 09:01: 要求將遞迴轉為非遞迴形式，太容易被 interviewee 猜出來，可改為遞迴深度和執行成本的分析
• 17:56: interviewer應該可以再延伸問題或是探討最佳化的寫法，像是請interviewee也簡述一下postorder與inorder的方式

關於 interviewee

• 優點

• 說話清晰，語速正常

• 可改進的地方

• 沒有依循 REACTO 流程，過早撰寫程式碼，應該將 Approach 充分討論
• 0:31: 「受試人」與需要「互動」的 interview 精神相去甚遠，避免用這詞彙
• 避免過多的關鍵字中英交錯，例如 node 和 struct 都有行之有年的翻譯詞彙 (節點/結構體)，把英語留在變數名稱或者電腦科學的術語
• 0:50: 考慮到台灣人的發音習慣和聽力，相近的發音如「值」、「址」，和「子」就避免在同一個討論標的裡頭出現，可改為(節點的)「內含值」、「地址」，和「子樹」/「子節點」，寧可多說一些，也不要造成誤會。既然有 Google Docs，其實就可一邊說，一邊用文字 (搭配 ASCII art) 來強化描述
• 01:00: 考慮到應徵者說話的速度略慢 (畢竟不免緊張)，撰寫程式碼的時候，可先寫成員 (即 left 和 right)，再補上 struct 和必要的指標宣告，這樣一來可跟口語連動，二來 interviewer 的注意力也會引導到程式碼上
• 01:22: 打字速度要提升，儘量先展現會吸引 interviewer 的程式碼區域，之後可一邊說話，一邊補強程式碼
• 03:14: 作答前應該先溝通使用的程式語言，例如 C 語言的 malloc 不需要額外的轉型 (自 void *)，但 C++ 語言則需要顯式 (explicit) 轉型
• 04:21: 有些相似度高的程式碼，如 node->left = NULL; 和 node->right = NULL; 就可合併一行，甚至可先口頭帶過 (除非 interviewer 堅持要完整書寫)，以便強調 REACTO
• 05:03: 既然要強調「最重要」的部分，但卻沒有對應的描述和後續可重用的素材，而且若能搭配實例講解而非口頭帶過，能讓interviewer更明白自己的意思
• 05:30: 其實 print 不是很關鍵，反而要想「用什麼形式 traveral？」和「之後要做什麼？」
• 09:08: 當被問到能否修改為非遞迴時，能藉機與interviewer互動，詢問此改變的動機，以及分析兩種方式的差別與適用的情形
• 可適當空行方便interviewer閱讀程式，也顯示自己能有條理架構的處理問題
• 12:43: STL 的 stack 是否必要？
• 18:29: 能先提及各種可行方式並分析，在挑出符合需求的方法

英文題目

• 00:37: 撰寫程式前可先知會interviewer需要一段時間，也能讓interviewer對接下來的過程有心理準備
• 05:03: 可以將原先程式碼留下，方便之後和新的版本做比對，更能看出差別
• 12:01: 能更詳細解釋為何time complexity能變成
  $O(n)$ 會更好

第二次作業 - 他評 02

Interviewer

• 可改進部分

• 18:09: 提到 star graph 可以講解star graph的定義

Interviewee

• 優點

• 口齒清晰，音量合適

• 可改進部分

• 17:16: 這邊有一段無聲的時間，檢查程式可以用舉例測試
• 00:52: 講解解法可以多花一點時間，不用直接開始寫程式，這之後有很長一段的暫停，看起來就像沒想好。
• 05:43: 沒解釋 pointer 怎麼在 array 中移動
• 05:54: 能更詳細解釋為何有重複就一定有cycle

第二次作業 - 他評 03

Interviewer

• 優點

• 0:00: 音量適當，咬字清楚

• 可改進的地方

• 0:00: 面試官與受試者互動太少，建議多與受試者互動
• 0:27: 應該避免使用 LeetCode 原題，建議將題目適當做變形

Interviewee

• 優點

• 0:27: 音量適當，咬字清楚

• 可改進的地方

• 0:29: 受試者 REA 部份太短，建議多舉一些例子，並且說明做法

第二次作業 - 他評 04

Interviewer

• 優點

• 0:00: 題目敘述的清楚

• 可改進的地方

• 11:59: 可針對修改後版本的回答給評論

Interviewee

• 優點

• 4:50: 描述簡明扼要，有說明自己打算採用的方案

• 可改進的地方

• 0:33: 實際撰寫程式碼前可以重複提問確認自己對題目的理解是否有誤
• 因為題目沒有example，因此可以自己舉例。

第二次作業 - 他評 05

Interviewer

• 優點

• 指示清晰，明確要求要達到甚麼條件

• 可改進的地方

• 我認為通常主管面試是找未來會一起工作很久、要相處一陣子的人，感受不出主管有在確認這種方面
• 可能題目可以變換下，多出點應用超出leetcode 的codeing範圍，更應用到商品的想法，比如二元墅連接到ubuntu的記憶體控制，找東西順序，或著商品排序找些

Interviewee

• 優點

• 咬字真的很清晰，我用兩倍速聽都很清楚，不會誤會
• 有遵守確認，舉例，說明方案，撰寫程式

• 可改進的地方

• 感覺互動有點少，可能coding過程可以多點閒聊
• 可能多點驗證程式的方案，例如舉例套進去看看
• 感覺說這題就做完好像不太好