【面试试题】6概率面试题精讲.ppt

概率相关面试题精讲 七月算法 曹鹏 2015年5月7日2/提纲n简介n题外话n面试题总体分析n一些例题o例1 关于独立的理解o例2 构造随机数发生器o例3 不均匀随机数发生器构造均匀o例4 随机变量的和o例5 水库采样o例6 随机排列产生——random_shuffleo例7 带权采样问题n总结简介o概率n对“独立”事件的理解n古典概率 （计数、除法）n条件概率n期望n随机数产生和利用 （采样）＊3/题外话o随机数n随机数生成并不容易o“随机性”和“不可预测性”n固定m，自然数n % m 是“均匀”的，具有一定随机性，但密码学不采用它n一般假设已有一个均匀的随机数生成器o期望的计算n一般转化为方程组oE(A) = E(A1) * p1 + E(A2) * P2 +…+14/面试题总体分析o概率 （简单）n概率、期望的计算： 笔试n随机数o产生：笔试、面试o利用：采样n相关算法 （快排） 面试5/例1 关于独立的理解o例1 X1,X2,都是二元随机变量，取值0和1的概率各一半，则X3＝ X1 xor X2,它与X1、X2独立。

o分析： 枚举, {000,011,101,110},可见X1＝0，1时各有一半情况X3=0,1反直觉？o关于独立： 用定义P(A∩B） ＝ P(A) * P(B)6/例2 构造随机数发生器o例2 假设一个随机数发生器rand7均匀产生1到7之间的随机整数，如何构造rand10，均匀产生1-10之间的随机整数？n分析：关键在于，不想要的数可以扔，要保证“等概率”n方法1 （笨方法） 1-7之间有4个奇数，3个偶数，我们扔掉一个奇数,比如7，这样剩余3个奇数，3个偶数产生的概率相同——我们构造了一个0-1整数的均匀产生器，用它产生4个bit，对应表示整数0..15, 保留1..10就可以了7/例2 续o代码8/例2 续2o方法2 （聪明一点）n使用“七进制” ： 我们把1-7减去1，变为0-6产生一个两位的七进制数，对应0-48，我们把40-48扔掉（因为这只有9个数），其余按照个位数字分类，0-9对应我们要的1-109/例2 续3o关键问题n保证均匀，才能扔掉orand2() + rand2() – 1并不是均匀的1-3n1和3的概率是1/4, 2的概率是1/2 o分析： 一个实验成功的概率是p,则不断实验直到一次成功的期望次数是1/pnp * 1 + (1 – p) * (x + 1) = xo请计算方法1和2的期望循环次数n112/15和49/2010/例3 不均匀随机数发生器构造均匀o例3 一个随机数发生器，不均匀，以概率p产生0，以(1-p)产生1， (0

11/例4 随机变量的和 o例4 （笔试题） 实数随机变量x和y分别在[0,a]与[0,b]之间均匀分布（a和b是给定的实数），再给一个实数z,问x + y <= z的概率？n分析x和y分布是一个矩形，求直线x + y = z下边在矩形内的面积与矩形本身的面积比12/例5 水库（Reservoir）采样o例5 流入若干个对象（整数），事先不知道个数如何随机取出k个 （k小于总数）？n算法：用一个数组a保存k个数 a[0..k -1]n对于第i个元素(i = 1,2,…)o如果i <= k： 则a[i -1]存放这个元素o否则：产生随机数x = rand() % in若x < k,则用a[x]存放这个元素（扔掉之前的元素）13/例5 续o算法优点n不需要预先知道元素个数（可以一个一个流入）o证明，假设目前已经流入n > k个元素，o第i( i <= k)个元素被选中的可能性n1 * k / (k + 1) * (k + 1) / (k + 2) *…*(n -1) / n = k / no第i (i > k)个元素被选中的可能性nk / i * i / (i + 1) * (i + 1) / (i + 2) *…* (n – 1) / n = k / n14/例5 续o思考与扩展nk == 1的特殊性n一个若干行的大文件，随机选择一行n一个不知道长度的链表，随机选择一个或者多个元素n带权采样——如果每个元素权重不同，如何办？o见例715/例6 随机排列产生——random_shuffleo例6 用数组a[0..n -1]随机产生一个全排列n方法1—— 一般不符合要求o产生一个[1,n!]的随机数，然后求出一个排列n方法2 常规方法 请思考证明o初值na[i]和a[i..n – 1]交换16/例7 带权采样问题o例7 给定n种元素，再给定n个权值，按权值比例随机抽样一个元素。

为了方便我们可以假设权值全是整数n方法1 复制若干份，每个元素复制权值那么多份，用例5的方法水库采样o例： 3个a，2个b，6个cn变为aaa, bb, ccccccn优点： 可以使用已有的方法n缺点： 需要自己复制 17/例7 续n方法2 每个元素按照权值对应一个区间o例如 3个a，2个b，6个coa对应[0..2]，b对应[3..4], c对应[5..10]o随机产生一个[0..10]的随机数，二分查找最后对应的元素是哪一个o优点：省空间o缺点： 需要二分查找n方法3 假设有m种元素n（1）先按1/m的概率随机选择一种元素n（2）＊再产生随机数根据权值决定能否选择这种元素，如果能则选取它并结束，否则返回（1）18/例7 续2o详细分析n第（2）步的概率多大？oPi1 = Wi / Wtot 或Pi2 ＝Wi / Wmax 无关紧要（正比于Wi）n实验一次成功的概率？oPsuc = 1/m * sigma(Pi) 注意Pi取不同值的差别o失败(谁也没选中) 的概率 Plose = 1 – Psuco最终选择第i个的概率n1/m * Pi + Plose * 1/m * Pi + Plose2 * ( 1/m * Pi) +….n无穷递缩等比数列， 显然正比于Pi19/例7 续3o关于步骤（2）nPi = a / bo老办法n产生随机数 % b, 看是否小于an或者产生[1..b]的随机数看是否小于等于a n或者产生[0..b – 1]的随机数看是否小于ao期望次数n1/Psucc = m / sigma(Pi) (注意分母不一定是1)oPi1 = Wi / Wtot 期望 恰好是m oPi2 ＝Wi / Wmax 期望是m * Wmax / sigma(W) ，比m小一些o应用n按照分数给用户推荐歌曲、产品等 20/总结o采样o概率算法n快速排序 pivot的选择——避免最差情况n雇佣问题 （算法导论）o不假设输入分布情况oHash函数解决碰撞n一致性hasho多次尝试n如一个算法有一半的可能性得到正确（最优）解——尝试30次，几乎能得到正确（最优）解21/谢谢大家o更多视频尽在： n us：微博n@七月算法n@七月问答n@曹鹏博士22/。