跳转至

概率与算法

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

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

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

期望：线性性、递推、鞅

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

最优停止与动态规划

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

几何概率

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

智力题

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

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

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