[[260358]]

春招來襲啦！又要面試?yán)玻?/p>

程序員面試展示什么最重要？當(dāng)時(shí)是你淵博的計(jì)算機(jī)學(xué)識(shí)，以及聰明的小腦瓜。

如果你學(xué)富五車，上知深度學(xué)習(xí)， 下知財(cái)務(wù)會(huì)計(jì)，那短短數(shù)小時(shí)也絕不夠你表演。所以，你一定得知曉面試官的套路，隨口丟出幾個(gè)應(yīng)景的“冷知識(shí)”賣個(gè)乖巧。

如果你基礎(chǔ)不行，三天前剛準(zhǔn)備轉(zhuǎn)碼，那就更得準(zhǔn)備幾個(gè)的小把戲，不用打腫臉也能充一回胖子。

基于這兩個(gè)需求，今天文摘菌就來給大家介紹三個(gè)討巧的數(shù)據(jù)結(jié)構(gòu)。面試當(dāng)中一提，那可是相當(dāng)撐場面。

這三個(gè)數(shù)據(jù)結(jié)構(gòu)就是。登登登等…

1. 布隆過濾器（bloom filter）

2. 前綴樹（prefix trie）

3. 環(huán)形緩沖（ring buffer）

先來說一下，為什么挑了這三個(gè)數(shù)據(jù)結(jié)構(gòu)。

首先我覺得，你提到的數(shù)據(jù)結(jié)構(gòu)要稍微冷門一些，這樣別人就會(huì)認(rèn)為你了解很多不同類型的數(shù)據(jù)結(jié)構(gòu)。但它不能太冷門，以免你的面試官要求你真正解釋實(shí)現(xiàn)細(xì)節(jié)或原理，那時(shí)你就game over了。***是你提到的數(shù)據(jù)結(jié)構(gòu)有點(diǎn)冷門，但你的面試官聽說過，對(duì)它有印象。

面試官都希望自己什么都知道，他們聽說過這種數(shù)據(jù)結(jié)構(gòu)但又不太了解，當(dāng)你向他們介紹時(shí)，他們就會(huì)覺得你懂得特別多。

除此之外，這些數(shù)據(jù)結(jié)構(gòu)還應(yīng)該具有實(shí)際用例，以便在技術(shù)面試的時(shí)候，你能有機(jī)會(huì)展開介紹。它雖然稍微有點(diǎn)冷門但也不能太low，你如果只知道一些菜雞水平的數(shù)據(jù)結(jié)構(gòu)（比如雙向鏈表），你的面試八成就涼了。

所以，這三個(gè)數(shù)據(jù)結(jié)構(gòu)就被***選中啦！

布隆過濾器

布隆過濾器是集合的概率版本。檢測集合是否包含某元素的時(shí)間復(fù)雜度為O(1)、空間復(fù)雜度為O(N)。Bloom過濾器也可以檢測出集合是否可能包含該元素，它的時(shí)間復(fù)雜度為O(1)，而空間復(fù)雜度只需要O(1)！

誰會(huì)真正使用布隆過濾器？

Chrome需要在不犧牲速度或空間的情況下保護(hù)你免受訪問垃圾郵件網(wǎng)站。

想象一下，如果每次你點(diǎn)擊一個(gè)鏈接，Chrome都必須進(jìn)行網(wǎng)絡(luò)通話來檢查它龐大的垃圾郵件URL數(shù)據(jù)庫，然后才允許你訪問這個(gè)頁面，這會(huì)不會(huì)讓你等瘋掉。此外，設(shè)想一下，如果Chrome改善延遲的解決方案是在本地存儲(chǔ)整個(gè)垃圾郵件URL列表，這根本就是不可行的！

所以，chrome在本地存儲(chǔ)了一個(gè)潛在垃圾郵件URL的布隆過濾器，這既節(jié)省時(shí)間又節(jié)省空間，可以快速檢查給定的URL是否為垃圾郵件。對(duì)于普通的URL，布隆過濾器對(duì)“非垃圾郵件”的響應(yīng)就足夠判定了。如果一個(gè)URL被標(biāo)記為“可能是垃圾郵件”，那么Google可以在跳轉(zhuǎn)之前檢查它真實(shí)數(shù)據(jù)庫。事實(shí)證明，當(dāng)你愿意犧牲絕對(duì)時(shí)，你可以做出偉大的事情！

