主要介紹算法面試的一些問(wèn)題、以及如何準(zhǔn)備算法面試

算法面試不僅僅是正確的回答問(wèn)題

對(duì)于面試中遇到的大多數(shù)問(wèn)題，都能有一個(gè)合理的思考路徑

什么是算法面試？

• 讓大家在面對(duì)面試中的算法問(wèn)題時(shí)，有一個(gè)合理的思考路徑:

• 不代表能夠“正確”回答每一個(gè)算法問(wèn)題，但是合理的思考方向其實(shí)更重要，也是正確完成算法面試問(wèn)題的前提

• 算法面試優(yōu)秀不意味著技術(shù)面試優(yōu)秀

• 技術(shù)面試優(yōu)秀不意味著能夠拿到Offer

什么是給出合理的思考路徑?

• 算法面試的目的不是給出一個(gè)“正確”答案，

• 而是展示給面試官你思考問(wèn)題的方式。

“正確”本身是一個(gè)相對(duì)概念

• 算法面試不是高考。

• 把這個(gè)過(guò)程看作是和面試官一起探討一個(gè)問(wèn)題的解決方案。

• 對(duì)于問(wèn)題的細(xì)節(jié)和應(yīng)用環(huán)境，可以和面試官溝通。

• 這種溝通本身很重要，它暗示著你思考問(wèn)題的方式。

例子

我們需要對(duì)一組數(shù)據(jù)進(jìn)行排序

• 設(shè)計(jì)排序接口，標(biāo)準(zhǔn)庫(kù)的設(shè)計(jì)，業(yè)務(wù)中排序算法。

• 排序是基礎(chǔ)操作，很重要。

解決

快速排序算法：O(nlogn)

• 忽略了算法使用的基礎(chǔ)環(huán)境。要?jiǎng)討B(tài)選擇。

(向面試官提問(wèn)):這組數(shù)據(jù)有什么樣的特征？

• 有沒(méi)有可能包含有大量重復(fù)的元素？

• 如果有這種可能的話，三路快排是更好地選擇。

• 普通數(shù)據(jù)：普通快速排序就行了；java語(yǔ)言標(biāo)準(zhǔn)庫(kù)排序使用的三路快排。

• 是否大部分?jǐn)?shù)據(jù)距離它正確的位置很近？是否近乎有序？

• 如果是這樣的話，插入排序是更好地選擇。

  • 按照業(yè)務(wù)發(fā)生順序,先發(fā)生先完成,幾乎有序，插入排序是更好的選擇。

• 是否數(shù)據(jù)的取值范圍非常有限？比如對(duì)學(xué)生成績(jī)排序。

  • 如果是這樣的話，計(jì)數(shù)排序是更好地選擇。高考成績(jī)?nèi)≈捣秶邢?#xff1a;計(jì)數(shù)排序更好。

(向面試官提問(wèn)):對(duì)排序有什么額外的要求？

• 是否需要穩(wěn)定排序？

  • 如果是的話，歸并排序是更好地選擇。

(向面試官提問(wèn)):數(shù)據(jù)的存儲(chǔ)狀況是怎樣的？

• 是否是使用鏈表存儲(chǔ)的？

  • 如果是的話，歸并排序是更好地選擇。

  • 快排依賴(lài)于數(shù)組的隨機(jī)存取。

(向面試官提問(wèn)):數(shù)據(jù)的存儲(chǔ)狀況是怎樣的？

• 數(shù)據(jù)的大小是否可以裝載在內(nèi)存里？

  • 數(shù)據(jù)量很大，或者內(nèi)存很小，不足以裝載在內(nèi)存里，需要使用外排序算法。

對(duì)一組數(shù)據(jù)進(jìn)行排序小結(jié)

• 有沒(méi)有可能包含有大量重復(fù)的元素？

• 是否大部分?jǐn)?shù)據(jù)距離它正確的位置很近？是否近乎有序？

• 是否數(shù)據(jù)的取值范圍非常有限？比如對(duì)學(xué)生成績(jī)排序。

• 是否需要穩(wěn)定排序？

• 是否是使用鏈表存儲(chǔ)的？

• 數(shù)據(jù)的大小是否可以裝載在內(nèi)存里？

什么是“正確”的回答一個(gè)算法問(wèn)題

• 正確除了你能把代碼編出來(lái)運(yùn)行出正確的結(jié)果。正確還包含對(duì)問(wèn)題的獨(dú)到見(jiàn)解；優(yōu)化；代碼規(guī)范；容錯(cuò)性；

  • 不僅僅是給出解決算法問(wèn)題的代碼,還要把上面因素包括。

  • 如果是非常難的問(wèn)題，對(duì)你的競(jìng)爭(zhēng)對(duì)手來(lái)說(shuō)，也是難的。

