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

问题:

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 条评论
登录 后参与评论

相关文章

来自专栏CSDN技术头条

不服来战,看Kotlin如何完爆Java

前言:Kotlin因支持谷歌和简化Android开发而声名鹊起。看看它如何解决Java的许多痛点。 Why Kotlin? 如果我今天被问到如何区别开发Andr...

1855
来自专栏数据小魔方

创意彩虹图表!

今天跟大家分享一款当前非常流行的创意彩虹图表! ▽ 这种图表其实制作起来没有任何难度,主要是使用特殊的数据展现形式以及协调匀称的配色,使得整个图表看起来非常的新...

2579
来自专栏王亚昌的专栏

采用共享内存或文件映射的方式保存用户数据

    举个例子,假如一个网站提供给用户8种特权服务,用户可以选择性的开通其中一个或多个,而用户一般的操作行为是查看自己的特权以及查看好友的特权。这类数据的特点...

742
来自专栏葡萄城控件技术团队

ActiveReports 9实战教程(3): 图文并茂的报表形式

基于上面2节内容,我们搭建了AR9的开发环境,配置好了数据源。在本节,我们以官方提供的3个中文图文并茂的报表来展示AR9的功能,并通过实战的方式一一分享。 以往...

1756
来自专栏前端小作坊

CSS硬件加速的好与坏

每个人都痴迷于60桢每秒的顺滑动画。为了实现这个顺滑体验现在用的最流行的一个做法就是使用『CSS硬件加速』。在一些极端例子中,强制使用translate3d意味...

762
来自专栏牛客网

前端一面 - 阿里

13.算法题:电脑里有很多大小不一样的照片,我现在要复制到U盘上,但是U盘容量固定。让你写一个程序,挑选一组照片,让U盘的剩余空间最小。

872
来自专栏申龙斌的程序人生

零基础学编程014:小海龟做画

在《零基础学编程012:画出复利曲线图》这篇文章中,我们使用了强大的matplotlib和numpy模块,可以用几行代码画出复杂的图形来。但对于初学者来说,里面...

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

如何用R语言从网上读取多样格式数据

第一部分:数据信息 生活中,我们面临着各种各样的数据:比如你的成绩单,比如公司的财务报表,比如朋友圈的一些状态,比如微信里的一段语音……我们生活的大数据时代的一...

2895
来自专栏Crossin的编程教室

【每周一坑】记账本

每周一坑,只管挖,不管填。有阵子没挖坑了,今天来整一个: 做一个可以用来记账的小程序 就在控制台下,可以输入收支数额和名目。程序会记录下每笔收支。之后可以查询余...

32910
来自专栏程序员宝库

我的编程之路:知识管理与知识体系

本文的资料放到了Github Repo(https://github.com/wxyyxc1992/Coder-Knowledge-Graph)(本文介绍的这种...

2755

扫码关注云+社区