---
tags: 資訊科技產業專案設計作業
---
# 資訊科技產業專案設計課程作業 4
### [模擬面試錄影](https://youtu.be/nWv9eTt9xYw)

🧔：interviewer 👶：interviewee
## [863. All Nodes Distance K in Binary Tree](https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/description/)
### 面試流程
* 🧔: Hello, welcome to today's interview.I am today's interviewer.
* 🧔: Then we will have two problem today.
* 🧔: let's start first problem!
* 👶： OK!
* 🧔: First we will have three inputs.
1. the root of a binary tree.
2. the value of a target node target.
3. an integer k.
* 🧔: The return answer is an array of the values of all nodes that have a distance k from the target node.
* 🧔: All the values Node.val are unique.
* 🧔: For example:

target = 5, k = 2
intpu binary tree:
         3
       /   \
      5     1
     / \   / \
    6  2   0  8
      / \
     7  4
outptu: [7,4,1] can in any order

* 👶: OK, Let's start by the above tree as an example and making some cases for the problem.

target = 1, k = 1
intpu binary tree:
         3
       /   \
      5     1
     / \   / \
    6  2   0  8
      / \
     7  4
outptu: [3,0,8] can in any order

* 🧔: yes! you are right.
* 👶: Ok, so the first solution I thought of was to use dfs.
* 👶: Start from target node, use dfs to traversal the tree and execute k times
* 👶: So there are three directions to choose when executing dfs.
1. parent node
2. left node
3. right node
* 👶: In order to find the parent node, I will use hash table to store the parent node of each node.
* 👶: In addition, I will also use unodered_set data structure to record the visited nodes
* 🧔: Ok, that sounds ok, so you can start coding
* 👶: <coding>

void recur(TreeNode* target, unordered_map<TreeNode*, TreeNode*> mp, int k, vector<int> ans, unodered_set<TreeNode*> seen) {
	if (k == 0) {
		ans.push_back(target->val);
		return;
	}

	// set seen
	seen.insert(target);

	// check left
	if (target->left != nullptr && seen.find(target->left) == seen.end()) {
		recur(target->left, mp, k-1, ans, seen);
	}

	// check right
	// same as left

	// check parent
	if (mp[target] != nullptr && seen.find(mp[target]) == seen.end()) {
		recur(mp[target], mp, k-1, ans, seen);
	}
}

vector<int> func(TreeNode* root, TreeNode* target, int k) {
	vector<int> ans;
    if (root == nullptr)
        return ans;

    // TODO: store all the parent in hash map
    mp[root] = nullptr
    mp

    // dfs
    unodered_set<TreeNode*> seen;
    recur(target, mp, k, ans, seen);

    return ans;		
}

## [47. Permutations II](https://leetcode.com/problems/permutations-ii/description/)
* 題目: Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
* 範例
* Example 1:
* Input: nums = [1,1,2]
* Output:[[1,1,2],[1,2,1],[2,1,1]]
* Example 2:
* Input: nums = [1,2,3]
* Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
* 🧔：interviewer 👶：interviewee
### 面試流程
* 🧔： OK, let's start the second question
* 🧔： I will Give you a collection of numbers, nums, that might contain duplicates
* 🧔： You have to find out all possible unique permutations in any order.
* 🧔： For example

    Input: nums = [1,1,2]
    Output:[[1,1,2],[1,2,1],[2,1,1]]

* 👶： ok, assume all the elements are unique, I can use dived and counqure to solve this problem => [1, 2, 3] => 1[2, 3] + 2[1, 3] + 3[1, 2]
* 👶： But there is a problem here that when the input is [1, 2, 1], duplicate answers will be generated.
* 👶： So I thought that sorting could be used first to handle this, when iterate all nodes, skip if there are duplicates.
* 🧔: Ok, that sounds ok, so you can start coding
* 👶: <coding>

void recur(vector<int> input, vector<vector<int>> ans, int index) {
	if (index == input.size()-1) { 2
		ans.push_back(input); // 112, 211
		return;
	}

	// iterate and swap
	for (int i = index; i < input.size(); i++) {
		// swap if the element is different.
		if (input[i] != input[index] || i == index) {
			swap(input[i], input[index]);  // [2, 1, 1]
			// recursion
			recur(input, ans, index+1); // index: 1 [2, 1, 1]
			// swap back
			swap(input[i], input[index]); // [1, 1, 2]
		}
	}
}

// [1, 2, 1]
vector<vector<int>> func(vector<int> input) {
	vector<vector<int>> ans;

	// sort
	sort(input.begin(), input.end());
	// [1, 1, 2]
	// recur
	recur(input, ans, 0); 
	return ans;
}

## 自我檢討
* 我在這堂課學到了知識 & 自我檢討:
1. 如何分析職缺並找到自己真正想要的工作，並不適是要符合所有需求才能去面試，大概有一半就可以了。
2. 對照比較自己目前的能力以及職缺的需求的差異，並懂得去加強、補足自己的缺陷。
3. 聽了非常多學長姐的經驗分享受益良多，了解了有甚麼路可以走。
4. 這堂課的作業模擬了面試流程，面試是一場表演，必須要有充足的準備才可以展現出來，讓我知道我還有很多不足的地方需要加強。
5. 這堂課的作業由於需要拍影片，所以我也學到了影片的錄製以及影片後製的方法。
6. 學到如何當任一個合格的 interviewee 和 interviewer，也知道自己需要補強的地方
* interviewee: 必須要避免雙方的沉默，但又必須要在短時間內想好問題的解法，這部分是很看重 interviewee 的能力的，另外再講解自己的想法時也是一門學問，需要解釋的精簡扼要，只講重點，並且有辦法適當的舉出例子來說明。
* interviewer: 需要給 interviewee 一個完整的題目說明，並且在 interviewee 卡住時給予引導，然後在面試前也需要對題目有非常充分的理解，不然面試時不知道 interviewee 的想法就糟糕了。
7. 最後就是這堂課的第四次作業-與一名夥伴配對並進行模擬面試，這邊比較有趣的是我們為了追求臨場感所以事前並沒有告訴對方題目。在整個模擬面試完後，我才深深感覺到真的會超緊張，在想題目的同時也要不忘記與面試官的互動，老師也有提到 15、30 原則，最多 15 秒內一定要有回覆，30 秒內要有個大概的想法出來。我認為這是非常難的一個部分，也是我最需要加強的。