• 關(guān)鍵在于你所表達(dá)出的解決問(wèn)題的思路。

• 甚至通過(guò)表達(dá)解題思路的方向，得出結(jié)論：這個(gè)問(wèn)題的解決方案，應(yīng)該在哪一個(gè)領(lǐng)域，我可以通過(guò)查閱或者進(jìn)一步學(xué)習(xí)解決問(wèn)題。

算法面試只是面試的一部分

• 算法面試只是技術(shù)面試的一部分。

• 根據(jù)你的簡(jiǎn)歷和應(yīng)聘職位的不同，勢(shì)必要考察其他技術(shù)方面。

• 項(xiàng)目經(jīng)歷和項(xiàng)目中遇到的實(shí)際問(wèn)題

  • 解決能力，是否參與

  • 深入思考

  • 技術(shù)態(tài)度

面試前梳理自己簡(jiǎn)歷上所寫(xiě)到的項(xiàng)目：整理一下可能會(huì)問(wèn)到的。

• 你遇到的印象最深的bug是什么？

• 面向?qū)ο?/p>

• 設(shè)計(jì)模式

• 網(wǎng)絡(luò)相關(guān)；安全相關(guān)；內(nèi)存相關(guān)；并發(fā)相關(guān)；…

• 系統(tǒng)設(shè)計(jì)；scalability（大規(guī)模）

技術(shù)面試優(yōu)秀不意味著能夠拿到Offer

技術(shù)面試只是面試的一部分。面試不僅僅是考察你的技術(shù)水平，還是了解你的過(guò)去以及形成的思考行為方式。

• 關(guān)于過(guò)去：參與項(xiàng)目至關(guān)重要

項(xiàng)目經(jīng)歷:

• 工作人士

• 研究生

• 本科生

  • 畢業(yè)設(shè)計(jì)

  • 其他課程設(shè)計(jì)（大作業(yè)）

如何找到項(xiàng)目？

• 實(shí)習(xí)

• 創(chuàng)建自己的項(xiàng)目

  • 自己做小應(yīng)用：計(jì)劃表；備忘錄；播放器…

  • 自己解決小問(wèn)題：爬蟲(chóng)；數(shù)據(jù)分析；詞頻統(tǒng)計(jì)...

  • “不是項(xiàng)目”的項(xiàng)目：一本優(yōu)秀的技術(shù)書(shū)籍的代碼整理等…（github）

  • 分享：自己的技術(shù)博客；github等等

行為類(lèi)問(wèn)題

通過(guò)過(guò)去了解你的思考行為方式：

• 遇到的最大的挑戰(zhàn)？

• 犯過(guò)的錯(cuò)誤？

• 遭遇的失敗？

• 最享受的工作內(nèi)容？

• 遇到?jīng)_突的處理方式？

• 做的最與眾不同的事兒？

具體闡述：我在某某項(xiàng)目中遇到一個(gè)怎樣的算法問(wèn)題：這個(gè)問(wèn)題是怎樣的。它是我遇到的最大的挑戰(zhàn),我是如何克服解決的。

準(zhǔn)備好合適的問(wèn)題問(wèn)面試官

• 整個(gè)小組的大概運(yùn)行模式是怎樣的？

• 整個(gè)項(xiàng)目的后續(xù)規(guī)劃是如何的？

• 這個(gè)產(chǎn)品中的某個(gè)問(wèn)題是如何解決的？

• 為什么會(huì)選擇某些技術(shù)？標(biāo)準(zhǔn)？

• 我對(duì)某個(gè)技術(shù)很感興趣，在你的小組中我會(huì)有怎樣的機(jī)會(huì)深入這種技術(shù)？

算法面試仍然是非常重要的一部分

如何準(zhǔn)備算法面試

準(zhǔn)備面試和準(zhǔn)備算法面試 是兩個(gè)概念

• 算法面試，只是面試中的一個(gè)環(huán)節(jié)。

• 遠(yuǎn)遠(yuǎn)不需要啃完一本《算法導(dǎo)論》

  • 強(qiáng)調(diào)理論證明

  • 第一遍讀不需要弄懂證明

  • 前幾遍閱讀應(yīng)該記住結(jié)論就行了，不需要弄懂證明。把更多的精力放在算法思想上。

• 針對(duì)算法面試，算法導(dǎo)論里面的理論推導(dǎo)和證明不是很重要的方面。

?

學(xué)習(xí)切記完美主義

• 高級(jí)數(shù)據(jù)結(jié)構(gòu)和算法面試提及的概率很低

• 基礎(chǔ)的概念要知道，但是不需要實(shí)現(xiàn)等更深入的層面。

• 遠(yuǎn)遠(yuǎn)不需要到達(dá)信息學(xué)競(jìng)賽的水平

算法面試的準(zhǔn)備范圍

