写点什么

百度、小红书三面,均遇“赛马”问题

用户头像
执鸢者
关注
发布于: 2021 年 04 月 18 日
百度、小红书三面,均遇“赛马”问题

关注公众号“执鸢者”,回复“资料”获取 500G 资料(各“兵种”均有),还有专业交流群等你一起来潇洒。(哈哈)


适逢金三银四的跳槽的黄金时段,看到很多小伙伴都在拼命的找工作、找实习,自己曾经的面试经历也浮现在眼前,特别是一道在百度和小红书三面时遇到的“赛马”问题,既然很多公司都爱问这个问题,那么是时候将该问题储备到自己的面筋小题库中了。

一、题目

一个赛场中有 5 条赛道,现在有 25 匹马,在没有定时器的前提下最少跑多少圈可以角逐出前三名?

二、头脑风暴

刚遇到这个问题的时候,不知道小伙伴们是什么想法,反正瞬间属于懵逼状态,懵逼过后就进入了分析问题的环节。

2.1 全部马均需跑一次

不管怎样,25 匹马肯定都需要上跑道跑一下(是骡子是马,拉出来溜溜),所以先将马匹分成 5 组(25 / 5 = 5;其中 25 指马匹数、5 指赛道数,获取到的就是组数),各组标号分别是 A、B、C、D、E,最终全部 5 组比赛之后的结果如下表所示:



经过本轮比赛之后,已经跑了五圈,经过这五圈之后能够获取到的信息就是每组都角逐出了第一名(A1、B1、C1、D1、E1),但是到底谁是前三名还不能确定,接下来我们所能做的是继续进行比赛,但是让谁进行比呢?这个时候肯定不是随便选,随便选的话我们前面五圈做的铺垫就没有意义了,所以此时将每组第一名赛一圈再说,至少能够角逐出 25 匹马中谁是最快的那个仔。

2.2 每组第一名赛一次

下面将每组第一名的马匹(A1、B1、C1、D1、E1)牵出来进行比赛,比赛结果如下所示:



经过本轮比赛之后,已经跑了六圈,在第六圈结束之后,我们获取的信息就变的丰富很多,很多老铁肯定会说了,经过第六圈之后我们不就知道了第一名是谁了,除了这个还有啥有用信息,这个时候才是最最重点的位置(敲黑板),下面我直接罗列出来能够获取到的信息:


  1. 第一名是 A1

  2. 每组第一名的顺序也确定了,速度顺序是:B1 > C1 > D1 > E1

  3. A2-A5 的速度有可能比其它组的都快;B2-B5 的速度有可能比 C、D、E 组的都快;C2-C5 的速度有可能比 D、E 组的都快;D2-D5 的速度有可能比 E 组的都快。


通过获取到的信息进一步用咱们聪明的脑袋加工一下,到底谁有可能获取到 2、3 名呢?



上述图中直接标出了可能获取 2、3 名的马匹,但是为什么会是这些马匹呢?下面一起分析一下。


  1. 若 A2、A3 的速度比其它组的都快,则肯定是 A2、A3 分别包揽 2、3 名;

  2. 若 A2、A3 的速度比一定比其它组的速度快,则 B2 就有可能竞争 2、3 名;B2、C1 就有可能竞争第 3 名。

2.3 A2、A3、B1、B2、C1 赛一次

经过这五匹马再赛一圈之后,就已经跑了七圈,第七圈角逐出来的 2、3 名就是最终结果的 2、3 名。

2.4 结论

通过上述分析,5 条赛道,现在有 25 匹马,在没有定时器的前提下最少需要 7 圈可以角逐出前三名。

三、扩展

若现在想角逐出前 4 名最少需要多少圈?

3.1 信息分析

在赛到第七圈的时候,已经角逐出来了前三名,此时能够获取到的信息有:


  1. 前三名是谁

  2. 第七圈的第三名是谁


目前要角逐出第四名,只需要通过比第七圈里面的第三名,和总体第三名后面可能产生第三名的位置即可。

3.2 问题解答

若前三名分别是 A1、B1、C1,第七圈结果是 B1、C1、A2、A3、B2,则可能产生总体第四名的位置是 A2、C2、D1,则只需要比较三者即可跑出第四名。


3.3 结论

角逐出前 4 名至少需要跑 8 圈。

四、思考

5 条赛道,25 匹马,没有定时器的情况下角逐出前三名最少需要 7 圈,角逐出前四名最少需要 8 圈,那么角逐出前五名呢?欢迎老铁留言解答。

发布于: 2021 年 04 月 18 日阅读数: 34
用户头像

执鸢者

关注

让前端知识变的简单可依赖。 2019.09.05 加入

以脑图分享前端知识,让知识变的简单可依赖。

评论

发布
暂无评论
百度、小红书三面,均遇“赛马”问题