---
description: "量化面试常见的概率题与智力题：对称性、期望、最优停止、几何概率、智力题、估算与做市，每题记可迁移的技巧"
---

# 概率与算法

量化面试里常见的概率题和智力题。按考点分组，每行一个钩子，点进去看完整推导；每篇的数值验证都跑过。

## 对称性：看穿结构，一步出答案

- [12 枚硬币的奇偶性](coin-parity.md) —— 一枚公平硬币就足以把正面总数的奇偶性洗成 1/2；技巧是算 $E[(-1)^X]$
- [飞机上的最后一个座位](airplane-seat.md) —— 最后一人坐对的概率恰好 $1/2$；技巧是只盯 1 号座和 $n$ 号座——每次乱选时两者对称
- [断棍成三角形](broken-stick-triangle.md) —— 随机两刀断成三段能围成三角形的概率 $1/4$；三角不等式 = 每段短于一半，三个坏事件两两互斥
- [圆上 n 点落在同一半圆](semicircle-points.md) —— 圆上 $n$ 个随机点落在同一半圆的概率 $n/2^{n-1}$；技巧是指定领头点，$n$ 个互斥事件直接相加
- [100 个囚徒的红蓝帽](hat-parity.md) —— 最后一人喊出前方红帽数的奇偶，其余 99 人全活；一个 bit 的奇偶校验就够，$k$ 色换成 mod $k$
- [两个孩子问题](two-children.md) —— 至少一个男孩 $1/3$、老大是男孩 $1/2$、周二男孩 $13/27$；同一句话，答案由信息怎么来的决定
- [三门问题](monty-hall.md) —— 换门赢 $2/3$；主持人知情且必开空门，他的动作不改变你那扇门的 $1/3$，剩下的 $2/3$ 全压到另一扇

## 期望：线性性、递推、鞅

- [100 次抛硬币的最长连正](longest-head-run.md) —— 期望 $5.99 \approx \log_2 100 - 0.667$；尾和公式 + 两行 DP，方差永不收缩
- [等 HH 与等 HT](hh-vs-ht.md) —— 等 HH 要 6 次、等 HT 只要 4 次；状态递推或 ABRACADABRA 鞅一行出答案，自重叠越多等得越久
- [集卡问题：骰子掷几次六面全出](coupon-collector.md) —— 集齐 $n$ 种卡期望 $nH_n$，骰子六面全出约 14.7 次；拆成 $n$ 段几何分布再用期望线性性
- [随机排列的不动点](fixed-points.md) —— 随机排列的不动点期望恰为 1、方差也是 1，与 $n$ 无关；指示变量 + 期望线性性，分布趋于 Poisson(1)
- [均匀随机数累加超过 1](uniform-sum-exceeds-one.md) —— 均匀随机数累加到超过 1 平均要 $e$ 个；$P(N>n)=1/n!$ 是单纯形体积，再套尾和公式
- [面条打结成圈](noodle-loops.md) —— $n$ 根面条端点随机两两相接，期望圈数 $\sum_{k=1}^n \frac{1}{2k-1}$，100 根约 3.28；每接一次面条数减 1，逐步递推
- [掷到 6、全程偶数的期望次数](dice-until-six-even.md) —— 掷到 6 为止、已知全程都是偶数，期望 3/2 次而不是 3；条件化等于把停止规则改成掷到 {1,3,5,6} 即停
- [赌徒破产](gamblers-ruin.md) —— 公平赌局从 $i$ 出发先到 $N$ 的概率 $i/N$、期望步数 $i(N-i)$；对 $S_n$ 与 $S_n^2-n$ 两个鞅用可选停时定理

## 最优停止与动态规划

- [骰子最多掷 3 次](dice-reroll.md) —— 最多掷 3 次、随时可停，期望 $14/3$；从最后一掷倒推，门槛就是后面还能拿到的期望
- [秘书问题](secretary-problem.md) —— 先只看前 $n/e$ 个、之后选第一个破纪录的，成功率趋于 $1/e$；按最优者的位置拆概率，和式化积分 $-x\ln x$
- [两个鸡蛋 100 层楼](two-eggs.md) —— 两个鸡蛋 100 层楼最坏 14 次；反过来问 $m$ 次能测几层，$f(k,m)=\sum_{i\le k} \binom{m}{i}$，$1+2+\cdots+14=105$

