你的丈夫有外遇吗
一座小镇里有100对夫妇，他们都遵守一个奇怪的风俗：如果妻子发现丈夫背叛了她，那她就会在当天夜里杀死自己的丈夫。小镇里的女人都知道别人丈夫 的秘密，却不会说出来。换言之，每个女人只知道除自己丈夫之外其他男人的外遇情况。突然有一天镇长宣布，至少有一个男人背叛了他的妻子，假设镇长说的是真 话，所有人都相信镇长所说的，那么接下来将会发生什么？
我们不妨先假设只有1个男人背叛了他的妻子，这时那个男人的妻子会猛然发现自己竟然不知道任何男人有外遇的消息（而其他99个女人知道的都是1个男 人背叛了自己的妻子，即真相），对此唯一的解释便是有且只有一个有外遇的男人，就是自己的丈夫。所以她会在当天夜里杀死自己的丈夫。然后，没有然后了。
那如果有2个男人呢？这时小镇里有98个女人知道真相，但另外2个女人只知道1个男人有外遇，并不能确定自己的丈夫是否也有外遇。所以在镇长宣布此 事的当天，全镇相安无事。但到了第2天，当这2个女人发现对方都未处死自己的老公时，就会意识到不止一个男人有外遇了。那便是有2个男人有外遇，这样的 话，其中1个肯定是自己的丈夫。于是，这2个女人会同时在夜里处死自己的丈夫。 以此类推，很容易归纳出来，如果小镇里有n 个不忠的丈夫，他们都会在镇长宣布后的第n 天夜里被处死。
实际上，有时候虽然只有极少量的信息，但只要仔细分析，一样可以得出有效的结论。上述这个谜题相信有很多人见过，类似的还有著名的 蓝眼睛岛问题 ，只是这个更加复杂一点。
隔离监狱中的100个犯人
在一所监狱中，关押了100个相互隔离的犯人。典狱长每天随机选择一名犯人（他可能被重复选中多次），扔到一间小黑屋中关禁闭。这个房间中只有一个 电灯和开关，除了小黑屋中的人，谁都看不到这盏灯，更无法控制它。关进去的人则可以打开或关闭电灯，也可以选择什么都不干。犯人们随时可以叫停这场游戏并 告诉典狱长：“所有犯人都被关过小黑屋。”如果这句话是真的，所有犯人将会被释放；但如果这句话是假的，他们全部会被处死。在游戏开始前，犯人们被允许聚 在一起商议对策，他们该怎么做才能保证自己一定能够被释放呢？
首先我们随意选择一个犯人A 作为计数者。
现在让除了A 以外的任何一个犯人进入小黑屋后，都将严格遵循下面这个法则：
如果他以前从来没有打开过这盏电灯，并且现在这盏电灯是关着的，那么打开它，除此以外不作任何事情。而如果典狱长选择的是A ，并且当他进入这个房间 以后房间里的电灯是开着的，那么他就把电灯关掉，并在自己的计数里加1。当他的计数达到99之日（从1开始），便是所有犯人重获自由之时。
工作分金问题
有个工人将为你工作七天，你用一块金条来支付工资。每天工作结束以后你都要给工人发工资，但你只能在这块金条上折两次。应该如何选择金条上的折断位置，以及支付工资的方法？ 这个问题并不困难，但如果工人为你工作X 天，你该怎么分割这块金条呢？
让我们先来回答最初的问题，为读者做个启发。把金条分成如下三份：第一份是原金条的 1／7（编号为1号金条）；第二份是原金条的 2／7（2号金条）；第三份是 4／7（3号金条）。接下来的7天你将这样支付工资：
第1
第2
第3
第4
第5
第6
第7天：给工人1号金条（此时你有2号和3号金条，工人有1号金条） 天：给工人2号金条，并取回1号金条（此时你有1号和3号金条，工人有2号金条） 天：给工人1号金条（此时你有3号金条，工人有1号和2号金条） 天：给工人3号金条，并取回1号和2号金条（此时你有1号和2号金条，工人有3号金条） 天：给工人1号金条（此时你有2号金条，工人有1号和3号金条） 天：给工人2号金条，并取回1号金条（此时你有1号金条，工人有2号和3号金条） 天：给工人1号金条，事成收工。
有过一些编程经验的读者可能会马上意识到，这其实正是二进制的原理。 1，2，4 三个十进制数的二进制形式分别是 1，10，100，用这三个数可以表示 [0，7] 区间（换成二进制形式即 [000，111] 区间）里的所有整数。
同样的道理可以计算出，如果有工人为你工作X 天，而你依然打算用一块金条来支付工资的话，那么最少需要在金条上折断（ log 2 [X+1] - 1 ） 处。
寻找次品
你有10只装满了球的盒子，其中有一只盒子里装的是次品。已知正常的球每个重 10g，而次品球每个重 9g。如何只使用一次电子秤，就找出哪只盒子装的是次品？
我们在面对这类称重找次品的问题时，第一想法通常是从每个盒子中拿出一个球来称重。然而，这道题的关键恰恰是从不同的盒子里取出不同数目的球。
我们先把 10 只盒子从 0 到 9 编号，然后从每只盒子中取出与这只盒子编号数目相等的球来，举例来说，0号盒子里不需要取球， 1 号盒子里拿出 1 只球， 2 号盒子里拿出 2 只球，等等。
然后我们这些球一起放到电子秤上。假如所有的球都是正品，那么电子秤上的读数应该是450g ；但是因为这堆球里可能有次品，所以实际读数是 ( 450 - x )g ，其中x 是次品球的个数，同时这个个数又恰好次品盒子的编号。
过桥问题
四个人需要在夜间度过一座摇摇晃晃的吊桥。不幸的是，他们只有一个火把，而这座桥又太危险了，他们无法在不借助火把的情况下度过这座危桥。而更不幸 的是，这座桥又不怎么结实，最多允许两个人同时度桥。四个人过桥的速度各不相同，分别是：1分钟，2分钟，7分钟，10分钟。显然，两人同时度桥，耗时就 取决于最慢的人。那么，他们全部度过这座桥所需的时间最短是多少？
大部分人的第一想法往往是利用一个最快的人反复度桥来接送其他人，这样需要的时间是 2 + 1 + 7 + 1 + 10 = 21 分钟。的确很快，但是实际上还有更快的方法。
很容易想到的是，我们应该能让 7 和 10 一起过桥。但是接下来呢？难道让其中1个人再回去一趟吗？不，这样的话就太耗时了。如何解决这个问题呢？我们可以提前让1个脚程较快的家伙在桥的对岸等着。因此就有方案如下：
先让 1 和 2 一起过桥。耗时2分钟。
让 1 拿着火把回来。耗时1分钟。
让 7 和 10 一起过桥，耗时10分钟。
让 2 拿着火把回来。耗时2分钟。
最后再让 1 和 2 一起过桥。耗时2分钟。
最后总耗时为 2 + 1 + 10 + 2 + 2 = 17 分钟。
表针问题
一天中时钟的时针和分针重叠几次？
直觉也许会告诉你24次，但事实并非如此，我们不妨来算一下。
当分针和时针从 12：00 处开始走动后，T 个小时的时间里时钟的分针走T 圈，时针则是 T／12 圈，两个表针第一次重合的时候分针比时针领先整整一圈，也就是 T = T／12 + 1 ，此时 T = 12／11 ，也就是表针在 12／11 时（比 1：05 稍微晚一些）第一次重叠。把重叠的次数换成N ，然后把式子中的T 换成24，我们就可以得到：
24=2+N
显然，N=22
即两个表针在一天内重叠22次。它们从来不会在上午或者下午的11点重合，因为它们要同时到达表盘的12点方向。
看到这里，各位读者是对打进微软内部更有把握了呢？
汽车加油：一辆载油500升的汽车从A 开往1000公里外的B ，已知汽车每公里耗油量为1升 (2010-10-09
09:35:34)转载
标签： 杂谈 分类： 脑子转转
问题：一辆载油 500升的汽车从A 开往1000公里外的B ，已知汽车每公里耗油量为1升，A 处有无穷多的油，
其他任何地点都没有油，但该车可以在任何地点存放油以备中转，问从A 到B 最少需要多少油？
解决方法：
1） 将A 到B 的距离进行8等分；若汽车到达第四点，即500公里时，油箱中有500升油即可到达B 点，此时
，汽车用油量最少。
2） 从开始到第一点，需要汽车第一次从开始装500升油，到达第一点，将邮箱中的250升油放到第一点
，此时，汽车从开始到达第一点已经用了125升油，剩下125升，可以回到出发点，以此类推，汽车要从开
始点12次装500升油，直到第12次，不用回去，直接在从第一点到达第二点，以此类推，到达第四点汽车
正好有500升油可以使用，因此，12个500升油，一共是6000升油。在此过程中，在第一点的汽车剩余油量
是3125升，在第二点的汽车剩余油量是1500升，在第三点的汽车剩余油量是875升，在第四点的汽车剩余
油量是500升，正好在第四点剩余500升，可以完成后续的路程，到达B 点。
微软面试题：飞机加油问题
2010-02-05 19:34
已知（1）每个飞机只有一个油箱；（2）飞机之间可以相互加油(注意是相互，没有加油机) ；（3）一箱
油可供一架飞机绕地球飞半圈。那么为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几
架飞机?(所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场)
解答：
3架飞机5架次。具体飞法：ABC 3架同时起飞，1/8处，C 给AB 加满油，C 返航，1/4处，B 给A 加满油，B 返航
，A 到达1/2处，C 从机场往另一方向起飞，3/4处，C 同已经空油箱的A 平分剩余油量，同时B 从机场起飞，
AC 到7/8处同B 平分剩余油量，刚好3架飞机同时返航。所以是3架飞机5架次。
微软面试题：给出一种洗牌算法
2010-02-28 22:09
给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。
假设数组Card[0 - 53]中的54个数对应54张牌，从第一张牌（i = 0）开始直到倒数第二张牌（i = 52）
，每次生成一个[ i, 53]之间的数r ，将Card[i]和Card[r]中的数互换。
微软面试题：找到两个单向链表的第一个公共节点
2010-02-24 20:37
两个单向链表，可能存在公共节点。如何判断是否存在公共节点，并找出它们的第一个公共结点。
如果两个单向链表有公共节点，则两个链表会构成Y 型结构，最后一个节点相同。
我们可以从头开始遍历两个链表，找到最后一个节点的指针，设为p_a，p_b。同时记录下两个链表的长度
len_a，len_b（假设len_a >= len_b)。
如果p_a == p_b，则说明两个链表有公共节点，否则没有。
如果有公共节点，则第一个公共节点距起始节点的距离满足 len_a - start_a == len_b - start_b。
所以第一个可能的公共节点距起始节点的距离是 len_a - len_b, 0。我们从这两个节点开始比较，直到
找到第一个公共节点。
微软面试题：如何在链表里如何发现循环链接?
2010-02-05 19:38
如何在链表里如何发现循环链接?
解答：
从链表的开始处，由两个指针A 和B 同时开始遍历链表。指针A 每向前移动一步，指针B 都向前移动两步。如
果在移动了N 步以后，指针A 和B 指向了同一个节点，则此链表中存在循环链表。
分析：
当然还可以在遍历的过程中存储节点的地址，通过不断的比较地址来判断有没有循环链表。但这种算法会
使用更多的内存。
如果考官比较变态，还可以直接考复制链表。如果复制前没有测试循环链表，那不好意思，只能扣分了。
微软面试题：删除链表中的重复项
一个没有排序的链表，比如list={a,l,x,b,e,f,f,e,a,g,h,b,m}，请去掉重复项，并保留原顺序，以上链
表去掉重复项后为newlist={a,l,x,b,e,f,g,h,m}，请写出一个高效算法(时间比空间更重要) 。
建立一个hash_map，key 为链表中已经遍历的节点内容，开始时为空。
从头开始遍历链表中的节点：
- 如果节点内容已经在hash_map中存在，则删除此节点，继续向后遍历；
- 如果节点内容不在hash_map中，则保留此节点，将节点内容添加到hash_map中，继续向后遍历。
你的丈夫有外遇吗
一座小镇里有100对夫妇，他们都遵守一个奇怪的风俗：如果妻子发现丈夫背叛了她，那她就会在当天夜里杀死自己的丈夫。小镇里的女人都知道别人丈夫 的秘密，却不会说出来。换言之，每个女人只知道除自己丈夫之外其他男人的外遇情况。突然有一天镇长宣布，至少有一个男人背叛了他的妻子，假设镇长说的是真 话，所有人都相信镇长所说的，那么接下来将会发生什么？
我们不妨先假设只有1个男人背叛了他的妻子，这时那个男人的妻子会猛然发现自己竟然不知道任何男人有外遇的消息（而其他99个女人知道的都是1个男 人背叛了自己的妻子，即真相），对此唯一的解释便是有且只有一个有外遇的男人，就是自己的丈夫。所以她会在当天夜里杀死自己的丈夫。然后，没有然后了。
那如果有2个男人呢？这时小镇里有98个女人知道真相，但另外2个女人只知道1个男人有外遇，并不能确定自己的丈夫是否也有外遇。所以在镇长宣布此 事的当天，全镇相安无事。但到了第2天，当这2个女人发现对方都未处死自己的老公时，就会意识到不止一个男人有外遇了。那便是有2个男人有外遇，这样的 话，其中1个肯定是自己的丈夫。于是，这2个女人会同时在夜里处死自己的丈夫。 以此类推，很容易归纳出来，如果小镇里有n 个不忠的丈夫，他们都会在镇长宣布后的第n 天夜里被处死。
实际上，有时候虽然只有极少量的信息，但只要仔细分析，一样可以得出有效的结论。上述这个谜题相信有很多人见过，类似的还有著名的 蓝眼睛岛问题 ，只是这个更加复杂一点。
隔离监狱中的100个犯人
在一所监狱中，关押了100个相互隔离的犯人。典狱长每天随机选择一名犯人（他可能被重复选中多次），扔到一间小黑屋中关禁闭。这个房间中只有一个 电灯和开关，除了小黑屋中的人，谁都看不到这盏灯，更无法控制它。关进去的人则可以打开或关闭电灯，也可以选择什么都不干。犯人们随时可以叫停这场游戏并 告诉典狱长：“所有犯人都被关过小黑屋。”如果这句话是真的，所有犯人将会被释放；但如果这句话是假的，他们全部会被处死。在游戏开始前，犯人们被允许聚 在一起商议对策，他们该怎么做才能保证自己一定能够被释放呢？
首先我们随意选择一个犯人A 作为计数者。
现在让除了A 以外的任何一个犯人进入小黑屋后，都将严格遵循下面这个法则：
如果他以前从来没有打开过这盏电灯，并且现在这盏电灯是关着的，那么打开它，除此以外不作任何事情。而如果典狱长选择的是A ，并且当他进入这个房间 以后房间里的电灯是开着的，那么他就把电灯关掉，并在自己的计数里加1。当他的计数达到99之日（从1开始），便是所有犯人重获自由之时。
工作分金问题
有个工人将为你工作七天，你用一块金条来支付工资。每天工作结束以后你都要给工人发工资，但你只能在这块金条上折两次。应该如何选择金条上的折断位置，以及支付工资的方法？ 这个问题并不困难，但如果工人为你工作X 天，你该怎么分割这块金条呢？
让我们先来回答最初的问题，为读者做个启发。把金条分成如下三份：第一份是原金条的 1／7（编号为1号金条）；第二份是原金条的 2／7（2号金条）；第三份是 4／7（3号金条）。接下来的7天你将这样支付工资：
第1
第2
第3
第4
第5
第6
第7天：给工人1号金条（此时你有2号和3号金条，工人有1号金条） 天：给工人2号金条，并取回1号金条（此时你有1号和3号金条，工人有2号金条） 天：给工人1号金条（此时你有3号金条，工人有1号和2号金条） 天：给工人3号金条，并取回1号和2号金条（此时你有1号和2号金条，工人有3号金条） 天：给工人1号金条（此时你有2号金条，工人有1号和3号金条） 天：给工人2号金条，并取回1号金条（此时你有1号金条，工人有2号和3号金条） 天：给工人1号金条，事成收工。
有过一些编程经验的读者可能会马上意识到，这其实正是二进制的原理。 1，2，4 三个十进制数的二进制形式分别是 1，10，100，用这三个数可以表示 [0，7] 区间（换成二进制形式即 [000，111] 区间）里的所有整数。
同样的道理可以计算出，如果有工人为你工作X 天，而你依然打算用一块金条来支付工资的话，那么最少需要在金条上折断（ log 2 [X+1] - 1 ） 处。
寻找次品
你有10只装满了球的盒子，其中有一只盒子里装的是次品。已知正常的球每个重 10g，而次品球每个重 9g。如何只使用一次电子秤，就找出哪只盒子装的是次品？
我们在面对这类称重找次品的问题时，第一想法通常是从每个盒子中拿出一个球来称重。然而，这道题的关键恰恰是从不同的盒子里取出不同数目的球。
我们先把 10 只盒子从 0 到 9 编号，然后从每只盒子中取出与这只盒子编号数目相等的球来，举例来说，0号盒子里不需要取球， 1 号盒子里拿出 1 只球， 2 号盒子里拿出 2 只球，等等。
然后我们这些球一起放到电子秤上。假如所有的球都是正品，那么电子秤上的读数应该是450g ；但是因为这堆球里可能有次品，所以实际读数是 ( 450 - x )g ，其中x 是次品球的个数，同时这个个数又恰好次品盒子的编号。
过桥问题
四个人需要在夜间度过一座摇摇晃晃的吊桥。不幸的是，他们只有一个火把，而这座桥又太危险了，他们无法在不借助火把的情况下度过这座危桥。而更不幸 的是，这座桥又不怎么结实，最多允许两个人同时度桥。四个人过桥的速度各不相同，分别是：1分钟，2分钟，7分钟，10分钟。显然，两人同时度桥，耗时就 取决于最慢的人。那么，他们全部度过这座桥所需的时间最短是多少？
大部分人的第一想法往往是利用一个最快的人反复度桥来接送其他人，这样需要的时间是 2 + 1 + 7 + 1 + 10 = 21 分钟。的确很快，但是实际上还有更快的方法。
很容易想到的是，我们应该能让 7 和 10 一起过桥。但是接下来呢？难道让其中1个人再回去一趟吗？不，这样的话就太耗时了。如何解决这个问题呢？我们可以提前让1个脚程较快的家伙在桥的对岸等着。因此就有方案如下：
先让 1 和 2 一起过桥。耗时2分钟。
让 1 拿着火把回来。耗时1分钟。
让 7 和 10 一起过桥，耗时10分钟。
让 2 拿着火把回来。耗时2分钟。
最后再让 1 和 2 一起过桥。耗时2分钟。
最后总耗时为 2 + 1 + 10 + 2 + 2 = 17 分钟。
表针问题
一天中时钟的时针和分针重叠几次？
直觉也许会告诉你24次，但事实并非如此，我们不妨来算一下。
当分针和时针从 12：00 处开始走动后，T 个小时的时间里时钟的分针走T 圈，时针则是 T／12 圈，两个表针第一次重合的时候分针比时针领先整整一圈，也就是 T = T／12 + 1 ，此时 T = 12／11 ，也就是表针在 12／11 时（比 1：05 稍微晚一些）第一次重叠。把重叠的次数换成N ，然后把式子中的T 换成24，我们就可以得到：
24=2+N
显然，N=22
即两个表针在一天内重叠22次。它们从来不会在上午或者下午的11点重合，因为它们要同时到达表盘的12点方向。
看到这里，各位读者是对打进微软内部更有把握了呢？
汽车加油：一辆载油500升的汽车从A 开往1000公里外的B ，已知汽车每公里耗油量为1升 (2010-10-09
09:35:34)转载
标签： 杂谈 分类： 脑子转转
问题：一辆载油 500升的汽车从A 开往1000公里外的B ，已知汽车每公里耗油量为1升，A 处有无穷多的油，
其他任何地点都没有油，但该车可以在任何地点存放油以备中转，问从A 到B 最少需要多少油？
解决方法：
1） 将A 到B 的距离进行8等分；若汽车到达第四点，即500公里时，油箱中有500升油即可到达B 点，此时
，汽车用油量最少。
2） 从开始到第一点，需要汽车第一次从开始装500升油，到达第一点，将邮箱中的250升油放到第一点
，此时，汽车从开始到达第一点已经用了125升油，剩下125升，可以回到出发点，以此类推，汽车要从开
始点12次装500升油，直到第12次，不用回去，直接在从第一点到达第二点，以此类推，到达第四点汽车
正好有500升油可以使用，因此，12个500升油，一共是6000升油。在此过程中，在第一点的汽车剩余油量
是3125升，在第二点的汽车剩余油量是1500升，在第三点的汽车剩余油量是875升，在第四点的汽车剩余
油量是500升，正好在第四点剩余500升，可以完成后续的路程，到达B 点。
微软面试题：飞机加油问题
2010-02-05 19:34
已知（1）每个飞机只有一个油箱；（2）飞机之间可以相互加油(注意是相互，没有加油机) ；（3）一箱
油可供一架飞机绕地球飞半圈。那么为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几
架飞机?(所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场)
解答：
3架飞机5架次。具体飞法：ABC 3架同时起飞，1/8处，C 给AB 加满油，C 返航，1/4处，B 给A 加满油，B 返航
，A 到达1/2处，C 从机场往另一方向起飞，3/4处，C 同已经空油箱的A 平分剩余油量，同时B 从机场起飞，
AC 到7/8处同B 平分剩余油量，刚好3架飞机同时返航。所以是3架飞机5架次。
微软面试题：给出一种洗牌算法
2010-02-28 22:09
给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。
假设数组Card[0 - 53]中的54个数对应54张牌，从第一张牌（i = 0）开始直到倒数第二张牌（i = 52）
，每次生成一个[ i, 53]之间的数r ，将Card[i]和Card[r]中的数互换。
微软面试题：找到两个单向链表的第一个公共节点
2010-02-24 20:37
两个单向链表，可能存在公共节点。如何判断是否存在公共节点，并找出它们的第一个公共结点。
如果两个单向链表有公共节点，则两个链表会构成Y 型结构，最后一个节点相同。
我们可以从头开始遍历两个链表，找到最后一个节点的指针，设为p_a，p_b。同时记录下两个链表的长度
len_a，len_b（假设len_a >= len_b)。
如果p_a == p_b，则说明两个链表有公共节点，否则没有。
如果有公共节点，则第一个公共节点距起始节点的距离满足 len_a - start_a == len_b - start_b。
所以第一个可能的公共节点距起始节点的距离是 len_a - len_b, 0。我们从这两个节点开始比较，直到
找到第一个公共节点。
微软面试题：如何在链表里如何发现循环链接?
2010-02-05 19:38
如何在链表里如何发现循环链接?
解答：
从链表的开始处，由两个指针A 和B 同时开始遍历链表。指针A 每向前移动一步，指针B 都向前移动两步。如
果在移动了N 步以后，指针A 和B 指向了同一个节点，则此链表中存在循环链表。
分析：
当然还可以在遍历的过程中存储节点的地址，通过不断的比较地址来判断有没有循环链表。但这种算法会
使用更多的内存。
如果考官比较变态，还可以直接考复制链表。如果复制前没有测试循环链表，那不好意思，只能扣分了。
微软面试题：删除链表中的重复项
一个没有排序的链表，比如list={a,l,x,b,e,f,f,e,a,g,h,b,m}，请去掉重复项，并保留原顺序，以上链
表去掉重复项后为newlist={a,l,x,b,e,f,g,h,m}，请写出一个高效算法(时间比空间更重要) 。
建立一个hash_map，key 为链表中已经遍历的节点内容，开始时为空。
从头开始遍历链表中的节点：
- 如果节点内容已经在hash_map中存在，则删除此节点，继续向后遍历；
- 如果节点内容不在hash_map中，则保留此节点，将节点内容添加到hash_map中，继续向后遍历。