腾讯二面，我被 “赛马” 问题难住了
很难一次答对的经典面试题，处处是坑
大家好，我是鱼皮。
今天分享一道我曾经被难住了的面试题，也是一道大厂面试时经常会被问到的面试题，赛马问题。
题目其实不难，但是第一次被问到时，稍有不慎，就会答错。所以，一起来学习下吧！
问题
有 64 匹马 赛跑，没有任何秒表之类的计时工具，跑道每次只允许 8 匹马 同时比，问 最少 需要比赛几场才能够选出跑的最快的 前 4 名？
题目描述就这么多，大家可以先思考一下，然后在投票中给出答案吧~
下面公布解题思路和答案。
解题思路
这道题目坑点很多，题目中任何一个数字的改动都会影响到最终结果，因此一定要明确题目上的关键数字。
网上也有很多题目的变种，比如 36 匹马 6 个跑道找前三名，但思路都是一致的，下面我们模拟一下比赛全程。
第一轮
首先，跑道最多允许 8 匹马同时比，那我们一定要最大程度地利用资源，每场比赛都要上满 8 匹马。
所以第一轮最简单，无脑 将 64 匹马分为 8 组，每组 8 匹马比一场 就好了，共计 8 场比赛。
| 组号 | 参赛选手 |
|---|---|
| 组 1 | 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴 |
| 组 2 | 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴 |
| 组 3 | 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴 |
| 组 4 | 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴 |
| 组 5 | 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴 |
| 组 6 | 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴 |
| 组 7 | 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴 |
| 组 8 | 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴 |
本轮比赛之后，由于题目要求选出前 4 名，因此，每组比赛第 4 名之后的马可以直接淘汰，还剩 32 匹马。
| 组号 | 参赛选手（🐎 = 组内冠军） |
|---|---|
| 组 1 | 🐎 🐴 🐴 🐴 |
| 组 2 | 🐎 🐴 🐴 🐴 |
| 组 3 | 🐎 🐴 🐴 🐴 |
| 组 4 | 🐎 🐴 🐴 🐴 |
| 组 5 | 🐎 🐴 🐴 🐴 |
| 组 6 | 🐎 🐴 🐴 🐴 |
| 组 7 | 🐎 🐴 🐴 🐴 |
| 组 8 | 🐎 🐴 🐴 🐴 |
第二轮
第二轮开始，我们必须精打细算了。
最简单的方式是将剩下的 32 匹马直接分为 4 组去比赛，但其实利用上一轮的信息，我们可以有更好的方法。
让上轮比赛中，每组第 1 名一起比赛 1 场，然后按照本轮比赛结果，选出前 4 组。
赛场：🐎 🐎 🐎 🐎 🐎 🐎 🐎 🐎
比赛结果：
| 组号 | 参赛选手（🐎 = 组内冠军） |
|---|---|
| 组 1 | 🐎 🐴 🐴 🐴 |
| 组 2 | 🐎 🐴 🐴 🐴 |
| 组 3 | 🐎 🐴 🐴 🐴 |
| 组 4 | 🐎 🐴 🐴 🐴 |
| 组 5 | 🐎 🐴 🐴 🐴 |
这么操作的原因是：如果某个组的第一名都进不了前 4，那这个组剩下的马肯定也进不了前 4，直接整组淘汰即可。
截止到目前，还剩下 16 匹马，那这一轮淘汰到这里就结束了么？
其实并没有，以这轮比赛排名第四的马所在的组为例，这个组的冠军最高也才第四名，那么这个组其他的马也是可以被淘汰的。同理，可以淘汰更多的马，剩余 10 匹。
| 组号 | 参赛选手（🐎 = 组内冠军） |
|---|---|
| 组 1 | 🐎 🐴 🐴 🐴 |
| 组 2 | 🐎 🐴 🐴 🐴 |
| 组 3 | 🐎 🐴 🐴 🐴 |
| 组 4 | 🐎 🐴 🐴 🐴 |
现在场上还有 10 匹马，看似胜利近在咫尺，但其实，接下来才是关键！
第三轮
接下来我们的目标是从 10 匹马中选出前 4 名，但一场比赛只能容纳 8 匹马，那好像至少还得比两场。
一步步来吧，先选 8 匹马比一场呗，问题是选哪 8 匹马呢？
不知道大家有没有发现，在无意中，冠军已经产生了，那就是组内组外都未尝败绩的那匹马，强中之强！
| 组号 | 参赛选手（🐎 = 组内冠军） |
|---|---|
| 组 1 | 🏆 🐴 🐴 🐴 |
| 组 2 | 🐎 🐴 🐴 |
| 组 3 | 🐎 🐴 |
| 组 4 | 🐎 |
因此，它不用再比了，目标变成，从剩余 9 匹马中选出第 2 - 4 名。
让我们任意选 8 匹马先比一场吧，选出前 3 名。
| 组号 | 参赛选手（🐎 = 组内冠军） |
|---|---|
| 组 1 | 🏆 [ 🐴 🐴 🐴 ] 出战 |
| 组 2 | [ 🐎 🐴 🐴 ] 出战 |
| 组 3 | [ 🐎 🐴 ] 出战 |
| 组 4 | 🦓（未参与比赛的马） |
那么最后一轮，还需要让上轮没比的马与前 3 名比 1 场，万一人家是黑马呢？
赛场：🐎 🐴 🐴 🦓
至此，答案出来了，最少需要 8 + 1 + 1 + 1 = 11 场。
然而，这是一个错误答案！
其实，还有更优解！
在还剩 9 匹马的时候，如果不任选 8 匹马比赛，而是先移除组 2 的冠军，让剩下 8 匹马赛一场。
如果这场比赛中，组 3 的冠军拿了第一，那么由于之前已经证明了组 2 的冠军强于组 3 的冠军，则前 4 名已经确定，只需要比 10 场。如果它不是第一，那么还是要多比一场了。
因此正确答案是，最少需要 10 场，你做对了么？
最后，为什么这道题目会出现在程序员面试中呢？聪明的你一定发现了，上述的赛马问题本质上是一个 TopN（取前几名）问题，可以通过分治的方式解决，是一种经典的算法思维。如果是在分布式系统中，则体现了 并行计算 的优势，可以利用资源（比如有 8 个跑道）对各个组同时计算，从而提高运算效率。此外，利用已有的数据结果也是非常重要的。
祝大家周末愉快，学到的话别忘了帮鱼皮点个 赞 + 在看 支持下吧！❤️
往期推荐