---
title: 資訊科技產業專案設計課程作業 4
tags: 資訊科技產業專案設計
---
# [資訊科技產業專案設計課程](https://hackmd.io/@sysprog/info2022/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FBJLSJ3ggi)作業 4
> 貢獻者：瓈文琳－Lorian
> 模擬面試夥伴：郝酉乾－RichMan
> [影片](https://youtu.be/3txYsEN6g2I)
## 題目
### [104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)
:::success
題目方向
---
1. 原始
+ 給一個 binary tree 的 root ，回傳樹的最大深度
+ tree node 的數量範圍為 0~10000
+ node value 的範圍為 -100~100
2. 要求改變寫法，總共有兩種作法，依照之前作法回另一種
+ Recursive(Depth-first-search)
+ Iterative(Breadth-first-search)
:::
:::info
答案
---
1. 深度優先搜索 (DFS)
> 時間複雜度：O(n)
> 空間複雜度：O(n)
```cpp
int maxDepth(TreeNode* root) {
// 如果binary tree為空，則返回 0
if (root == NULL) {
return 0;
}
// 否則，通過遞迴的方式來求解
// 先求出左子樹的最大深度
int left_depth = maxDepth(root->left);
// 然後求出右子樹的最大深度
int right_depth = maxDepth(root->right);
// 最後，返回左子樹和右子樹的最大深度的較大值
return max(left_depth, right_depth) + 1;
}
```
2. 廣度優先搜索 (BFS)
> 時間複雜度：O(n)
> 空間複雜度：O(n)
首先，我們需要判斷binary tree是否為空，如果是空的，那麼最大深度就是 0。
接著使用一個queue來保存每一層的節點。在每一次迭代中，我們先將這一層的節點取出，然後將它們的左右子節點添加到queue中。每遍歷完一層之後，把深度加 1，這樣就能夠求出整棵樹的最大深度了。
```cpp
int maxDepth(TreeNode* root) {
// 如果binary tree為空，則返回 0
if (root == NULL) {
return 0;
}
// 創建一個queue，用於保存每一層的節點
queue<TreeNode*> q;
// 將根節點添加到queue中
q.push(root);
// 記錄樹的深度
int depth = 0;
// 循環遍歷queue中的節點
while (!q.empty()) {
// 循環遍歷這一層的節點
int size = q.size();
for (int i = 0; i < size; i++) {
// 取出頭節點
TreeNode* node = q.front();
q.pop();
// 將左右子節點添加到queue中
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
// 每遍歷完一層之後，深度加 1
depth++;
}
// 返回樹的深度
return depth;
}
```
:::
### [743. Network Delay Time](https://leetcode.com/problems/network-delay-time/)
:::success
題目方向
---
1. 原始(其實就是 shortest path problem 的變化版本)
+ 給一個 direct graph(number of node, edge and edge weight) 和一個指定的 node，在這裡 edge weight 代表 time 表示為 times[i] = (ui, vi, wi)，求特定點到所有點所需要的最短時間，如果有到達不了的點則回傳-1
+ node 數量的範圍為 1~100
+ edge 數量的範圍為 1~6000
+ 不會有重邊，不會有 loop，time 的範圍為 0~100
+ 可以先用 Dijkstra's Algorithm 的做法
2. 改進 Dijkstra's Algorithm 時間複雜度
若使用 Array，需要O(E+V^2)
若使用 Binary Heap，需要O((E+V)logV)
若使用 Fibonacci Heap，需要O(E+VlogV)
3. 改算法(如果覺得已經太多就不用了)
可改寫成 Bellmem-Ford Algorithm 的算法
:::
:::info
答案
---
1. Dijkstra
```cpp
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<pair<int,int>>adj[n+1];
for(auto time:times){
int u = time[0];
int v = time[1];
int t = time[2];
adj[u].push_back({v,t});
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
vector<int>wt(n+1,INT_MAX);
wt[k] = 0;
pq.push({0,k});
while(!pq.empty()){
int node = pq.top().second;
pq.pop();
for(auto x:adj[node]){
if(wt[x.first]>x.second + wt[node]){
wt[x.first] = x.second + wt[node];
pq.push({x.second,x.first});
}
}
}
int ans = INT_MIN;
for(int i=1;i<=n;i++){
ans = max(ans,wt[i]);
}
return ans==INT_MAX?-1:ans;
}
```
如果有負不能用dijkstra
2. Bellman Ford
```cpp
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<int> wt(n + 1, INT_MAX);
wt[k] = 0;
for (int i = 0; i < n; i++) {
for (vector<int> time : times) {
int u = time[0], v = time[1], t = time[2];
if (wt[u] != INT_MAX && wt[v] > wt[u] + t) {
wt[v] = wt[u] + t;
}
}
}
int ans = INT_MIN;
for (int i = 1; i <= n; i++){
ans = max(ans, wt[i]);
}
return ans == INT_MAX ? -1 : ans;
}
```
:::
### [421. Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/)
:::success
題目方向
---
1. 原始
* 給一個整數陣列，回傳陣列中任兩個數字做XOR的最大值，數字可以重複
* 陣列長度最小為1，最長為20萬
* 數值最小為0，最大為2的31次方減1
2. 改變演算法(看原本用哪個選下面其中一個)
(1)減少時間複雜度
* ex.用hash table(或Trie)做？
(2)不要管時間，希望用比較少空間
:::
:::info
答案
---
simple way
$O(n^2)$
```cpp
int findMaximumXOR(vector<int>& nums) {
int max = 0, number = nums.size();
for(int i = 0;i < number - 1; i++){
for(int j = i+1; j < number; j++)
if(max < (nums[i] ^ nums[j]))
max = nums[i] ^ nums[j];
}
return max;
}
```
bit manipulation
```cpp
int findMaximumXOR(vector<int>& nums) {
int max = 0, mask = 0;
set<int> s;
for(int i = 31; i >= 0; i--){
//
mask = mask | (1 << i);
for(int j = 0; j < nums.size(); j++)
s.insert(mask & nums[j]);
// d
int candidate = max | (1 << i);
for(auto prefix : s){
if(s.count(prefix ^ candidate)){
max = candidate;
break;
}
}
s.clear();
}
return max;
}
```
Trie method
$O(n)$
```cpp
class Node{
public:
Node* links[2];
};
class Trie{
public:
Node* root;
Trie(){
root = new Node();
}
void insert(int num){
Node* node = root;
for(int i = 31; i >= 0; i--){
int bit = (num >> i)&1;
if(!node -> links[bit])
node -> links[bit] = new Node();
node = node -> links[bit];
}
}
int maxnum(int num){
Node* node = root;
int max = 0;
for(int i = 31; i >= 0; i--){
int bit=(num >> i)&1;
if(!node -> links[1-bit]){
node = node -> links[bit];
}
else{
max = max | (1<<i);
node = node -> links[1-bit];
}
}
return max;
}
};
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int ans = 0;
Trie trie;
for(int i = 0; i < nums.size(); i++){
trie.insert(nums[i]);
}
for(int i = 0; i < nums.size(); i++){
ans = max(ans, trie.maxnum(nums[i]));
}
return ans;
}
};
```
:::
## 面試
> interviewer：🧐 = 郝酉乾
> interviewee：🤓 = 瓈文琳
### 104. Maximum Depth of Binary Tree
🧐：Welcome to our interview. Please open the google doc for the question.
🤓：Hello. Okay I have opened it.
🧐：Following I will explain the question, given a binary tree, you should return the maximum depth of this tree.
🧐：The input parameter only contains the tree root node, and return value is an interger.
🧐：Do you have any question?
🤓：Ok, so I need to find the depth of a binary tree. And, I would like to ask that what is the maximum and minimum number of tree nodes?
🧐：The maximum number is ten thousands. And the minimum number is zero.
🤓：I got it. I think depth-first search algorithm can solve this problem.
🧐：OK, then can you give me a briefly description about how depth-first search apply on this problem.
🤓：I will use recursive to apply DFS. In every round, check if the root is null or not, if it is null, then return 0.
🤓：Or, get the depth of left and right subtree, the max depth plus one of the subtrees is the depth of the tree in the current round.
🤓：So, finally I can get the depth of the whole tree.
🧐：Ok,you can start write your code now.
🤓：(Writing and explaining.....)
🧐：Can you tell me the time complexity of your method?
🤓：Because this method travels all nodes, so the time complexity is O(n).
🧐：I got it. However, sometimes recursive method will use more resource, so can you give me a nonrecursive method to solve this problem?
🤓：I think I can use Breadth-first search. Traverse each node of the layer, and store their left and right node in a queue, after traverse all the nodes in a layer, plus one to depth, and keep going on the next layer.
🤓：This also travels all nodes of the tree, so the time complexity is also O(n)
🧐：No problem, you can start writing your code now.
🤓：(Writing and explaining.....)
---
> interviewer：🧐 = 郝酉乾
> interviewee：🤓 = 瓈文琳
### 743. Network Delay Time
🧐：Next, please see the next problem. There is a network with n nodes, labeled from 1 to n. Each network edge is assigned a time variable. Simple example can see in fig And you will get the list of time structure like this. ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.
🧐：If we send a signal from a node. return the shortest time when all the nodes receive it. If there is any node can't receive the signal return -1.
🤓：I got it, so I need to return the time when all nodes receive the signal from a node.
🤓：Is the edge in the network have direction?
🧐：Yes, all the edges have direction.
🤓：Can the edge be multiple edge? And, is there any loop in the network?
🧐：There is no multiple edge and loop in this network.
🤓：I see. This problem is like shortest path problem, and because it is time, so there is no negative edge, so I think Dijkstra algorithm can solve it.
🤓：I would store the time it takes from one node to the other with a vector of pair and use the piority queue for choosing and updating the time.
🤓：And use a vector to save the shortest time from the start node to every nodes.
🧐：I got it, you can start coding now.
🤓：(Writing and explaining.....)
🧐：well done, but if the time can be negative, Dijkstra algorithm can't apply to this situation. How do you solve this problem.
🤓：Well...I think I can use Bellman Ford, it can solve the situation when there is negative edge
🧐：Ok, you can write code now.
🤓：(Writing and explaining.....)
---
> interviewer：🧐 = 瓈文琳
> interviewee：🤓 = 郝酉乾
### 421. Maximum XOR of Two Numbers in an Array
🧐：Hi,welcome to our interview. Please open the google doc for the question.
🤓：Hi, I have opened it.
🧐：Following I will explain the question, give you an integer array, you need to find the maximum XOR of two numbers in the array.
🤓：Can a number do XOR with itself?
🧐：Yes.
🤓：And What is the size of array?
🧐：It is at least 1 and at most 200 thousand.
🤓：Ok, I think it can solve with double for loop. And in each iteration, compared the max variable with two interger XOR value, then save bigger one.
🧐：Good idea, but it may take too much time, can you think of a faster solution?
🤓：the max XOR value is that two interger are complementary. But it may not exist complementary numbers in this array. So we need to find the close one. first.
🧐：Yes, so how can you find the closest one?
🤓：We can construct binary tree to represent number in array. then search this tree to find the closest one.
🤓：(show example)
🧐：Good, and what is the time complexity of this one?
🤓：when constructing tree, we need to traverse all array, so time complexity is O(32n). Then when we find complementary numbers, the tree height is 32, so the time complexity is also O(32n). All the time complexity is O(n).
🧐：Ok, please write the code down
🤓：(Writing and explaining.....)
🧐：Welldone, thank you for your time. We will send email to you for the consequence.
## 改進方案(檢討)
* 可以先確認一下對方聽不聽得清楚，再開始
### Q1(擔任interviewee)
* [10:14](https://www.youtube.com/watch?v=3txYsEN6g2I#t=10m14s) 寫完code應該要用例子測試是否有錯誤的地方
### Q2(擔任interviewee)
* 應該和interviewer討論可不可以寫簡略一點，表達意思就好，不然兩個code都打有點久
* [39:41](https://www.youtube.com/watch?v=3txYsEN6g2I#t=39m41s) follow up提到如果有負的Dijkstra不能解，舉例測試的時候就不應該用原本的例子，會看不出follow up的特點，且這個例子的順序甚至跑一次迴圈就得到最佳解了，應該自己舉別的例子。
### Q3(擔任interviewer)
* 雖然對方回答得蠻順利，但還是可以適當給一些回應互動，才能更了解這個人
## 檢討自己整學期的表現
* 作業都有如期完成沒有遲交
* 周二早上剛好有一堂很早的課，導致下午有時候上課會度估漏聽一點東西，很不好，應該要強迫自己中午午休，讓下午精神更好
* 老師在問同學問題時會在心中想如果是我要怎麼回答，但其實很多時候都答不出來，需要再查，意識到自己過去的知識學得很不扎實，應該要再複習與精進
* 以前會覺得找工作還一陣子就沒在看職缺，上這門課之後發現自身和業界要求差得很遠，而且進入社會也不是多久的事了，在考慮將來課表時會考慮更多，也會開始上求職網站看職缺能力要求
Sign in with Wallet
Connect another wallet