> 瑞比-Rabbit
> :man_in_tuxedo: : interviewer
> :rabbit: : interviewee
> [模擬面試錄影(漢)](https://youtu.be/pfpinBhNWnA)
> [模擬面試錄影(漢)](https://youtu.be/EsNEfzwKAfs)
> [模擬面試錄影(英)](https://youtu.be/8l4UMyluP3Q)
## [104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/description/)
>[模擬面試錄影](https://youtu.be/pfpinBhNWnA)
### 模擬面試過程
:man_in_tuxedo: : 你好，那現在開始我們的面試題目，給你一個Binary Tree，請回傳它的最大深度是多少。
:rabbit: : 我想確認我有沒有理解錯這個題目，如果用這個範例解釋的話，我要回傳的值就是從根節點3到離3最遠的節點15或7的距離，也就最大深度3，最後就是回傳這個數值，這樣我的理解有錯嗎?
:man_in_tuxedo: : 對你的理解是對的，請繼續你的解釋。
:rabbit: : 好，如果我的理解沒有錯的話，我想可以用遞迴的方式來解決這個問題。
詳細方法是找到一個node，得到這個node的left child和right child的maximum depth，並取得這兩個數值中的最大值+1，就會是這個node的maximum depth。
以上面的example來說，要得到20這個node的maximum depth，就是取15跟7的maxamum depth的最大值，也就是1，再加上1得到2，就是20這個node的maximum depth。
再透過遞迴就可以歷遍整個Binary Tree，就可以得到這個Binary Tree的maximum depth了。
:rabbit: :實際的程式碼如下
### Recursive
```C++=
int maxDepth(TreeNode* root){
int maxLeft = maxDepth(root->left);
int maxRight = maxDepth(root->right);
return max(maxLeft, maxRight) + 1;
}
```
:man_in_tuxedo: : 好，這程式基本上沒什麼問題，但它還不夠完整，如果要新增一行它更完整的話，你會怎麼做。
:rabbit: : 對，這樣我還缺一個判斷式，如果這個node是空的話要return0。
### Complete Solution
```C++=
int maxDepth(TreeNode* root){
if(!root) return 0;
int maxLeft = maxDepth(root->left);
int maxRight = maxDepth(root->right);
return max(maxLeft, maxRight) + 1;
}
```
:man_in_tuxedo: : 好，那我想問一下這個程式的時間複雜度跟空間複雜度是多少?
:rabbit: : 時間複雜度是總結點的個數，因為它要用回來歷遍所有的節點。
空間複雜度因為是recursive stack，所以是level的個數。
:man_in_tuxedo:: 好那今天的面試就到這裡，謝謝。
### 初步檢討
針對interviewer的檢討:
* 在一開始講解題目的時候可以講一個example，讓interviewee更好了解題目。
* 可以再和interviewee有更多互動。
針對interviewee的檢討:
* 在寫程式的時候，說話音量可以再大聲自信一點。
* 減少語助詞(EX:恩)
* 講解時間複雜度和空間複雜度時要用O(n)，不要只是陳述個數。
* 在寫完第一版的程式後就要發現自己程式不夠完整。
----
## [199. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/description/)
>[模擬面試錄影](https://youtu.be/EsNEfzwKAfs)
### 模擬面試過程
:man_in_tuxedo: : 嗨你好，這次的題目是給你一個Binary Tree，你要想想你站在這個Binary Tree的右邊，我要你return從上到下順序的節點的數值。
:rabbit: : 我想確認一下我的想法是不是對的，我用exmaple來解釋，假設我站在這個Binary Tree的右邊的話，我要return的順序會是[1, 3, 4] 這樣理解是對的嗎?
:man_in_tuxedo: : 對你這個方向是對的，請繼續。
:rabbit: : 這個方向如果是對的話，我會用level order traversal 去歷遍整個Binary Tree。先寫一個array (ans)，來存我要返回的數值，也就是每一個level的最右邊節點的值，再創一個array (lot)來存訪問過的節點的value和level，再寫兩個迴圈並判斷現在的節點是不是在每個level的最右邊，是的話就加到叫ans的array裡，最後再return這個array(ans)的值，就會得到答案。
:man_in_tuxedo: :你的想法是對的，可以開始寫程式了。
```C++=
vector<int>rightSideView(TreeNode *root){
vector<int> ans;
vector<pair<int, int>> lot;
if(root == nullptr)
return ans;
queue<pair<TreeNode *, int>> q;
q,push({root, 0});
while(!q.emy()){
TreeNode *current = q.front().first;
int level = q.front().second;
q.pop();
lot.push_back({current->val, level});
if(current->left)
q.push({current->left, level + 1});
if(current->right)
q.push({current->right, level + 1});
}
for(int i = 0; i < lot.size()-1; i++){
if(lot[i].second != lot[i+1].second){
ans.push_back(lot[i].first);
}
}
ans.push_back(lot[lot.size()-1].first);
return ans;
}
```
:man_in_tuxedo: : 好，那我們今天的面試就到這邊，謝謝。
### 初步檢討
針對interviewer的檢討:
* 在解釋題目時可以搭配一個example讓interviewee更好的了解題目的問題。
* 在interviewee講解完解題概念之後，可以再更深入的和interviewee的討論實際的做法。
針對interviewee的檢討:
* 一開始在確定使否有理解題目錯誤時，應避免說，"我想確認這樣是不是對的"，而應該用 "我對題目的理解是..."。
* 因為這題在解釋概念上比較複雜，所以可以在講解時搭配打字在google document上，幫助interviewer更加了解這個解釋跟想法。
* 在打程式碼的時候要檢查是否有打錯的情況，像是變數名稱跟函式名稱、括號跟;有沒有少打。
* 因面試有時間限制，可以再增加自己的打字速度。
* 在邊打程式邊解說的時候，解釋的音量可以再大聲一點。
## [136. Single Number](https://leetcode.com/problems/single-number/)
>[模擬面試錄影](https://youtu.be/8l4UMyluP3Q)
### 模擬面試過程
:man_in_tuxedo: : Hello, today's question is given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
:rabbit: : Ok, I have to make sure I've correctly understand of this question.
If I've been given a array = [2,1,1], output=2
If I've been given a array = [4,2,1,2,1], output=4
```C++=
Input: nums = [2,1,1]
Output: 2
Input: nums = [4,2,1,2,1]
Output: 4
```
:man_in_tuxedo: : Yes, you're on the right track. You can explain your solution.
:rabbit: : For sovling this problem, first come into my mind is using maps, I'll map the given array's elements to their frequency, and traverse that map and return the key whose value is 1.
:man_in_tuxedo: : OK, you can try.
:rabbit: : So the code is like this.
### Maps
```C++=
int singleNumber(vector<int>& nums){
unordered_map<int, int> a;
for(auto x: nums)
a[x]++;
for(auto z:a)
if(z.second==1)
return z.first;
return -1;
}
```
:man_in_tuxedo: : OK, but this method uses variable extra space, so it's not gonna be our answer. If I ask you to use sorting, can you do so?
:rabbit: : To use sorting, I'll first sort the array. And
traverse that array and check if the current element is equal to its adjacent element. If not,I'll return the current element's value.
### Sorting
```C++=
int singleNumber(vector<int>& nums){
sort(nums.begin(), nums.end());
for(int i=1; i<nums.size();i+=2){
if(nums[i] != nums[i-1])
return nums[i-1];
}
return nums[nums.size()-1];
}
```
:man_in_tuxedo: : This solution might be the answer. But what if I want to improve the time complexity and I don't want to use sorting, can you come up with another method?
:rabbit: : I'll use bitwise XOR operator, To imply this solution, I have to traverse the array and take the bitwise XOR of each element and then return the value.
### Bitwise XOR Operator
```C++=
int singleNumber(vector<int>& nums){
int ans=0;
for(auto x:nums)
ans^=x;
return ans;
}
```
:man_in_tuxedo: : OK, so it's the interview for today, thank you.
### 初步檢討
針對interviewer:
* 在解釋題目的時候語速要放慢且咬字清晰，並舉例讓interviewee更好了解題目。
* 在知道interviewee的方法錯時，就應該讓他想其他方法，而不是打完程式後才說他這樣不對。
* 在一開始說話時不要一直說"Ok"
針對interviewee:
* 在打字時可以加大說話音量，讓面試官更理解你在說什麼
* 英語表達要再更順暢一點
* 打字速度要加快，畢竟面試時間有限
Sign in with Wallet
Connect another wallet