如何快速尝出毒酒?- 用bit解决问题

问题

国王有一百桶酒,比自己的生命还重要。结果有一天其中一桶被投了慢性毒药,喝了以后半个小时以后就会死掉。国王大怒,命令玩忽职守的侍卫去试毒。酒不能被混合,一个侍卫可以喝多桶酒,一桶酒也可以由多个侍卫喝,怎么样才能用最少的侍卫、在最短的时间知道哪桶是毒酒。侍卫可以理解为线程,即怎么样用最少的线程用最快的速度完成这个工作。

方案

此问题是我在面试时经常用的一道题目,主要考察的是候选人能不能以计算机的思维考虑问题。

最简单的方案肯定是找100个人,每个人试一桶酒,那么用时30分钟,就可以判断出哪一桶就有毒。

再进一步的,可以使用分段法,把酒分成n份,先找n个侍卫试酒,可以定位出哪一段的酒有毒,再接着分段试酒。但这种方案,分段数目越少,试出毒酒的平均耗时就越长。

如果用计算机的思维来分析这个问题,那么首先考虑如何存储这100桶酒。100桶酒可以用二进制7个bit来表示(27>100)。对应那一桶毒酒,其二进制表示中为1的位置如果能够可以定位出来,就可以定位出此桶毒酒。可以找7个侍卫编号1-7。对于每一桶酒的二进制表示(不足七位前面用0表示),从第一位到第七位,如果是1,则对应编号的侍卫喝此桶酒。这样,每个侍卫喝掉对应的酒。30分钟后,侍卫按照编号1-7,死掉的置为1,活着的置为0,如此,侍卫的一个序列如0000111就表示第七桶酒为毒酒。

总结

上述最后一种方案提现了在计算机中使用bit来解决问题的思路。当需要节省存储的时候,使用bit来做经常会有出其不易的效果。就比如最近很火的电影《天才枪手》中,主角们记忆选择题的答案A、B、C、D,完全可以使用位编码来表示四种答案:00-A 01-B 10-C 11-D,四个bit转换为一个十六进制数字,如此就可以节省一半的存储,记忆起来也会简单很多。此外,我们处理大数据去重/计数使用的Bitmap、BloomFilter,也都是一种使用bit节省存储的思路。

技术琐话2018-01-01

日常的工作学习中,经常会看到好的知识点,对自己有提示的一句话,或者是自己突然想通了一件事情。决定以博客的形式记录下来,以“技术琐话”作为主题。

2018年以“技术琐话”开篇,主要是整理了一下自己以前一些零散的知识点。

技术感悟

  • 阅读各种技术的使用/说明/示例/原理文档时,能不能快速吸收为自己的知识?能不能注意到细节关键点?是一个开发工程师优不优秀,能不能比别人更突出、更快成长起来的一个非常重要的地方。

  • 你东西学得广了,别人就会攻击你不够深入;你东西学得够深了,别人就会攻击你知识面不广;你专精在技术时,别人就会说你管理不好;你花心力好好做管理之后,别人就会说你技术没有跟上;你研究方法论时,别人就会说你很虚;你专心做项目时,别人就会说你没有提炼方法,没有系统。… 想挑你毛病,总有办法。但你自己知道自己在干什么最重要,那些你的「缺点」其实可能不是缺点,而是一件事物的另一面。你选择这一面,自然会缺另一面。这是取舍点,不是优缺点。(from 微博@蔡学镛)

  • 来自硅谷的启示

技术点

  • 在写Java代码的时候,如果匿名内部类里面传递变量,变量必须声明为final,而在Java8中,可以不用写这个final了,因为Java8引入了Effectively final 功能,由系统默认添加。What is Effectively Final variable of Java 8

  • 将Nginx中的一个配置指令proxyinterceptorerrors设置为true,可以捕获后端服务器返回的错误码进行处理,从而可以使用nginx自己的错误显示页面。 ​​​​

  • 在Servlet开发中,request.setCharacterEncoding必须在所有filter最开始执行,否则只要调用过request相关方法去获取其参数等,再去设置编码是无效的。

  • Java中File类的listFiles和list方法最终调用的是FileSystem的本地接口,返回的文件列表顺序是没有保证的。Spring中的san某一basepackage下的类就是使用的此方法,因此加载的bean的顺序也是无法保证的。这一点需要特别注意。 ​​​​​​

  • Tomcat各个版本特性对比图

  • Java集合类对比图表

技术琐话2017-11-26

日常的工作学习中,经常会看到好的知识点,对自己有提示的一句话,或者是自己突然想通了一件事情。决定以博客的形式记录下来,以“技术琐话”作为主题。

  • The interesting thing about performance is that if you analyze most programs, you find that they waste most of their time in a small fraction of code. If you optimize all the code equally, you end up with 90 percent of the optimizations wasted, because you are optimizing code that isn’t run much. The time spent making the program fast, the time lost because of lack of clarity, is all wasted time.《重构》一书的一段话,也是不要过早优化的意思,即在不确定这段代码真的会被频繁调用、真的是系统的性能瓶颈之前,没必要花时间优化此处的性能。

  • 这句话揭示了成为技术专家的一个关键特质: 理解一个系统应该如何工作并不能使人成为专家,只能靠调查系统为何不能正常工作才行。(From SRE ,by Brian Redman)

  • 技术书籍的出版门槛越来越低,该如何识别是否是一本烂书呢?在我自己看来,英文书籍质量远远好于中文书籍,翻译的版本一般来说质量也不错,不过作为一个互联网从业的技术人员,能够直接阅读英文原版是最好不过的。而对于中文书籍,如果是以公司名义或者书的序多于3篇,是一本烂书的概率非常大,写推荐语、写序的人名头越大,并不代表这本书的质量有多好。此外,现在某sdn专家真的是门槛低到不行,挂这个名头出的书更要慎重选择。对于InfoQ推荐的书,倒是可以值得一读。

Spring注解概览

从Java5.0开始,Java开始支持注解。Spring做为Java生态中的领军框架,从2.5版本后也开始支持注解。相比起之前使用xml来配置Spring框架,使用注解提供了更多的控制Spring框架的方式。

现在越来越多的项目也都在使用注解做相关的配置,但Spring的注解非常多,相信很多注解大家都没有使用过。本文就尽量全面地概括介绍一下Spring中常用的注解。

有效解决问题

来自于内部的一次培训,主要讲述了如何有效地解决问题,包括识别问题、描述问题、分析问题、找出方案、决策问题等。

Java9来了

2017.9.21,Java9终于正式发布。其带来了诸如模块化、REPL环境、集合工厂方法等一系列有用的新特性。本文列出一些链接,可以通过阅读相关的内容来了解学习Java9。

官方资料

第三方资料

[译]Java中9个处理Exception的最佳实践

在Java中处理异常并不是一个简单的事情。不仅仅初学者很难理解,即使一些有经验的开发者也需要花费很多时间来思考如何处理异常,包括需要处理哪些异常,怎样处理等等。这也是绝大多数开发团队都会制定一些规则来规范对异常的处理的原因。而团队之间的这些规范往往是截然不同的。

本文给出几个被很多团队使用的异常处理最佳实践。