## 几何概率

- [约会问题：等 15 分钟](meeting-problem.md) —— 两人一小时内随机到、先到等 15 分钟，相遇概率 $7/16 = 1-(3/4)^2$；单位正方形里挖掉两个角三角形
- [Buffon 投针](buffon-needle.md) —— 针长 $l \le d$ 时相交概率 $2l/(\pi d)$；不积分的做法是期望交点数的线性性 + 直径为 $d$ 的圆恒交 2 次

## 智力题

- [3 根绳子烧出 7 分钟](rope-timing.md) —— 两端点燃 = 剩余时间减半，级联三次 $4+2+1=7$；本质是 $7/8$ 的二进制展开
- [1000 瓶酒找毒酒](poison-wine.md) —— 10 只老鼠 = 10 位二进制，$2^{10} = 1024 \ge 1000$ 恰好顶到信息论下界；两轮检测换三进制只要 7 只
- [五张牌魔术：24 种排列怎么猜中 48 张底牌](five-card-trick.md) —— 1 号藏 1 张、摆 4 张，2 号猜底牌；24 种排列看似只够 48 张的一半，但「藏哪张」也是信号：同花色先定底牌花色，13 点圆环把 12 折成 6，剩下 3 张的 6 种顺序传步数
- [100 个囚徒开 100 个盒子](prisoners-boxes.md) —— 顺着盒里的号码走环，全员成功 = 排列没有长于 50 的环，概率 $1-\sum_{k=51}^{100}\frac1k \approx 0.312$；各自乱开只有 $2^{-100}$
- [25 匹马找前 3 名](horse-race.md) —— 5 场分组 + 1 场组冠军赛 + 1 场候选赛 = 7 场；每场至多造出 4 个输家，对手论证卡死第 6 场
- [12 个球找假球](twelve-balls.md) —— 三次称重 27 种读数装下 24 个假设；Dyson 三进制编码给出写死的称法，$n$ 次的上限是 $(3^n-3)/2$，恰好 12
- [100 盏灯的开关](light-switches.md) —— 灯 $n$ 被拨 $d(n)$ 次，约数两两配对、只有完全平方数落单；100 盏里亮 10 盏
- [杆上蚂蚁相撞掉头](ants-on-pole.md) —— 相撞掉头 ≡ 互相穿过，全部掉落最多 $L/v$；蚂蚁无名、只看幽灵，相对顺序不变给出每只的下场
- [过桥问题：1、2、5、10 分钟](bridge-crossing.md) —— 1,2,5,10 过桥最少 17 分钟；每送走最慢两人比一次 $2b$ 与 $a+c$，两行 DP 与穷举逐一吻合
- [5 个海盗分 100 枚金币](pirate-gold.md) —— 5 海盗分 100 金币，最资深者拿 98、隔一人送 1 枚；从 2 人局逆向归纳，超过 200 人时只有 $200+2^k$ 号能活

## 量化面试特有：估算、做市、下注

- [Fermi 估算：上海有多少加油站](fermi-estimation.md) —— 上海加油站约 800 座量级：需求侧 760、供给侧 860 交叉核对；拆成独立因子后误差在对数尺度按 $\sqrt{k}$ 而非 $k$ 累积
- [做市游戏：10 枚骰子的和](market-making.md) —— 10 枚骰子和：中价 35、sd $\approx 5.4$ 定 spread；被成交本身是信息，按 $E[S \mid \text{对手买}]$ 移价
- [Kelly 公式：每次押多少](kelly-criterion.md) —— Kelly 公式 $f^* = p - q/b$ 最大化 $E[\log W]$：60% 胜率 1:1 押 20%；半 Kelly 保住 75% 增长、腰斩概率从 1/2 降到 1/8