• 不要輕視基礎(chǔ)算法和數(shù)據(jù)結(jié)構(gòu)，而只關(guān)注“有意思”的題目

• 各種排序算法

• 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和算法的實(shí)現(xiàn)：如堆、二叉樹(shù)、圖…

• 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的使用：如鏈表、棧、隊(duì)列、哈希表、圖、Trie、并查集…

• 基礎(chǔ)算法：深度優(yōu)先、廣度優(yōu)先、二分查找、遞歸…

• 基本算法思想：遞歸、分治、回溯搜索、貪心、動(dòng)態(tài)規(guī)劃…

例子

Intel的面試題：

初始序列為1 8 6 2 5 4 7 3的一組數(shù)采用堆排序，當(dāng)建堆(小根堆)完畢時(shí)，堆所對(duì)應(yīng)的二叉樹(shù)中序遍歷序列為：( )

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

樂(lè)視的面試題：

對(duì)一個(gè)含有20個(gè)元素的有序數(shù)組做二分查找，數(shù)組起始下標(biāo)為1，則查找A[2]的比較序列的下標(biāo)為（）

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)

百度面試題

在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹(shù)的Prim算法的時(shí)間復(fù)雜度為( )

• O(n)

• O(n+e)

• O(n^2)

• O(n^3)

重點(diǎn)關(guān)注

• 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的使用：如鏈表、棧、隊(duì)列、哈希表、圖、Trie、并查集…

• 基礎(chǔ)算法：深度優(yōu)先、廣度優(yōu)先、二分查找、遞歸…

• 基本算法思想：遞歸、分治、回溯搜索、貪心、動(dòng)態(tài)規(guī)劃…

選擇合適的OJ（Online judge）:在線判題系統(tǒng)

• 不要選擇過(guò)于偏向程序設(shè)計(jì)競(jìng)賽的OJ *面向競(jìng)賽難度過(guò)高

• 選擇合適的oj

• leetcode

  • Online Portal for IT Interview

  • 真實(shí)的面試問(wèn)題

  • www.leetcode.com

• HackerRank

  • 特點(diǎn)是對(duì)于問(wèn)題的分類(lèi)很詳細(xì)。偏難，不過(guò)可以對(duì)某一類(lèi)細(xì)分問(wèn)題解決。

  • www.hackerrank.com

注意

• 在學(xué)習(xí)和實(shí)踐做題之間，要掌握平衡

• 基礎(chǔ)算法實(shí)現(xiàn)與算法思想

如何回答算法面試問(wèn)題

解決算法面試問(wèn)題的整體思路

• 注意題目中的條件

  • 給定一個(gè)有序數(shù)組...（二分法）

• 有一些題目中的條件本質(zhì)是暗示

  • 設(shè)計(jì)一個(gè)O(nlogn)的算法（分治：在一顆搜索樹(shù)中完成任務(wù)，對(duì)于數(shù)據(jù)排序）

  • 無(wú)需考慮額外的空間（用空間換時(shí)間上的優(yōu)化）

  • 數(shù)據(jù)規(guī)模大概是10000（O(n^2)就可以）

當(dāng)沒(méi)有思路的時(shí)候

• 自己給自己幾個(gè)簡(jiǎn)單的測(cè)試用例，試驗(yàn)一下

• 不要忽視暴力解法。暴力解法通常是思考的起點(diǎn)。

例子

LeetCode 3 Longest Substring Without Repeating Characters

在一個(gè)字符串中尋找沒(méi)有重復(fù)字母的最長(zhǎng)子串 如”abcabcbb”，則結(jié)果為”abc” 如”bbbbb”，則結(jié)果為”b”

• 對(duì)于字符串s的子串s[i...j]

• 使用O(n^2)的算法遍歷i,j，可以得到所有的子串s[i...j]

• 使用O(length(s[i...j]))的算法判斷s[i...j]中是否含有重復(fù)字母

• 三重循環(huán)：復(fù)雜度O(n^3)，對(duì)于n=100的數(shù)據(jù)，可行

優(yōu)化算法

• 遍歷常見(jiàn)的算法思路

• 遍歷常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)

• 空間和時(shí)間的交換 （哈希表）

• 預(yù)處理信息（排序）

• 在瓶頸處尋找答案：O(nlogn) + O(n^2) ; O(n^3)

  • O(n^2)能否優(yōu)化。

• 什么樣的問(wèn)題使用什么樣的思路和數(shù)據(jù)結(jié)構(gòu)。

實(shí)際編寫(xiě)問(wèn)題

• 極端條件的判斷

  • 數(shù)組為空？

  • 字符串為空？

  • 數(shù)量為0？

  • 指針為NULL?

• 代碼規(guī)范:

  • 變量名

  • 模塊化

  • 復(fù)用性

總結(jié)

以上是生活随笔為你收集整理的算法与面试之-如何准备算法面试的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。