介紹

1.在筆試面試中常作為客觀問題出現(xiàn)（選擇題）。
2、在筆試中往往出現(xiàn)概率、期望的計算。
3、往往利用古典概率進行計算（組合數(shù)學）。

概率的應(yīng)用

1、利用概率改進著名算法（快速排序）
利用概率產(chǎn)生比較好的劃分值，最終使算法的期望時間復(fù)雜度為O(n * logn)，所以概率一般用來打亂輸入，打亂輸入之后算法的復(fù)雜度和輸入的分布沒有關(guān)系，這樣從概率上放置最壞情況的出現(xiàn)
2、隨機數(shù)發(fā)生器
要產(chǎn)生純隨機序列是一個比較難的過程，通常面試中會給定一個隨機數(shù)的發(fā)生器，讓面試者利用這個發(fā)生器構(gòu)造出另一個隨機數(shù)的發(fā)生器，工程中，概率主要用于隨機采樣，即面試中會問如何利用一個隨機數(shù)的發(fā)生器對一批數(shù)據(jù)進行采樣。

經(jīng)典題

有8支球隊，其中有3支強隊和5支弱隊，隨機把它們分成4組進行比賽，則強強相遇的概率是多少
1、總共的分法有：7 * 5 * 3 * 1 = 105種
2、兩強不相遇的分法有： $C_{5}^{3} * A_{3}^{3} = 60$ 種
3、兩強相遇的概率為 (105 - 60) / 105
3只螞蟻，從正三角形的三個頂點出發(fā)，它們移動的速度相同，則碰頭的概率是多少
1、總共有2³種走法
2、不相遇的走法有2種
3、相遇的概率為：(8 - 2) / 8
一個地區(qū)重男輕女，每個家庭都是一直生小孩直到生男孩為止，問在足夠長的時間后，該地區(qū)的男女比例是多少
n / 2的家庭生了一個男孩，孩子數(shù)位1
n / 4的家庭生了一個女孩一個男孩，孩子數(shù)位2
n / 8的家庭生了兩個女孩一個男孩，孩子數(shù)位3
……
n / 2^k的家庭生了k - 1個女孩一個男孩，孩子數(shù)位k
則足夠長的時間后該地區(qū)孩子總數(shù)為1 * n / 2 + 2 * n / 4 + 3 * n / 8 + …… + k * n / 2^k = 2 * n
每個家庭有一個男孩，所以共有n個男孩，所以男女比例為1 ：1
給定一個等概率隨機產(chǎn)生1 ~ 5的隨機函數(shù)f(n)，除此之外不能再用其他隨機機制，請實現(xiàn)隨機產(chǎn)生1 ~ 7的隨機函數(shù)
1、f'(n) = f(n) - 1：產(chǎn)生0 ~ 4的隨機數(shù)
2、f(n) = 5 * f'(n)：隨機產(chǎn)生0、4、8、12、16、20中的數(shù)
3、f(n) = f(n) + f'(n)：產(chǎn)生0 ~ 24的隨機數(shù)
4、用f(n)可產(chǎn)生1 ~ 20中的隨機數(shù)（如產(chǎn)生隨機數(shù)大于20則舍棄）
5、f(n) = f(n) % 7：產(chǎn)生0 ~ 6之間的隨機數(shù)
6、f(n) = f(n) + 1：產(chǎn)生1 ~ 7之間的隨機數(shù)
其實這道題左神沒有講清楚本質(zhì)，這道題本質(zhì)就是得到一串均勻分布且長度大于等于7的連續(xù)序列即可（必須連續(xù)，這樣才能保證對7取余后得到的0~6等概率），在這個序列里選中7個（或7的倍數(shù)個），若得到的數(shù)不是這7個中的，重新產(chǎn)生。這樣這7個數(shù)的概率肯定是相同的。
給定以p概率產(chǎn)生0，以1 - p概率產(chǎn)生1的隨機函數(shù)，p固定且未知，請實現(xiàn)等概率產(chǎn)生0 1隨機數(shù)的隨機函數(shù)，不可以使用額外的隨機機制
1、利用隨機函數(shù)產(chǎn)生兩個數(shù)，則產(chǎn)生序列為0 1和1 0的概率相等且為：p * (1 - p)
2、兩次利用隨機函數(shù)產(chǎn)生一個序列，若產(chǎn)生0 1記0，若產(chǎn)生1 0記1，其他則舍棄
給定f()，等概率返回一個在[0, 1)區(qū)間的浮點數(shù)，則出現(xiàn)[0, x)區(qū)間數(shù)的概率為x，現(xiàn)給定一個屬于0的整數(shù)k，請實現(xiàn)一個返回[0, 1)范圍上數(shù)的函數(shù)，但[0, x)上數(shù)出現(xiàn)的概率為x^k
調(diào)用函數(shù)f()k次，產(chǎn)生k個結(jié)果，返回所有結(jié)果中最大的那個數(shù)，如果返回值在[0, x)區(qū)間，則k次調(diào)用結(jié)果都在[0, x)區(qū)間，這種情況發(fā)生的概率為x^k
給定一個長度為n，且沒有重復(fù)元素的數(shù)組arr和一個整數(shù)m，實現(xiàn)函數(shù)等概率打印arr中的m個數(shù)
此題為無放回采樣，實現(xiàn)過程中只需要產(chǎn)生采樣區(qū)間內(nèi)的隨機數(shù)i，然后將arr[i]和采樣區(qū)間的最后一個數(shù)交換，然后采樣區(qū)間從尾部縮短一，重復(fù)這樣的操作，直到采樣數(shù)位m即可
有一個機器可以依次從小到大吐出按自然數(shù)編號的球，假設(shè)有一個袋子最多可以裝入k個球，每次從袋子中倒出球后不可恢復(fù)，當機器一共吐出N個球時，袋子里共有k個球，請設(shè)計算法調(diào)整袋子中的球，使吐出的N個球中被選入袋子中的概率為k/N
蓄水池抽樣算法
1、處理1~k號球時，直接放進袋子里。
2、處理第i號球時，以k/i的概率的概率將球放入袋子，同時以1/k的的概率從袋子中扔掉任意一個球（隨機扔掉任意一球），如果不把第i號球入袋則直接扔掉i號球
- 證明：
  - 當1<i<k時
    1、吐出k + 1號球時i號球還在袋子里的概率為：1 - (k + 1號球被選中入袋的概率 * i號球被選中出袋的概率)，即：
    $(1- \frac {k} {k + 1} * \frac {1} {k}) = \frac {k} {k + 1}$
    吐出k + 2號球時i號球還在袋子里的概率為：1 - (k + 2號球被選中入袋的概率 * i號球被選中出袋的概率)，即：
    $(1- \frac {k} {k + 2} * \frac {1} {k}) = \frac {k + 1} {k + 2}$
    吐出k + 3號球時i號球還在袋子里的概率為：1 - (k + 3號球被選中入袋的概率 * i號球被選中出袋的概率)，即：
    $(1- \frac {k} {k + 3} * \frac {1} {k}) = \frac {k + 2} {k + 3}$
    ……
    吐出N號球時i號球還在袋子里的概率為：1 - (N號球被選中入袋的概率 * i號球被選中出袋的概率)，即：
    $(1- \frac {k} {N} * \frac {1} {k}) = \frac {N - 1} {N}$
    2、從1 ~ N號球的過程中第i號球一直存在的概率為：吐出k + 1號球時i在袋子里的概率 * 吐出k + 2號球時i在袋子里的概率 * 吐出k + 3號球時i在袋子里的概率 * …… *吐出N號球時i在袋子里的概率 *，即：
    $\frac {k} {k + 1} * \frac {k + 1} {k + 2} * \frac {k + 2} {k + 3} * …… * \frac {N - 1} {N} = \frac {k} {N}$
  - 當k<i<N時
    1、吐出i + 1號球時i號球還在袋子里的概率為：1 - (i + 1號球被選中入袋的概率 * i號球被選中出袋的概率)，即：
    $(1- \frac {k} {i + 1} * \frac {1} {k}) = \frac {i} {i + 1}$
    吐出i + 2號球時i號球還在袋子里的概率為：1 - (i + 2號球被選中入袋的概率 * i號球被選中出袋的概率)，即：
    $(1- \frac {k} {i + 2} * \frac {1} {k}) = \frac {i + 1} {i + 2}$
    吐出i + 3號球時i號球還在袋子里的概率為：1 - (i + 3號球被選中入袋的概率 * i號球被選中出袋的概率)，即：
    $(1- \frac {k} {i + 3} * \frac {1} {k}) = \frac {i + 2} {i + 3}$
    ……
    吐出N號球時i號球還在袋子里的概率為：1 - (N號球被選中入袋的概率 * i號球被選中出袋的概率)，即：
    $(1- \frac {k} {N} * \frac {1} {k}) = \frac {N - 1} {N}$
    2、從i + 1 ~ N號球的過程中第i號球一直存在的概率為：吐出i + 1號球時i在袋子里的概率 * 吐出i + 2號球時i在袋子里的概率 * 吐出i + 3號球時i在袋子里的概率 * …… *吐出N號球時i在袋子里的概率 *，即：
    $\frac {i} {i + 1} * \frac {i + 1} {i + 2} * \frac {i + 2} {i + 3} * …… * \frac {N - 1} {N} = \frac {k} {N}$