百度的一道假盐面试题引发的争论,评论略叼

问题:

N个瓶子里装着一种盐,其中有一瓶是假盐,假盐的特点是溶于水后变色,其他的盐则不变色。现在给你X碗水找出那瓶假盐,则X至少为?


一楼

听完这道题后,我第一感觉X应该是log2(N)的上界。不过我当时没说出答案,我在想如何证明出来,最后一时没想出来好的简单的证明方法,也错失了这个机会。 现在证明一下,其实这个思路非常简单。 假设这N个瓶子分别标号为0、1、2、...、N - 1、N 用0表示水加入盐后不变色,1表示水加入盐后变色,则X碗水中加入盐后的状态可用X位的二进制来表示。 易知这状态有2^X种,用一种状态就可以对应假盐的瓶子号,而假盐的瓶子号只有N种。 现在关键是怎么样往水中加盐使其最后的状态就可以看出唯一的假盐的瓶号。 先看几个数的二进制表示(我从左往右记,与平时的刚好相反) 0 0000…… 1 1000…… 2 0100…… 3 1100…… 从这个几个数大家会发现用什么方法呢? 比如0号状态对应结果是0号瓶是假盐,X个碗状态都不变色,则显然0号瓶盐不加入任何碗中 1号状态对应结果是1号瓶是假盐,X个碗只有第1个碗变色,则只把1号瓶盐加入第一个碗中 2号状态对应结果是2号瓶是假盐,X个碗只有第2个碗变色,则只把2号瓶盐加入第一个碗中 3号状态对应结果是3号瓶是假盐,X个碗只有第1、2个碗变色,则只把2号瓶盐加入第一、二个碗中 现在给定一个具体的数,N=8,该如何往碗中加盐,从上面的分析中可以我们可以按如下方法加盐 X = log2(N) = 3 0 000 1 100 2 010 3 110 4 001 5 101 6 011 7 111 则0号瓶盐不加入任何碗中,1号瓶盐只加入第一个碗中,2号瓶盐只加入第二个碗中,3号瓶盐加入第一、二个碗中,4号瓶盐只加入第三个碗中,5号瓶盐加入第一、三个碗中,6号瓶盐加入第二、三个碗中 ,7号瓶盐三个碗中都加入。 即第一个碗中将加入1、3、5、7号瓶盐 第二个碗中将加入2、3、5、7号瓶盐 第三个碗中将加入4、5、6、7号瓶yan 这样由3个碗中最后的状态就可以知道唯一的假盐的瓶号了。 N为其他数,方法也跟这个一样,不再赘述~

看完这个评论,我表示大神给跪了,说的好有道理,不明觉厉。


二楼

没错,一碗就够了。 加1号瓶的盐,加2号,加3号,看加到第几号瓶变色.

感觉好有道理,我竟无言以对。


三楼

这些人, 用来面试程序员, 感觉有点过份, 因为有N种答案, 就像偻主那样, 认为他的才正确, 还算成logn碗, 好简单的事情, 不是说只有一种会变色吗? 直接每瓶顺序倒点盐进去, 水变色就是假盐了, 或者打一碗水来倒进盐瓶里, 变色的也是. 这题和工厂选空的盒子一样, 请了个科学家, 花了几个月, 精准的计算, 花了几千万, 终于做出一款可以选空盒子, 请个农民, 农民只用一台风扇就搞定的事一样.

科学家的脑回路比较长……


四楼

设a=碗的容积,b=融化一粒盐与融化一粒假盐所需的水量的最小公倍数 x=(n/b)/a ——这个不对吧,你这算的是最坏的情况下,即加盐是放在最后的那个位置 假盐是放在第i个位置的概率为1/n 那么需要的水杯数: (1/n)*(1/ab)+(1/n)*(2/ab)+(1/n)*(3/ab)+....+(1/n)*(n/ab) =(n+1)/2ab,再向上取整

不知道你在说什么鬼。

看到这么对回复,那么你觉得答案是什么呢?毕竟百度面试题,评论下方留言你的答案!


End

原文发布于微信公众号 - java工会(javagonghui)

原文发表时间:2018-04-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码神联盟

语音识别 | Java 实现 AI 人工智能技术 - 语音识别功能

说到语音识别、语音翻译、图像识别、人脸识别等等,现在已经非常非常非常普及了,看过‘最强大脑’的朋友,也应该对‘小度’这个机器人有所了解,战胜国际顶尖的‘大脑’-...

2.2K6
来自专栏精讲JAVA

十年之后再看“面向对象”

一起帮里有人问“面向对象”的问题。但我创建“一起帮”的目的是帮人解决“具体的”“实务性的”问题,“面向对象”太过于抽象,所以没批准发布。后来在QQ群里讨论,看他...

1966
来自专栏HansBug's Lab

1015: [JSOI2008]星球大战starwar

1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec  Memory Limit: 162 MB Submit: 3001...

2827
来自专栏大数据挖掘DT机器学习

python机器学习入门资料梳理

在python基本语法入门之后,就要准备选一个研究方向了。马上就要进行春季实习招聘了,加油!总结一下python机器学习方面的资料吧。 1、数据处理 1....

3025
来自专栏小小挖掘机

数据城堡参赛代码实战篇(一)---手把手教你使用pandas

小编们最近参加了数据城堡(http://www.pkbigdata.com/)举办的“大学生助学金精准资助预测”比赛,分组第19名的成绩进入了复赛,很激动有木有...

3694
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第四章 时间复杂度

增长量级 ? 函数的增长量级 上一篇算法分析基础中,我们分析了插入排序,知道了其最好情况下的运行时间为T(n) = an + b,最差情况下的运行时间为T(n...

2938
来自专栏韩伟的专栏

字节的奥秘

在数码产品中,最常见的名词就是“字节”了。不管是U盘容量、手机存储空间,还是网络带宽,下载速度,都会涉及所谓“字节”这个单位。但到底“字节”是一个什么东西呢?本...

3704
来自专栏带你撸出一手好代码

暗号与二进制

「暗号」这个词的意义想必大家都熟悉, 它也是人与人的一种交流方式,只是它的规则并不如我们使用的语言或文字一样由大众所掌握, 因此当人们想传递一些私密的信息又不想...

42814
来自专栏大数据挖掘DT机器学习

使用 pandas处理股票数据并作分析

文/kamidox(简书作者) 原文:http://www.jianshu.com/p/1f1d4952669c pandas 是数据分析的瑞士军刀。我们...

1.5K7
来自专栏数据派THU

一文读懂PyTorch张量基础(附代码)

本文介绍了PyTorch Tensor最基础的知识以及如何跟Numpy的ndarray互相转换。

1103

扫码关注云+社区

领取腾讯云代金券