复试那天拿到题目纸条上面就写着“情书问题”四个字我愣了一下。坐在我对面的考官补了一句“给你十分钟说说怎么给一群写情书的人安排配对让他们谁都不后悔。”我低头看了一眼草稿纸忽然想明白这不就是稳定婚姻问题的换皮版本嘛。这个场景我想很多考研党都可能有共鸣。今天把这套题的思路、代码和现场踩坑经验完整写出来权当给后来人留一份参考。重要补充说明本文以“某高校复试”中的一道算法场景题为引子展开不涉及任何具体院校、人员与政策信息所有案例均为通用技术讲解。1. 情书问题到底在问什么1.1 从题目表面到问题本质所谓“情书问题”原题描述通常是这样的有 n 个男生和 n 个女生每个人都按照自己心里的喜欢程度给所有异性排了一个好感度名次。现在要求给出一个一男一女的配对方案使得配对结果“稳定”。什么叫稳定呢官方说法是不存在“私奔对”。举例来说如果男生 A 和女生 X 配对男生 B 和女生 Y 配对但 A 心里更喜欢 Y同时 Y 心里也更喜欢 A那么 A 和 Y 这两个人就有可能互递情书、推翻现有安排这就是不稳定配对。所以这道题的别名其实很多在算法领域它有个更响亮的名字稳定婚姻问题Stable Marriage Problem。复试里故意不叫稳定婚姻叫情书问题大概率是想看你能不能绕过花哨的题干直接抓住匹配问题的骨架。我在现场时意识到这一点之后就明白了考的不是情书是建模能力。1.2 为什么复试面试官偏爱这种题面试官选这道题我个人认为有三个考量。第一它题干短、场景直观考生不需要太多背景知识就能理解。第二它背后隐藏着经典的 Gale-Shapley 算法既能考察算法积累又能考察现场推导能力。第三也是最关键的一点它能区分“背过模板的人”和“真懂原理的人”。如果你只知道套用 Gale-Shapley 的结论却说不清为什么它能保证稳定为什么主动方有优势面试官几句追问就能把你问穿。我在复试前的准备阶段看过一些匹配类问题但说实话当时只记住了“男生主动、女生被动、男生最优”这句话。真在草稿纸上推了一遍之后才发现这句话背后全是坑比如主动方最优到底是全局最优还是局部最优被动方最差又是什么意思。这些细节如果不亲手推导到了现场真的很容易翻车。2. 从情书场景到数学模型的转化2.1 偏好表是第一步拿到情书问题第一件事不是急着写代码而是把题目里的“好感排名”抽象成数据结构。每个男生维护一个对女生的偏好列表每个女生维护一个对男生的偏好列表。为了方便算法操作一般用二维数组或者哈希表存。我用的是二维数组 prefer_men[m][n]表示第 m 个男生心中第 1 名到第 n 名的女生编号同理 prefer_women[w][n] 表示第 w 个女生的偏好排名。在复试的白板上我没写完整代码只画了一个 3x3 的例子然后口头说明如何把偏好列表转换成匹配关系。这样做的好处是快速和面试官对齐模型避免一上来写一堆变量名把场面搞乱。后来我自己在电脑上复现时才发现数据结构选得不好会带来很多边界问题不如直接定义成 0-index 的整数数组方便操作。2.2 稳定性的数学判定稳定不能靠感觉必须有一个可程序化的判定条件。设最终匹配中男生 m 配对到女生 w1另一个男生 m2 配对到女生 w2。要判断整体是否稳定需要遍历所有可能的男女组合 (m, w2) 和 (m2, w1)检查是否存在这样一对男生 m 对女生 w2 的喜欢程度高于 w1且女生 w2 对男生 m 的喜欢程度也高于 m2。如果存在就说明 m 和 w2 有互相改配的动机匹配不稳定。这个判定逻辑在实现时有一个很容易忽略的点只能按“双方都更满意”来判定不能只看单方面。我在第一次写校验函数时只检查了男生满意程度更高的情况结果漏掉了女生那头的不满导致测试用例怎么跑都好像没问题但换一组数据就报错。后来养成了习惯写稳定校验时一定把两个条件都写上并且注释里明确标出。2.3 为什么暴力枚举不靠谱看到 n 个男生和 n 个女生时很多人第一反应是枚举所有排列。每个男生可以有 n 个选择不考虑约束的话总数是 n^n即使限定为一对一配对那也有 n! 种可能。n 等于 10 的时候就是 3628800 种n 等于 15 瞬间过亿。复试现场虽然只是讲思路但如果你敢说“枚举所有方案再检查稳定性”面试官大概率会追问一句“复杂度呢”。所以这道题真正考察的落脚点是需要一个比暴力搜索高效得多的确定性算法。Gale-Shapley 算法的厉害之处在于它的时间复杂度是 O(n^2)空间复杂度是 O(n^2)而且一定能结束一定能给出一个稳定匹配。这在复试那种时间紧张的场景里几乎是标准答案。3. Gale-Shapley 算法手撕全过程3.1 算法核心思路求婚-拒绝循环Gale-Shapley 算法的通俗版本是每个男生都向自己心里最喜欢的女生表白女生如果暂时没有更好的选择就先收下但如果后来有一个她更喜欢的人出现她就会甩掉当前男生换成新人被甩的男生只好在偏好列表里继续往下找下一个目标重复这个过程直到所有男生都找到对象为止。这里面最关键的是“循环”的设计。我习惯用队列来维护还没有完成配对的男生每次从队列头部取一个男生让他按自己的偏好列表依次去试探。如果他当前试探的女生还是单身直接配对成功如果女生已经名花有主那就比较现任男生和这个新男生在女生心里的排名谁靠前留下谁靠后的那个重新入队。这里有个细节男生被拒绝后不能重复试探同一个女生所以需要维护一个指针数组 next[i]记录每个男生下一次该尝试的女生下标。3.2 代码实现从伪代码到可运行 Python下面这份代码是我后来在电脑上反复调试过的版本可以直接跑也加了详细注释。用 Python 写这个算法很自然因为队列和数组操作都比较直观。核心函数有两个一个是执行匹配的 build_matches另一个是校验稳定性的 is_stable。匹配函数返回两个数组wife 表示每个男生匹配到的女生编号husband 表示每个女生匹配到的男生编号。这两个数组是互相对偶的后续校验会用到。from collections import deque def build_matches(prefer_men, prefer_women): :param prefer_men: 二维数组prefer_men[i] 表示男生 i 对女生的偏好排名从高到低 :param prefer_women: 二维数组prefer_women[j] 表示女生 j 对男生的偏好排名从高到低 :return: (wife, husband) n len(prefer_men) # wife[i] 表示男生 i 匹配到的女生编号初始为 -1 wife [-1] * n # husband[j] 表示女生 j 匹配到的男生编号初始为 -1 husband [-1] * n # 每个男生下一次要向哪个女生表白 next_choice [0] * n # 男生自己心中的排名映射rank_men[i][girl] 男生 i 心中女生 girl 的名次越小越好 rank_men [[0] * n for _ in range(n)] for i in range(n): for idx, girl in enumerate(prefer_men[i]): rank_men[i][girl] idx # 女生心中的排名映射rank_women[j][boy] 女生 j 心中男生 boy 的名次 rank_women [[0] * n for _ in range(n)] for j in range(n): for idx, boy in enumerate(prefer_women[j]): rank_women[j][boy] idx free_men deque(range(n)) while free_men: man free_men.popleft() girl prefer_men[man][next_choice[man]] next_choice[man] 1 if husband[girl] -1: wife[man] girl husband[girl] man else: current_man husband[girl] if rank_women[girl][man] rank_women[girl][current_man]: # 新人更被喜欢旧人被甩 wife[man] girl husband[girl] man free_men.append(current_man) else: # 旧人还是更被喜欢新人继续单身 free_men.append(man) return wife, husband def is_stable(wife, husband, prefer_men, prefer_women): n len(wife) rank_men [[0] * n for _ in range(n)] for i in range(n): for idx, girl in enumerate(prefer_men[i]): rank_men[i][girl] idx rank_women [[0] * n for _ in range(n)] for j in range(n): for idx, boy in enumerate(prefer_women[j]): rank_women[j][boy] idx for man in range(n): current_wife wife[man] # 对于每一位女生检查是否存在不稳定对 for girl in range(n): if girl current_wife: continue # 男生更喜欢这个女生同时这个女生也更喜欢这个男生 if rank_men[man][girl] rank_men[man][current_wife] and \ rank_women[girl][man] rank_women[girl][husband[girl]]: return False return True这段代码我测试过很多组随机数据稳定校验全部通过。如果你在复试现场不一定要写出完整实现但伪代码里的“队列 指针数组 双排名映射”这三个东西一定要讲到因为它们是整个算法的骨架。3.3 复杂度分析为什么是 O(n^2)很多人记复杂度只记结论在这里我用最直白的方式推一遍。每个男生最多只会向每个女生表白一次所以每个男生最多完成 n 次尝试n 个男生合起来最多 n^2 次“求婚”操作。每次操作中对女生现任男友的比较是 O(1) 的因为我们已经提前用 rank_women 数组存好排名了。队列的进出操作也是 O(1)。因此总体时间复杂度就是 O(n^2)。空间方面存储两个偏好矩阵本身就是 O(n^2)rank 映射也是 O(n^2)其余辅助数组都是 O(n)所以空间复杂度 O(n^2)。面试官如果接着问“能不能优化空间”你可以说可以把偏好矩阵和 rank 合并存储减少一个二维数组的占用但整体量级不变。这种追加问题考察的是工程敏感度我当时就是因为提前想过这一步才没有被问住。3.4 一个容易混淆的理论点主动方最优、被动方最差Gale-Shapley 有个非常反直觉的性质在同一组偏好数据下主动求婚的一方会得到所有稳定匹配中对自己最好的结果而被动接受的一方会得到所有稳定匹配中对自己最差的结果。注意这是在不同稳定匹配之间的比较并不是说主动方得到的一定是全局个人最优。全局最优当然人人都想要但稳定性的约束会限制这种可能性。我在复试时被追问过“是不是男生主动就一定让每个男生都最爽”。我当时的回答是不是算法只是保证男生整体上拿到了“他们能拿到的稳定结果里的最优解”但某个具体男生可能更喜欢另一种稳定匹配里的伴侣。女生那头同理算法给她们的结果是“最差稳定结果”有的女生可能有怨气但整体不会有人互相满意到要私奔。面试官点了点头这个点答对很关键。4. 复试现场的演示与实操经验4.1 在白板上画 3x3 实例我建议任何人在面对这种题时都不要一开始就写大段代码而是先画一个小例子。我用的是三男三女给了两组偏好表。男生0喜欢女生0、1、2男生1喜欢女生2、0、1男生2喜欢女生1、2、0女生0喜欢男生1、2、0女生1喜欢男生2、0、1女生2喜欢男生0、1、2。这个例子我特意设计成每个人都有不同的偏好顺序这样能完整展示算法循环的每个分支。第一轮男生0表白女生0配对成功男生1表白女生2配对成功男生2表白女生1配对成功。看起来一轮就结束了但这个匹配不稳定因为男生0更喜欢女生1而女生1也更喜欢男生0。这时候算法并不会停止但因为初始时所有男生都有伴了循环就会正常退出。这里就要注意了Gale-Shapley 算法必须处理“所有人都有伴”和“还有人没伴”两种情况。如果所有人第一轮就都有伴直接结束如果还有单身汉说明有人被甩了需要继续循环。所以我用队列判断就要谨慎不能简单数匹配数。为了完整演示“被甩再追”我又换了一个例子女生0的偏好里男生2比男生0排名更靠前。这样男生0表白女生0后后来男生2也表白女生0女生0就会选择男生2把男生0甩了。男生0再去表白女生1。这个过程在白板上画两三轮面试官就能看到算法在动态调整。4.2 代码实现时容易踩的坑第一个坑是“男生被拒绝后没有把当前选择往后移”。我一开始写的时候next_choice 更新放在判断之前结果男生被拒绝后再次入队列下次还是尝试同一个女生形成死循环。正确做法是每次尝试完一个女生立刻让 next_choice 加一不管表白成功还是失败。第二个坑是“男生已经有对象了却还留在自由队列里”。在算法里只有当前没有对象的男生才需要入队。一旦配对成功就要从队列里移除。但这里有个特殊情况男生被甩之后要重新入队。如果你的代码逻辑是“从队列取出来的时候才维护状态”就要小心重复入队导致队列里出现同一个男生两次。我当时在调试时遇到过这种情况最后用字典记录每个男生是否在队列里才排查清楚。第三个坑是“数据处理时下标没对齐”。很多适合复试题给的偏好列表是从 1 开始的但代码里用 0-index转换不到位就会出现莫名其妙的“女生0不存在”错误。我建议所有参与复试模拟训练的人都明确规定统一用 0-index然后在读入数据时直接减一。4.3 和面试官的对答技巧如果面试官问“你为什么用队列而不是栈”你要知道他考察的是算法特性Gale-Shapley 对处理顺序并不敏感用队列只是实现方便。你可以回答“队列保证每轮都处理所有当前单身的男生但其实换成栈也不影响最终稳定匹配结果”。这种回答能展示你对算法本质的理解而不是死记模板。如果面试官问“如果偏好列表里有并列名次怎么办”你要知道经典算法假设没有并列每个排名都是严格全序。如果有并列问题就变成了允许平局的稳定婚配问题情况复杂得多。你可以大方承认经典版本假设严格排序并列情况可以另开讨论不需要现场硬答。诚实比瞎编更安全。5. 情书问题背后的应用价值远不止复试5.1 学生志愿分配与平台派单稳定匹配算法在现代系统里到处都在用。比如高校里的宿舍分配、双选会岗位分配、导师与学生互选本质上都是“双方都有偏好需要稳定配对”的场景。复试里这题叫“情书问题”换到真实系统里就是几千个学生和几千个导师的双向选择。某高校的某实验室就用过类似方案来做导师双选核心就是偏好排序加稳定匹配。至于具体是哪所学校我就不提了反正思路完全一样。平台派单场景也类似司机和乘客互评偏好、骑手和订单之间的匹配。不过真实场景里通常还叠加了位置、时效、价格等因素纯稳定匹配只作为基础框架上边还得加约束优化。所以复试里只要你能把“情书问题”和“匹配系统”联系起来就已经比大多数只会背算法的考生强很多。5.2 双向选择效率的量化提升我为什么说稳定匹配能让系统变好举个简单例子如果不做任何匹配策略直接用先到先得很可能出现“一个差配对”卡住整个系统的情况。比如导师 A 和导师 B 都想要学生 X学生 X 却想去没名额的导师 C最后系统为了满足 X 就得打乱一堆已配对的组合。用稳定匹配算法所有“互相满意到可以换”的组合都不会存在省去了大量后续调度成本。这在工程里有个实际收益减少返工。你做导师双选系统时最怕的就是匹配结果公布后有人申诉“我想换导师”那个过程非常消耗人力。稳定匹配虽然不能保证所有人都满意但能保证没有人组合出“互相更满意”的配对申诉量会大幅下降。5.3 变体问题当人数不对称时怎么办复试题目通常固定男女各 n 个但实际应用里两边人数很难相等。我来分享一个常用的处理思路把人数少的一方保持不变人数多的一方模拟为“所有人都可以单身”。具体做法是把多出来的那一侧加一个“虚拟对象”任何人和虚拟对象匹配都意味着单身。这样就把不对称问题转化为标准 n x n 匹配问题。但是要注意加了虚拟对象后稳定性的定义也要改虚拟对象对所有真实对象都没有兴趣真实对象对虚拟对象也没有偏好相当于他们只是“没有匹配结果”。这个变体非常常见。我见过有人直接用原算法硬跑不对称数据结果在下标访问时直接崩溃。所以如果面试官追问“如果男生比女生多算法怎么改”你能答出虚拟对象方案基本就稳了。5.4 情书问题在求职匹配中的应用思路秋招春招里的“人才池 岗位池”也可以套用稳定匹配模型。候选人会投简历对不同岗位有偏好排序HR 也会按简历筛人对候选人有优先级排序。往年的痛点是一人手上多个 Offer接了又鸽掉导致岗位空着招不满。如果引入稳定匹配机制理论上可以显著减少此类“鸽中鸽”现象。当然现实中人的偏好会变Offer 信噪比又低所以真正全自动化的匹配系统并不多。多数企业只是把这种算法作为决策辅助我先给出一份稳定匹配名单再由 HR 人工微调。这样既发挥算法效率又保留人的判断。如果你在做这类系统我的建议是不要一上来就追求全局自动匹配。先做“候选名单排序”再用稳定匹配算法辅助决策上线观察几轮数据后再逐步增加自动化程度。这个思路放到导师双选、宿舍分配、选修课抢课系统里都一样适用。6. 日常训练中我常用的一些案例与工具6.1 随机生成偏好数据来验证算法自己练这道题时如果只用一个手写案例验证不了算法的稳定性。我写了一个小脚本随机生成 n 个男生和 n 个女生的偏好排列然后跑匹配并调用 is_stable 校验。每次生成不同的随机种子能覆盖很多边界情况比如某个女生是所有男生的第一志愿或者某个男生的偏好列表和另一个人的偏好完全相同。import random def generate_case(n): men_pref [] women_pref [] for _ in range(n): p list(range(n)) random.shuffle(p) men_pref.append(p) for _ in range(n): p list(range(n)) random.shuffle(p) women_pref.append(p) return men_pref, women_pref这个生成器写起来很简单但对训练特别有用。每次跑完匹配我都会打印 wife、husband 和稳定校验结果。如果校验结果是 False就回溯那组随机种子定位是算法 bug 还是数据问题。用这种“随机生成 自动校验”的方式训练比反复默写代码有效得多。6.2 纸质推导训练法面试前我还做过一种训练不给电脑纯用纸笔推 5x5 甚至 6x6 的随机案例。这个训练看起来很笨实际上非常锻炼对算法流程的敏感度。推几组之后你会发现自己不需要再逐行模拟代码看到某个先生的偏好列表就能预判他会不会被甩看到某个女生的现有男友很快就能判断她要不要换人。这种“人脑模拟”能力在现场特别宝贵因为面试官有时候会中途改偏好顺序或者故意制造一个复杂的反例你要是只能照着代码逻辑想会很被动。我用这个方法练了一周后来复试现场看到一个 4x4 的反例时几乎是秒反应出结果。面试官还问了一句“你怎么这么快”我说我用这个案例手推了无数遍太熟了。虽然这个回答有点实在过头但反而让面试官觉得我是真练过。6.3 可视化调试的必要性给代码加上简单的打印日志也非常重要。我的调试方式是在每次配对或拆对时打印“男生 X 向女生 Y 表白当前男友 Z比较结果是分手/继续”。这样能把整个循环过程完整呈现。配对问题最难调的就是状态不一致常常是 wife 数组变了husband 数组没同步变于是稳定校验直接报错。打日志能第一时间定位是哪个男生被落了单哪个女生的记录没有更新。用打印日志的方式跑一个 5 个男生的案例屏幕上大概会输出 10 到 20 行过程记录。看起来乱但配合断点看代码你会发现自己对算法的直观理解突然上升了一个台阶。这个方法不是某本算法书教的是我调了一晚上 bug 后悟出来的特别值得分享。7. 情书问题让我明白的道理7.1 算法题不是背出来的准备复试时我曾经试图把所有常见算法都背一遍但真到了情书问题这种“包装过的陌生题”背过的模板反而成了干扰。因为我总想着“这题是不是应该套什么模板”结果忘了从题目本质去思考。后来我发现真正有效的准备方式不是背模板而是做“换皮训练”同一个稳定婚姻问题今天用“情书”来包装明天用“导师双选”来包装后天用“宿舍分配”来包装。每次都能在五分钟内识别出底层模型这才是复试要的能力。情书问题就是典型的例子看起来像是在讲恋爱实际是稳定的心仪对象匹配。如果只看表面文字很容易慌如果抓住了“偏好列表 稳定条件”这个骨架无论题干怎么变都能从容面对。7.2 主动与被动的关系映射到生活里写情书的人对应主动求婚方被表白的人对应被动接受方这个关系映射到生活中的所有双边匹配。算法本身是客观的但设计算法时的博弈立场是主观的。复试里默认男生主动只是很多教材的惯例实际工程里你可以让更紧缺的一方主动或者让需要保留更多选择权的一方主动。这一点在系统设计时特别重要。比如导师双选制度里如果导师是稀缺资源那么让导师“主动”匹配得到的稳定结果就对导师更有利如果学生稀缺就让学生“主动”。这实际上不是算法偏好而是策略选择。想设计一个让两边都能接受的系统恐怕还得在稳定匹配的约束之外再加一些补偿机制比如允许少量排序靠后的学生和导师有二次协商的机会。7.3 关于复试的一点个人建议如果你正为复试焦虑我的体会是算法题有套路但套路的根基永远是理解。情书问题能流行起来恰恰是因为它不靠死记硬背只要你把稳定婚姻的内在逻辑吃透了遇到任何变体都能迎刃而解。在白板上写不出完整代码没关系把思路讲清楚、边界说明白、复杂度算准确就已经能证明你的水平了。最后分享一个我自己的习惯每次看完一道算法题都问自己三个问题。第一这个问题能不能拆成更简单的模型。第二数据规模如果很大内存和时间的瓶颈在哪。第三如果数据出现极端情况算法会不会退化。情书问题三个问题都问一遍之后你会发现自己对它的理解比背十遍代码都深。这是我踩过很多坑之后才总结出的方法后面练其他算法题我也一直在用。备考的各位不妨试试看。 
长河君 · 2026/10/11 7:24:08 · 阅读 1.2k 情书问题背后的稳定婚姻算法：Gale-Shapley原理与工程落地
复试那天拿到题目纸条上面就写着“情书问题”四个字我愣了一下。坐在我对面的考官补了一句“给你十分钟说说怎么给一群写情书的人安排配对让他们谁都不后悔。”我低头看了一眼草稿纸忽然想明白这不就是稳定婚姻问题的换皮版本嘛。这个场景我想很多考研党都可能有共鸣。今天把这套题的思路、代码和现场踩坑经验完整写出来权当给后来人留一份参考。重要补充说明本文以“某高校复试”中的一道算法场景题为引子展开不涉及任何具体院校、人员与政策信息所有案例均为通用技术讲解。1. 情书问题到底在问什么1.1 从题目表面到问题本质所谓“情书问题”原题描述通常是这样的有 n 个男生和 n 个女生每个人都按照自己心里的喜欢程度给所有异性排了一个好感度名次。现在要求给出一个一男一女的配对方案使得配对结果“稳定”。什么叫稳定呢官方说法是不存在“私奔对”。举例来说如果男生 A 和女生 X 配对男生 B 和女生 Y 配对但 A 心里更喜欢 Y同时 Y 心里也更喜欢 A那么 A 和 Y 这两个人就有可能互递情书、推翻现有安排这就是不稳定配对。所以这道题的别名其实很多在算法领域它有个更响亮的名字稳定婚姻问题Stable Marriage Problem。复试里故意不叫稳定婚姻叫情书问题大概率是想看你能不能绕过花哨的题干直接抓住匹配问题的骨架。我在现场时意识到这一点之后就明白了考的不是情书是建模能力。1.2 为什么复试面试官偏爱这种题面试官选这道题我个人认为有三个考量。第一它题干短、场景直观考生不需要太多背景知识就能理解。第二它背后隐藏着经典的 Gale-Shapley 算法既能考察算法积累又能考察现场推导能力。第三也是最关键的一点它能区分“背过模板的人”和“真懂原理的人”。如果你只知道套用 Gale-Shapley 的结论却说不清为什么它能保证稳定为什么主动方有优势面试官几句追问就能把你问穿。我在复试前的准备阶段看过一些匹配类问题但说实话当时只记住了“男生主动、女生被动、男生最优”这句话。真在草稿纸上推了一遍之后才发现这句话背后全是坑比如主动方最优到底是全局最优还是局部最优被动方最差又是什么意思。这些细节如果不亲手推导到了现场真的很容易翻车。2. 从情书场景到数学模型的转化2.1 偏好表是第一步拿到情书问题第一件事不是急着写代码而是把题目里的“好感排名”抽象成数据结构。每个男生维护一个对女生的偏好列表每个女生维护一个对男生的偏好列表。为了方便算法操作一般用二维数组或者哈希表存。我用的是二维数组 prefer_men[m][n]表示第 m 个男生心中第 1 名到第 n 名的女生编号同理 prefer_women[w][n] 表示第 w 个女生的偏好排名。在复试的白板上我没写完整代码只画了一个 3x3 的例子然后口头说明如何把偏好列表转换成匹配关系。这样做的好处是快速和面试官对齐模型避免一上来写一堆变量名把场面搞乱。后来我自己在电脑上复现时才发现数据结构选得不好会带来很多边界问题不如直接定义成 0-index 的整数数组方便操作。2.2 稳定性的数学判定稳定不能靠感觉必须有一个可程序化的判定条件。设最终匹配中男生 m 配对到女生 w1另一个男生 m2 配对到女生 w2。要判断整体是否稳定需要遍历所有可能的男女组合 (m, w2) 和 (m2, w1)检查是否存在这样一对男生 m 对女生 w2 的喜欢程度高于 w1且女生 w2 对男生 m 的喜欢程度也高于 m2。如果存在就说明 m 和 w2 有互相改配的动机匹配不稳定。这个判定逻辑在实现时有一个很容易忽略的点只能按“双方都更满意”来判定不能只看单方面。我在第一次写校验函数时只检查了男生满意程度更高的情况结果漏掉了女生那头的不满导致测试用例怎么跑都好像没问题但换一组数据就报错。后来养成了习惯写稳定校验时一定把两个条件都写上并且注释里明确标出。2.3 为什么暴力枚举不靠谱看到 n 个男生和 n 个女生时很多人第一反应是枚举所有排列。每个男生可以有 n 个选择不考虑约束的话总数是 n^n即使限定为一对一配对那也有 n! 种可能。n 等于 10 的时候就是 3628800 种n 等于 15 瞬间过亿。复试现场虽然只是讲思路但如果你敢说“枚举所有方案再检查稳定性”面试官大概率会追问一句“复杂度呢”。所以这道题真正考察的落脚点是需要一个比暴力搜索高效得多的确定性算法。Gale-Shapley 算法的厉害之处在于它的时间复杂度是 O(n^2)空间复杂度是 O(n^2)而且一定能结束一定能给出一个稳定匹配。这在复试那种时间紧张的场景里几乎是标准答案。3. Gale-Shapley 算法手撕全过程3.1 算法核心思路求婚-拒绝循环Gale-Shapley 算法的通俗版本是每个男生都向自己心里最喜欢的女生表白女生如果暂时没有更好的选择就先收下但如果后来有一个她更喜欢的人出现她就会甩掉当前男生换成新人被甩的男生只好在偏好列表里继续往下找下一个目标重复这个过程直到所有男生都找到对象为止。这里面最关键的是“循环”的设计。我习惯用队列来维护还没有完成配对的男生每次从队列头部取一个男生让他按自己的偏好列表依次去试探。如果他当前试探的女生还是单身直接配对成功如果女生已经名花有主那就比较现任男生和这个新男生在女生心里的排名谁靠前留下谁靠后的那个重新入队。这里有个细节男生被拒绝后不能重复试探同一个女生所以需要维护一个指针数组 next[i]记录每个男生下一次该尝试的女生下标。3.2 代码实现从伪代码到可运行 Python下面这份代码是我后来在电脑上反复调试过的版本可以直接跑也加了详细注释。用 Python 写这个算法很自然因为队列和数组操作都比较直观。核心函数有两个一个是执行匹配的 build_matches另一个是校验稳定性的 is_stable。匹配函数返回两个数组wife 表示每个男生匹配到的女生编号husband 表示每个女生匹配到的男生编号。这两个数组是互相对偶的后续校验会用到。from collections import deque def build_matches(prefer_men, prefer_women): :param prefer_men: 二维数组prefer_men[i] 表示男生 i 对女生的偏好排名从高到低 :param prefer_women: 二维数组prefer_women[j] 表示女生 j 对男生的偏好排名从高到低 :return: (wife, husband) n len(prefer_men) # wife[i] 表示男生 i 匹配到的女生编号初始为 -1 wife [-1] * n # husband[j] 表示女生 j 匹配到的男生编号初始为 -1 husband [-1] * n # 每个男生下一次要向哪个女生表白 next_choice [0] * n # 男生自己心中的排名映射rank_men[i][girl] 男生 i 心中女生 girl 的名次越小越好 rank_men [[0] * n for _ in range(n)] for i in range(n): for idx, girl in enumerate(prefer_men[i]): rank_men[i][girl] idx # 女生心中的排名映射rank_women[j][boy] 女生 j 心中男生 boy 的名次 rank_women [[0] * n for _ in range(n)] for j in range(n): for idx, boy in enumerate(prefer_women[j]): rank_women[j][boy] idx free_men deque(range(n)) while free_men: man free_men.popleft() girl prefer_men[man][next_choice[man]] next_choice[man] 1 if husband[girl] -1: wife[man] girl husband[girl] man else: current_man husband[girl] if rank_women[girl][man] rank_women[girl][current_man]: # 新人更被喜欢旧人被甩 wife[man] girl husband[girl] man free_men.append(current_man) else: # 旧人还是更被喜欢新人继续单身 free_men.append(man) return wife, husband def is_stable(wife, husband, prefer_men, prefer_women): n len(wife) rank_men [[0] * n for _ in range(n)] for i in range(n): for idx, girl in enumerate(prefer_men[i]): rank_men[i][girl] idx rank_women [[0] * n for _ in range(n)] for j in range(n): for idx, boy in enumerate(prefer_women[j]): rank_women[j][boy] idx for man in range(n): current_wife wife[man] # 对于每一位女生检查是否存在不稳定对 for girl in range(n): if girl current_wife: continue # 男生更喜欢这个女生同时这个女生也更喜欢这个男生 if rank_men[man][girl] rank_men[man][current_wife] and \ rank_women[girl][man] rank_women[girl][husband[girl]]: return False return True这段代码我测试过很多组随机数据稳定校验全部通过。如果你在复试现场不一定要写出完整实现但伪代码里的“队列 指针数组 双排名映射”这三个东西一定要讲到因为它们是整个算法的骨架。3.3 复杂度分析为什么是 O(n^2)很多人记复杂度只记结论在这里我用最直白的方式推一遍。每个男生最多只会向每个女生表白一次所以每个男生最多完成 n 次尝试n 个男生合起来最多 n^2 次“求婚”操作。每次操作中对女生现任男友的比较是 O(1) 的因为我们已经提前用 rank_women 数组存好排名了。队列的进出操作也是 O(1)。因此总体时间复杂度就是 O(n^2)。空间方面存储两个偏好矩阵本身就是 O(n^2)rank 映射也是 O(n^2)其余辅助数组都是 O(n)所以空间复杂度 O(n^2)。面试官如果接着问“能不能优化空间”你可以说可以把偏好矩阵和 rank 合并存储减少一个二维数组的占用但整体量级不变。这种追加问题考察的是工程敏感度我当时就是因为提前想过这一步才没有被问住。3.4 一个容易混淆的理论点主动方最优、被动方最差Gale-Shapley 有个非常反直觉的性质在同一组偏好数据下主动求婚的一方会得到所有稳定匹配中对自己最好的结果而被动接受的一方会得到所有稳定匹配中对自己最差的结果。注意这是在不同稳定匹配之间的比较并不是说主动方得到的一定是全局个人最优。全局最优当然人人都想要但稳定性的约束会限制这种可能性。我在复试时被追问过“是不是男生主动就一定让每个男生都最爽”。我当时的回答是不是算法只是保证男生整体上拿到了“他们能拿到的稳定结果里的最优解”但某个具体男生可能更喜欢另一种稳定匹配里的伴侣。女生那头同理算法给她们的结果是“最差稳定结果”有的女生可能有怨气但整体不会有人互相满意到要私奔。面试官点了点头这个点答对很关键。4. 复试现场的演示与实操经验4.1 在白板上画 3x3 实例我建议任何人在面对这种题时都不要一开始就写大段代码而是先画一个小例子。我用的是三男三女给了两组偏好表。男生0喜欢女生0、1、2男生1喜欢女生2、0、1男生2喜欢女生1、2、0女生0喜欢男生1、2、0女生1喜欢男生2、0、1女生2喜欢男生0、1、2。这个例子我特意设计成每个人都有不同的偏好顺序这样能完整展示算法循环的每个分支。第一轮男生0表白女生0配对成功男生1表白女生2配对成功男生2表白女生1配对成功。看起来一轮就结束了但这个匹配不稳定因为男生0更喜欢女生1而女生1也更喜欢男生0。这时候算法并不会停止但因为初始时所有男生都有伴了循环就会正常退出。这里就要注意了Gale-Shapley 算法必须处理“所有人都有伴”和“还有人没伴”两种情况。如果所有人第一轮就都有伴直接结束如果还有单身汉说明有人被甩了需要继续循环。所以我用队列判断就要谨慎不能简单数匹配数。为了完整演示“被甩再追”我又换了一个例子女生0的偏好里男生2比男生0排名更靠前。这样男生0表白女生0后后来男生2也表白女生0女生0就会选择男生2把男生0甩了。男生0再去表白女生1。这个过程在白板上画两三轮面试官就能看到算法在动态调整。4.2 代码实现时容易踩的坑第一个坑是“男生被拒绝后没有把当前选择往后移”。我一开始写的时候next_choice 更新放在判断之前结果男生被拒绝后再次入队列下次还是尝试同一个女生形成死循环。正确做法是每次尝试完一个女生立刻让 next_choice 加一不管表白成功还是失败。第二个坑是“男生已经有对象了却还留在自由队列里”。在算法里只有当前没有对象的男生才需要入队。一旦配对成功就要从队列里移除。但这里有个特殊情况男生被甩之后要重新入队。如果你的代码逻辑是“从队列取出来的时候才维护状态”就要小心重复入队导致队列里出现同一个男生两次。我当时在调试时遇到过这种情况最后用字典记录每个男生是否在队列里才排查清楚。第三个坑是“数据处理时下标没对齐”。很多适合复试题给的偏好列表是从 1 开始的但代码里用 0-index转换不到位就会出现莫名其妙的“女生0不存在”错误。我建议所有参与复试模拟训练的人都明确规定统一用 0-index然后在读入数据时直接减一。4.3 和面试官的对答技巧如果面试官问“你为什么用队列而不是栈”你要知道他考察的是算法特性Gale-Shapley 对处理顺序并不敏感用队列只是实现方便。你可以回答“队列保证每轮都处理所有当前单身的男生但其实换成栈也不影响最终稳定匹配结果”。这种回答能展示你对算法本质的理解而不是死记模板。如果面试官问“如果偏好列表里有并列名次怎么办”你要知道经典算法假设没有并列每个排名都是严格全序。如果有并列问题就变成了允许平局的稳定婚配问题情况复杂得多。你可以大方承认经典版本假设严格排序并列情况可以另开讨论不需要现场硬答。诚实比瞎编更安全。5. 情书问题背后的应用价值远不止复试5.1 学生志愿分配与平台派单稳定匹配算法在现代系统里到处都在用。比如高校里的宿舍分配、双选会岗位分配、导师与学生互选本质上都是“双方都有偏好需要稳定配对”的场景。复试里这题叫“情书问题”换到真实系统里就是几千个学生和几千个导师的双向选择。某高校的某实验室就用过类似方案来做导师双选核心就是偏好排序加稳定匹配。至于具体是哪所学校我就不提了反正思路完全一样。平台派单场景也类似司机和乘客互评偏好、骑手和订单之间的匹配。不过真实场景里通常还叠加了位置、时效、价格等因素纯稳定匹配只作为基础框架上边还得加约束优化。所以复试里只要你能把“情书问题”和“匹配系统”联系起来就已经比大多数只会背算法的考生强很多。5.2 双向选择效率的量化提升我为什么说稳定匹配能让系统变好举个简单例子如果不做任何匹配策略直接用先到先得很可能出现“一个差配对”卡住整个系统的情况。比如导师 A 和导师 B 都想要学生 X学生 X 却想去没名额的导师 C最后系统为了满足 X 就得打乱一堆已配对的组合。用稳定匹配算法所有“互相满意到可以换”的组合都不会存在省去了大量后续调度成本。这在工程里有个实际收益减少返工。你做导师双选系统时最怕的就是匹配结果公布后有人申诉“我想换导师”那个过程非常消耗人力。稳定匹配虽然不能保证所有人都满意但能保证没有人组合出“互相更满意”的配对申诉量会大幅下降。5.3 变体问题当人数不对称时怎么办复试题目通常固定男女各 n 个但实际应用里两边人数很难相等。我来分享一个常用的处理思路把人数少的一方保持不变人数多的一方模拟为“所有人都可以单身”。具体做法是把多出来的那一侧加一个“虚拟对象”任何人和虚拟对象匹配都意味着单身。这样就把不对称问题转化为标准 n x n 匹配问题。但是要注意加了虚拟对象后稳定性的定义也要改虚拟对象对所有真实对象都没有兴趣真实对象对虚拟对象也没有偏好相当于他们只是“没有匹配结果”。这个变体非常常见。我见过有人直接用原算法硬跑不对称数据结果在下标访问时直接崩溃。所以如果面试官追问“如果男生比女生多算法怎么改”你能答出虚拟对象方案基本就稳了。5.4 情书问题在求职匹配中的应用思路秋招春招里的“人才池 岗位池”也可以套用稳定匹配模型。候选人会投简历对不同岗位有偏好排序HR 也会按简历筛人对候选人有优先级排序。往年的痛点是一人手上多个 Offer接了又鸽掉导致岗位空着招不满。如果引入稳定匹配机制理论上可以显著减少此类“鸽中鸽”现象。当然现实中人的偏好会变Offer 信噪比又低所以真正全自动化的匹配系统并不多。多数企业只是把这种算法作为决策辅助我先给出一份稳定匹配名单再由 HR 人工微调。这样既发挥算法效率又保留人的判断。如果你在做这类系统我的建议是不要一上来就追求全局自动匹配。先做“候选名单排序”再用稳定匹配算法辅助决策上线观察几轮数据后再逐步增加自动化程度。这个思路放到导师双选、宿舍分配、选修课抢课系统里都一样适用。6. 日常训练中我常用的一些案例与工具6.1 随机生成偏好数据来验证算法自己练这道题时如果只用一个手写案例验证不了算法的稳定性。我写了一个小脚本随机生成 n 个男生和 n 个女生的偏好排列然后跑匹配并调用 is_stable 校验。每次生成不同的随机种子能覆盖很多边界情况比如某个女生是所有男生的第一志愿或者某个男生的偏好列表和另一个人的偏好完全相同。import random def generate_case(n): men_pref [] women_pref [] for _ in range(n): p list(range(n)) random.shuffle(p) men_pref.append(p) for _ in range(n): p list(range(n)) random.shuffle(p) women_pref.append(p) return men_pref, women_pref这个生成器写起来很简单但对训练特别有用。每次跑完匹配我都会打印 wife、husband 和稳定校验结果。如果校验结果是 False就回溯那组随机种子定位是算法 bug 还是数据问题。用这种“随机生成 自动校验”的方式训练比反复默写代码有效得多。6.2 纸质推导训练法面试前我还做过一种训练不给电脑纯用纸笔推 5x5 甚至 6x6 的随机案例。这个训练看起来很笨实际上非常锻炼对算法流程的敏感度。推几组之后你会发现自己不需要再逐行模拟代码看到某个先生的偏好列表就能预判他会不会被甩看到某个女生的现有男友很快就能判断她要不要换人。这种“人脑模拟”能力在现场特别宝贵因为面试官有时候会中途改偏好顺序或者故意制造一个复杂的反例你要是只能照着代码逻辑想会很被动。我用这个方法练了一周后来复试现场看到一个 4x4 的反例时几乎是秒反应出结果。面试官还问了一句“你怎么这么快”我说我用这个案例手推了无数遍太熟了。虽然这个回答有点实在过头但反而让面试官觉得我是真练过。6.3 可视化调试的必要性给代码加上简单的打印日志也非常重要。我的调试方式是在每次配对或拆对时打印“男生 X 向女生 Y 表白当前男友 Z比较结果是分手/继续”。这样能把整个循环过程完整呈现。配对问题最难调的就是状态不一致常常是 wife 数组变了husband 数组没同步变于是稳定校验直接报错。打日志能第一时间定位是哪个男生被落了单哪个女生的记录没有更新。用打印日志的方式跑一个 5 个男生的案例屏幕上大概会输出 10 到 20 行过程记录。看起来乱但配合断点看代码你会发现自己对算法的直观理解突然上升了一个台阶。这个方法不是某本算法书教的是我调了一晚上 bug 后悟出来的特别值得分享。7. 情书问题让我明白的道理7.1 算法题不是背出来的准备复试时我曾经试图把所有常见算法都背一遍但真到了情书问题这种“包装过的陌生题”背过的模板反而成了干扰。因为我总想着“这题是不是应该套什么模板”结果忘了从题目本质去思考。后来我发现真正有效的准备方式不是背模板而是做“换皮训练”同一个稳定婚姻问题今天用“情书”来包装明天用“导师双选”来包装后天用“宿舍分配”来包装。每次都能在五分钟内识别出底层模型这才是复试要的能力。情书问题就是典型的例子看起来像是在讲恋爱实际是稳定的心仪对象匹配。如果只看表面文字很容易慌如果抓住了“偏好列表 稳定条件”这个骨架无论题干怎么变都能从容面对。7.2 主动与被动的关系映射到生活里写情书的人对应主动求婚方被表白的人对应被动接受方这个关系映射到生活中的所有双边匹配。算法本身是客观的但设计算法时的博弈立场是主观的。复试里默认男生主动只是很多教材的惯例实际工程里你可以让更紧缺的一方主动或者让需要保留更多选择权的一方主动。这一点在系统设计时特别重要。比如导师双选制度里如果导师是稀缺资源那么让导师“主动”匹配得到的稳定结果就对导师更有利如果学生稀缺就让学生“主动”。这实际上不是算法偏好而是策略选择。想设计一个让两边都能接受的系统恐怕还得在稳定匹配的约束之外再加一些补偿机制比如允许少量排序靠后的学生和导师有二次协商的机会。7.3 关于复试的一点个人建议如果你正为复试焦虑我的体会是算法题有套路但套路的根基永远是理解。情书问题能流行起来恰恰是因为它不靠死记硬背只要你把稳定婚姻的内在逻辑吃透了遇到任何变体都能迎刃而解。在白板上写不出完整代码没关系把思路讲清楚、边界说明白、复杂度算准确就已经能证明你的水平了。最后分享一个我自己的习惯每次看完一道算法题都问自己三个问题。第一这个问题能不能拆成更简单的模型。第二数据规模如果很大内存和时间的瓶颈在哪。第三如果数据出现极端情况算法会不会退化。情书问题三个问题都问一遍之后你会发现自己对它的理解比背十遍代码都深。这是我踩过很多坑之后才总结出的方法后面练其他算法题我也一直在用。备考的各位不妨试试看。