布隆過濾器的原理

布隆過濾器的維基百科頁用大量的術(shù)語描述了實(shí)現(xiàn)細(xì)節(jié)，所以在這里我會(huì)用簡單的描述一下實(shí)現(xiàn)過程。如果你想要更精確的細(xì)節(jié)，你應(yīng)該去看看維基百科。我會(huì)略過很多步驟，但我會(huì)讓你有一個(gè)大致了解。

如果你想在Bloom過濾器中插入一個(gè)元素，首先假設(shè)有N個(gè)不同的確定性哈希函數(shù)。當(dāng)同一個(gè)元素輸入不同哈希函數(shù)時(shí)，會(huì)得到不同的值（沖突是可以有的）。

使用每個(gè)哈希函數(shù)的輸出作為數(shù)組的索引[注釋1，注釋2]，并對(duì)應(yīng)每個(gè)索引i將數(shù)組[i]設(shè)置為true。插入元素就完成了！插入元素的時(shí)間復(fù)雜度是O(1)，因?yàn)閷?duì)每個(gè)插入元素所做的唯一工作是運(yùn)行恒定數(shù)量的哈希函數(shù)，并設(shè)置恒定數(shù)量的數(shù)組索引。

那該如何檢查布隆過濾器是否包含該元素？ 再次運(yùn)行所有相同的哈希函數(shù)！

哈希函數(shù)是確定性的，因此相同的輸入應(yīng)返回相同的輸出。所以相對(duì)應(yīng)每個(gè)索引，檢查布隆過濾器的數(shù)組是否在該索引處設(shè)置為true即可。如果哈希函數(shù)輸出的數(shù)組的每個(gè)單元都為真，那么可以很高的概率說這個(gè)元素已經(jīng)插入到了布隆過濾器中。這一方法總是存在誤報(bào)的可能性。不過，布隆過濾器的一大特色是永遠(yuǎn)不會(huì)出現(xiàn)漏報(bào)。

那么，你需要多少個(gè)哈希函數(shù)，又需要多大的數(shù)組呢？這你就得好好算一番了。維基百科對(duì)它們的解釋更詳細(xì)，你值得一讀。

注釋1：如何使用哈希函數(shù)的輸出作為索引：設(shè)哈希函數(shù)輸出整數(shù)值M，取長度N。N%M（N mod M）得到一個(gè)值Q，即0≤Q

注釋2：實(shí)際上，你應(yīng)該使用位數(shù)組而不是普通數(shù)組。數(shù)組的每個(gè)元素至少需要1個(gè)字節(jié)，而你只需要為“數(shù)組”的每個(gè)元素存儲(chǔ)true / false。因此，你可以通過將其存儲(chǔ)為位數(shù)組來節(jié)省空間，這是這個(gè)數(shù)據(jù)結(jié)構(gòu)的重點(diǎn)。如果你想要聽起來很聰明，那么位數(shù)組（也就是位向量）也值得你在面試時(shí)提出。嗯，真正的面試專家建議總是在腳注中。

注釋3：嚴(yán)格來說，如果你的所有哈希函數(shù)都在O（1）時(shí)間內(nèi)運(yùn)行，那么插入的復(fù)雜度才是O（1）。

前綴樹（prefix trie）

前綴樹是一種數(shù)據(jù)結(jié)構(gòu)，允許你通過其前綴快速查找字符串，還可以查找有公共前綴的字符串。

我對(duì)介紹這一數(shù)據(jù)結(jié)構(gòu)的***條建議是，將它稱為“前綴樹”，而不僅僅是“樹”。這樣，你就讓面試官知道你是那種了解與前綴和后綴相關(guān)算法的人，并且你也希望對(duì)你的fancy數(shù)據(jù)結(jié)構(gòu)進(jìn)行準(zhǔn)確描述。后綴樹也是一個(gè)非常有趣的話題，但實(shí)現(xiàn)細(xì)節(jié)十分殘暴。這就是為什么我只是談?wù)撉熬Y樹，并且假裝了解后綴樹。

