面试问题浓缩总结 面试问题浓缩总结
  • Go
  • Java
  • C/C++
  • JavaScript/HTML
  • MySQL
  • Redis
  • MongoDB
  • 操作系统
  • 计算机网络
  • spring全家桶
  • mybatis
  • 中间件
  • 软件相关
  • 系统相关
  • 算法
  • 数据结构
  • 设计模式
  • CMU硕士经典100题
  • 剑指offer
  • 重点手撕代码
  • 程序员面试金典
  • 3月
  • 4月
  • 智力题
  • 业务问题
  • 一些技术
  • 安全相关
APP下载 (opens new window)
GitHub (opens new window)
  • Go
  • Java
  • C/C++
  • JavaScript/HTML
  • MySQL
  • Redis
  • MongoDB
  • 操作系统
  • 计算机网络
  • spring全家桶
  • mybatis
  • 中间件
  • 软件相关
  • 系统相关
  • 算法
  • 数据结构
  • 设计模式
  • CMU硕士经典100题
  • 剑指offer
  • 重点手撕代码
  • 程序员面试金典
  • 3月
  • 4月
  • 智力题
  • 业务问题
  • 一些技术
  • 安全相关
APP下载 (opens new window)
GitHub (opens new window)
  • 智力题

    • 世界500强的智力题
    • 面试常问
    • 业务问题

    • 一些技术

    • 安全相关

    • 其他
    • 智力题
    小游
    2021-04-10

    面试常问

    # 64匹马,8个赛道,找出跑得最快的4匹马

    全部马分为8组,每组8匹,每组各跑一次,然后淘汰掉每组的后四名,如下图(需要比赛8场)

    image-20210410171912299

    第一步 因为我们只需要找出最快的四匹马,所以我们在这8组里面每组第一名进行比赛,这样我们就可以淘汰最后四名所在组的所有马(因为如果第一名都比不过的话,其他的也不可能比过,因为我们要找最快的四匹)

    image-20210410183452781

    第二步 当然,如果我们想找第一名的话其实就已经找到了(下图蓝色区域),不过我们要找最快的4匹。所以我们还需要在比,而其他可能跑得最快的三匹马只可能是下图中的黄色区域了(A2,A3,A4,B1,B2,B3,C1,C2,D1,共9匹马)

    这里简单解释一下为什么是9块,我们就拿D1来说,因为D1是第4名,所以D1所在的队伍肯定只有D1,然后C1也是同理,如果C1是快马的话,那么A1,B1,肯定也是,所以最差也有C1,C2这两个是快马

    image-20210410183615496

    第三步 只要从上面的9匹马中找出跑得最快的三匹马就可以了,但是现在只要8个跑道,怎么办?那就随机选出8匹马进行一次比赛吧(需要比赛一场)

    第四步 上面比赛完,选出了前三名,但是9匹马中还有一匹马没跑呢,它可能是一个潜力股啊,那就和前三名比一比吧,这四匹马比一场,选出前三名。最后加上总冠军,跑得最快的四匹马诞生了!!!(需要一场比赛)

    所以一共需要比 8 + 1 + 1 + 1 = 11 次

    最少10场,第三步:除A2外,剩下的8匹比一场,如果A3跑了第一,那么直接确定前四。否则需要多比一场

    因为如果A3是第一名,那么A1,A2是第一和第二A3是第三,后面的就是第4了

    # 海盗分金币的问题

    有五个理性的海盗 (opens new window),A, B, C, D和E,找到了100个金币,需要想办法分配金币。

    海盗们有严格的等级制度:A比B职位高,B比C高,C比D高,D比E高。

    海盗世界的分配原则是:等级最高的海盗提出一种分配方案。所有的海盗投票决定是否接受分配,包括提议人。并且在票数相同的情况下,提议人有决定权 (opens new window)。如果提议通过,那么海盗们按照提议分配金币。如果没有通过,那么提议人将被扔出船外,然后由下一个最高职位的海盗提出新的分配方案。

    如何分配

    直觉上认为,A海盗会给自己分配很少,以避免被扔出船外。然而这和理论结果相差甚远。

    让我们反过来看:如果只剩下D和E,D给自己100个金币,给E 0个。因为D有决定权,所以分配达成。

    如果剩下三个人(C,D和E),C知道D下轮会给E 0个金币,所以C这轮给E 1个金币,让E支持自己以使得提议通过。因此如果剩下三个人,结果是C:99,D:0,E:1。

    如果B, C, D 和 E 剩下, B 知道上述结果。所以为了避免被扔出去,他只需要给D 1个金币,因为他有决定权,只需要D的支持就足够了。因此他会提议 B:99, C:0, D:1,E:0。有人可能想到提议B:99, C:0, D:0,E:1,因为E知道即使把B扔出去,也不会得到更多了。但由于海盗会优先把别人扔出去,所以E会选择杀死B,然后仍然可以从C的提议中得到相同金币。(若要让E同意他,就至少要给他2个金币才行,这样并不划算,因为这样B自己只能得到98金币,所以不用浪费金币给E)

    假设A知道所有的一切,他就能选择让C和E来支持他,提议变成:

    • A: 98金币
    • B: 0金币
    • C: 1金币
    • D: 0金币
    • E: 1金币

    同样的 A:98,B:0,C:0,D:1,E:1 或者其他的提议都不是最好的,因为D会选择把A扔出去,然后从B那里得到相同的金币。(若要让D同意他,就至少要给他2个金币才行,这样并不划算,因为这样A自己只能得到97金币,所以不用浪费金币给D)

    海盗博弈 - 维基百科,自由的百科全书 (wikipedia.org) (opens new window)

    # 老鼠试毒问题

    问题一

    有16瓶水,其中只有一瓶水有毒,小白鼠喝一滴之后一小时会死。请问最少用() 只小白鼠,在1小时内一定可以找出至少14瓶无毒的水?

    答案为 三只

    解析

    这个题目可以转换为二进制来进行理解

    将16瓶水两瓶为一组,组号标为A1-A8,三只小白鼠分别标号为b1、b2、b3。 A1,001,只让b1喝 A2,010,只让b2喝 A3,011,让b1、b2喝 A4,100,只让b3喝 A5,101,b1、b3喝 A6,110,b2、b3喝 A7,111,让b1、b2、b3喝 A8组不喝.

    如果只有b1死了,b2、b3都活着,那么有毒的水在A1组里,剩下的14瓶无毒;如果只有b2死了,b1、b3都活着,则A2组有毒;如果b1、b2死,b3活,则A3组有毒;如果只有b3死了,b1、b2都活着,则A4组有毒;如果b1、b3死,b2活,则A5有毒;如果b2、b3死,b1活,则A6有毒;如果三只全死,A7组有毒;如果三只全活,A8有毒。

    问题二

    这个题目和上个题目一样,都是转换为二进制来进行计算

    有1000瓶水,其中有一瓶有毒,小白鼠只要尝一点带毒的水24小时后就会死亡至少要多少只小白鼠才能在24小时 至少要多少只小白鼠才能在24小时鉴别出哪瓶水有毒 答案是10只

    给1000个瓶分别标上如下标签(10位长度): 0000000001 (第1瓶) 0000000010 (第2瓶) 0000000011 (第3瓶) . 1111101000 (第1000瓶) 从编号最后1位是1的所有的瓶子里面取出1滴混在一起(比如从第一瓶,第三瓶,.里分别取出一滴混在一起)并标上记号为1.给第一个小白鼠喝。 从编号倒数第2位是1的所有的瓶子里面取出1滴混在一起并标上记号为2.给第2个小白鼠喝。 从编号倒数第3位是1的所有的瓶子里面取出1滴混在一起并标上记号为3.给第3个小白鼠喝。 从编号倒数第4位是1的所有的瓶子里面取出1滴混在一起并标上记号为4.给第4个小白鼠喝。 从编号倒数第5位是1的所有的瓶子里面取出1滴混在一起并标上记号为5.给第5个小白鼠喝。 从编号倒数第6位是1的所有的瓶子里面取出1滴混在一起并标上记号为6.给第6个小白鼠喝。 以此类推。。。。 24小时过去了,过来验尸吧: 如果只有第一个小白鼠死了。即00000 00001,则第1瓶有毒。 如果只有第1,4个小白鼠死了。即00000 01001,则第9瓶有毒。

    编辑 (opens new window)
    上次更新: 2021/04/11, 21:38:22
    世界500强的智力题
    设计一个抢红包功能

    ← 世界500强的智力题 设计一个抢红包功能→

    Theme by Vdoing | Copyright © 2021-2021 小游
    • 跟随系统
    • 浅色模式
    • 深色模式
    • 阅读模式