# 2023 資訊科技產業專案設計 作業1
>拍手-clap
>🧔：interviewer
>👶：interviewee
>[模擬面試1(中文)]
>[模擬面試2(中文)]
>[模擬面試3(英文)]

## [148. Sort List](https://leetcode.com/problems/sort-list/)
### 面試過程
>[影片](https://youtu.be/Hj-H5U6K8Dg)
>
🧔 : 現在有一個 linklist 我希望你按照每一個 node 的值將他們由小到大做排序。

👶 : 好的，那這邊想確認一下，假設 input 為一個 [5,3,7,9,-1,3] 那我們的 output 會是 [-1,3,3,5,7,9] 其中 3 是代表 input 可能會有重複的數字，-1 代表可能有負數，這樣我理解有錯嗎?

🧔 : 沒有錯，你理解得很好。

👶 : 那這邊一開始會想先判斷 input 有幾個 node，如果沒有或只有一個的話，那可以直接將值傳回去，如果節點數大於1的話想採用 bubble sort 來完成排序。

🧔 : 聽起來不錯，你可以開始實作了。


👶 : 那我的程式時間複雜度會是 O(n^2)。

🧔 : 那你有辦法把時間複雜度控制在 O(logn)嗎?

👶 : 恩......(思考)，那我會將排序的方法由 bubble sort 改成 merge sort，這樣就可以滿足時間複雜度在 O(logn)。
🧔 : 聽起來很棒，你可以繼續實作了。

## [1282. Group the People Given the Group Size They Belong To](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/?envType=daily-question&envId=2023-09-11)
### 面試過程
>[影片](https://youtu.be/JNbQcGB0AL8)

🧔 : 現在有個 array，裡面一個 index 就是一個人而 index 的值就是人在的團體有幾個人，例如 : [1,1,3,3,3]第0個人在一個人的團體裡，第二個人在三個人的團體裡，然後我需要你將團體給分類好，像上面的例子會變成 [[0],[1],[2,3,4]] 會有很多種答案只要給我其中一種就可以。

👶 : 那想先請問一下總人數有可能是空的嗎或是總人數有什麼上限?

🧔 : 總人數一定大於1且小於500。

👶 : 那想再請問有可能給的數值無法剛好分配成剛好的團體嗎?例如 array 給 [1,1,2] 但是第二個人沒有人跟他配對。

🧔 : 不會，array的值都是設訂好的，不會發生上面的情況。

👶 : 好的，那我想在確認一次題目，如果收到 array [3,2,1,3,2,3] 那麼第0個人在三個人的團體，第1個人在兩個人的團體後面以此類推，output 會產出 [[2],[1,4],[0,3,5]] 這樣我理解有錯嗎?

🧔 : 沒有錯，你理解的非常好。

👶 : 那我的想法是因為數值不一定是由小排到大，所以想要先排序，但是因為 index 代表一個人所以要跟數值綁定一起排序，所以我會先將數值跟index排序完後，再從排序完的結果一個一個按照他的數值取人，就可以得到答案了。

🧔 : 聽起來是沒甚麼問題，你可以開始實作了。


👶 : 目前整體的時間複雜度是 O(n^2) 因為排序採用的是bubble sort如果採用其他排序法可以縮短到 O(nlogn)，而空間複雜度是 O(n)。

🧔 : 那有時麼方法可以比 O(nlogn) 還要更快的嗎?

👶 : 恩......(思考)我想到可以用 hash table 來記錄這樣時間複雜度可以縮短到 O(n)。

🧔 : 聽起來不錯，你可以開始實作了。


## [100. Same Tree](https://leetcode.com/problems/same-tree/description/)
### 面試過程
>[影片](https://youtu.be/pZyi5PspeCc)

🧔: I want yot to determine whether every value in two binary trees is the same. The input for this task will be the roots of the two binary trees.

👶 : So, if there are two binary trees with the structures [1,9,6,3,2] and [1,6,9,3,2], the return value will be false because even though both of them contain 6 and 9, in the first tree, 9 is in the left subtree, while in the second tree, 9 is in the right subtree. Therefore, the two binary trees are still not equal. Is this understanding correct?

🧔 : You are right, and your understanding is accurate.

👶 : We will first create a function with the purpose of checking whether the values at corresponding positions in two subtrees are equal. If they are not equal, the function will return false. If they are equal, the comparison will continue downward. The entire algorithm operates through recursion, starting from the root, comparing the left subtrees first, then the right subtrees, until all nodes have been compared. If all nodes are found to be equal, the function will return true.

🧔 : Sounds good! Let's begin the implementation.


👶 : Here, the time complexity of my algorithm will be O(n) because we need to visit all the nodes once.

🧔 : This is great,Thank you for participating in the interview. We will provide you with the results within the next two weeks. Have a wonderful day, and goodbye!