Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >专栏 >【前端词典】有趣的大厂算法面试题

【前端词典】有趣的大厂算法面试题

作者头像
小生方勤
发布于 2019-07-18 09:12:20
发布于 2019-07-18 09:12:20
7160
举报
文章被收录于专栏:前端词典前端词典

前言

昨天看到 TingRongGao 大佬发了关于一道算法题的一篇文章,觉得着实有趣,但不知为何我看到题后首先想到的是田忌赛马。今天我也试着解释下这题,当做是一个学习的过程。

解题过程

题目:64 匹马,8 个赛道,找出前 4 名最少比多少场?(马的速度恒定不变)

直接开始

第一轮

64 匹马分 8 次在全部比完一次,然后我们可以把目标缩小到 32 匹马。

第一轮解析

1、八次比完后,我们可以将每一匹马的速度按下表排好。

2、每组比赛的后 4 名直接淘汰(小组中都无法进前四,全部中必然无法进前四);

到现在为止,已经进行了 8 次比赛

第二轮

剩下的 8 组 32 匹马选每组的第一名进行一次比赛,然后我们可以把目标缩小到 10 匹马。

第二轮解析

1、8组中第一名比完后(假设 A1 表示最快的,依次为较慢者,H1最慢),这次比赛直接影响到它们这组是否可以参加下一场的比赛,因为每组的第一都进不了前四的话那这组肯定就没有前四的马啦。

2、所以这轮比赛的后四名直接全组淘汰,剩下 16 匹马。

3、先别急着进行下一场的比赛,因为这里面还可以淘汰 6 匹马。

D 组第一名 D1 都最多只是第四名,所以 D2、D3、D4 就不需要再比了;C 组第一名 C1 最好成绩是第三名,所以只有 C2 可以冲一下第四名,C3、C4 淘汰;B 组第一名 B1 最好成绩是第二名,所以 B2、B3 还是有机会进前 4 的,B4 淘汰;A 组就运气比较好,全组都可能进前 4 。 现在只有 10 匹马的范围啦。

即剩 A1、A2、A3、A4、B1、B2、B3、C1、C2、D1 十匹马可能进前四。

到现在为止,已经进行了 9 次比赛

第三轮

A1 必定是第一名无需再比。B1 这个暂定第二的基本不需要再比,所以剩下的 A2、A3、A4、B2、B3、C1、C2、D1 这八匹马再比一次。

第三轮解析(情况有二)

1、这轮比赛如果 B2 或 C1 中二者有其一进入前三,那比赛结束,前四名已经区分出来。(这点想不明白的话你想想这个问题:跑步比赛中你跑过了第二名你是第几名)

我们知道 B1 在 BCD 三组中肯定是最快的,所以 B2 或 C1 进入前三,B1 就一定再前四。


若结果为: A2>B2>C1>C2>D1>A3>A4>B3

那么前四就是 A1、A2、B1、B2(A2、B1 的名次不知)


2、如果比赛的前三戏剧性的是 A2、A3、A4,那么我们是不清楚 A4 快还是 B1 快的,所以需要在比一场,就能找出前四。

情况一:8 + 1 + 1 = 10, 共 10 次 情况二:8 + 1 + 1 + 1 = 11,共 11 次

总结

