关于java:程序员求助腾讯面试题64匹马8个跑道多少轮选出最快的四匹

51次阅读

共计 1926 个字符,预计需要花费 5 分钟才能阅读完成。

昨天,有网友私信我,说去阿里面试,彻底的被打击到了。问了为什么网上大量应用 ThreadLocal 的源码都会加上 private static?他被难住了,因为他素来都没有思考过这个问题。独一无二,明天笔者又发现有网友吐槽了一道腾讯的面试题,咱们一起来看看。

程序员求助:腾讯面试题,64 匹马 8 个跑道,多少轮选出最快的四匹
一名程序员发帖求助到。二面腾讯,其中一个算法题:64 匹马,8 个跑道,选出最快的四匹马。起码跑几个回合可能选出最快的四匹马。这样的求助也是霎时引来了网友的围观与谈论,咱们先来看看网友们都是怎么解答这道题,一起来看看。

有网友就说到。南大的算法课题目之一,腾讯这么没创造力吗?又是我二面题目。能够计时吗,计时的话就 8 场。

有网友就答复到。随机分八组较量,这是 8 场了,把每组第一名拿进去跑一场,每次把第一名选出来,把所在组的后一名拿进去补位,跟剩下的跑,这样跑 4 次就 ok 了。总共 12 次。不晓得对不对

也有网友剖析到。64 分 8 组比 8 场,淘汰每组后四名;8 个第一比 1 场,淘汰后四名所在组;残余 16 匹马中有一个确定冠军,除此之外还剩第一名所在组后三位,第二名所在组前三位,第三名所在组前两位,第四名所在组第一位,共计 9 匹马未定,随机选 8 匹赛 1 场,取前三名;前三名 + 上一场漏掉的马赛 1 场,再取前三名加上固定冠军就是最快的四匹马。是这个思路不?

更多的网友退出了探讨。最小堆排序,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 场

也有比拟理智的网友剖析到。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 轮选出前四。因题目问“起码”,故第十轮不思考其余可能呈现的后果。

蠢才答复:

=======

看了这么多网友的回复,其实答对的网友也是不少的。看似一个简略的问题,的确考的也是十分全面,不晓得各位网友对于腾讯这样的面试题有没有更清晰的答案,欢送留言与笔者一起探讨。

举荐浏览:

对于【暴力递归算法】你所不晓得的思路

=

彩蛋

往年最新的三道面试题你能答上来吗?

为了这三道面试题的最优解,曾经专门录制了一整集面试视频,有须要的敌人能够关注公众号【Java 斗帝】回复【666】收费获取

看完三件事❤️

========

如果你感觉这篇内容对你还蛮有帮忙,我想邀请你帮我三个小忙:

点赞,转发,有你们的『点赞和评论』,才是我发明的能源。

关注公众号『Java 斗帝』,不定期分享原创常识。

同时能够期待后续文章 ing????

正文完
 0