面試經歷-演算法篇

04-12

數據結構和演算法基本是後端碼農面試中必考項，根據個人經驗，面試官出的題大多來自leetcode和《編程之美》，甚至很少碰到會對原題進行變形的。所以，如果你能把leetcode上Easy級的全部刷完，Medium級的稍微看看，應付演算法方面的面試基本沒啥問題。

本文試圖將面試中遇到過的各類數據結構和演算法相關的面試題進行總結(不提供求解，同學們可以自行上網找)。

二進位

二進位相關面試題，基本運用以下三個性質，都能找到解題思路。

常用的等式：-n=~(n-1)=~n+1；
獲取整數n的二進位中最後一個1：n&(-n)或者n&~(n-1)；
去掉整數n的二進位中最後一個1：n&(n-1)。

常見問題

1、用位運算實現加法；

2、求二進位表示中1的個數；

數組

數組相關的面試題一般通過查找和排序進行考查，通常考慮的出發點：

數組中數據的特徵，如鴿籠原理，計數等；
巧妙地利用下標；
二分法；
巧妙地利用標記(指針)，類似於快速排序中的標記；

常見問題

1、給定一個數組，共有N-1個元素，每個元素由1到N組成，且不重複，找出數組中不存在的元素。

2、實現冒泡排序。註：考慮提前退出。

3、找出整數數組中的中位數；

4、給定一個數組，找出從1開始，第一個不在裡面的正整數；

5、找出數組中第k大元素；

6、對數組進行向右循環移位k位；

7、移除數組中的重複元素；

8、求數組中出現次數超過一半的元素；

9、對數組進行排序，要求，所有0元素在前，非0元素在後，且非0元素在排序前後相對位置不變；

字元串

字元串相關的面試題，解題思路與數組基本類似，但需要注意：

處理好各種細節，如內存越界，輸入非法等問題；
利用好字元計數；

常見問題

1、實現atoi函數；

2、實現memcpy函數；

3、字元串反轉；

4、給定一個字元串，按照單詞進行反轉；

5、實現字元串拷貝函數(strcpy)；

6、假設兩個字元串中所含有的字元和個數都相同我們就叫這兩個字元串匹配，比如：abcda和adabc，這兩個字元串是匹配的；

鏈表

求解鏈表相關的問題，一般解題思路：

通過多指針操作；
注意考慮鏈表本身是否健康，即是否存在環的情況；

常見問題

1、判斷兩個鏈表是否相交；

2、求兩個鏈表的交叉點；

3、判斷鏈表是否有環；

4、求鏈表環的入口點；

5、鏈表逆轉；

6、求鏈表倒數第k個節點；

7、鏈表循環移位；

8、將鏈表奇數位和偶數位上的節點拆分成兩個鏈表(奇偶鏈表)；

9、在O(1)時間刪除鏈表節點；

10、求鏈表的中間節點；

11、對鏈表進行重新排序，如給定鏈表為：L0→L1→…→Ln-1→Ln，重新排序後，變為： L0→Ln→L1→Ln-1→L2→Ln-2→…；

12、鏈接實現歸併排序；

二叉樹

二叉樹相關的題，一般沒有多少技巧性的東西，通常是能用遞歸方式實現就可以了。

常見問題

1、最近的共同祖先；

2、前、中、後序遍歷；

3、判斷是否為二叉排序樹；

4、二叉樹高度；

1. 求二叉樹中的節點個數；

2. 求二叉樹的深度；

3. 前序遍歷，中序遍歷，後序遍歷；

4.分層遍歷二叉樹（按層次從上往下，從左往右）；

5. 將二叉查找樹變為有序的雙向鏈表；

6. 求二叉樹第K層的節點個數；

7. 求二叉樹中葉子節點的個數；

8. 判斷兩棵二叉樹是否結構相同；

9. 判斷二叉樹是不是平衡二叉樹；

10. 求二叉樹的鏡像；

11. 求二叉樹中兩個節點的最低公共祖先節點；

12. 求二叉樹中節點的最大距離；

13. 由前序遍歷序列和中序遍歷序列重建二叉樹；

14.判斷二叉樹是不是完全二叉樹；

大數據

三板斧：點陣圖、索引(哈希)、分散式。

一個原則：盡量不寫磁碟(內存)，盡量少寫磁碟(壓縮)，盡量順序寫磁碟(追加)。

寫在最後

從面試官的角度來說，是想通過這種演算法題，看看面試者是不是」機靈「。但是面試官本身很難設計出一個」機靈「的演算法。所以大多數的面試官，也就是從網上找找，從書上看看。

從面試者的角度來說，平時真正關注演算法的同學就不多，能有意識地將演算法應用於實踐的就更少了。通常就是在換工作時，去網上刷刷題。

最終演算法面試就變成了一場，純粹地應試考試。至於以後工作上，是否能夠靈活運用那是另外一回事。個人認為，最好的演算法面試，應該是設計一個業務場景，然後與面試者一起探討解決方案，沒有標準答案，也沒有對錯，只關注能否有效地解決問題。其實，一個好的解決方案，並不是臨時抱佛腳，或者上網刷刷題能想出來的，更能全面地發現面試者的思維方式和經驗積累。通過這種方式，更容易找到合適的人，更能全面地考察到面試者。

(原創文章，轉載請註明。)