64 匹马,8 个赛道,找出前 4 名最少需要比 10 场。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-07-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 小生方勤 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
解一道经典的腾讯算法面试题(小白也能看懂)
算法,对于一个程序员还是非常重要的,它不单单能体现你的数学思维,还能体现出一种逻辑能力,如果你要进BAT这样的大厂,请一定重视算法,它是你的必经之路。
帅地
2019/07/17
2.6K0
解一道经典的腾讯算法面试题(小白也能看懂)
解一道经典的腾讯算法面试题(小白也能看懂)
算法,对于一个程序员还是非常重要的,它不单单能体现你的数学思维,还能体现出一种逻辑能力,如果你要进BAT这样的大厂,请一定重视算法,它是你的必经之路。
用户1462769
2019/08/09
5190
解一道经典的腾讯算法面试题(小白也能看懂)
????无了,人傻了
请听题: 有64匹🐴,一共8个赛道,需要多少次比赛可以知道当中最快的4匹🐴 最近偶然看帖子看到了这么一个算法问题,我因为一直都是在写业务,对算法这块也没有太研究过,知道的也就只有什么二分查找,二叉树,冒泡排序啥的,所以看到这个题的第一反应就是递归。。。。。。。好吧,我是真滴🥬 好在原文有配图,看起来不费力,我终于是理解到了原理,故我自己记录一下加深理解。 解题思路: 先把64匹🐴分成[A, B, C, D, E, F, G, H]8组,每组8匹 image.png 每组各跑一次,可以得到每组的第一名🐴
零式的天空
2022/03/28
1990
????无了,人傻了
100匹马,4个赛道,找出跑最快的4匹马。
其实在网上也有不少该题目的文章,但是可能题目不一样,能找到的题目名为《64匹马,8个赛道,找出跑得最快的4匹马》。该题目出现在腾讯的面试题里面。
LamHo
2022/09/26
6580
c++开发面试问题(java面试app)
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/127604.html原文链接:https://javaforall.cn
全栈程序员站长
2022/07/25
1920
带答案分享-算法面试中的趣味题目
今天给大家分享一下去年校招面试过程中遇到一些比较有趣的题目,并附上我个人理解的答案,希望对大家校招有所帮助。
石晓文
2019/08/16
9340
带答案分享-算法面试中的趣味题目
计算机思维:二叉树的应用(树形选择排序)【面试题】
单淘汰的锦标赛中,选手们两两比赛,胜者晋级,败者被淘汰, 把比赛的赛程和结果对应成一个二叉树。
公众号iOS逆向
2023/09/11
2170
计算机思维:二叉树的应用(树形选择排序)【面试题】
腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹?
昨天,有网友私信我,说去阿里面试,彻底的被打击到了。问了为什么网上大量使用ThreadLocal的源码都会加上private static?他被难住了,因为他从来都没有考虑过这个问题。无独有偶,今天笔者又发现有网友吐槽了一道腾讯的面试题,我们一起来看看。
美的让人心动
2020/02/13
1.4K0
面经 | 记录秋招遇到的概率题与智力题(附答案)
概率论是计算机科学非常重要的基础学科之一,智力题是概率题的另一种形式,概率题也是在程序员求职过程中经常遇到的问题。下面稍作整理,供大家参考。
用户3946442
2022/04/11
4520
面经 | 记录秋招遇到的概率题与智力题(附答案)
面经 | 概率题与智力题(附答案)
在本篇文章中,小媛为大家整理了“算法”、”开发”面试中常见的概率题与智力题。概率论是计算机科学非常重要的基础学科之一,也是在程序员求职过程中经常遇到的问题。
用户3946442
2022/04/11
1.2K0
面经 | 概率题与智力题(附答案)
【SQL server】玩转SQL server数据库:第二章 关系数据库
表示方法:一张二维表,行对应元组,列对应属性【域】 3. 关系 定义: D1×D2×…×Dn的子集叫作在域D1,D2,…,Dn上的关系,表示为 R(D1,D2,…,Dn) R:关系名,n:关系的目或度 当n=1时,称该关系为一元关系 当n=2时,称该关系为二元关系 ... 相关概念
SarPro
2024/03/03
3120
【SQL server】玩转SQL server数据库:第二章 关系数据库
腾讯二面,我被 “赛马” 问题难住了
今天分享一道我曾经被难住了的面试题,也是一道大厂面试时经常会被问到的面试题,赛马问题。
程序员鱼皮
2021/04/18
2.8K0
数据科学 IPython 笔记本 7.9 组合数据集:连接和附加
一些最有趣的数据研究来自于不同的数据源的组合。这些操作可能涉及,从两个不同数据集的非常简单的连接,到更复杂的数据库风格的连接和合并,来正确处理数据集之间的任何重叠。Series和DataFrame是考虑到这类的操作而构建的,而 Pandas 包含的函数和方法使得这种数据整理变得快速而直接。
ApacheCN_飞龙
2022/06/03
8700
Pandas 2.2 中文官方教程和指南(十三)
写时复制将成为 pandas 3.0 的默认设置。我们建议现在就启用它以从所有改进中受益。
ApacheCN_飞龙
2024/04/25
4950
matrix3d()
用途 matrix3d 规定3D转换,使用 16 个值的 4×4 矩阵。 语法 matrix3d(a1, b1, c1, d1, a2, b2, c2, d2, a3, b3, c3, d3, a4, b4, c4, d4) 值 值 描述 a1、b1、c1、d1、a2、b2、c2、d2、a3、b3、c3、d3、d4 规定线性转换。 a4、b4、c4 规定适用的转换 例子 <div class="stage"></div> /* CSS */ .stage{ color:#fff;
Html5知典
2019/11/26
4720
【python】详解pandas库的pd.merge函数「建议收藏」
本篇详细说明merge的应用,join 和concatenate的拼接方法的与之相似。
全栈程序员站长
2022/08/11
1.6K0
这几道const和iota的面试题你能做对吗?
const 用于定义常量,定义之后不能修改,不能再次赋值,在程序运行期间不会改变。
王中阳Go
2022/10/26
2050
SSE图像算法优化系列四:图像转置的SSE优化(支持8位、24位、32位),提速4-6倍
本文介绍了如何利用SSE/AVX指令集进行CPU并行加速,以解决图像转置中存在的内存访问瓶颈问题。首先介绍了图像转置的算法和实现过程,然后通过具体示例展示了如何使用SSE/AVX指令集进行CPU并行加速,最后给出了针对不同CPU架构的优化策略。
用户1138785
2018/01/03
2.1K0
Python excel 功能扩展库 —
说明:本文档内容参考自 https://www.cnblogs.com/zeke-python-road/p/8986318.html (作者:关关雎鸠`)的文档
py3study
2020/01/17
4580
【C语言笔记】变量的初始值是?
可见,全局变量的默认初值为0。局部变量的默认是随机的,没有规律的。所以,我们在使用局部变量之前应该首先进行初始化,否则可能会出现意想不到的错误。
正念君
2019/07/01
1.9K0
推荐阅读
相关推荐
解一道经典的腾讯算法面试题(小白也能看懂)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档