# [509. Fibonacci Number](https://leetcode.com/problems/fibonacci-number/) 🐯: interviewer 🦝 : interviewee 暱稱 布撥(Pawmi) >[video](https://youtu.be/5zIShr5qc8I) > ## 模擬面試過程 🐯:布撥先生你好，歡迎來到本公司，本次面試為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++ 來撰寫我的程式碼。 ## 解法 1 ``` cpp 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個數值，這樣就可以避免重複計算的發生。 🦝: 我現在來修改一下程式的做法。 ## 解法 2 ```cpp 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) ``` 🐯: 我理解了，那你能改寫前段的程式碼來實作紀錄表的方案嗎? 🦝: 好的，為了簡化程式碼，我先簡化主程式的設計，將需求的索引值先預設好，以前面的範例來說.... ## 延伸解法 3 ```cpp 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中找出對應的數列值，而不需要重複進行計算了。 🐯: 紀錄表的應用可以大幅改善運算資源的浪費，很好的優化方式。 🐯: 那我們今天的面試就到此結束。感謝你的參與。 🦝: 謝謝。 # 對其他同學的批評 ## 抹茶-Matcha ### interviewer - [ ] 優點 * 有給interviewee明確的指示，一步一動作。 - [ ] 可改進的地方 * 把題目給的過於明確，可能會導致後續與interviewee沒有更多的討論空間，coding interview淪為線上觀看別人寫LeetCode。 * 或許可以用一些實務場景來對題目進行包裝，也能夠以此延伸討論方向。 ### interviewee - [ ] 優點 * 在畫面的呈現上有經過思考與設計，範例與遞迴的結構都能夠明確的呈現。 - [ ] 可改進的地方 * [08:01](https://youtu.be/tg1ID5F-dUg?si=buE_qKSK6DKlWQbh&t=480):有口誤，應該是空間複雜度。 ## 屎地芬森-Stevenson ### Interviewer - [ ] 優點 * 模擬面試先預設了題目已經預先傳送給Interviewee，解決了Interviewee畫面已經先有完整題目的不合理處。 * Interviewer 每次給的指示都很明確，不會讓Interviewee在實作時摸不清頭緒。 - [ ] 可改進的地方 * 一開始自稱面試官，以及說這是你的"工作"，聽起來蠻有壓迫感的，不太有利於後續的對等討論。 ### Interviewee - [ ] 優點 * 在驗證作法可行性時連帶特殊的情況都有一併考慮，且撰寫程式的過程也會附帶說明。 * 撰寫程式碼與講解時，整體過程很流程。 - [ ] 可改進的地方 * 說明完解題思路後，可以跟Interviewer進行相應的討論，或是反向提問，來讓Interviewer 更加理解你的想法，也避免發生程式需求上的落差。 ## 優嬉兔-UCII ### interviewer - [ ] 優點 * interviewer一開始有透過interviewee相關的經驗著手，進而延伸至題目本身，轉折設計良好。 - [ ] 可改進的地方 * interviewer後續在進行延伸討論時問題太過直白，例如直接詢問時間複雜度等，可以提出一些可能的改進方向，待interviewee完成改進後，再橫向進行時間複雜度比較。 * ### interviewee - [ ] 優點 * 口說速度勻稱，咬字清楚 * 有表格跟圖片搭配說明，能清楚理interviewee欲表達概念。 - [ ] 可改進的地方 * 第一題與第二題的連接方式設計不太合理，怎麼是interviewee提出自己接下來要做什麼題目。 * 影片中interviewee 與 interviewer區分不易，如果剪輯不易，建議可以在影片畫面角落加上不同貼圖來區分目前是哪一位在說話。 ## Huaxin ### 他評 - [ ] 優點 * 再驗證程式可行性時有透過範例逐步將演算法運作的過程打在畫面上，能夠幫助interviewer理解。 - [ ] 可以改進的地方 * 英文面試開始時可以說明一下問題的應用場景，取代開頭直接說 "We have a problem"。 ## 牙塑-Wind ### 優點 解釋解題思路清楚明確，且在撰寫程式碼時會同時解釋該段程式碼作用。 雖然使用python撰寫程式，但interviewee有同時說明底層實作的原理。 ### 可以改進的地方 缺乏了舉例說明與程式碼可行性驗證的階段，interviewee一開始說明解題邏輯時沒有搭配畫面內容，稍顯可惜。 ## 自我敦促 * 需要對題目進行更好的包裝，避免直接使用原題目進行面試。 * 在提出Approch時都直接進到coding環節，應該多跟interviewer進行討論與提問。 * 在撰寫程式時應該多加說明，不要只是乾打程式。 * 範例應該多舉一些，最好要加上特別情況的說明。 * 有注意到部分同學的演算法時間複雜度計算錯誤，這種極易被辨識出的錯誤應該要盡可能避免。 ## 第四次作業-他評01 [1:34](https://youtu.be/5zIShr5qc8I?t=94)即使費氏數列很值觀但還是要重新確定一次題目REACTO裡面少了Repeat [10:25](https://youtu.be/5zIShr5qc8I?t=625)改良方法不要把前面寫的蓋掉，直接在下面複製一個方便比較兩者差別 [21:05](https://youtu.be/5zIShr5qc8I?t=1265)你可以直接把fib_arr指定為global variable ，因為你每呼叫一次fib他還是會再重新計算一次，由於費事數列是固定的，那乾脆把表移到外面，可以更加減少計算冗餘