本文主要是介绍百度、小红书三面,均遇“赛马”问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
适逢金三银四的跳槽的黄金时段,看到很多小伙伴都在拼命的找工作、找实习,自己曾经的面试经历也浮现在眼前,特别是一道在百度和小红书三面时遇到的“赛马”问题,既然很多公司都爱问这个问题,那么是时候将该问题储备到自己的面筋小题库中了。
一、题目
一个赛场中有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)牵出来进行比赛,比赛结果如下所示:
经过本轮比赛之后,已经跑了六圈,在第六圈结束之后,我们获取的信息就变的丰富很多,很多老铁肯定会说了,经过第六圈之后我们不就知道了第一名是谁了,除了这个还有啥有用信息,这个时候才是最最重点的位置(敲黑板),下面我直接罗列出来能够获取到的信息:
第一名是A1
每组第一名的顺序也确定了,速度顺序是:B1 > C1 > D1 > E1
A2-A5的速度有可能比其它组的都快;B2-B5的速度有可能比C、D、E组的都快;C2-C5的速度有可能比D、E组的都快;D2-D5的速度有可能比E组的都快。
通过获取到的信息进一步用咱们聪明的脑袋加工一下,到底谁有可能获取到2、3名呢?
上述图中直接标出了可能获取2、3名的马匹,但是为什么会是这些马匹呢?下面一起分析一下。
若A2、A3的速度比其它组的都快,则肯定是A2、A3分别包揽2、3名;
若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 信息分析
在赛到第七圈的时候,已经角逐出来了前三名,此时能够获取到的信息有:
前三名是谁
第七圈的第三名是谁
目前要角逐出第四名,只需要通过比第七圈里面的第三名,和总体第三名后面可能产生第三名的位置即可。
3.2 问题解答
若前三名分别是A1、B1、C1,第七圈结果是B1、C1、A2、A3、B2,则可能产生总体第四名的位置是A2、C2、D1,则只需要比较三者即可跑出第四名。
3.3 结论
角逐出前4名至少需要跑8圈。
四、思考
5条赛道,25匹马,没有定时器的情况下角逐出前三名最少需要7圈,角逐出前四名最少需要8圈,那么角逐出前五名呢?欢迎老铁留言解答。
1.如果觉得这篇文章还不错,来个分享、点赞、在看三连吧,让更多的人也看到~
2.关注公众号执鸢者,领取学习资料,定期为你推送原创深度好文
3.扫描下方添加进群,里面大佬多多,一起向他们学习
1. 图解JavaScript——代码实现(Object.create()、flat()等十四种代码原理实现不香吗?)
2. 图解JavaScript——代码实现【2】(重点是Promise、Async、发布/订阅原理实现)
3. 图解javascript——基础篇
4. 图解JavaScript——进阶篇
5. 十五张图带你彻底搞懂从URL到页面展示发生的故事
6. 图解浏览器安全(同源策略、XSS、CSRF、跨域、HTTPS、安全沙箱等串成糖葫芦)
7. 六张图带你从HTTP/0.9进化到HTTP3.0
8. (2.6w字)网络知识点灵魂拷问(上)——前端面试必问
9. (2.6w字)网络知识点灵魂拷问(下)——前端面试必问
10. 理论与API相结合理解Node中的网络通信
11. 硬核知识点——浏览器中的三类五种请求
12. 理论与实践相结合彻底理解CORS
13. 三步法解析Express源码
14. 一篇搞定前端高频手撕算法题(36道)
15. 十七张图玩转Node进程——榨干它
16. 理论与API相结合理解Node中的网络通信
17. 一文彻底搞懂前端监控
18. 前端的葵花宝典——架构
19. canvas从入门到猪头
20. 前端工程师的一大神器——puppeteer
21. 2021 年前端宝典【超三百篇】
22. 前端也要懂机器学习(上)
23. 前端也要懂机器学习(下)
24. 学架构助力前端起飞
这篇关于百度、小红书三面,均遇“赛马”问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!