🐯: interviewer
🦝 : interviewee
暱稱 布撥(Pawmi)
🐯:布撥先生你好,歡迎來到本公司,本次面試為coding interview ,我們會與你討論一些問題,在過程中如果對問題有任何的疑問,都可以提出。如果你準備好就可以開始了。
🦝:好的沒問題,我們可以開始了。
🐯:首先我想先跟你討論一個經典的問題,請問你知道費波那契數列嗎?
🦝:你說的是費氏數列嗎?費氏數列的特點是每一個數字都是前兩個數字的和,數列起始於0和1,因此數列前幾個數為 :
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ..
🐯:是的,這個數列有很多特殊的性質,它可以用來描述植物的分枝結構、兔子的繁殖模式,以及金融市場中的波動等,此外在資料結構裡也有基於費氏數列特性設計的斐波那契堆積(Fibonacci heap),可以用於圖演算法和一些最小生成樹演算法中。
🐯:既然你已經知道費氏數列的性質,你能否設計一個方法來取得數列任意位置的數值呢?
🦝:讓我先假設一下該方法的輸入與輸出格式:
fib : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ..
Input : 5
Output : 5
Input : 7
Output : 13
🦝: 請問我這樣的設定符合你的需求嗎?
🐯: 可以,那你打算如何實作方法呢?
🦝: 我打算直觀的透過遞迴式來進行設計,對於數列第n個數值,他會等於第n-1個數值加上第n-2個數值,已知數列的第 0 個與第 1 個數為 0 跟 1,他們可以做為遞迴函式的終止條件。以此就能夠透過遞迴設計解決方法。
🦝:接下來我會透過 C++ 來撰寫我的程式碼。
class Solution {
public:
int fib(int n) {
if(n<=1)return n ;
else return fib(n-1) + fib(n-2);
}
};
🦝: 我們可以用上面假設的範例來驗證一下方法的可行性。
🦝: 假設輸入是5 ,我們的目標是得到數列的第五個數值…
🐯: 理解,的確可以解決假設的範例,另外你的方案使用到遞迴式來解決此問題,可以分析一下遞迴的方法在此問題上有什麼樣的優缺點嗎?
🦝: 遞迴最大的優勢就是在撰寫上很直覺,且程式可讀性較高,不過遞迴在底層實作上仰賴stack,可能會發生stack overflow的問題,且以本題來說,在呼叫遞迴的過程中,發生了很多重複計算,例如:
fib(5) = fib(4) +fib(3)
fib(4) = fib(3) +fib(2)
fib(3) = fib(2) +fib(1)
🦝:這個時候可以看到重複計算的發生。
🐯: 的確有需多的冗餘計算,如果讓你進行優化,你會如何解決重複計算的問題呢?
🦝: 我想我會透過迭代的方式,以迴圈改寫方法。
🦝: 如果我們的目標是數列的第n個值,我們可以透過遞迴的方式,逐步計算出第 2、3、4… 直至第n個數值,這樣就可以避免重複計算的發生。
🦝: 我現在來修改一下程式的做法。
class Solution {
public:
int fib(int n) {
if(n<=1)return n ;
int a = 0;
int b = 1;
for (int i = 2 ;i<=n;i++){
int temp = a+b;
a = b;
b = temp;
}
return b;}
};
🦝: 這是修改後的結果,透過迴圈取代遞迴的設計。
🐯: OK,那你稍微評估這樣的優化方案,相比原本的作法優化的程度為何?
🦝: 以原來的遞迴方法來說,每次的遞迴呼叫會向下進行 fib(n-1) 與 fib(n-2) 兩次遞迴呼叫,所以時間複雜度為O(2^n),改寫成迴圈的方法後,對於目標數列第n個數值,我們只要逐步計算 2 到 n 的數列值就可以得到答案,因此時間複雜度優化至 O(n)。
🐯: 了解,改進的幅度很大。接下來我們進行一些延伸的討論,如果我們希望能夠一次得到多個索引值對應的數列數值,你覺得上面的方法有可以改進的地方嗎?
🦝: 如果一次要取得多個索引值對應的數列數值,那上面的迴圈方法需要進行額外的改良,否則會有需多重複的計算發生,
🐯: 什麼樣的情況下會有重複計算發生呢?
🦝:舉例來說,在計算fib(8)時,迴圈的方式會計算2 到 n 的數列數值,但其實在計算的過程中我們已經計算出 fib(5)的答案了,只是因為沒有紀錄所以更換索引值時需要重新計算,如果一次要取得的數值很多,就會浪費大量的計算資源。因此我們可以透過Memorization的技巧,在計算的過程中將費氏數列的值紀錄下來,這樣當下次的索引值在紀錄表裡已經有答案的話,就不需要再重複計算了。
input index = [1 5 8]
fib(1)
fib(5)
fib(8)
🐯: 我理解了,那你能改寫前段的程式碼來實作紀錄表的方案嗎?
🦝: 好的,為了簡化程式碼,我先簡化主程式的設計,將需求的索引值先預設好,以前面的範例來說…
class Solution {
public:
void fib(vector<int> n) {
int len = n[n.size()-1];
int fib_arr[len];
fib_arr[0] = 0;
fib_arr[1] = 1;
if(len>1){
int a = 0;
int b = 1;
for (int i = 2 ;i<=len;i++){
fib_arr[i] = a+b;
a = b;
b = fib_arr[i];
}
}
for(int i = 0 ;i<n.size() ;i++){
cout << fib_arr[n[i]] << "\n";}
}
};
int main() {
Solution s;
vector<int> n = {1,5,8};
s.fib(n);
return 0;
}
🦝: fib_arr就是用來記錄計算過的數列值,我們透過迴圈的方式先將所有索引值中最大索引值的數值計算出來,在計算的過程中也同時進行紀錄,之後其他的索引值就可以到fib_arr中找出對應的數列值,而不需要重複進行計算了。
🐯: 紀錄表的應用可以大幅改善運算資源的浪費,很好的優化方式。
🐯: 那我們今天的面試就到此結束。感謝你的參與。
🦝: 謝謝。
解釋解題思路清楚明確,且在撰寫程式碼時會同時解釋該段程式碼作用。
雖然使用python撰寫程式,但interviewee有同時說明底層實作的原理。
缺乏了舉例說明與程式碼可行性驗證的階段,interviewee一開始說明解題邏輯時沒有搭配畫面內容,稍顯可惜。
1:34即使費氏數列很值觀但還是要重新確定一次題目REACTO裡面少了Repeat
10:25改良方法不要把前面寫的蓋掉,直接在下面複製一個方便比較兩者差別
21:05你可以直接把fib_arr指定為global variable ,因為你每呼叫一次fib他還是會再重新計算一次,由於費事數列是固定的,那乾脆把表移到外面,可以更加減少計算冗餘