作者:克勞迪(Cloudy)
👨💻: Interviewer
👨💼: Interviewee
Viedo Link: https://youtu.be/N4eiA2HKRUc
Questions
- LeetCode 322. Coin Change
- LeetCode 217. Contains Duplicate
👨💻 (Interviewer)
克勞迪您好,我是負責本次面試的人員。
如果沒有什麼問題,我們就直接開始今天的面試吧。
👨💼 (Interviewee)
我沒有任何問題,隨時都能開始。
👨💻 (Interviewer)
好的,那麼首先想請問您一個問題,題目是這樣子的:我會給您一組輸入,輸入包含兩個變數,分別是 coins 和 amount。
coins 是一個整數陣列,裡面儲存了各種硬幣的幣值,amount 則是一個整數,代表的是總金額。
題目的要求是找到一個最小硬幣數量,這個最小的硬幣數量搭配各種幣值而組成的總金額,要和給定總金額相等,如果輸入的條件無法找到滿足條件的硬幣數量,則輸出 -1。
👨💼 (Interviewee)
也就是說,我要做的是計算構成總金額的最小硬幣數量,總金額和硬幣幣值由輸入決定,如果遇到找不到任何組合,也就是無解的輸入,則輸出 -1。
假設現在給定 coins = [1, 6, 10],amount = 13,正確的輸出就應該要是 3,因為 3 枚硬幣分別由兩個 6 元硬幣加上一個 1 元硬幣組成,而不是輸出 4,也就是一個 10 元硬幣加上三個 1 元硬幣組成,那請問我的理解正確嗎?
👨💻 (Interviewer)
完全正確。
您能開始介紹作法了。
👨💼 (Interviewee)
好的,針對這個題目,我首先想到的是使用遞迴實作分治法。
也就是說,我會撰寫一個函式,這個函式會以當前的總金額嘗試所有幣值。
如果當前的總金額扣掉當前嘗試的幣值,金額還大於等於零,就代表當前的金額能夠兌換一個當前幣值的硬幣。
接著,我會把扣除了當前幣值的總金額作為新的函式的輸入,也就是做遞迴,如此反覆來拆解總金額,並計算所需的硬幣數量。
由於題目要求的是計算出組成總金額的最少硬幣數,因此這個函式會比較,是當前的硬幣數比較小,還是遞迴函式計算得到的值加一會比較小,然後從二者中選擇比較小的值,再作為現在這個函式的回傳值。
當前的硬幣數比較小意味著,也許遞迴函式有找到其他的硬幣組合,不過這個組合它需要的硬幣數比較多,或者是遞迴函式的它本身沒有找到任何解,也就是回傳值為 -1,就是無解的情況。
那如果是遞迴函式的回傳值比較小就剛好相反,也就是遞迴函式它有找到一個組合,而且這個組合需要的硬幣數更小,那我們只要基於這個值再加一,我們就能得到組成當前這個遞迴函式金額的最小硬幣數。
👨💻 (Interviewer)
聽起來沒什麼問題,請您先依照您所說的作法,實作程式碼。
👨💼 (Interviewee)
好的。
我撰寫完程式碼了。
那如前面所說,我使用遞迴將硬幣拆解拆成許多許多的小任務。
我認為這樣做的時間複雜度會是 O(na/c),那其中 n 為硬幣幣值的數量、a 為 amount 的數值、c 則為最小硬幣的幣值。
我會這麼認為的原因是:從這邊的程式碼可以看到,每一次進入遞迴函式之前,程式都會通過 for 迴圈來檢驗每一種硬幣的幣值,而從遞迴函式的輸入可以知道,執行遞迴的次數其實就是總金額除以硬幣幣值的商。時間複雜度從整體來看,就可以很明顯的看出說是硬幣幣值的種類乘以遞迴的次數,那換成時間複雜度就會是 O(na/c)。
那空間複雜度就相對容易很多,在我寫的函式裡面,我並沒有額外地儲存很多資訊,因此空間複雜度不會受到輸入資料的數量影響,所以我認為這隻程式的空間複雜度會是 O(1),也就是常數空間。
👨💻 (Interviewer)
分析的不錯,不過您的作法最大耗時在於遞迴,我們公司的服務大多對於執行時間的要求度比較高一點,請問您認為程式中遞迴部份是否還能再優化,例如通過節省計算量以降低計算時間?
👨💼 (Interviewee)
嗯…
目前程式中的遞迴執行到最後,其實會重複解到相同的問題。
例如說小金額所需要的最少硬幣數量。
因此如果對執行時間比較有要求,我認為能利用動態規劃來優化程式,那簡單來說就是通過建一個表格來儲存會重複使用到的小問題的計算結果,從而減少重複的計算量而且避免遞迴,就能夠提昇執行時間方面的效能。
我再寫一支關於動態規劃的程式。
好,我撰寫完程式了。
其實如我前面在開始寫程式之前所說,我透過建表儲存已經計算過的小問題的計算結果,後面較大的金額,在拆解的過程中,就能直接從表格內讀取之前算好的小金額結果,減少重複的計算,提昇效能。
👨💻 (Interviewer)
好的,我想目前的作法已經是本題很好的作法了。
如果您沒有問題,我們就繼續下一題?
👨💼 (Interviewee)
我沒有任何問題,可以繼續面試。
👨💻 (Interviewer)
下一題的要求是這樣子的,輸入一個整數陣列 nums,如果輸入的陣列內存在的元素個數超過一個,就回傳 True,反之,如果有重複的元素,就回傳 False。
👨💼 (Interviewee)
也就是說,題目的需求是讓我寫一個函式,其功能為判斷輸入的陣列內是否有重複的元素。
舉個例子來說,如果輸入的 nums = [1, 2, 3],那這時的輸出就應該要是 True,因為 [1, 2, 3] 都是不同的元素。
如果 nums = [1, 2, 3, 1],那這時的輸出就要變成 False,因為這四個元素中,1 重複了兩次。
想跟您確認一下,我的理解是否正確?
👨💻 (Interviewer)
沒錯,就是這樣。
對於這個問題,您有什麼想法嗎?
👨💼 (Interviewee)
我目前想到最直觀的方法是使用兩層的巢狀迴圈,分別檢查每一個數和其他數字是否相同,從而解決這個問題。
那我先開始寫程式。
我撰寫好程式了,其實就和我上面說的一樣,我會通過兩層的迴圈,分別用 i 和 j 進行索引,如果發現有兩個數是一樣的,就返回 true。
如果全部的都執行完,還沒有回傳,就代表說這個陣列內是沒有重複元素的,此時就回傳 false。
👨💻 (Interviewer)
這個作法很直觀,確實能解決問題,不過時間複雜度很明顯是 O(n^2)。
想請問您對加速計算過程有沒有什麼想法?
例如先對資料進行處理再檢驗,而不是單用迴圈暴力解?
👨💼 (Interviewee)
有的!
我想可以使用任意排序演算法先對輸入的陣列進行大小的排序。
只要陣列內的元素依照大小被排好之後,我們只要從頭到尾遍歷一次,對陣列中的每一個元素檢查它們相鄰元素和本身是否相等,就能知道陣列中是否有相同的元素。
這樣的作法可行的原因是,如果存在兩個元素相等,那經過排序後,他們理應會相鄰。
那我就直接開始撰寫程式碼。
我撰寫好程式碼了。
這個作法的時間複雜度其實會取決於前面的排序演算法,因為在這支程式中,耗時主要有兩部份,第一個部份是排序演算法,第二部份則是後面的 for 迴圈。
不過其實能很明顯的發現,for 迴圈的時間複雜度是 O(n),如果排序演算法的時間複雜度比 for 迴圈高,就會影響到整體的時間複雜度。
排序演算法的時間複雜度通常都會大於 O(n),以這邊寫的程式為例,我是用的語言是 C plus plus,sort 使用的是 standard library 裡面的 sort function,它的平均時間複雜度會是 O(nlog(n)),所以整支程式的時間複雜度就會是 O(nlog(n))。
👨💻 (Interviewer)
通過排序簡化檢索是很不錯的想法,不過這個題目其實最好的做法可以做到線性時間,不知道您是否能夠提供一個時間複雜度也是線性時間的作法呢?
👨💼 (Interviewee)
嗯…
我目前有一些想法,不過想與您對照一下,確認方向是否正確,不知道方不方便請您先說說看?
👨💻 (Interviewer)
如果能在遍歷的時候,將已經遍歷過元素都紀錄起來,也許能很有效率的排查是否有重複的元素在陣列裡面?
👨💼 (Interviewee)
我想到了!
可以建一個表格,表格的索引值對應到的是元素的值,要紀錄元素時,只要在表格相應的位置記數,也就是紀錄此元素出現的次數,當我們對所有元素都進行資料處理,只要遍歷整個表格一次,如果發現某欄位的值大於一,就代表陣列有重複的元素,反之就沒有,如此就能很輕鬆的知道陣列內是否有重複的元素值!
除此之外,我有想到一些問題,如果現在輸入的元素值域很大,假設一個值是一億,但另一個值是一,而且元素的個數不多,以這個例子來說,如果依照前面說的方式建表,就會浪費很多空間,也會增加遍歷表格的時間。
針對這個問題,我認為也許可以利用字典,也就是把元素值當成字典的 key,計數的值則當成 value,這樣就能同時優化時間和空間的效能。
那我就直接開始寫程式。
我寫好程式碼了。
上面的程式碼的時間複雜度是 O(n),主要能分成兩個部份分析,第一個部份是迴圈,迴圈會跑過所有元素,因此時間複雜度是 O(n),第二部份則和 unordered_map 的建立和搜尋有關,unordered_map 是基於 hash table 的一種資料結構,在處理碰撞的策略,它大多使用 Closed Addressing,也就是說,當沒有任何碰撞情況發生時,時間複雜度最好能達到常數時間,也就是 O(1),當有碰撞發生時,最壞的情況則是 O(n)。
綜合以上敘述,整體的時間複雜度會是 O(n)。
空間複雜度部份,在最壞的情況下,也就是輸入的元素每個都不一樣時,每一個元素都會分別佔用一個 hash bucket,因此空間複雜度會是 O(n)。
👨💻 (Interviewer)
最後有使用到 hash table 進一步優化建表可能造成的時間和空間負擔非常好!
今天的面試差不多到這邊結束,關於今天的面試結果再請您留意個人信箱。
如果沒有問題的話,感謝您今天的參與,先這樣囉,掰掰!
👨💼 (Interviewee)
也非常謝謝您!
再見!
Viedo Link: https://youtu.be/icIoCbfhwb8
Question: LeetCode 104. Maximum Depth of Binary Tree
👨💻 (Interviewer)
Hello, Cloudy.
Nice to see you!
If you don't have any questions, we can start today's interview.
👨💼 (Interviewee)
No problem.
We can start at any time.
👨💻 (Interviewer)
OK.
There is a question.
I will give you the root of a binary tree.
Please give me a method that can return the maximum depth of the given root.
A binary tree's maximum depth is a number of nodes along the longest path from the root node down to the farthest leaf node.
👨💼 (Interviewee)
Sure.
The question is calculating the longest path length of a binary tree.
For example, there is a binary tree:
The longest path of this tree is 20 -> 10 -> 5 -> 1, and the maximum depth of this tree will be 4.
Is my understanding correct?
👨💻 (Interviewer)
Yes.
I think your understanding is right.
👨💼 (Interviewee)
Thank you!
There is a particular case if the given root is null.
In this situation, the maximum depth will be 0.
👨💻 (Interviewer)
How do you want to solve this problem?
👨💼 (Interviewee)
Hmm…
A naive approach I first think of is to implement a Depth-First Search algorithm based on recursion.
The fundamental key of this method is treating all nodes as subtrees.
It means the maximum depth of any root of the subtree will be the bigger maximum depth between the left subnode plus 1 and right subnode plus 1.
If the current node has no subnodes, we can know that the maximum depth of the current node's subtree is 1 (Due to the current node is a leaf node).
With this approach, I can calculate the maximum depth of root from down to top.
👨💻 (Interviewer)
Sounds great, you can start to code.
👨💼 (Interviewee)
OK.
Let me write some code for you.
I finish my code.
The time complexity of this approach is O(n), because this algorithm will triversal all nodes in the binary tree.
And the space complexity is O(1), due to this algorithm does not need to save any data.
👨💻 (Interviewer)
Although linear time is the best time complexity for this question, the recursion-based approach may not perform well when the number of nodes or the depth of the tree is big.
Can you give me another method whose time complexity is still O(n) but performs better?
👨💼 (Interviewee)
Sure, I can also implement the DFS algorithm with a stack.
Firstly, I will define a new struct which will save the node and its depth.
And then just implement the DFS based on the stack.
OK.
I finish my code.
With this approach, the time complexity is still O(n), but it can avoid calling itself multi-times.
So that it can save the execution time.
However, this approach needs to save the information of all nodes in the stack. So, the space complexity will be O(n).
👨💻 (Interviewer)
How do you verify your code is correct?
👨💼 (Interviewee)
I will take an example to verify my method is correct.
I use this as the example.
According to my method, there will have a stack and maxDepth.
In first step, push the node 20 into the stack, and update the value of maxDepth (Due to the depth of node 20 is bigger than 0).
In second step, pop the node 20 from the stack, push the left node of node 20 (node 10) and right node of node 20 (node 30) into the stack, and update the value of maxDepth (Due to the depth of node 10 and node 30 is bigger than 1).
In third step, pop the node 30 from the stack, push the left node of node 30 (node 25) into the stack, and update the value of maxDepth (Due to the depth of node 25 is bigger than 2).
In fourth step, just pop the node 25 from the stack, because node 25 has no any subnodes.
In fifth step, pop the node 10 from the stack, push the left node of node 10 (node 5) into the stack, but does not need to update the value of maxDepth (Due to the depth of node 5 equals to 3).
In sixth step, pop the node 5 from the stack, push the left node of node 5 (node 1) into the stack, and update the value of maxDepth (Due to the depth of node 1 is bigger than 3).
In last step, just pop the node 1 from the stack, because node 1 has no any subnodes.
So the final result is 4.
If we see the graph of example, we also can know that the maximum depth of the tree is 4.
👨💻 (Interviewer)
Great job!
I think it's almost time.
Today’s interview has come to an end.
Please wait for notification by email.
Have a nice day, goodbye!
👨💼 (Interviewee)
Thank you, have a nice day too!
Goodbye!