文章目錄
- 第二章 面試需要的基礎知識
- 1.1 面試官談基礎知識
- 1.2 編程語言
- 1.3 數據結構
- 1.4 算法和數據操作
第二章 面試需要的基礎知識
1.1 面試官談基礎知識
- 數據結構和算法，編程能力，部分數學能力，問題分析和推理能力
- 編程基礎，計算機基礎，算法設計
- 計算機操作系統，編程語言，數據結構
1.2 編程語言
- 考察形式
- 語言的語法
- 通過實際寫代碼解決問題
- C++
- 推薦的書籍<effect c++>
- 設計模式中單例模式時常常考的內容
1.3 數據結構
- 數據結構是技術面試中的重點
- 主要圍繞著數組，鏈表，字符串，樹，隊列，棧幾種常見的數據結構
- 數組和鏈表是面試中常常考的兩種數據結構，由于使用了指針，應該注意程序的魯棒性2.
- 數組
- 數組需要實現申明空間大小，數組支持隨機存取，讀取時間復雜度為O(1),插入刪除操作時間復雜度為O(N)
- 動態數組的考察，數組和指針的關系
- 當我們遇到復雜的問題的時候，一個有效的方法就是從一個具體的問題入手，通過分析簡單具體的例子，找出普遍的規律。（二位數組的查找）
- 字符串
- C/C++中的字符串都是以“\n”結尾的。
- 為了節省內存，C/C++把常量字符串放到單獨的一個內存區域中，當使用幾個不同的指針指向的時候，實際指向的是相同的內存地址。
- 常考的字符串的復制，比較，插入等。可以打破常規思維，從后往前遍歷。
- 鏈表
- 鏈表是面試時候被問及最多的一種數據結構
- 鏈表的創建，插入刪除節點和查詢節點實現起來代碼量都不大。
- 在面試中如果要修改輸入數據時，最好問面試官是否允許進行修改。
在寫測試用例的時候，常常分為功能測試和特殊輸入測試。
- 樹
- 樹是一種在實際編程中常常用到的數據結構，由于樹的實驗涉及到大量的指針，所以面試中考的概率不大
- 面試中要考察的樹常常為二叉樹，常考查二叉樹的遍歷：
- 前序遍歷
- 中序遍歷
- 后序遍歷
3種遍歷方法都有循環和遞歸的時現，需要對這6種方法比較了解。
- 二叉樹的另外兩個特例是堆和紅黑樹
- 有很多快速找到最大值和最小值的算法都用到堆來實現
- 棧和隊列
- 棧是一個非常常見的數據結構，在計算機中被廣泛應用。
- 通常棧是一個不考慮排序的數據結構，找到最大值或者最小值需要O(N)的時間。
- 隊列是另外一種比較重要的數據結構
- 對列和棧兩個數據結構是相互聯系的，可以相互表示。
1.4 算法和數據操作
重點掌握二分查找，歸并排序，快速排序，能夠做到隨時隨地快速準確的用代碼實現他們。
很多算法都可以使用循環和遞歸實現，其中遞歸方法看起來代碼簡潔，但是性能不佳。
位操作應該也要進行掌握
- 查找和排序
- 查找和排序是程序設計中常用到的算法
- 查找比較簡單，包括：順序查找，二分查找，哈希查找和二叉樹查找。
- 如果面試中要對一個排好序的數組或者部分排序的數組進行查找，都可以考慮使用二分查找的方法
- 哈希表最主要的優點是可以完成在O(1)時間內查找某個元素，但是需要額外的空間來實現哈希表。
- 二叉搜索樹是樹結構在查找算法中的應用。
- 排序算法比查找算法要難一些，需要我們對常見的一些排序算法熟記于心。
- 插入排序，冒泡排序，歸并排序，快速排序等不同排序算法的優劣。
- 可以從空間消耗，平均時間復雜度和最壞時間復雜度去分析比較。
- 快速排序的代碼常常被要求寫出。
- 如果面試官要求實現一個排序算法，一定要問清楚排序算法的應用背景，再來決定使用哪種排序算法。
- 遞歸和循環
- 如歸針對一個問題需要重復多次計算相同的問題，則可以使用遞歸或者循環兩種方法。
- 遞歸代碼相比于循環代碼常常比較簡潔；在樹的前序，中序，后序遍歷中常常采用遞歸算法。如果面試中沒有說明用循環還是遞歸，最好先用循環實現后，再用遞歸實現。
測試用例：功能測試，邊界值測試，性能測試
- 位運算
- 位運算是把數字用二進制表示后，對每一位上的0或者1進行運算。
- 熟練掌握2進制和10進制之間的轉換關系，熟悉掌握二進制數的與，或，異或，左移好和右移操作。