誰會(huì)真的用前綴樹？

基因組學(xué)研究人員！

事實(shí)證明，現(xiàn)代基因組研究在很大程度上依賴于字符串算法和數(shù)據(jù)結(jié)構(gòu)，因?yàn)槟阍噲D從組成基因組序列的數(shù)百萬個(gè)核苷酸中探索奧秘。對(duì)于基因組數(shù)據(jù)，你經(jīng)常需要對(duì)齊序列，找到差異或找到重復(fù)的模式。如果你想了解更多相關(guān)信息，可以先閱讀生物信息學(xué)讀物，然后參與“DNA測序算法”或“生物信息學(xué)算法”等課程。

如果你想要閱讀一些真正有意思的讀物，我強(qiáng)烈建議你讀一讀藥物基因組學(xué)。隨著基因組測序和字符串算法的進(jìn)步，我們實(shí)際上可以預(yù)測使用個(gè)體的基因組，來確定它們是否具有對(duì)藥物正確反應(yīng)的正確基因。例如，如果他們的基因組缺少用于產(chǎn)生處理某種藥物的酶的基因，那么藥物可能會(huì)對(duì)他們產(chǎn)生副作用。如果我們知道什么基因是重要的，我們可以給他們一種不同的藥物！

我承認(rèn)，前綴樹和基因組學(xué)之間的聯(lián)系不太緊密。其實(shí)前綴樹的最直接用法就是用來查字典啦！但光這么講不是忒無聊了點(diǎn)么。

前綴樹的原理

想象一下，你有一棵樹，每個(gè)節(jié)點(diǎn)都有一個(gè)包含26個(gè)子節(jié)點(diǎn)的數(shù)組，每個(gè)子節(jié)點(diǎn)對(duì)應(yīng)一個(gè)英文字母。（如果要包含其他字符，可以將26更改為不同的值。）要在你的樹中表示單詞，你將從根節(jié)點(diǎn)開始，沿著路徑向下走，并在每個(gè)節(jié)點(diǎn)添加一個(gè)字母。

例如（圖片來源維基百科），對(duì)于“tea”這個(gè)詞，你從根開始，被引導(dǎo)到t節(jié)點(diǎn)，然后是e，***是a。因此，搜索單詞需要O（N）的時(shí)間（其中N是單詞的長度），如果單詞的前綴不存在，則可以提前結(jié)束。如果我查詢“zzzzzzzz”，樹可以在“zz”之后結(jié)束查詢。

環(huán)形緩沖區(qū)（ring buffer）

環(huán)形緩沖區(qū)是使用普通數(shù)組的一種非常好的方式，它主要被用于處理數(shù)據(jù)流。

誰會(huì)真的使用環(huán)形緩沖區(qū)？

說不定Netflix會(huì)用？

我用google搜索“netflix ring buffer”，發(fā)現(xiàn)了他們發(fā)布了一些開源環(huán)緩沖區(qū)代碼。但問題是，公司真的會(huì)用他們已經(jīng)開源的代碼嘛？

環(huán)形緩沖區(qū)的原理

好啦好啦。真的還有人在讀這篇文章嘛。

如果你讀到了這兒，說明你基礎(chǔ)一定還不錯(cuò)，那就直接去維基百科瞅一眼這個(gè)數(shù)據(jù)結(jié)構(gòu)吧，比前兩個(gè)簡單多了！

總結(jié)一下，今天文摘菌介紹了三個(gè)重要的數(shù)據(jù)結(jié)構(gòu)：布隆過濾器（bloom filter），前綴樹（prefix trie），環(huán)形緩沖（ring buffer）。

想當(dāng)一個(gè)聰明程序員，這些結(jié)構(gòu)你值得擁有！

【本文是51CTO專欄機(jī)構(gòu)大數(shù)據(jù)文摘的原創(chuàng)譯文，微信公眾號(hào)“大數(shù)據(jù)文摘（ id: BigDataDigest）”】

戳這里，看該作者更多好文