今天看到张栋在新浪微博上说一个他当时被 Google 面试时碰到的一个问题 (其实我也碰到过), 觉得这个问题很有意思, 我自己也在工作中碰到过该问题的实际应用, 扩展一下, 大家一起活动下脑子玩玩 :) (答案我就不说了, 不然多没意思)

原始版
有一个店老板, 他决定从每天光顾他的店的顾客中随机选出一个人, 在当天打烊时给这位顾客发去一份小礼品, 问怎样选才能保证随机 (我表达能力太弱, 没看懂的请直接看抽象版. 关键点, 顾客不是同时来, 所以没法让这一堆人站好随机挑, 而且每天会来多少人你不知道, 可能打烊前突然来一大拨人, 老板比较呆, 只能记住一两个人, 没法把所有人的信息都记录下来)

抽象版
有一个数据流输入过来, 请在数据流停止时, 返回数据流中的随机的一个数. 注意, 数据是流, 只能一次读, 而且数据流很大, 本机无法完整存储 (最多也就很少几条)

实际应用
从每天的日志中, 对符合条件的日志, 随机抽出一条来做校验, 数据太大只能一次读过去, 要保证是随机的

加强版
如果店老板每天不是送一个人礼品, 而是送 k 个人礼品, 怎么办?

加强版的抽象
从数据流中返回随机的 k 个数

加强版的实际应用
从每天的日志中随机挑出 k 条来做校验

带权版
每个顾客有一个会员级别, 级别越高的人获奖概率越大, 怎么办?

带权版的抽象
数据流中每个数有权重 w[i], 对数字 i, 返回他的概率从 1/n 变为 w[i] / SUM(w[j], j from 1 to n). k 个数的情况类推

带权版的实际应用
从日志中按权重挑出一条或 k 条来做校验

分布式版
老板开了 m 家分店, 希望还能按平均概率给随机一位或 k 位顾客奖品, 怎么办?

分布式版的抽象
有 m 个数据流, 最后返回的是 m 个数据流合并后的随机数, 一个或 k 个

分布式版的实际应用
日志太大, 一台机器搞不定, 分布式抽取随机的一条或 k 条来做校验 (我下星期会做这个, 所以不要说面试题都是面试官蛋疼想出来坑爹的…)