据传微软面试题(一)

q：有a、b、c、d四个人，要在夜里过一座桥。他们通过这座桥分别需要耗时1、2、5、10分钟，只有一支手电，并且同时最多只能两个人一起过桥。请问，如何安排，能够在17分钟内这四个人都过桥？

a: 第一步：ab过桥，a 返回，耗时 2+1 = 3

    第二步：cd过桥，b返回，耗时10+2 = 12

    第三步：ab过桥，耗时 2。累计 3+12+2=17

q：如果你有一个容量为5夸脱的水桶和一个容量为3夸脱的水桶，怎样准确地量出4夸脱的水？

a：盛满5夸脱的水桶，倒满3夸脱水桶，倒掉3夸脱的水桶的水，把5夸脱水桶剩下的水倒入3夸脱的水桶，再次盛满5夸脱的水桶，然后把3夸脱的水桶倒满，这时5夸脱的水桶内剩下的水就是4夸脱。

q：不用乘法或者加法增加8倍，现在用同样的方法增加7倍

a：使用位移，一个数向左位移3，增加8倍，再减自身，增加7倍。

q：1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现

一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空

间，能否设计一个算法实现？

a：利用数字的下标方式实现