知識星球點選上方“芋道原始碼”，選擇“置頂公眾號”
技術文章第一時間送達！
原始碼精品專欄
來源：https://juejin.im/post/5b23761a6fb9a00e67148e9e
演演算法面試不僅僅是正確的回答問題
對於面試中遇到的大多數問題，都能有一個合理的思考路徑
什麼是演演算法面試？
-
讓大家在面對面試中的演演算法問題時，有一個合理的思考路徑:
-
不代表能夠“正確”回答每一個演演算法問題，但是合理的思考方向其實更重要，也是正確完成演演算法面試問題的前提
-
演演算法面試優秀不意味著技術面試優秀
-
技術面試優秀不意味著能夠拿到Offer
-
演演算法面試的目的不是給出一個“正確”答案，
-
而是展示給面試官你思考問題的方式。
“正確”本身是一個相對概念
-
演演算法面試不是高考。
-
把這個過程看作是和麵試官一起探討一個問題的解決方案。
-
對於問題的細節和應用環境，可以和麵試官溝通。
-
這種溝通本身很重要，它暗示著你思考問題的方式。
例子
我們需要對一組資料進行排序
-
設計排序介面，標準庫的設計，業務中排序演演算法。
-
排序是基礎操作，很重要。
解決
快速排序演演算法：O(nlogn)
-
忽略了演演算法使用的基礎環境。要動態選擇。
(向面試官提問):這組資料有什麼樣的特徵？
-
有沒有可能包含有大量重覆的元素？
-
如果有這種可能的話，三路快排是更好地選擇。
-
普通資料：普通快速排序就行了；java語言標準庫排序使用的三路快排。
-
是否大部分資料距離它正確的位置很近？是否近乎有序？
-
如果是這樣的話，插入排序是更好地選擇。
-
按照業務發生順序,先發生先完成,幾乎有序，插入排序是更好的選擇。
-
是否資料的取值範圍非常有限？比如對學生成績排序。
-
如果是這樣的話，計數排序是更好地選擇。高考成績取值範圍有限：計數排序更好。
(向面試官提問):對排序有什麼額外的要求？
-
是否需要穩定排序？
-
如果是的話，歸併排序是更好地選擇。
(向面試官提問):資料的儲存狀況是怎樣的？
-
是否是使用連結串列儲存的？
-
如果是的話，歸併排序是更好地選擇。
-
快排依賴於陣列的隨機存取。
(向面試官提問):資料的儲存狀況是怎樣的？
-
資料的大小是否可以裝載在記憶體裡？
-
資料量很大，或者記憶體很小，不足以裝載在記憶體裡，需要使用外排序演演算法。
對一組資料進行排序小結
-
有沒有可能包含有大量重覆的元素？
-
是否大部分資料距離它正確的位置很近？是否近乎有序？
-
是否資料的取值範圍非常有限？比如對學生成績排序。
-
是否需要穩定排序？
-
是否是使用連結串列儲存的？
-
資料的大小是否可以裝載在記憶體裡？
什麼是“正確”的回答一個演演算法問題
-
正確除了你能把程式碼編出來執行出正確的結果。正確還包含對問題的獨到見解；最佳化；程式碼規範；容錯性；
-
不僅僅是給出解決演演算法問題的程式碼,還要把上面因素包括。
-
如果是非常難的問題，對你的競爭對手來說，也是難的。
-
關鍵在於你所表達出的解決問題的思路。
-
甚至透過表達解題思路的方向，得出結論：這個問題的解決方案，應該在哪一個領域，我可以透過查閱或者進一步學習解決問題。
演演算法面試只是面試的一部分
-
演演算法面試只是技術面試的一部分。
-
根據你的簡歷和應聘職位的不同，勢必要考察其他技術方面。
-
專案經歷和專案中遇到的實際問題
-
解決能力，是否參與
-
深入思考
-
技術態度
面試前梳理自己簡歷上所寫到的專案：整理一下可能會問到的。
-
你遇到的印象最深的bug是什麼？
-
面向物件
-
設計樣式
-
網路相關；安全相關；記憶體相關；併發相關；…
-
系統設計；scalability（大規模）
技術面試優秀不意味著能夠拿到Offer
技術面試只是面試的一部分。面試不僅僅是考察你的技術水平，還是瞭解你的過去以及形成的思考行為方式。
-
關於過去：參與專案至關重要
專案經歷:
-
工作人士
-
研究生
-
本科生
-
畢業設計
-
其他課程設計（大作業）
如何找到專案？
-
實習
-
建立自己的專案
-
自己做小應用：計劃表；備忘錄；播放器…
-
自己解決小問題：爬蟲；資料分析；詞頻統計…
-
“不是專案”的專案：一本優秀的技術書籍的程式碼整理等…（github）
-
分享：自己的技術部落格；github等等
行為類問題
透過過去瞭解你的思考行為方式：
-
遇到的最大的挑戰？
-
犯過的錯誤？
-
遭遇的失敗？
-
最享受的工作內容？
-
遇到衝突的處理方式？
-
做的最與眾不同的事兒？
具體闡述：我在某某專案中遇到一個怎樣的演演算法問題：這個問題是怎樣的。它是我遇到的最大的挑戰,我是如何剋服解決的。
準備好合適的問題問面試官
-
整個小組的大概執行樣式是怎樣的？
-
整個專案的後續規劃是如何的？
-
這個產品中的某個問題是如何解決的？
-
為什麼會選擇某些技術？標準？
-
我對某個技術很感興趣，在你的小組中我會有怎樣的機會深入這種技術？
演演算法面試仍然是非常重要的一部分
如何準備演演算法面試
準備面試和準備演演算法面試 是兩個概念
-
演演算法面試，只是面試中的一個環節。
-
遠遠不需要啃完一本《演演算法導論》
-
強調理論證明
-
第一遍讀不需要弄懂證明
-
前幾遍閱讀應該記住結論就行了，不需要弄懂證明。把更多的精力放在演演算法思想上。
-
針對演演算法面試，演演算法導論裡面的理論推導和證明不是很重要的方面。
學習切記完美主義
-
高階資料結構和演演算法面試提及的機率很低
-
基礎的概念要知道，但是不需要實現等更深入的層面。
-
遠遠不需要到達資訊學競賽的水平
演演算法面試的準備範圍
-
不要輕視基礎演演算法和資料結構，而只關註“有意思”的題目
-
各種排序演演算法
-
基礎資料結構和演演算法的實現：如堆、二叉樹、圖…
-
基礎資料結構的使用：如連結串列、棧、佇列、雜湊表、圖、Trie、並查集…
-
基礎演演算法：深度優先、廣度優先、二分查詢、遞迴…
-
基本演演算法思想：遞迴、分治、回溯搜尋、貪心、動態規劃…
例子
Intel的面試題：
初始序列為1 8 6 2 5 4 7 3的一組數採用堆排序，當建堆(小根堆)完畢時，堆所對應的二叉樹中序遍歷序列為：( )
A. 8 3 2 5 1 6 4 7
B. 3 2 8 5 1 4 6 7
C. 3 8 2 5 1 6 7 4
D. 8 2 3 5 1 4 7 6
樂視的面試題：
對一個含有20個元素的有序陣列做二分查詢，陣列起始下標為1，則查詢A[2]的比較序列的下標為（）
A. 9、5、4、2
B. 10、5、3、2
C. 9、6、2
D. 20、10、5、3、2
考查二分查詢法。
阿裡巴巴面試題
一組記錄排序碼為（5、11、7、2、3、17），則利用堆排序方法建立的初始堆為（）
A. （11、5、7、2、3、17)
B. （11、5、7、2、17、3)
C. （17、11、7、2、3、5)
D. （17、11、7、5、3、2)
E. （17、7、11、3、5、2)
F. （17、7、11、3、2、5)
百度面試題
在圖採用鄰接表儲存時，求最小生成樹的Prim演演算法的時間複雜度為( )
-
O(n)
-
O(n+e)
-
O(n^2)
-
O(n^3)
重點關註
-
基礎資料結構的使用：如連結串列、棧、佇列、雜湊表、圖、Trie、並查集…
-
基礎演演算法：深度優先、廣度優先、二分查詢、遞迴…
-
基本演演算法思想：遞迴、分治、回溯搜尋、貪心、動態規劃…
選擇合適的OJ（Online judge）:線上判題系統
-
不要選擇過於偏向程式設計競賽的OJ *面向競賽難度過高
-
選擇合適的oj
-
leetcode
-
Online Portal for IT Interview
-
真實的面試問題
-
www.leetcode.com
-
HankeRank
-
特點是對於問題的分類很詳細。偏難，不過可以對某一類細分問題解決。
-
www.hackerrank.com
註意
-
在學習和實踐做題之間，要掌握平衡
-
基礎演演算法實現與演演算法思想
如何回答演演算法面試問題
解決演演算法面試問題的整體思路
-
註意題目中的條件
-
給定一個有序陣列…（二分法）
-
有一些題目中的條件本質是暗示
-
設計一個O(nlogn)的演演算法（分治：在一顆搜尋樹中完成任務，對於資料排序）
-
無需考慮額外的空間（用空間換時間上的最佳化）
-
資料規模大概是10000（O(n^2)就可以）
當沒有思路的時候
-
自己給自己幾個簡單的測試用例，試驗一下
-
不要忽視暴力解法。暴力解法通常是思考的起點。
例子
LeetCode 3 Longest Substring Without Repeating Characters
在一個字串中尋找沒有重覆字母的最長子串 如”abcabcbb”，則結果為”abc” 如”bbbbb”，則結果為”b”
-
對於字串s的子串s[i…j]
-
使用O(n^2)的演演算法遍歷i,j，可以得到所有的子串s[i…j]
-
使用O(length(s[i…j]))的演演算法判斷s[i…j]中是否含有重覆字母
-
三重迴圈：複雜度O(n^3)，對於n=100的資料，可行
最佳化演演算法
-
遍歷常見的演演算法思路
-
遍歷常見的資料結構
-
空間和時間的交換 （雜湊表）
-
預處理資訊（排序）
-
在瓶頸處尋找答案：O(nlogn) + O(n^2) ; O(n^3)
-
O(n^2)能否最佳化。
-
什麼樣的問題使用什麼樣的思路和資料結構。
實際編寫問題
-
極端條件的判斷
-
陣列為空？
-
字串為空？
-
數量為0？
-
指標為NULL?
-
程式碼規範:
-
變數名
-
模組化
-
如果你對 Dubbo / Netty 等等原始碼與原理感興趣，歡迎加入我的知識星球一起交流。長按下方二維碼噢：
目前在知識星球更新了《Dubbo 原始碼解析》目錄如下：
01. 除錯環境搭建
02. 專案結構一覽
03. 配置 Configuration
04. 核心流程一覽
05. 拓展機制 SPI
06. 執行緒池
07. 服務暴露 Export
08. 服務取用 Refer
09. 註冊中心 Registry
10. 動態編譯 Compile
11. 動態代理 Proxy
12. 服務呼叫 Invoke
13. 呼叫特性
14. 過濾器 Filter
15. NIO 伺服器
16. P2P 伺服器
17. HTTP 伺服器
18. 序列化 Serialization
19. 叢集容錯 Cluster
20. 優雅停機
21. 日誌適配
22. 狀態檢查
23. 監控中心 Monitor
24. 管理中心 Admin
25. 運維命令 QOS
26. 鏈路追蹤 Tracing
… 一共 69+ 篇
目前在知識星球更新了《Netty 原始碼解析》目錄如下：
01. 除錯環境搭建
02. NIO 基礎
03. Netty 簡介
04. 啟動 Bootstrap
05. 事件輪詢 EventLoop
06. 通道管道 ChannelPipeline
07. 通道 Channel
08. 位元組緩衝區 ByteBuf
09. 通道處理器 ChannelHandler
10. 編解碼 Codec
11. 工具類 Util
… 一共 61+ 篇
目前在知識星球更新了《資料庫物體設計》目錄如下：
01. 商品模組
02. 交易模組
03. 營銷模組
04. 公用模組
… 一共 17+ 篇
原始碼不易↓↓↓↓↓
點贊支援老艿艿↓↓
