演算法面試表格

1. 海康威視研究院演算法崗面試經驗

海康威視研究院演算法崗面試經驗總結如下：

1. 面試流程：

   • 自我介紹：簡短介紹個人背景、教育經歷及專業技能。
   • 重點項目介紹：詳細闡述參與過的重點項目，突出自己的貢獻和成果。
   • 項目提問：面試官會針對項目細節進行提問，考察面試者的項目經驗和問題解決能力。
   • 機器學習與CV提問：涉及邏輯回歸、梯度彌散與爆炸、激活函數、L2與L1正則化、數據增強、小樣本學習、防止過擬合等知識點。
   • 演算法題提問：考察面試者的邏輯思維能力和數據結構與演算法的應用能力，如IOU計算、閉合曲線面積計算、圖像旋轉演算法等。
   • 對面試者問題的回答：面試者可以提出自己的問題，與面試官進行交流。

2. 專業技能要求：

   • 深入理解機器學習理論：熟悉常用的損失函數、激活函數、正則化方法，並能分析並解決實際項目中的問題。
   • 演算法題解決能力：具備較強的邏輯思維能力，能夠靈活運用數據結構與演算法解決實際問題。
   • 計算機基礎：掌握堆與棧的區別、Python編程的全局解釋器鎖與上下文管理器等基礎知識。

3. 面試表現建議：

   • 深入分析問題的能力：能夠清晰地解釋使用特定損失函數的原因，提出解決項目問題的策略。
   • 理論結合實際：在回答問題時，盡量結合項目經驗，展現自己的實際操作能力。
   • 邏輯思維清晰：在演算法題和理論問題回答中，保持清晰的邏輯思路，條理分明。
   • 積極互動：在面試過程中，積極與面試官交流，展示自己的專業素養和求知慾。

4. 綜合能力評估：

   • 面試官會通過面試者的回答，評估其專業技能、邏輯思維、問題解決能力和實際項目經驗。
   • 面試者需要展現出扎實的理論基礎和實際項目經驗，以及靈活應對各類問題的能力。

2. 【程序猿必備】數據結構與演算法精選面試題

編程面試主要由數據結構問題和演算法問題組成，這些問題旨在評估應聘者的編程技能、問題解決能力和對基本數據結構與演算法的理解。以下是一些精選的數據結構與演算法面試題，涵蓋了數組、鏈表、字元串、二叉樹以及其他常見的演算法問題。

數組是最基本的數據結構之一，它將元素存儲在一個連續的內存位置。數組的主要優點是，如果知道索引，它可以提供快速的O(1)搜索，但從數組中添加和刪除元素通常較慢。

• 如何在一個1到100的整數數組中找到丟失的數字？

  方法：可以使用求和公式（n*(n+1)/2）計算1到100的總和，然後減去數組中所有元素的和，得到的差值就是丟失的數字。

• 如何在給定的整數數組中找到重復的數字？

  方法：使用哈希表（字典）記錄每個數字出現的次數，或者對數組進行排序後檢查相鄰元素是否相同。

• 如何在未排序整數數組中找到最大值和最小值？

  方法：遍歷數組一次，同時記錄最大值和最小值。

• 如何找到數組所有和等於一個給定數的數對？

  方法：使用哈希表記錄已經遍歷過的元素，對於當前元素，檢查是否存在一個已遍歷過的元素與之相加等於給定數。

• 如果一個數組包含多重復制，那麼如何找到重復的數字？

  方法：同樣可以使用哈希表記錄每個數字出現的次數，當發現某個數字出現次數超過1時，即為重復數字。

• 在Java中如何從給定數組中刪除多重復制？

  方法：使用HashSet（集合）去重，或者利用排序後相鄰元素相同的特性進行去重。

• 如何使用快速排序演算法對整數數組進行排序？

  方法：快速排序是一種分治演算法，通過選擇一個基準元素，將數組分為兩部分，遞歸地對這兩部分進行排序。

