IT名企面试：微软笔试题(2)

想要进入微软公司，面试笔试是少不了的。那么现在就来熟悉一下微软笔试题的类型和内容吧。例如：写程序找出二叉树的深度等问题。

AD：

int n = 0;while (x)  
{  
xx = x & (x - 1);  
n++;  
}  
return n; 

微软笔试题：快速求取一个整数的7倍

乘法相对比较慢，所以快速的方法就是将这个乘法转换成加减法和移位操作。

可以将此整数先左移三位（×8）然后再减去原值：X << 3 - X。

微软笔试题：判断一个数是不是2的n次幂

设要判断的数是无符号整数X。

首先判断X是否为0，如果为0则不是2的n次幂，返回。

X和X-1进行按位与操作，如果结果是0，则说明这个数是2的n次幂；如果结果非0，则说明这个数不是2 的n次幂。

证明：

如果是2的n次幂，则此数用二进制表示时只有一位是1，其它都是0。减1后，此位变成0，后面的位变成1，所以按位与后结果是0。

如果不是2的n次幂，则此数用二进制表示时有多位是1。减1后，只有最后一个1变成0，前面的 1还是1，所以按位与后结果不是0。

微软笔试题：三只蚂蚁不相撞的概率是多少

在三角形的三个顶点上各有一只蚂蚁，它们向另一个顶点运动，目标随机（可能为另外两个顶点的任意一个）。问三只蚂蚁不相撞的概率是多少？

如果蚂蚁顺时针爬行记为0，逆时针爬行记为1。那么三只蚂蚁的状态可能为000，001，...，110，111中的任意一个，且为每种状态的概率相等。在这8种状态中，只有000和111可以避免相撞，所以蚂蚁不相撞的概率是1/4。

微软笔试题：判断数组中是否包含重复数字

给定一个长度为N的数组，其中每个元素的取值范围都是1到N。判断数组中是否有重复的数字。（原数组不必保留）

给定一个长度为N的数组，其中每个元素的取值范围都是1到N。判断数组中是否有重复的数字。（原数组不必保留）

微软笔试题：如何将蛋糕切成相等的两份

一块长方形的蛋糕，其中有一个小长方形的空洞（角度任意）。使用一把直刀，如何一刀将蛋糕切成相等的两份？

通过长方形中心的的任意直线都能将长方形等分，所以连接两个长方形的中心点的直线可以等分这个蛋糕。

一个没有排序的链表，比如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中，继续向后遍历。

微软笔试题：小明一家5口如何过桥？

小明一家过一座桥，过桥时是黑夜，所以必须有灯。现在小明过桥要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的妈妈要8秒，小明的爷爷要12秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30秒就会熄灭。问：小明一家如何过桥？

小明与弟弟过去，小明回来，用4s；

妈妈与爷爷过去，弟弟回来，用15s；

小明与弟弟过去，小明回来，用4s；

小明与爸爸过去，用6s；

总共用29s。

题目的关键是让速度差不多的一起走，免得过于拖累较快的一个人。

微软笔试题：编一个程序求质数的和

编一个程序求质数的和，例如F(7) = 2+3+5+7+11+13+17=58。

方法1：

对于从2开始的递增整数n进行如下操作：

用 [2，n-1] 中的数依次去除n，如果余数为0，则说明n不是质数；如果所有余数都不是0，则说明n是质数，对其进行加和。

空间复杂度为O(1)，时间复杂度为O(n^2)，其中n为需要找到的最大质数值（例子对应的值为17）。

方法2：

可以维护一个质数序列，这样当需要判断一个数是否是质数时，只需判断是否能被比自己小的质数整除即可。

对于从2开始的递增整数n进行如下操作：

用 [2，n-1] 中的质数（2，3，5，7，开始时此序列为空）依次去除n，如果余数为0，则说明n不是质数；如果所有余数都不是0，则说明n是质数，将此质数加入质数序列，并对其进行加和。

空间复杂度为O(m)，时间复杂度为O(mn)，其中m为质数的个数（例子对应的值为7），n为需要找到的最大质数值（例子对应的值为17）。

方法3：

也可以不用除法，而用加法。

申请一个足够大的空间，每个bit对应一个整数，开始将所有的bit都初始化为0。

对于已知的质数（开始时只有2），将此质数所有的倍数对应的bit都改为1，那么最小的值为0的bit对应的数就是一个质数。对新获得的质数的倍数也进行标注。

对这样获得的质数序列累加就可以获得质数和。

空间复杂度为O(n)，时间负责度为O(n)，其中n为需要找到的最大质数值（例子对应的值为17）。