據(jù)Top K問題解析：內(nèi)存受限下的最小堆解法)
去年春招的時候很多師弟師妹跑來問我百度實習生的筆試該怎么準備。我翻出當年自己做過的題單發(fā)現(xiàn)那道附加題放在今天看依然是很有代表性的海量數(shù)據(jù)考題給你一個包含大量整數(shù)的數(shù)據(jù)文件假設(shè)有10億個整數(shù)內(nèi)存只有幾百MB要求找出其中最大的1000個數(shù)。題目看似簡單卻能在“內(nèi)存受限”這個條件下刷掉一大半人。這篇文章就把這道題從頭到尾拆透包括我自己的解題過程和踩過的坑希望能幫到正在準備大廠實習面試的朋友。1. 題目還原與考點拆解1.1 題目原貌百度2015春季實習生招聘的這道附加題核心描述大致是這樣的有一個二進制文件里面按順序存儲了10億個32位整數(shù)也就是大概4GB的數(shù)據(jù)量。現(xiàn)在給你一臺內(nèi)存只有512MB的機器要求用盡可能快的方式輸出其中最大的1000個數(shù)。需要注意的是這道題在當時并不是獨立出現(xiàn)的而是作為整套筆試題的附加部分。和前面的基礎(chǔ)算法題不同附加題往往沒有標準答案面試官更看重你的思考過程。也正因為如此它其實是一個非常好的“壓力測試”題目你只有在有限的內(nèi)存條件和時間限制下拿出一個可行且高效的方案才能讓面試官眼前一亮。為什么我說這道題有代表性因為它同時考察了三個層面的能力第一對基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的掌握比如堆、分治這些概念第二對真實硬件環(huán)境的理解也就是內(nèi)存、磁盤IO的取舍第三對工程化方案的敏感度能不能從“做題家”思維切換到“解決實際問題”的思維。這三個層面恰恰是大廠招聘實習生時最看重的素質(zhì)。1.2 面試官真正想考察的點很多第一次看到這道題的同學第一反應(yīng)是“直接排序不就行了”。在內(nèi)存充足的前提下對10億個數(shù)排序然后取前1000個當然是可以的。但問題就在這里題目明確限制了內(nèi)存只有512MB而10億個整數(shù)占4GB根本不可能一次性載入內(nèi)存。就算你強行用虛擬內(nèi)存頻繁的缺頁中斷也會讓程序慢到無法接受。所以這道題的第一個隱含考點就是你能不能意識到“單機全量排序不可行”。意識到這個之后你需要繼續(xù)拆解問題并不需要全局有序只需要前1000個最大數(shù)。這個“只需要”三個字就是你優(yōu)化空間的突破口。此外這道題還考察了溝通能力。面試官在聽你講方案的時候會故意設(shè)置一些模糊地帶比如“如果數(shù)據(jù)量再翻10倍怎么辦”“如果前1000個里面允許誤差呢”。這些問題沒有標準答案但你的應(yīng)對方式會直接反映你對問題本質(zhì)的理解深度。我在面試別人的時候最怕聽到的就是應(yīng)聘者背答案一旦追問幾句就開始支支吾吾。真正的理解應(yīng)該是面對追問時能夠不斷迭代自己的方案。2. 海量數(shù)據(jù)Top K的4種解法對比2.1 排序法最直觀也最容易掛先說說最直覺的解法也就是全量排序。把4GB數(shù)據(jù)全部讀入內(nèi)存用快速排序或者歸并排序整體排序然后取前1000個。這個方案的代碼量確實很小大概十幾行就能寫完。但問題在于4GB的數(shù)據(jù)在512MB內(nèi)存的機器上根本放不下。那如果退一步用外部排序呢外部排序的思路是把大文件切分成多個可以載入內(nèi)存的小塊分別排序后寫入磁盤再通過多路歸并的方式得到全局有序的結(jié)果。這個方案從理論上講是可行的時間復(fù)雜度大約是O(n log n)但它有一個致命的問題——太慢了。以10億條數(shù)據(jù)為例即使你用看起來很高效的多路歸并磁盤IO的時間也會達到分鐘級別這在筆試場景下是不可接受的。更重要的是排序法做了大量“無用功”。我們需要的只是前1000個最大值而排序會把剩下的9億9千多萬個元素的順序也全部排好。這就好比你要在一個萬人體育館里找出最高的10個人理論上只需要把每個人量一下身高、打個標記而不需要讓全體觀眾按身高排成一條長隊。所以排序這個方案雖然正確但絕非最優(yōu)。2.2 局部淘汰法樸素但清晰如果面試官讓你在“排序法”和“更優(yōu)解法”之間做一個過渡你最容易想到的思路就是局部淘汰法。具體做法是先讀入前1000個數(shù)放到一個數(shù)組里然后遍歷剩下的所有數(shù)。每遍歷一個數(shù)就和當前數(shù)組里的最小值比較如果它比最小值大就替換掉最小值然后重新找出數(shù)組里的最小值。這個方案的優(yōu)點是空間占用只有1000個整數(shù)也就是4KB完全無視內(nèi)存限制。但它的缺點是時間復(fù)雜度偏高每處理一個新數(shù)都要在長度為1000的數(shù)組里線性掃描一遍找最小值整體復(fù)雜度是O(n×k)其中n是10億k是1000。你可以算一下10億乘以1000等于1萬億次比較這個時間足以讓程序跑到天荒地老。局部淘汰法給我們的啟發(fā)是它證明了用一個“固定大小的候選集合”來解決問題是可行的。接下來的問題就是如何高效地維護這個候選集合里的最小值這就自然而然引出了堆這個數(shù)據(jù)結(jié)構(gòu)。2.3 最小堆解法面試的“標準答案”最小堆解法是這道題最經(jīng)典、也最被面試官認可的答案。思路很簡單維護一個容量為1000的最小堆也就是根節(jié)點永遠是最小元素的完全二叉樹。遍歷10億個數(shù)的時候?qū)γ總€數(shù)執(zhí)行“如果它比堆頂元素大就替換堆頂并調(diào)整堆”的操作。這樣做的效果是遍歷結(jié)束后留在堆里的1000個元素就是整個數(shù)據(jù)集中最大的1000個。因為堆頂是這個集合里的最小值任何比它更大的數(shù)都已經(jīng)把它擠出去了。整個過程的建堆和維護復(fù)雜度是O(n log k)這里的k是1000log k大約是10。也就是說10億個數(shù)只需要大概100億次基本操作在C/C優(yōu)化過的代碼里是可以接受的。而且這個方案的空間占用依然只有O(k)也就是幾百KB到幾MB完全無視題目中的內(nèi)存限制。更妙的是這個過程可以流式處理數(shù)據(jù)可以一個一個從磁盤讀進來不需要一次性載入內(nèi)存。我當年在筆試中寫的就是這個方案面試官追問了幾輪之后也認可了這是單機條件下的最優(yōu)解。2.4 分治與哈希分流真正的大數(shù)據(jù)方案如果面試官繼續(xù)加碼說“現(xiàn)在數(shù)據(jù)量是100億分布在一百臺機器上你怎么算”這時候就要用到分治和哈希分流的思想了。最常用的方式是按數(shù)據(jù)的某種哈希規(guī)則把原始數(shù)據(jù)均勻切分到多臺機器上每臺機器在自己的分片數(shù)據(jù)上運行最小堆算法得出該分片的Top 1000。然后再把所有機器的Top 1000匯總到一臺機器上再做一次Top 1000得到全局結(jié)果。這個方案的巧妙之處在于它利用了哈希的均勻性把一個大問題拆解成多個互不相交的小問題。每個小問題都可以用前面提到的單機解法解決最后合并的結(jié)果也是精確的。需要注意的是哈希函數(shù)的選擇非常關(guān)鍵如果分布不均勻某臺機器可能分到很多數(shù)據(jù)另一臺卻很閑最后總耗時取決于最慢的那臺機器。分治和哈希分流的思想本質(zhì)上和MapReduce是一致的。所以如果你能在面試中主動提到“這個方案可以很自然地擴展到MapReduce框架”會給面試官留下不錯的好印象——說明你不是只會刷題而是真正理解大數(shù)據(jù)處理的基本范式。3. 最小堆解法詳解與代碼實現(xiàn)3.1 為什么最小堆而不是最大堆這是我在面試實習生時最喜歡追問的一個問題。很多同學能說出“用堆維護Top 1000”但當我問“為什么是堆頂為最小值的最小堆而不是堆頂為最大值的最大堆”時就答不上來了。原因其實很直接對于一個容量為k的堆堆頂就是當前這k個數(shù)的最小值。如果我們構(gòu)建的是最大堆堆頂是最大值那新來的數(shù)無論多大只要不是比最大值大就無法通過堆頂比較決定它是否進入候選集合。這樣一來新數(shù)必須和堆里的k個數(shù)逐一比較堆的效率就體現(xiàn)不出來了。從另一個角度理解最小堆像一個“淘汰機制”它總是把候選集合里最弱的一個暴露在根部任何一個新來的強者都可以直接擠掉它然后再通過調(diào)整恢復(fù)堆結(jié)構(gòu)。這種“比堆頂大就替換”的策略保證了每次比較都只需要O(log k)的時間就能完成堆調(diào)整。而最大堆則像一個“守門員”它把最強的一個放在門口新來的挑戰(zhàn)者反而要經(jīng)過仔細檢驗才能擠進隊伍。3.2 手寫最小堆的完整實現(xiàn)下面這個例子是當年我在筆試中寫的C版本。為了便于閱讀我稍微做了些注釋說明。核心邏輯分為兩部分建堆遍歷和堆調(diào)整。其中堆調(diào)整采用的是“下沉”方式從根節(jié)點開始與左右子節(jié)點中較小者交換直到滿足最小堆性質(zhì)。#include iostream #include fstream #include vector #include queue using namespace std; // 手寫最小堆的調(diào)整過程root是當前需要下沉的節(jié)點下標 void siftDown(vectorlong long heap, int root, int len) { int child root * 2 1; while (child len) { // 在左右孩子中選出較小值對應(yīng)的下標 if (child 1 len heap[child 1] heap[child]) { child 1; } // 如果當前節(jié)點已經(jīng)比孩子小說明堆結(jié)構(gòu)合理 if (heap[root] heap[child]) { break; } swap(heap[root], heap[child]); root child; child root * 2 1; } } int main() { const int K 1000; vectorlong long heap; heap.reserve(K); // 用模擬數(shù)據(jù)代替真實文件方便演示 // 實際場景中可以從文件流式讀取10億個整數(shù) for (long long i 0; i 10000; i) { long long val (i * 131 7) % 1000000; // 模擬一個隨機數(shù) if (heap.size() K) { // 堆未滿直接插入并向上調(diào)整 heap.push_back(val); push_heap(heap.begin(), heap.end(), greaterlong long()); } else { // 堆已滿如果當前值比堆頂大就替換堆頂并下沉 if (val heap[0]) { heap[0] val; siftDown(heap, 0, K); } } } // 輸出結(jié)果因為是最小堆需要把所有元素彈出才是降序 sort(heap.begin(), heap.end(), greaterlong long()); for (int num : heap) { cout num ; } cout endl; return 0; }這里有一個容易被忽略的細節(jié)C標準庫中的push_heap默認構(gòu)建的是最大堆如果你要構(gòu)建最小堆需要傳入greaterlong long()。但make_heap或者priority_queue的默認行為也是最大堆。為了避免混淆我在代碼里選擇了自己實現(xiàn)siftDown函數(shù)這樣面試官看到的是我對堆原理的完整理解而不是對STL的簡單調(diào)用。如果你對STL比較熟悉用priority_queuelong long, vectorlong long, greaterlong long會更簡潔。但筆試時最好還是手寫一遍原因有兩個第一手寫堆能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)功底第二有些公司的在線編譯器可能對STL的支持有差異手寫代碼的移植性更好。3.3 復(fù)雜度分析與數(shù)據(jù)量估算現(xiàn)在來算一筆賬。假設(shè)整數(shù)是32位也就是4字節(jié)。如果文件里存了10億個數(shù)那么文件大小大約是4GB。我們的最小堆只需要維護1000個元素每個元素占4字節(jié)如果用long long就是8字節(jié)加上堆結(jié)構(gòu)調(diào)整的臨時空間總內(nèi)存占用也就幾十KB到幾MB級別跟512MB的限制比起來可以忽略不計。時間方面堆頂替換和下沉操作的時間復(fù)雜度是O(log k)這里的k1000log2(1000)約等于10。最壞情況下10億個數(shù)里每一個都比堆頂大每一輪都需要做10次左右的比較和交換總操作數(shù)大約在100億級別。你可能覺得100億聽起來很多但實際上CPU每秒可以執(zhí)行幾十億次簡單操作加上C編譯器的優(yōu)化單機跑完這個流程也就是幾十秒到一兩分鐘的事。如果你使用priority_queue它的底層實現(xiàn)也是堆復(fù)雜度完全一致。但有一點要注意priority_queue的push和pop是分開的如果你要替換堆頂需要先pop再push這會產(chǎn)生不必要的堆調(diào)整。相比之下直接改寫根節(jié)點再下沉效率會更高。這類微小的優(yōu)化在筆試中未必能拉開差距但在工程的高性能場景下是實打?qū)嵉摹?. 從附加題到真實業(yè)務(wù)Top K的工程化落地4.1 搜索引擎里的Top K你可能會覺得這種題目是不是只存在于筆試中真到了公司里根本用不上恰恰相反Top K問題在搜索引擎里幾乎是“家常便飯”。比如用戶在搜索框中輸入“北京美食”后搜索引擎需要從海量的網(wǎng)頁索引中快速找出與這個查詢相關(guān)性最高的前10個網(wǎng)頁。這個過程的本質(zhì)就是Top K只不過分數(shù)不是整數(shù)而是相關(guān)性評分。在實際系統(tǒng)中相關(guān)性評分往往由多個因素加權(quán)計算包括詞頻、網(wǎng)頁權(quán)重、用戶地理位置、點擊歷史等。這些分數(shù)的計算可以在倒排索引遍歷階段完成然后把計算好的分數(shù)送入一個容量為10的堆結(jié)構(gòu)中始終保持堆里是當前最優(yōu)的10個結(jié)果。這樣做的目的和筆試是一樣的避免對所有候選結(jié)果做全量排序因為一次搜索可能召回幾十萬甚至上百萬個候選結(jié)果全量排序的延遲完全不可接受。我之前在一家搜索相關(guān)的公司實習時有一次需要優(yōu)化搜索接口的耗時。排查發(fā)現(xiàn)排名模塊為了簡便直接調(diào)用了std::sort對召回結(jié)果排序而召回量經(jīng)常達到幾十萬量級。后來我把它改成了優(yōu)先隊列維護Top 50耗時直接降了一個數(shù)量級。這件小事讓我意識到筆試中的那道附加題本質(zhì)上就是在為這類場景做準備。4.2 用戶行為日志中的高頻詞統(tǒng)計另一個典型的業(yè)務(wù)場景是統(tǒng)計用戶行為日志里的高頻詞。比如產(chǎn)品經(jīng)理想知道最近一天用戶搜索的關(guān)鍵詞Top 100用來做運營活動。這時候數(shù)據(jù)來源是海量日志可能一天的日志就有幾百GB。由于單個關(guān)鍵詞出現(xiàn)的次數(shù)是有限的可以先用哈希表做詞頻統(tǒng)計然后對詞頻執(zhí)行Top K操作。在某些分布式中臺框架比如MapReduce里思路會變成Map階段讀取日志輸出關(guān)鍵詞和計數(shù)1Reduce階段對同一個關(guān)鍵詞的計數(shù)相加得到總詞頻最后再用一個單獨的作業(yè)做Top K。這個流程的邏輯框架和我在第2.4節(jié)里講的分治與哈希分流方案如出一轍。所以你可以把這道附加題理解為一個大數(shù)據(jù)的微縮模型核心思路不變只是數(shù)據(jù)規(guī)模從“單機10億個整數(shù)”放大到了“集群上的幾百GB日志”。4.3 分布式場景下的兩層Top K如果數(shù)據(jù)量大到單機無法處理就需要引入分布式架構(gòu)。常見的做法是兩層Top K第一層每臺機器讀取一部分數(shù)據(jù)用最小堆求出本機的Top K第二層把每臺機器的Top K結(jié)果匯總到一臺合并機上再次用最小堆求出全局Top K。這樣做的數(shù)學依據(jù)是全局最大值一定會在某個分片的Top K里所以收集所有分片的Top K結(jié)果不會丟失全局最優(yōu)解。這里有一個容易踩的坑如果你的目標是Top 1000但每臺機器只返回Top 1000在極端情況下兩臺機器可能把某個并不屬于全局Top 1000的元素都返回了。這是允許的因為合并階段會再做一次完整的排序或堆選擇最終只保留前1000個。但如果每臺機器返回的數(shù)量小于目標值比如只返回Top 100那在分片不均勻的情況下就可能漏掉真正的全局Top 1000。所以“每臺機器返回Top KK等于或大于目標值”是一個安全法則。在真實業(yè)界常提到的“兩層 Top K”思想和 MapReduce 的作業(yè)流程很像你可以把它說成一個簡化版的歸并思路。如果面試官繼續(xù)追問數(shù)據(jù)傾斜怎么辦你可以回答增加一個哈希預(yù)分區(qū)步驟讓相同的關(guān)鍵字盡量落在同一臺機器上避免某個關(guān)鍵詞在每臺機器都出現(xiàn)導致的過度計數(shù)。這些細節(jié)在面試中會是非常加分的表現(xiàn)。5. 常見問題與解題誤區(qū)5.1 內(nèi)存估算容易踩的坑很多人在計算內(nèi)存時只考慮了存儲數(shù)據(jù)本身的空間。但如果你用vectorlong long存10億個數(shù)每個long long在64位系統(tǒng)上占8字節(jié)總空間就變成了80GB比4GB還要大得多。所以在真實的筆試環(huán)境里如果要處理10億個數(shù)應(yīng)該用int或int32_t除非數(shù)值范圍確實超過32位。堆結(jié)構(gòu)本身的內(nèi)存也不能忽略。雖然理論上只需要1000個元素但STL的vector擴容會預(yù)留capacity這個容量一般比size稍大。幸運的是堆的大小只有1000即使capacity翻倍到2000也才8KB不會對整體內(nèi)存有任何壓力。真正需要謹慎的是讀取文件時的緩沖區(qū)有些人喜歡一次性讀入一大塊數(shù)據(jù)到內(nèi)存里這在數(shù)據(jù)量大的時候可能會讓內(nèi)存瞬間飆升。流式讀取每次只處理一小塊才是最安全的。如果你在寫代碼的時候使用了遞歸算法來解決某個子問題比如某些分治方案還需要留意遞歸棧的深度。10億級別的數(shù)據(jù)如果處理不當遞歸層數(shù)可能非常深導致棧溢出。雖然最小堆方案本身沒有遞歸但一旦你擴展思路到分治就一定要把棧深度考慮進去。5.2 時間復(fù)雜度分析容易錯的點對于最小堆方案很多人會簡單地說“復(fù)雜度是O(n log k)”然后就不再繼續(xù)了。但如果面試官追問“為什么不是O(n log n)”你至少要能答出因為k遠小于nlog k是一個常數(shù)級別的因子。具體來說n10億k1000log k≈10所以整體復(fù)雜度相當于O(10n)接近線性。如果寫成O(n log n)在實際運行中會慢幾百倍。另一個容易出錯的點是忘記考慮建堆的復(fù)雜度。前1000個元素插入堆時如果每個元素都調(diào)用一次push_heap單次復(fù)雜度是O(log p)其中p是當前堆的大小累計復(fù)雜度是O(k log k)。幸好k很小這個開銷可以忽略不計。如果你一次性對1000個元素調(diào)用make_heap整體復(fù)雜度是O(k)也就是線性建堆。兩種方式都可行但如果你想展示更扎實的功底可以說出“線性建堆”這個知識點。時間估算的時候也不要只算CPU的時間。真實場景里最大的瓶頸其實是磁盤IO。從4GB的文件里讀取10億個數(shù)即使以每秒1GB的讀取速度也要4秒鐘。如果這臺機器磁盤性能一般讀取耗時會遠高于計算耗時。所以在方案設(shè)計中減少磁盤隨機讀寫、盡量順序讀往往比優(yōu)化堆調(diào)整更重要。5.3 邊界條件與異常處理我在面試別人的時候發(fā)現(xiàn)不少同學代碼寫得很流暢但一問邊界條件就啞了。比如如果文件里的整數(shù)數(shù)量本身就不到1000個呢這時候堆永遠填不滿最后輸出的就是全部數(shù)據(jù)。代碼中需要判斷堆是否已滿避免在堆未滿時執(zhí)行“替換堆頂”的邏輯。再比如如果數(shù)據(jù)里面有重復(fù)值怎么辦最小堆的處理方式對重復(fù)值是天然正確的。假設(shè)所有值都是同一個數(shù)那么堆里的元素都相等堆頂替換條件“val heap[0]”永遠不會為真最后輸出的堆里裝的就是這個數(shù)本身。這個輸出在數(shù)學上是正確的但如果你希望輸出“不同的Top K”那就需要額外引入去重邏輯比如用哈希集合或者先對所有值做一次哈希去重。這個問題在面試現(xiàn)場很容易被問到提前想好回答思路會讓你顯得更有經(jīng)驗。還有文件讀取異常的問題。如果文件指針走到了末尾或者文件損壞導致數(shù)據(jù)不完整代碼要能優(yōu)雅退出而不是直接崩潰。在實際生產(chǎn)代碼里這類異常處理往往占了很大篇幅但在筆試中你只需要在關(guān)鍵位置加上判斷即可。過度沉迷于異常處理反而會讓代碼變得冗長在有限時間內(nèi)得不償失。6. 這道題背后百度在選什么樣的人6.1 從題目風格看公司技術(shù)文化百度作為國內(nèi)搜索引擎的代表公司日常業(yè)務(wù)處理的數(shù)據(jù)量非常龐大。這道附加題的設(shè)計其實反映了百度對工程師的核心要求之一在海量數(shù)據(jù)面前不能慌不能蠻干而是要把問題進行合理的抽象和簡化。你可以不會背紅黑樹的實現(xiàn)細節(jié)但你必須對數(shù)據(jù)規(guī)模有敏銳的直覺知道什么時候該用堆什么時候該用哈希。從另一個角度講這題也透露出百度希望實習生具備“工程落地”意識。你不僅僅要給出理論上的最優(yōu)算法還要考慮磁盤IO、內(nèi)存限制、代碼穩(wěn)定性這些真實因素。這和學校里的算法課很不一樣算法課上的輸入規(guī)模通常是幾千到幾萬而真實業(yè)務(wù)里動輒百萬、千萬甚至上億。如果你能從筆試階段就開始建立這種規(guī)模意識對以后的工作會有很大幫助。6.2 判斷候選人潛力的核心標準我看到過很多候選人在講這道題的時候會提到“我用過Hadoop”“我做過大數(shù)據(jù)項目”。但真正的加分項不在于你用過什么框架而在于你能不能清楚地說出背后的原理。比如為什么MapReduce適合處理這類問題因為Map階段天然做了分片和并行Reduce階段做了合并這正好對應(yīng)了分治和Top K合并的流程。如果你能說清楚這一層說明你不是只會調(diào)用API而是理解了分布式計算的本質(zhì)。另外一個容易被忽略的點是態(tài)度。附加題之所以叫附加題通常意味著有一定難度面試官不期待你百分之百答對。你愿意主動思考、大膽給出方案并在追問中不斷修正自己這種積極解決問題的狀態(tài)往往比正確答案更打動面試官。我在面試中更喜歡看到候選人犯一個錯誤后能快速反應(yīng)、自我修正的過程這比全程順利更真實。6.3 對你備戰(zhàn)校招的幾點建議如果你現(xiàn)在正在準備實習招聘我建議你除了刷題也多花點時間做“數(shù)據(jù)規(guī)模估算”的訓練。比如看到任何一個系統(tǒng)試著估算一下它的日活和每天產(chǎn)生的數(shù)據(jù)量然后想一想如果讓你處理這些數(shù)據(jù)內(nèi)存夠不夠要不要分片用什么樣的數(shù)據(jù)結(jié)構(gòu)最合適這種習慣會慢慢培養(yǎng)起你“下意識考慮擴展性”的思維方式。最后我個人踩過幾次坑之后最深的體會是筆試中最重要的不是寫得多花哨而是“穩(wěn)”。把最小堆方案寫得清晰、完整把復(fù)雜度算明白對邊界條件有清晰的交代就已經(jīng)能超過絕大多數(shù)候選人了。在那個基礎(chǔ)上如果能主動討論分治擴展和分布式場景那就是可以給面試官留下“這人有潛力”印象的加分項。這道附加題雖然簡單樸素但它的價值絕不止于一場筆試。 海量數(shù)據(jù)Top K問題解析：內(nèi)存受限下的最小堆解法
去年春招的時候很多師弟師妹跑來問我百度實習生的筆試該怎么準備。我翻出當年自己做過的題單發(fā)現(xiàn)那道附加題放在今天看依然是很有代表性的海量數(shù)據(jù)考題給你一個包含大量整數(shù)的數(shù)據(jù)文件假設(shè)有10億個整數(shù)內(nèi)存只有幾百MB要求找出其中最大的1000個數(shù)。題目看似簡單卻能在“內(nèi)存受限”這個條件下刷掉一大半人。這篇文章就把這道題從頭到尾拆透包括我自己的解題過程和踩過的坑希望能幫到正在準備大廠實習面試的朋友。1. 題目還原與考點拆解1.1 題目原貌百度2015春季實習生招聘的這道附加題核心描述大致是這樣的有一個二進制文件里面按順序存儲了10億個32位整數(shù)也就是大概4GB的數(shù)據(jù)量。現(xiàn)在給你一臺內(nèi)存只有512MB的機器要求用盡可能快的方式輸出其中最大的1000個數(shù)。需要注意的是這道題在當時并不是獨立出現(xiàn)的而是作為整套筆試題的附加部分。和前面的基礎(chǔ)算法題不同附加題往往沒有標準答案面試官更看重你的思考過程。也正因為如此它其實是一個非常好的“壓力測試”題目你只有在有限的內(nèi)存條件和時間限制下拿出一個可行且高效的方案才能讓面試官眼前一亮。為什么我說這道題有代表性因為它同時考察了三個層面的能力第一對基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的掌握比如堆、分治這些概念第二對真實硬件環(huán)境的理解也就是內(nèi)存、磁盤IO的取舍第三對工程化方案的敏感度能不能從“做題家”思維切換到“解決實際問題”的思維。這三個層面恰恰是大廠招聘實習生時最看重的素質(zhì)。1.2 面試官真正想考察的點很多第一次看到這道題的同學第一反應(yīng)是“直接排序不就行了”。在內(nèi)存充足的前提下對10億個數(shù)排序然后取前1000個當然是可以的。但問題就在這里題目明確限制了內(nèi)存只有512MB而10億個整數(shù)占4GB根本不可能一次性載入內(nèi)存。就算你強行用虛擬內(nèi)存頻繁的缺頁中斷也會讓程序慢到無法接受。所以這道題的第一個隱含考點就是你能不能意識到“單機全量排序不可行”。意識到這個之后你需要繼續(xù)拆解問題并不需要全局有序只需要前1000個最大數(shù)。這個“只需要”三個字就是你優(yōu)化空間的突破口。此外這道題還考察了溝通能力。面試官在聽你講方案的時候會故意設(shè)置一些模糊地帶比如“如果數(shù)據(jù)量再翻10倍怎么辦”“如果前1000個里面允許誤差呢”。這些問題沒有標準答案但你的應(yīng)對方式會直接反映你對問題本質(zhì)的理解深度。我在面試別人的時候最怕聽到的就是應(yīng)聘者背答案一旦追問幾句就開始支支吾吾。真正的理解應(yīng)該是面對追問時能夠不斷迭代自己的方案。2. 海量數(shù)據(jù)Top K的4種解法對比2.1 排序法最直觀也最容易掛先說說最直覺的解法也就是全量排序。把4GB數(shù)據(jù)全部讀入內(nèi)存用快速排序或者歸并排序整體排序然后取前1000個。這個方案的代碼量確實很小大概十幾行就能寫完。但問題在于4GB的數(shù)據(jù)在512MB內(nèi)存的機器上根本放不下。那如果退一步用外部排序呢外部排序的思路是把大文件切分成多個可以載入內(nèi)存的小塊分別排序后寫入磁盤再通過多路歸并的方式得到全局有序的結(jié)果。這個方案從理論上講是可行的時間復(fù)雜度大約是O(n log n)但它有一個致命的問題——太慢了。以10億條數(shù)據(jù)為例即使你用看起來很高效的多路歸并磁盤IO的時間也會達到分鐘級別這在筆試場景下是不可接受的。更重要的是排序法做了大量“無用功”。我們需要的只是前1000個最大值而排序會把剩下的9億9千多萬個元素的順序也全部排好。這就好比你要在一個萬人體育館里找出最高的10個人理論上只需要把每個人量一下身高、打個標記而不需要讓全體觀眾按身高排成一條長隊。所以排序這個方案雖然正確但絕非最優(yōu)。2.2 局部淘汰法樸素但清晰如果面試官讓你在“排序法”和“更優(yōu)解法”之間做一個過渡你最容易想到的思路就是局部淘汰法。具體做法是先讀入前1000個數(shù)放到一個數(shù)組里然后遍歷剩下的所有數(shù)。每遍歷一個數(shù)就和當前數(shù)組里的最小值比較如果它比最小值大就替換掉最小值然后重新找出數(shù)組里的最小值。這個方案的優(yōu)點是空間占用只有1000個整數(shù)也就是4KB完全無視內(nèi)存限制。但它的缺點是時間復(fù)雜度偏高每處理一個新數(shù)都要在長度為1000的數(shù)組里線性掃描一遍找最小值整體復(fù)雜度是O(n×k)其中n是10億k是1000。你可以算一下10億乘以1000等于1萬億次比較這個時間足以讓程序跑到天荒地老。局部淘汰法給我們的啟發(fā)是它證明了用一個“固定大小的候選集合”來解決問題是可行的。接下來的問題就是如何高效地維護這個候選集合里的最小值這就自然而然引出了堆這個數(shù)據(jù)結(jié)構(gòu)。2.3 最小堆解法面試的“標準答案”最小堆解法是這道題最經(jīng)典、也最被面試官認可的答案。思路很簡單維護一個容量為1000的最小堆也就是根節(jié)點永遠是最小元素的完全二叉樹。遍歷10億個數(shù)的時候?qū)γ總€數(shù)執(zhí)行“如果它比堆頂元素大就替換堆頂并調(diào)整堆”的操作。這樣做的效果是遍歷結(jié)束后留在堆里的1000個元素就是整個數(shù)據(jù)集中最大的1000個。因為堆頂是這個集合里的最小值任何比它更大的數(shù)都已經(jīng)把它擠出去了。整個過程的建堆和維護復(fù)雜度是O(n log k)這里的k是1000log k大約是10。也就是說10億個數(shù)只需要大概100億次基本操作在C/C優(yōu)化過的代碼里是可以接受的。而且這個方案的空間占用依然只有O(k)也就是幾百KB到幾MB完全無視題目中的內(nèi)存限制。更妙的是這個過程可以流式處理數(shù)據(jù)可以一個一個從磁盤讀進來不需要一次性載入內(nèi)存。我當年在筆試中寫的就是這個方案面試官追問了幾輪之后也認可了這是單機條件下的最優(yōu)解。2.4 分治與哈希分流真正的大數(shù)據(jù)方案如果面試官繼續(xù)加碼說“現(xiàn)在數(shù)據(jù)量是100億分布在一百臺機器上你怎么算”這時候就要用到分治和哈希分流的思想了。最常用的方式是按數(shù)據(jù)的某種哈希規(guī)則把原始數(shù)據(jù)均勻切分到多臺機器上每臺機器在自己的分片數(shù)據(jù)上運行最小堆算法得出該分片的Top 1000。然后再把所有機器的Top 1000匯總到一臺機器上再做一次Top 1000得到全局結(jié)果。這個方案的巧妙之處在于它利用了哈希的均勻性把一個大問題拆解成多個互不相交的小問題。每個小問題都可以用前面提到的單機解法解決最后合并的結(jié)果也是精確的。需要注意的是哈希函數(shù)的選擇非常關(guān)鍵如果分布不均勻某臺機器可能分到很多數(shù)據(jù)另一臺卻很閑最后總耗時取決于最慢的那臺機器。分治和哈希分流的思想本質(zhì)上和MapReduce是一致的。所以如果你能在面試中主動提到“這個方案可以很自然地擴展到MapReduce框架”會給面試官留下不錯的好印象——說明你不是只會刷題而是真正理解大數(shù)據(jù)處理的基本范式。3. 最小堆解法詳解與代碼實現(xiàn)3.1 為什么最小堆而不是最大堆這是我在面試實習生時最喜歡追問的一個問題。很多同學能說出“用堆維護Top 1000”但當我問“為什么是堆頂為最小值的最小堆而不是堆頂為最大值的最大堆”時就答不上來了。原因其實很直接對于一個容量為k的堆堆頂就是當前這k個數(shù)的最小值。如果我們構(gòu)建的是最大堆堆頂是最大值那新來的數(shù)無論多大只要不是比最大值大就無法通過堆頂比較決定它是否進入候選集合。這樣一來新數(shù)必須和堆里的k個數(shù)逐一比較堆的效率就體現(xiàn)不出來了。從另一個角度理解最小堆像一個“淘汰機制”它總是把候選集合里最弱的一個暴露在根部任何一個新來的強者都可以直接擠掉它然后再通過調(diào)整恢復(fù)堆結(jié)構(gòu)。這種“比堆頂大就替換”的策略保證了每次比較都只需要O(log k)的時間就能完成堆調(diào)整。而最大堆則像一個“守門員”它把最強的一個放在門口新來的挑戰(zhàn)者反而要經(jīng)過仔細檢驗才能擠進隊伍。3.2 手寫最小堆的完整實現(xiàn)下面這個例子是當年我在筆試中寫的C版本。為了便于閱讀我稍微做了些注釋說明。核心邏輯分為兩部分建堆遍歷和堆調(diào)整。其中堆調(diào)整采用的是“下沉”方式從根節(jié)點開始與左右子節(jié)點中較小者交換直到滿足最小堆性質(zhì)。#include iostream #include fstream #include vector #include queue using namespace std; // 手寫最小堆的調(diào)整過程root是當前需要下沉的節(jié)點下標 void siftDown(vectorlong long heap, int root, int len) { int child root * 2 1; while (child len) { // 在左右孩子中選出較小值對應(yīng)的下標 if (child 1 len heap[child 1] heap[child]) { child 1; } // 如果當前節(jié)點已經(jīng)比孩子小說明堆結(jié)構(gòu)合理 if (heap[root] heap[child]) { break; } swap(heap[root], heap[child]); root child; child root * 2 1; } } int main() { const int K 1000; vectorlong long heap; heap.reserve(K); // 用模擬數(shù)據(jù)代替真實文件方便演示 // 實際場景中可以從文件流式讀取10億個整數(shù) for (long long i 0; i 10000; i) { long long val (i * 131 7) % 1000000; // 模擬一個隨機數(shù) if (heap.size() K) { // 堆未滿直接插入并向上調(diào)整 heap.push_back(val); push_heap(heap.begin(), heap.end(), greaterlong long()); } else { // 堆已滿如果當前值比堆頂大就替換堆頂并下沉 if (val heap[0]) { heap[0] val; siftDown(heap, 0, K); } } } // 輸出結(jié)果因為是最小堆需要把所有元素彈出才是降序 sort(heap.begin(), heap.end(), greaterlong long()); for (int num : heap) { cout num ; } cout endl; return 0; }這里有一個容易被忽略的細節(jié)C標準庫中的push_heap默認構(gòu)建的是最大堆如果你要構(gòu)建最小堆需要傳入greaterlong long()。但make_heap或者priority_queue的默認行為也是最大堆。為了避免混淆我在代碼里選擇了自己實現(xiàn)siftDown函數(shù)這樣面試官看到的是我對堆原理的完整理解而不是對STL的簡單調(diào)用。如果你對STL比較熟悉用priority_queuelong long, vectorlong long, greaterlong long會更簡潔。但筆試時最好還是手寫一遍原因有兩個第一手寫堆能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)功底第二有些公司的在線編譯器可能對STL的支持有差異手寫代碼的移植性更好。3.3 復(fù)雜度分析與數(shù)據(jù)量估算現(xiàn)在來算一筆賬。假設(shè)整數(shù)是32位也就是4字節(jié)。如果文件里存了10億個數(shù)那么文件大小大約是4GB。我們的最小堆只需要維護1000個元素每個元素占4字節(jié)如果用long long就是8字節(jié)加上堆結(jié)構(gòu)調(diào)整的臨時空間總內(nèi)存占用也就幾十KB到幾MB級別跟512MB的限制比起來可以忽略不計。時間方面堆頂替換和下沉操作的時間復(fù)雜度是O(log k)這里的k1000log2(1000)約等于10。最壞情況下10億個數(shù)里每一個都比堆頂大每一輪都需要做10次左右的比較和交換總操作數(shù)大約在100億級別。你可能覺得100億聽起來很多但實際上CPU每秒可以執(zhí)行幾十億次簡單操作加上C編譯器的優(yōu)化單機跑完這個流程也就是幾十秒到一兩分鐘的事。如果你使用priority_queue它的底層實現(xiàn)也是堆復(fù)雜度完全一致。但有一點要注意priority_queue的push和pop是分開的如果你要替換堆頂需要先pop再push這會產(chǎn)生不必要的堆調(diào)整。相比之下直接改寫根節(jié)點再下沉效率會更高。這類微小的優(yōu)化在筆試中未必能拉開差距但在工程的高性能場景下是實打?qū)嵉摹?. 從附加題到真實業(yè)務(wù)Top K的工程化落地4.1 搜索引擎里的Top K你可能會覺得這種題目是不是只存在于筆試中真到了公司里根本用不上恰恰相反Top K問題在搜索引擎里幾乎是“家常便飯”。比如用戶在搜索框中輸入“北京美食”后搜索引擎需要從海量的網(wǎng)頁索引中快速找出與這個查詢相關(guān)性最高的前10個網(wǎng)頁。這個過程的本質(zhì)就是Top K只不過分數(shù)不是整數(shù)而是相關(guān)性評分。在實際系統(tǒng)中相關(guān)性評分往往由多個因素加權(quán)計算包括詞頻、網(wǎng)頁權(quán)重、用戶地理位置、點擊歷史等。這些分數(shù)的計算可以在倒排索引遍歷階段完成然后把計算好的分數(shù)送入一個容量為10的堆結(jié)構(gòu)中始終保持堆里是當前最優(yōu)的10個結(jié)果。這樣做的目的和筆試是一樣的避免對所有候選結(jié)果做全量排序因為一次搜索可能召回幾十萬甚至上百萬個候選結(jié)果全量排序的延遲完全不可接受。我之前在一家搜索相關(guān)的公司實習時有一次需要優(yōu)化搜索接口的耗時。排查發(fā)現(xiàn)排名模塊為了簡便直接調(diào)用了std::sort對召回結(jié)果排序而召回量經(jīng)常達到幾十萬量級。后來我把它改成了優(yōu)先隊列維護Top 50耗時直接降了一個數(shù)量級。這件小事讓我意識到筆試中的那道附加題本質(zhì)上就是在為這類場景做準備。4.2 用戶行為日志中的高頻詞統(tǒng)計另一個典型的業(yè)務(wù)場景是統(tǒng)計用戶行為日志里的高頻詞。比如產(chǎn)品經(jīng)理想知道最近一天用戶搜索的關(guān)鍵詞Top 100用來做運營活動。這時候數(shù)據(jù)來源是海量日志可能一天的日志就有幾百GB。由于單個關(guān)鍵詞出現(xiàn)的次數(shù)是有限的可以先用哈希表做詞頻統(tǒng)計然后對詞頻執(zhí)行Top K操作。在某些分布式中臺框架比如MapReduce里思路會變成Map階段讀取日志輸出關(guān)鍵詞和計數(shù)1Reduce階段對同一個關(guān)鍵詞的計數(shù)相加得到總詞頻最后再用一個單獨的作業(yè)做Top K。這個流程的邏輯框架和我在第2.4節(jié)里講的分治與哈希分流方案如出一轍。所以你可以把這道附加題理解為一個大數(shù)據(jù)的微縮模型核心思路不變只是數(shù)據(jù)規(guī)模從“單機10億個整數(shù)”放大到了“集群上的幾百GB日志”。4.3 分布式場景下的兩層Top K如果數(shù)據(jù)量大到單機無法處理就需要引入分布式架構(gòu)。常見的做法是兩層Top K第一層每臺機器讀取一部分數(shù)據(jù)用最小堆求出本機的Top K第二層把每臺機器的Top K結(jié)果匯總到一臺合并機上再次用最小堆求出全局Top K。這樣做的數(shù)學依據(jù)是全局最大值一定會在某個分片的Top K里所以收集所有分片的Top K結(jié)果不會丟失全局最優(yōu)解。這里有一個容易踩的坑如果你的目標是Top 1000但每臺機器只返回Top 1000在極端情況下兩臺機器可能把某個并不屬于全局Top 1000的元素都返回了。這是允許的因為合并階段會再做一次完整的排序或堆選擇最終只保留前1000個。但如果每臺機器返回的數(shù)量小于目標值比如只返回Top 100那在分片不均勻的情況下就可能漏掉真正的全局Top 1000。所以“每臺機器返回Top KK等于或大于目標值”是一個安全法則。在真實業(yè)界常提到的“兩層 Top K”思想和 MapReduce 的作業(yè)流程很像你可以把它說成一個簡化版的歸并思路。如果面試官繼續(xù)追問數(shù)據(jù)傾斜怎么辦你可以回答增加一個哈希預(yù)分區(qū)步驟讓相同的關(guān)鍵字盡量落在同一臺機器上避免某個關(guān)鍵詞在每臺機器都出現(xiàn)導致的過度計數(shù)。這些細節(jié)在面試中會是非常加分的表現(xiàn)。5. 常見問題與解題誤區(qū)5.1 內(nèi)存估算容易踩的坑很多人在計算內(nèi)存時只考慮了存儲數(shù)據(jù)本身的空間。但如果你用vectorlong long存10億個數(shù)每個long long在64位系統(tǒng)上占8字節(jié)總空間就變成了80GB比4GB還要大得多。所以在真實的筆試環(huán)境里如果要處理10億個數(shù)應(yīng)該用int或int32_t除非數(shù)值范圍確實超過32位。堆結(jié)構(gòu)本身的內(nèi)存也不能忽略。雖然理論上只需要1000個元素但STL的vector擴容會預(yù)留capacity這個容量一般比size稍大。幸運的是堆的大小只有1000即使capacity翻倍到2000也才8KB不會對整體內(nèi)存有任何壓力。真正需要謹慎的是讀取文件時的緩沖區(qū)有些人喜歡一次性讀入一大塊數(shù)據(jù)到內(nèi)存里這在數(shù)據(jù)量大的時候可能會讓內(nèi)存瞬間飆升。流式讀取每次只處理一小塊才是最安全的。如果你在寫代碼的時候使用了遞歸算法來解決某個子問題比如某些分治方案還需要留意遞歸棧的深度。10億級別的數(shù)據(jù)如果處理不當遞歸層數(shù)可能非常深導致棧溢出。雖然最小堆方案本身沒有遞歸但一旦你擴展思路到分治就一定要把棧深度考慮進去。5.2 時間復(fù)雜度分析容易錯的點對于最小堆方案很多人會簡單地說“復(fù)雜度是O(n log k)”然后就不再繼續(xù)了。但如果面試官追問“為什么不是O(n log n)”你至少要能答出因為k遠小于nlog k是一個常數(shù)級別的因子。具體來說n10億k1000log k≈10所以整體復(fù)雜度相當于O(10n)接近線性。如果寫成O(n log n)在實際運行中會慢幾百倍。另一個容易出錯的點是忘記考慮建堆的復(fù)雜度。前1000個元素插入堆時如果每個元素都調(diào)用一次push_heap單次復(fù)雜度是O(log p)其中p是當前堆的大小累計復(fù)雜度是O(k log k)。幸好k很小這個開銷可以忽略不計。如果你一次性對1000個元素調(diào)用make_heap整體復(fù)雜度是O(k)也就是線性建堆。兩種方式都可行但如果你想展示更扎實的功底可以說出“線性建堆”這個知識點。時間估算的時候也不要只算CPU的時間。真實場景里最大的瓶頸其實是磁盤IO。從4GB的文件里讀取10億個數(shù)即使以每秒1GB的讀取速度也要4秒鐘。如果這臺機器磁盤性能一般讀取耗時會遠高于計算耗時。所以在方案設(shè)計中減少磁盤隨機讀寫、盡量順序讀往往比優(yōu)化堆調(diào)整更重要。5.3 邊界條件與異常處理我在面試別人的時候發(fā)現(xiàn)不少同學代碼寫得很流暢但一問邊界條件就啞了。比如如果文件里的整數(shù)數(shù)量本身就不到1000個呢這時候堆永遠填不滿最后輸出的就是全部數(shù)據(jù)。代碼中需要判斷堆是否已滿避免在堆未滿時執(zhí)行“替換堆頂”的邏輯。再比如如果數(shù)據(jù)里面有重復(fù)值怎么辦最小堆的處理方式對重復(fù)值是天然正確的。假設(shè)所有值都是同一個數(shù)那么堆里的元素都相等堆頂替換條件“val heap[0]”永遠不會為真最后輸出的堆里裝的就是這個數(shù)本身。這個輸出在數(shù)學上是正確的但如果你希望輸出“不同的Top K”那就需要額外引入去重邏輯比如用哈希集合或者先對所有值做一次哈希去重。這個問題在面試現(xiàn)場很容易被問到提前想好回答思路會讓你顯得更有經(jīng)驗。還有文件讀取異常的問題。如果文件指針走到了末尾或者文件損壞導致數(shù)據(jù)不完整代碼要能優(yōu)雅退出而不是直接崩潰。在實際生產(chǎn)代碼里這類異常處理往往占了很大篇幅但在筆試中你只需要在關(guān)鍵位置加上判斷即可。過度沉迷于異常處理反而會讓代碼變得冗長在有限時間內(nèi)得不償失。6. 這道題背后百度在選什么樣的人6.1 從題目風格看公司技術(shù)文化百度作為國內(nèi)搜索引擎的代表公司日常業(yè)務(wù)處理的數(shù)據(jù)量非常龐大。這道附加題的設(shè)計其實反映了百度對工程師的核心要求之一在海量數(shù)據(jù)面前不能慌不能蠻干而是要把問題進行合理的抽象和簡化。你可以不會背紅黑樹的實現(xiàn)細節(jié)但你必須對數(shù)據(jù)規(guī)模有敏銳的直覺知道什么時候該用堆什么時候該用哈希。從另一個角度講這題也透露出百度希望實習生具備“工程落地”意識。你不僅僅要給出理論上的最優(yōu)算法還要考慮磁盤IO、內(nèi)存限制、代碼穩(wěn)定性這些真實因素。這和學校里的算法課很不一樣算法課上的輸入規(guī)模通常是幾千到幾萬而真實業(yè)務(wù)里動輒百萬、千萬甚至上億。如果你能從筆試階段就開始建立這種規(guī)模意識對以后的工作會有很大幫助。6.2 判斷候選人潛力的核心標準我看到過很多候選人在講這道題的時候會提到“我用過Hadoop”“我做過大數(shù)據(jù)項目”。但真正的加分項不在于你用過什么框架而在于你能不能清楚地說出背后的原理。比如為什么MapReduce適合處理這類問題因為Map階段天然做了分片和并行Reduce階段做了合并這正好對應(yīng)了分治和Top K合并的流程。如果你能說清楚這一層說明你不是只會調(diào)用API而是理解了分布式計算的本質(zhì)。另外一個容易被忽略的點是態(tài)度。附加題之所以叫附加題通常意味著有一定難度面試官不期待你百分之百答對。你愿意主動思考、大膽給出方案并在追問中不斷修正自己這種積極解決問題的狀態(tài)往往比正確答案更打動面試官。我在面試中更喜歡看到候選人犯一個錯誤后能快速反應(yīng)、自我修正的過程這比全程順利更真實。6.3 對你備戰(zhàn)校招的幾點建議如果你現(xiàn)在正在準備實習招聘我建議你除了刷題也多花點時間做“數(shù)據(jù)規(guī)模估算”的訓練。比如看到任何一個系統(tǒng)試著估算一下它的日活和每天產(chǎn)生的數(shù)據(jù)量然后想一想如果讓你處理這些數(shù)據(jù)內(nèi)存夠不夠要不要分片用什么樣的數(shù)據(jù)結(jié)構(gòu)最合適這種習慣會慢慢培養(yǎng)起你“下意識考慮擴展性”的思維方式。最后我個人踩過幾次坑之后最深的體會是筆試中最重要的不是寫得多花哨而是“穩(wěn)”。把最小堆方案寫得清晰、完整把復(fù)雜度算明白對邊界條件有清晰的交代就已經(jīng)能超過絕大多數(shù)候選人了。在那個基礎(chǔ)上如果能主動討論分治擴展和分布式場景那就是可以給面試官留下“這人有潛力”印象的加分項。這道附加題雖然簡單樸素但它的價值絕不止于一場筆試。