• 如何在不使用任何庫的情況下從數組中刪除多重復制？

  方法：手動實現去重邏輯，如使用兩個指針或哈希表等。

鏈表是另一種常見的數據結構，它以節點的方式存儲元素，每個節點包含存儲的值和指向下一個節點的指針。鏈表的主要優點是插入和刪除操作較快，但查找元素通常較慢。

• 如何在一次遍歷中找到單個鏈表的中值？

  方法：使用快慢指針，快指針每次移動兩步，慢指針每次移動一步，當快指針到達鏈表末尾時，慢指針指向的節點即為中值節點。

• 如何證明給定的鏈表是否包含循環？如何找到循環的頭節點？

  方法：使用快慢指針，如果鏈表存在循環，快指針和慢指針最終會相遇。相遇後，將其中一個指針重新指向鏈表頭部，兩個指針同時移動，再次相遇時即為循環的頭節點。

• 如何使鏈表反向？

  方法：遍歷鏈表，逐個改變節點的指針方向。

• 如何在不使用遞歸的情況下逆轉單鏈表？

  方法：使用迭代方法，通過三個指針（prev、curr、next）來逆轉鏈表。

• 如何得到單鏈表的長度？

  方法：遍歷鏈表，計數節點的數量。

字元串是編程面試中的另一個熱門話題，因為字元串操作是編程中常見的需求。字元串可以看作是一個字元數組，因此解決基於數組的編程問題所學習的技術也可以用於解決字元串編程問題。

• 如何從字元串列印重復字元？

  方法：遍歷字元串，使用哈希表記錄每個字元出現的次數，然後列印出現次數大於1的字元。

• 如何檢查兩個字元串是否互相顛倒？

  方法：將其中一個字元串反轉後，比較兩個字元串是否相等。

• 如何從字元串中列印第一個非重復字元？

  方法：使用哈希表記錄每個字元出現的次數，然後遍歷字元串找到第一個出現次數為1的字元。

• 如何使用遞歸反轉給定的字元串？

  方法：遞歸地交換字元串的首尾字元，直到達到字元串的中間位置。

• 如何計算字元串中給定字元的出現次數？

  方法：遍歷字元串，計數給定字元的出現次數。

二叉樹是一種重要的樹形數據結構，每個節點最多有兩個子節點（左子節點和右子節點）。二叉樹在編程面試中經常出現，因為它們是許多演算法和數據結構的基礎。

• 如何實現二叉搜索樹？

  方法：定義節點類，包含值、左子節點和右子節點的引用，然後實現插入、查找和刪除等操作。

• 如何在給定的二叉樹中執行先序遍歷？

  方法：按照「根節點-左子樹-右子樹」的順序遍歷二叉樹。

• 如何在不使用遞歸的情況下按順序遍歷給定的二叉樹？

  方法：使用棧或隊列等輔助數據結構實現迭代遍歷。

• 如何實現後序遍歷演算法？

  方法：按照「左子樹-右子樹-根節點」的順序遍歷二叉樹。

除了基於數據結構的問題外，大多數編程工作面試還會涉及演算法、設計、位操作和基於邏輯的問題。

• 如何實現冒泡排序演算法？

  方法：重復地遍歷要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。遍歷數列的工作是重復進行的，直到沒有再需要交換的元素為止。

• 如何實現迭代快速排序演算法？

  方法：選擇一個基準元素，通過一趟排序將待排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另一部分的所有數據要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

• 如何實現歸並排序演算法？

  方法：採用分治法（Divide and Conquer），將一個大列表分成兩個小列表，分別排序，然後將兩個已排序的小列表合並成一個完整的排序列表。

• 如何在不使用第三個變數的情況下交換兩個數字？

  方法：通過加減法或位運算實現兩個數的交換。

以下是一些相關圖片，展示了數據結構與演算法在編程面試中的重要性：

