面試如泡池,蓄水似人生
起初你滿懷期待跳進大廠池子,以為自己是天選之子,結果發現池子里早擠滿了和你一樣的“錦鯉候選人”。HR
的漁網一撒,撈誰全看概率——這不就是蓄水池算法的精髓嗎?
- 初入池(i≤k):前
k
個幸運兒直接進池,像極了校招提前批的“VIP
通道”。 - 概率博弈(i>k):第
k + 1
個候選人開始,以k / i
的概率被撈,同時池子里隨機一位“前輩”出局。- “面完三面等消息?恭喜,你進入了
k / N
的量子糾纏態。”
- “面完三面等消息?恭喜,你進入了
- 公平玄學:無論你是第
100
還是第1000
號候選人,最終被撈的概率都是k / N
——池子越深,緣分越隨機。
所以,下次面試官問你“如何公平抽獎”,請優雅地回答:
“簡單,像泡池子一樣,先到的不一定穩,后來的未必涼,一切交給蓄水池的數學之美。”
畢竟,泡池子的終極奧義是:
“池中躺平,等一個伯樂;算法加持,信命不認輸。”
機器持續吐出編號遞增的球(1,2,3…),你有一個容量為k的袋子(k=10),怎么保證機器吐出第N個球時,每個球進入袋子的概率都是k/N?
直接上蓄水池采樣規則:
階段 | 處理邏輯 |
---|---|
前k個球 | 直接放入袋子(100%保留) |
第k+1個球起 | 對第i個球: - 以k/i概率決定是否保留 - 若保留,隨機替換袋中一個球 |
每個球進入袋子的概率都是k / N
的證明:
情況1:前k個球(1 ≤ i ≤ k)的保留概率推導
- 初始狀態:前
k
個球直接入袋,保留概率為1
。 - 處理第k+1個球時:
- 第
k+1
個球入袋的概率為k/(k+1)
; - 若入袋,隨機替換袋中某球的概率為
1/k
,即第i
號球被淘汰的概率為(k/(k+1)) × (1/k) = 1/(k+1)
; - 因此,第
i
號球的保留概率為1 - 1/(k+1) = k/(k+1)
。
- 第
- 處理第k+2個球時:
- 第
k+2
個球入袋的概率為k/(k+2)
; - 淘汰第i號球的概率為
(k/(k+2)) × (1/k) = 1/(k+2)
; - 保留概率為
1 - 1/(k+2) = (k+1)/(k+2)
。
- 第
- 遞推至第N個球:
- 每一步的保留概率依次為
k/(k+1)
,(k+1)/(k+2)
, …,(N-1)/N
; - 最終保留概率為各步概率的乘積:
k k + 1 × k + 1 k + 2 × ? × N ? 1 N = k N \frac{k}{k+1} \times \frac{k+1}{k+2} \times \cdots \times \frac{N-1}{N} = \frac{k}{N} k+1k?×k+2k+1?×?×NN?1?=Nk?
- 每一步的保留概率依次為
情況2:后N-k個球(k < i ≤ N)的保留概率推導
- 第i號球入袋時:
- 入袋概率為
k/i
。
- 入袋概率為
- 處理第i+1個球時:
- 第
i+1
個球入袋的概率為k/(i+1)
; - 淘汰第i號球的概率為
(k/(i+1)) × (1/k) = 1/(i+1)
; - 保留概率為
1 - 1/(i+1) = i/(i+1)
。
- 第
- 處理第i+2個球時:
- 保留概率為
(i+1)/(i+2)
。
- 保留概率為
- 遞推至第N個球:
- 每一步的保留概率依次為
i/(i+1)
,(i+1)/(i+2)
, …,(N-1)/N
; - 最終保留概率為各步概率的乘積:
k i × i i + 1 × i + 1 i + 2 × ? × N ? 1 N = k N \frac{k}{i} \times \frac{i}{i+1} \times \frac{i+1}{i+2} \times \cdots \times \frac{N-1}{N} = \frac{k}{N} ik?×i+1i?×i+2i+1?×?×NN?1?=Nk?
- 每一步的保留概率依次為
結論
無論球的編號i
在哪個區間(1 ≤ i ≤ N
),其最終留在蓄水池中的概率均為 k/N
,即實現了等概率采樣。
C++代碼實現(改寫左神Java版本)
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>using namespace std;class Pool {
private:int size;vector<int> bag;public:Pool(int s) : size(s), bag(s) {}// 判斷是否選擇第i號球bool pick(int i) {return rand() % i < size;}// 隨機選擇袋子中的一個位置int where() {return rand() % size;}// 處理新進入的球void enter(int i) {if (i <= size) {bag[i - 1] = i;} else {if (pick(i)) {bag[where()] = i;}}}// 獲取袋子中的球vector<int> getBag() {return bag;}
};int main() {srand(time(NULL)); // 初始化隨機數種子cout << "測試開始" << endl;int n = 41; // 一共吐出多少球int m = 10; // 袋子大小多少int testTimes = 10000; // 進行多少次實驗vector<int> cnt(n + 1, 0);for (int k = 0; k < testTimes; k++) {Pool pool(m);for (int i = 1; i <= n; i++) {pool.enter(i);}vector<int> bag = pool.getBag();for (int num : bag) {cnt[num]++;}}cout << "機器吐出到" << n << "號球, " << "袋子大小為" << m << endl;cout << "每個球被選中的概率應該接近" << (double)m / n << endl;cout << "一共測試" << testTimes << "次" << endl;for (int i = 1; i <= n; i++) {cout << i << "被選中次數 : " << cnt[i] << ", 被選中概率 : " << (double)cnt[i] / testTimes << endl;}cout << "測試結束" << endl;return 0;
}
測試開始
機器吐出到41號球, 袋子大小為10
每個球被選中的概率應該接近0.243902
一共測試10000次
1被選中次數 : 2484, 被選中概率 : 0.2484
2被選中次數 : 2414, 被選中概率 : 0.2414
3被選中次數 : 2445, 被選中概率 : 0.2445
4被選中次數 : 2439, 被選中概率 : 0.2439
5被選中次數 : 2456, 被選中概率 : 0.2456
6被選中次數 : 2434, 被選中概率 : 0.2434
7被選中次數 : 2452, 被選中概率 : 0.2452
8被選中次數 : 2405, 被選中概率 : 0.2405
9被選中次數 : 2385, 被選中概率 : 0.2385
10被選中次數 : 2387, 被選中概率 : 0.2387
11被選中次數 : 2413, 被選中概率 : 0.2413
12被選中次數 : 2463, 被選中概率 : 0.2463
13被選中次數 : 2425, 被選中概率 : 0.2425
14被選中次數 : 2405, 被選中概率 : 0.2405
15被選中次數 : 2463, 被選中概率 : 0.2463
16被選中次數 : 2434, 被選中概率 : 0.2434
17被選中次數 : 2406, 被選中概率 : 0.2406
18被選中次數 : 2456, 被選中概率 : 0.2456
19被選中次數 : 2400, 被選中概率 : 0.24
20被選中次數 : 2467, 被選中概率 : 0.2467
21被選中次數 : 2403, 被選中概率 : 0.2403
22被選中次數 : 2415, 被選中概率 : 0.2415
23被選中次數 : 2432, 被選中概率 : 0.2432
24被選中次數 : 2438, 被選中概率 : 0.2438
25被選中次數 : 2464, 被選中概率 : 0.2464
26被選中次數 : 2514, 被選中概率 : 0.2514
27被選中次數 : 2416, 被選中概率 : 0.2416
28被選中次數 : 2546, 被選中概率 : 0.2546
29被選中次數 : 2440, 被選中概率 : 0.244
30被選中次數 : 2350, 被選中概率 : 0.235
31被選中次數 : 2398, 被選中概率 : 0.2398
32被選中次數 : 2483, 被選中概率 : 0.2483
33被選中次數 : 2405, 被選中概率 : 0.2405
34被選中次數 : 2472, 被選中概率 : 0.2472
35被選中次數 : 2449, 被選中概率 : 0.2449
36被選中次數 : 2431, 被選中概率 : 0.2431
37被選中次數 : 2494, 被選中概率 : 0.2494
38被選中次數 : 2515, 被選中概率 : 0.2515
39被選中次數 : 2507, 被選中概率 : 0.2507
40被選中次數 : 2384, 被選中概率 : 0.2384
41被選中次數 : 2411, 被選中概率 : 0.2411
測試結束
設計抽獎系統,在參與某廠招聘會的學生中,抽取100人送offer
等概率抽取100
人,且學生不能重復報名(去重)。維護一個大小為100
的蓄水池,只需要判斷學生是否首次報名,并確定是第幾個參與者即可。第i
個首次報名的學生,以100 / i
概率決定是否入池,若入選則隨機替換池中一人。
? 單服務器輕量級維護
? 規避多節點數據匯總
? 實時性高,無最終計算延遲
蓄水池采樣核心
在數據流持續輸入且總量未知的情況下,用固定容量的容器維護一個等概率樣本集。
典型場景及變種
- 判斷條件:
- 數據流式輸入且總量未知;
- 需要等概率采樣固定數量樣本。
- 變種處理:
- 動態容量:將固定
k
改為動態k(i)
,概率調整為k(i)/i
; - 分布式:先本地采樣再合并二次采樣,利用分治保證概率正確性。
- 動態容量:將固定
- 日志采樣:分布式系統中按
1/1000
比例抽樣百萬級日志,保留統計特征; - 推薦系統冷啟動:維護固定大小的歷史交互樣本,保證新物品等概率曝光;
- 實時彈幕過濾:從千萬級彈幕中實時抽取固定數量展示;
為什么 MapReduce中要用蓄水池采樣?
MapReduce
是一種處理海量數據的編程模型,核心思想是 “分而治之”,就像一群人分工合作完成大任務。
MapReduce
處理的往往是TB
級甚至PB
級數據(比如日志、用戶行為數據),直接全量采樣或分析不現實:- 全量存儲消耗大量內存和磁盤;
- 直接處理所有數據會拖慢計算速度。
- 蓄水池采樣能用固定大小的樣本(比如
1000
條數據)代表整體特征,大幅減少計算量。
- 如果采樣不均勻(比如總選前
10%
的數據),樣本就會失真,無法反映整體特征。- 蓄水池采樣能確保每個數據被選中的概率相等。
- 即使數據是動態流入的(不知道總量
N
),也能保證等概率,這對MapReduce
處理實時或未知總量的數據很關鍵。
MapReduce
的分布式架構適配蓄水池采樣Map
階段:每個節點獨立對本地數據做蓄水池采樣(比如每個節點存m
條樣本),避免傳輸全量數據,減少網絡開銷;Reduce
階段:合并所有節點的樣本(總共有M = 節點數 × m
條),再用蓄水池采樣取m
條作為最終樣本,保證全局等概率。
如何等概率采樣1個元素,但數據量極大且只能遍歷一次?
蓄水池采樣的k=1
特例,對第i
個元素以1/i
概率替換當前選中元素。
若數據以鏈表形式存儲,如何高效實現蓄水池采樣?
遍歷鏈表時,對第i
個節點(i從1開始
)用k/i
概率決定是否加入蓄水池,維護大小為k
的數組,替換時隨機選位置,時間復雜度O(n)
,空間O(m)
。
帶權重的蓄水池采樣如何實現?
選中概率改為權重之和的比例,元素i
權重為w_i
,第i
步選中概率為w_i/(w?+w?+…+w_i)
,替換時按權重隨機選擇對象。
(注:算法公平,但offer
未必,建議多投幾個池子。)
參考
[1] 程序員代碼面試指南
[2] 算法講解107【擴展】大廠面試中經常漫聊的有趣算法問題