在算法考试中布置七题有趣的问题

目录

1、25 匹马，有一条只能 5 匹马比赛的赛道，我们无法计时，只能看到马的排名，如何用最短的次数找出跑的最快的 5 匹马？

2、一条无限长的直线，有两个机器人，两个机器人执行同一段代码，这一段代码中只有几条语句：right 代表向右走，left 代表向左走，if arrived else 代表另一个机器人是否走过这个地方。goto 代表代码的跳转，请写一段代码确保两个机器人能够相遇。

3、海量数据如何求中位数？（数据无法放入内存，只需考虑空间复杂度，不需要考虑时间复杂度）

4、信息流采样，有 n 份数据，但是 n 的长度并不知道。设计一个采样算法，使得每份被选择的概率是相同的。

5、n 个 [0,n) 的数，求每个数的出现次数（不能开辟额外空间）

6、三色旗问题

7、 已知有个 rand7() 的函数，返回 1 到 7 随机自然数，怎样利用这个 rand7() 构造 rand10()，随机 1~10。

---

1、25 匹马，有一条只能 5 匹马比赛的赛道，我们无法计时，只能看到马的排名，如何用最短的次数找出跑的最快的 5 匹马？

核心结论：在最优策略下，最少需要 7 次比赛；而在最坏情况下，最多需要 10 次比赛。

为了系统化地解决这个排序问题，我们首先构建一个逻辑矩阵，将 25 匹马划分为 5 个小组，每组 5 匹。这种