准備這些面試題不僅有助於提高你的編程技能，還能讓你對在真正的編程工作面試中可能遇到的問題有更深入的了解。一旦你掌握了這些問題，你就應該有足夠的信心參加任何電話或面對面的面試。

3. 演算法面試題——動態規劃Kadane』s algorithm

動態規劃是大公司面試必考的演算法題。其中，「最大子序和」是其中的經典：

面試官：年輕人，前面表現的不錯嘛！看下這道題，給你這個數組[-2, 1, -3, 4, -1, 2, 1, -5, 4]，找到其中和最大的連續子數組，返回最大值。

我：

使用Kadane』s Algorithm解決這個問題。Kadane』s Algorithm可以簡單理解為動態規劃的一種應用，它通過維護兩個變數：localMax和globalMax，來計算連續子數組的最大和。localMax表示以當前元素結尾的子數組的最大和，而globalMax則記錄遍歷過程中發現的最大值。

我們以數組[-2, 1, -3, 4, -1, 2, 1, -5, 4]為例，從左到右遍歷數組。

當遍歷到元素4時，localMax為4（因為4是當前元素），globalMax也更新為4（因為這是遍歷到的第一個元素）。

遍歷到元素-1時，我們考慮兩種情況：
1. 包括前面的元素4，即localMax更新為4 + (-1) = 3。
2. 不包括前面的元素4，即從元素-1開始新的子數組。由於-1 > 3，我們選擇-1作為新的localMax。
因此，globalMax更新為-1。

遍歷到元素2時，localMax為2（因為2 > 1），globalMax更新為2。

遍歷到元素1時，localMax更新為3（因為3 > 2 + 1），globalMax也更新為3。

遍歷到元素-5時，我們考慮兩種情況：
1. 包括前面的元素3，即localMax更新為3 + (-5) = -2。
2. 不包括前面的元素3，即從元素-5開始新的子數組。由於-5 < 3，我們選擇3作為新的localMax。
因此，globalMax更新為3。

遍歷到元素4時，localMax為4（因為4 > 3 + 4），globalMax更新為4。

最終，我們得到數組的最大子序和為4。

動態規劃和Kadane』s Algorithm在解決「最大子序和」問題時，通過維護局部最優解和全局最優解，避免了暴力演算法中的重復計算，大大提高了效率。

理解Kadane』s Algorithm的關鍵在於，它通過比較當前元素和當前元素加上前面元素的最大和，來決定是否更新局部最優解。這樣，我們不僅避免了重復計算，還能在遍歷過程中不斷更新全局最優解。

此外，Kadane』s Algorithm在解決類似問題時，如「買賣股票的最佳時機」，同樣可以應用動態規劃的思想，通過維護局部最優解和全局最優解，來找到最優策略。

動態規劃和Kadane』s Algorithm是解決一系列動態規劃問題的有效工具，通過理解和應用這些演算法，可以大大提高解決問題的效率和准確性。

4. 面試會出哪些經典演算法題

如下：

1、排序演算法∶快速排序、歸並排序、計數排序

2、搜索演算法∶回溯、遞歸、剪枝技巧

3、圖論∶最短路、最小生成樹、網路流建模

4、動態規劃：背包問題、最長子序列、計數問題

5、基礎技巧：分治、倍增、二分、貪心

6、數組與鏈表：單/雙向鏈表、跳舞鏈

7、棧與隊列

8、樹與圖：最近公共祖先、並查集

9、哈希表

10、堆：大/小根堆、可並堆

11、字元串∶字典樹、後綴樹

演算法簡介：

演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。

如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。

演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。

形式化演算法的概念部分源自嘗試解決希爾伯特提出的判定問題，並在其後嘗試定義有效計算性或者有效方法中成形。

這些嘗試包括庫爾特·哥德爾、Jacques Herbrand和斯蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義為形式化演算法的情況。