字节跳动算法工程师面经 读后

读到字节跳动的面试题目(https://www.nowcoder.com/discuss/395924)，觉得很有趣，尝试给了我的答案。

问题：10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。要求用Python程序模拟十万次，暴力求出该概率。

直接算不难，大概1.09e-6。难度在于要”暴力”模拟十万次内求出。因为概率太小，直接模拟结果常得出0，不是我们想得到的答案。

import random
total_number = 100000
def stimulation(balls = 10, boxes = [0] * 12):
    for i in range(balls):
        index = random.randint(0,11)
        boxes[index] += 1
    return boxes
def emptyBoxes(boxes):
    number = 0
    for item in boxes:
        if item == 0:
            number += 1
    return number
def simulations(number):
    ten_empty_boxes = 0
    for i in range(number):
        result = stimulation(10, [0] * 12)
        if emptyBoxes(result) == 10:
            ten_empty_boxes += 1
    return float(ten_empty_boxes) / total_number
print(simulations(total_number))

0.0

答案：在不假设概率分布的情况下，我们定义两个events。

Event A: 10个小球，随机分到12个盒子里，恰好10个盒子都为空

Event B: 10个小球，其中5个小球随机分到12个盒子里，＞=10个盒子都为空

明显P(B|A) = 1，所以 P(A) = P(AB) = P(A|B)P(B)

而 P(A|B) 和P(B) 明显远大于P(A) ，我们只要”暴力”求得P(A|B) 和P(B) 就可以。

def simulations_part1(number):
    five_empty_boxes = 0
    states = []
    for i in range(number):
        result = stimulation(5, [0] * 12)
        if emptyBoxes(result) >= 10:
            five_empty_boxes += 1
            states.append(result)
    return float(five_empty_boxes) / number, states
prob_part1, states_part1 = simulations_part1(10000)
print(prob_part1)
0.0071
def simulations_part2(number, states):
    ten_empty_boxes = 0
    for i in range(number):
        index = random.randint(0,len(states)-1)
        state = states[index][:]    
        result = stimulation(5, state)
        if emptyBoxes(result) == 10:
            ten_empty_boxes += 1
    return float(ten_empty_boxes) / number
prob_part2 = simulations_part2(90000, states_part1)
print(prob_part2)
0.000155555555556

print(prob_part1 * prob_part2)
1.10444444444e-06

所以我们在十万次模拟内估算P(A) = P(A|B)*P(B) 大概等于1.10444e-6，跟真实答案已经相差不远。

至于为什么是五个小球，分成一万跟九万次模拟，这里我只给出一个答案，不一定是最佳答案，欢迎大家讨论。