腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹?-创新互联
昨天,有网友私信我,说去阿里面试,彻底的被打击到了。问了为什么网上大量使用ThreadLocal的源码都会加上
创新互联建站是一家集网站建设,竹溪企业网站建设,竹溪品牌网站建设,网站定制,竹溪网站建设报价,网络营销,网络优化,竹溪网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。private static?他被难住了,因为他从来都没有考虑过这个问题。无独有偶,今天笔者又发现有网友吐槽了一道腾
讯的面试题,我们一起来看看。
腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹?
在互联网职场论坛,一名程序员发帖求助到。二面腾讯,其中一个算法题:64匹马,8个跑道,选出最快的四匹马。
最少跑几个回合能够选出最快的四匹马。这样的求助也是瞬间引来了网友的围观与议论,我们先来看看网友们都是
怎么解答这道题,一起来看看。
腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹?
有网友就说到。南大的算法课题目之一,腾讯这么没创造力吗?又是我二面题目。可以计时吗,计时的话就8场。
有网友就回答到。随机分八组比赛,这是8场了,把每组第一名拿出来跑一场,每次把第一名选出来,把所在组的
后一名拿出来补位,跟剩下的跑,这样跑4次就ok了。总共12次。不知道对不对
也有网友分析到。64分8组比8场,淘汰每组后四名;8个第一比1场,淘汰后四名所在组;剩余16匹马中有一个确定
冠军,除此之外还剩第一名所在组后三位,第二名所在组前三位,第三名所在组前两位,第四名所在组第一位,共计
9匹马未定,随机选8匹赛1场,取前三名;前三名+上一场漏掉的马赛1场,再取前三名加上固定冠军就是最快的四匹
马。是这个思路不?
腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹?
更多的网友加入了讨论。最小堆排序,8个回合吧,64匹马每匹马跑一次,根据每匹马花的时间,取最快的四匹马。
我7年前去腾讯面实习,三面就面的这个问题。
可以计时的话8场。不计时的话,选4匹家里有椅子的送到黎总办公室,剩余60杀掉,仅需跑0场。8轮对8组马分组
排序,去除每组后四名,剩余8组*4匹。第一名跑一次淘汰后四名所在的组,剩余4组*4匹。在进行2次。每次第一
都会有一个肯定是前四。
这个题目出的,连一些基础条件都没给。1,马的发挥是恒定的,每次跑相同的距离,时间务必相同。2,能不能用
秒表计时?3,赛道长度不能长到跑死马的长度。
看了答案才懂。不断缩小检索空间,淘汰尽可能多的数。另外这题,剩9匹马时,一直以为还有更简单的。
腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹?
更多的网友参与了回答。1,分8组,每组一次跑完,决出前4名,每组的后4名淘汰,这样8个来回之后,还剩32匹
马;2,把每一组的第一名拉出来赛一回合,淘汰后4名以及他整个小组,同时排第一的组,冠军出来了,还剩3匹
马,第二组,去掉最后一名,剩3屁,第三组去掉2名剩2名,最后一组剩1名,所以9个回合下来,剩9匹马争3个名
额;3,8匹马一组,再来一回合,选前3名,这三个和剩下那个再来一次,选前3名。一共11回合,全部搞定。
最少10场(剩9匹的时候,选第一组的后3,第二组的前3,第三组的前2,如果第三组的第一这轮名次大于等于3,
那就已经分出前四了),最多11场
腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹?
也有比较理智的网友分析到。8+4+2+1,每一次比赛都需要留下来最快的4个,大数据面试里面内存不够,需要
外部排序的一个变种,信息论算一下就出来了,8个赛道一次提供A8,8的信息,a64,60。 思路对但是以我的尿性
应该还有点bug,我们组也考这道题,我觉得当年进来的时候觉得这不就是奥数么很简单,5年没有变竟然。感觉8
个回合就够了啊,每只马跑一次,用毫秒表记录下每个马跑的时间,去前四。
step one:分八组,各跑一轮,依成绩组内编号。step two:各组一号跑一轮,依成绩编号。此时共跑九轮选出最快
马。step three:此时【1】【2】马(即第一次参赛跑第一,第二次参赛跑第二的马)与最快马第一次参赛剩下的七
匹为可能的次快马。让它们八匹跑一轮。此时假如【1】【2】马在该轮比赛中跑第三。则该轮的第一第二马分别为
64匹中的亚军与季军。而【1】【2】马为所有马中第四快的马。至此10轮选出前四。因题目问“最少”,故第十轮
不考虑其他可能出现的结果。
腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹?
看了这么多网友的回复,其实答对的网友也是不少的。看似一个简单的问题,确实考的也是非常全面,不知道各位网
友对于腾讯这样的面试题有没有更清晰的答案,欢迎留言与笔者一起探讨。
原文链接:https://blog.csdn.net/qq_21118431/article/details/102925078
当前文章:腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹?-创新互联
网页地址:http://hbruida.cn/article/cejssg.html