还是半年前，有幸接到某个大大公司的电话面试，当时基本没有什么准备，面试的过程一团糟，在这里感谢面试官听我胡说八道许久。在电话的最后，面试官提出这么一个问题：
一个楼梯，一次可以上一个或者两个台阶，问如果是n个台阶的楼梯能有多少种上去的方法。
当时脑子完全没有头绪，满脑子是感觉可以用二进制去解决，但是没有答案。
后来偶尔也会想起这个问题，直到半年后得出来答案，
第n层上去的方法 = 第n-1层上去的方法+第n-2层上去的方法。
是的，这是一个斐波那契数列。第n层最后一步要么是上一层要么上两层，
上一层的时候：就是第n-1层所有方法后面加一步一层，
上两层的时候：就是第n-2层所有方法后面加一步两层。
然后查了一下这是很经典的跳台阶问题。
。。想明白之后，觉得自己真的是晚睡降智商，以前对这种脑筋急转弯一样的提特别感兴趣，结果现在一个题想半年，，
另外一个问题，来自于小伙伴的面试：
一个酒窖有1000瓶酒，其中有一瓶毒酒，并且毒酒无论多么少的剂量都可让人在一天内产生明显反应，（即只用一轮测试），问最少需要多少试酒人可以确定出这瓶毒酒。
先说一下我当时比较容易能想到的思路，1000 = 10乘10乘10，当时我想的是，27个人组成三维数组的三个轴，每个人会喝由100瓶酒各取一滴混合的酒，比如x轴第2人喝第200-299编号的酒各取一滴混合的酒，y轴第二人喝十位数为2标号的所有酒各取一滴混合的酒，z轴的第二人喝个位数为2标号的所有酒各取一滴混合的酒。
则一轮实验之后，每个人都没反应则000号为毒酒，否则通过有反应的人的坐标数即可确定毒酒，
然而这不是最佳答案，后来得知有更好的答案是10个人即可：
将每瓶酒以二进制标号，10个人站一排，每个人代表2进制的10个位中的一位，2的10次方=1024,足够用了。然后每瓶酒的二进制标号中，为1的位所对应的人喝掉这瓶酒的一滴（多个位为1则多个人都要喝掉一滴），则一轮实验后，产生反应的人所对应的位为1，没有产生反应的人对应的位为0，标号为此二进制数的酒即为毒酒，没人中毒则0号酒为毒酒。
第一种思路:
一个人可以试出两瓶酒，两个人可以试出4瓶，3个人可以试出8瓶， n个人可以比n-1个人多试一倍的酒，即n-1人可以从x瓶中试出一瓶毒酒，则n个人可以从2x瓶试出一瓶毒酒。即 位数增加1，能表示的数字增加一倍，和二进制规则一样，这时候应该会有二进制这个思路然后可以得出答案，
第二种思路：
以我最初的想法，其实是将酒以十进制标记，即0-999。最大数是一个三位数，每一位最大值是9，3位数引申为三维坐标，1-9是每个坐标轴的人。进一步可以想想：采用n进制，需要x位的话，即x坐标系，每个坐标轴是n-1人，需要的试酒人为：
x（n-1）个。
然后可以得出答案。
网友评论