NO IMAGE

演算法面試

什麼是演算法面試?

·不代表能夠“正確回答”每個演算法問題,合理的思考方向更重要,是正確完成演算法面試的前提;

·演算法面試優秀不意味著技術面試優秀;

·技術面試的遊戲不意味著能夠拿到offer

對一組資料進行排序

·這組資料有什麼樣的特徵?

·有沒有可能包含大量重複的元素?

  如果有這種可能的話,三路排序法是更好的選擇

如果可以肯定陣列中每個元素都是獨特的,那麼普通的快速排序法是最佳的。

·是否大部分資料距離它正確的位置很近?是否近乎有序?

  如果是這種可能的話,插入排序是更好的選擇

·是否資料的取值範圍非常有限?比如說對學生的成績排序。

  如果是這種可能的話,計數排序是更好的選擇

·對排序有什麼額外的要求?

  是否需要穩定排序?

  如果是的話,歸併排序是更好的選擇

·資料具體的儲存狀況是怎麼樣的?

  快速排序非常依賴陣列的隨機儲存

  若使用連結串列進行排序,歸併排序是更好的選擇

·資料的大小是否可以裝載在記憶體裡?

  資料量很大,或者記憶體很小,不足以裝載再記憶體裡,需要使用外排序演算法。

面試問題:

·專案經歷和專案中遇到的實際問題

·你遇到的印象最深的bug是什麼?

·物件導向

·設計模式

·網路相關、安全相關、記憶體相關、併發相關……

·系統設計;scalability

通過過去了解思考行為方式

·遇到的最大的挑戰?

·犯過的錯誤?

·遭遇的失敗?

·最享受的工作內容?

·遇到衝突的處理方式?

·做的最與眾不同的事兒?

準備好合適的問題問面試官

·整個小組的大概執行模式是怎樣的?

·整個專案的後續/中長期規劃是如何的?

·這個產品中的某個問題是如何解決的?

·為什麼選擇某些技術?標準?

·我對某個技術很感興趣,在你的小組中我會有怎樣的機會深入這種技術?

高階資料結構和演算法面試提及概率很低:

·紅黑樹

·B-Tree

·斐波那契堆

·計算幾何

·數論

·FFT

基礎演算法和資料結構

·各種排序演算法

·基礎資料結構和演算法的實現:如堆、二叉樹、圖……

·基礎資料結構的使用:如連結串列、棧、佇列、雜湊表、圖、Trie、並查集

·基礎演算法:深度優先、廣度優先、二分查詢、遞迴……

·基本演算法思想:遞迴、分治、回溯搜尋、貪心、動態規劃……

選擇合適的OJ(線上判題系統)

·LeetCode真實的面試問題 www.leetcode.com

·HackerRank對問題的分類很詳細
www.hackerrank.com

注意題目中的條件

·給定一個有序陣列……

·有一些題目中的條件本質是暗示:

  ·設計一個O(nlogn)的演算法——分治法(搜尋樹)、是否是考慮先排序,再找

O(n)或者O(logn)的演算法

  ·無需考慮額外的空間——考慮是否開闢額外空間,以空間換時間的方法

  ·資料規模大概是10000——設計O(n^2)的演算法

……

當沒有思路的時候

·用幾個簡單的測試用例、體驗一下

·不要忽視暴力解法。暴力解法通常是思考的起點

優化演算法

·遍歷常見的演算法思路

·遍歷常見的資料結構

·空間和事件的交換(雜湊表)

·預處理資訊(排序)

·在瓶頸處尋找答案:O(nlogn) O(n^2); O(n^3)

實際編寫問題

·極端條件的判斷

  -陣列為空?字串為空?數量為0?指標為NULL?

·變數名

·模組化、複用性