微软笔试题目分享

微软笔试题目分享

1、1000!有几位数，为什么

2、F(n)=1n8n12

F(n)=2n2

F(n)=3n=6

F(n)=4n=other

使用+-*/和sign(n)函数组合出F(n)函数

sign(n)=0n=0

sign(n)=-1n

sign(n)=1n0

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

辑考题此题源于1981年柏林的德国规律思索学院，98%的测验者无法解题。

前提：

有五间房屋排成一列;全部房屋的外表颜色都不一样;全部的屋主来自不同的国家

;全部的屋主都养不同的宠物;喝不同的饮料;抽不同的香烟。

提示：

英国人住在红色房屋里;瑞典人养了一只狗;丹麦人喝茶;绿色的房子在白色的房

子的左边;绿色房屋的屋主喝咖啡;抽PallMall香烟的屋主养鸟;黄色屋主抽Dunhill;

位于最中间的屋主喝牛奶;挪威人住在第一间房屋里;抽Blend的人住在养猫人家的隔壁;

养马的屋主在抽Dunhill的人家的隔壁。抽BlueMaster的屋主喝啤酒;德国人抽Prince;

挪威人住在蓝色房子隔壁;只喝开水的人家住在抽Blend的隔壁。

问：谁养鱼?

五个人来自不同地方，住不同房子，养不同动物，吸不同牌子香烟，喝不同饮料，

喜爱不同食物。依据以下线索确定谁是养猫的人?

1.红房子在蓝房子的右边，白房子的左边(不肯定紧邻)

2.黄房子的仆人来自香港，而且他的房子不在最左边。

3.?员热??娜俗诎?瓤笕??娜说母舯凇?

4.来自北京的人爱喝茅台，住在来自上海的人的隔壁。

5.吸希尔顿香烟的人住在养马的人?右边隔壁。

6.爱喝啤酒的人也爱吃鸡。

7.绿房子的人养狗。

8.爱吃面条的人住在养蛇的人的隔壁。

9.来自天津的人的邻居(紧邻)一个爱吃牛肉，另一个来自成都。

微软笔试题目共享(二)

写程序找出二叉树的深度

一个树的深度等于max(左子树深度，右子树深度)+1。可以使用递归实现。

假设节点为定义为

structNode{

Node*left;Node*right;

};

intGetDepth(Node*root){

if(NULL==root){

return0;

}

intleft_depth=GetDepth(root-left);

intright_depth=GetDepth(root-right);

returnleft_depthright_depth?left_depth+1:right_depth+1;

}

利用天平砝码，三次将140克的盐分成50、90克两份?

有一个天平，2克和7克砝码各一个。如何利用天平砝码在三次内将140克盐分成50，90克两份。

第一种方法：

第一次:先称7+2克盐(相当于有三个法码2,7,9)

其次次:称2+7+9=18克盐(相当于有2,7,9,18四个法码)

第三次:称7+18=x+2,得出x是23，23+9+18=50克盐.

剩下就是90克了.

其次种方法：

1.先把140克盐分为两份，每份70克

2.在把70克分为两份，每份35克

3.然后把两个砝码放在天平两边，把35克面粉分成两份也放在两边(15+7=20+2)

现在有四堆面粉70，35，15，20，分别组合得到

70+20=90

35+15=50

地球上有多少个满意这样条件的点

站在地球上的某一点，向南走一公里，然后向东走一公里，最终向北走一公里，回到了原点。地球上有多少个满意这样条件的点?

北极点满意这个条件。

距离南极点很近的一个圈上也满意这个条件。在这个圆圈上，向南走一公里，然后向东走一公里恰好绕南极点一圈，向北走一公里回到原点。

所以地球上总共有很多点满意这个条件。

或者

首先，在地球表面上，南北走向是沿着经度方向，东西是沿着纬度方向。假如你始终往北走就会达到北极点，往南走就到了南极点。因此，向南走一公里，然后向东走一公里，最终向北走一公里，回到了原点，一种状况就是，动身点是在北极点，这样向南走一公里，然后向东走任意几公里，最终向北走一公里，最终都会回到北极点;

其次，可以这么认为假如从A点向南走一公里到达B点，那么若向东走一公里能回到B，那么最终向北走一公里，就能回到了原点A。这样就可以先找出在南北极点四周找出绕一周只有1公里的圈，那么这个圈落在南极四周时，只要往北推1公里，此时该圈上的点都能满意;若这个圈落在北极四周时，能不能往北推1公里我就不分析了。反正在南极四周能找到任意多个点就能回到这个问题了

正确标注水果篮

有三个水果篮。其中一个里面只有苹果，一个里面只有橘子，另外一个既有苹果又有橘子。每个水果篮上都有标签，但标签都是错的。如何检查某个水果篮中的一个水果，然后正确标注每个水果篮?

从标注成既有苹果也有橘子的水果篮中选取一个进行检查。

假如是橘子，则此篮中只有橘子;标有橘子的水果篮中只有苹果;标有苹果的水果篮中既有苹果也有橘子。

假如是苹果，则此篮中只有苹果;标有苹果的水果篮中只有橘子;标有橘子的水果篮中既有苹果也有橘子。

不利用浮点运算，画一个圆

不利用浮点运算，在屏幕上画一个圆(x**2+y**2=r**2，其中r为正整数)。

考虑到圆的对称性，我们只需考虑第一象限即可。

等价于找到一条连接点(0，r)到点(r，0)的一条曲线，曲线上的点距圆心(0，0)的'距离最接近r。

我们可以从点(0，r)开头，搜寻右(1，r)，下(0，r-1)，右下(1，r-1)三个点到圆心的距离，选择距圆心距离最接近r的点作为下一个点。反复进行这种运算，直至到达点(r，0)。

由于不能利用浮点运算，所以距离的比较只能在距离平方的基础上进行。也就是比较x**2+y**2和r**2之间的差值。

将一个句子按单词反序

将一个句子按单词反序。比如"hibaiducommianshiti'，反序后变为"mianshiticombaiduhi'。

可以分两步走：

第一步按找字母反序，"hibaiducommianshiti'变为"itihsnaimmocudiabih'。

其次部将每个单词中的字母反序，"itihsnaimmocudiabih'变成"mianshiticombaiduhi'。

这个方法可以在原字符串上进行，只需要几个整数变量来保持指针即可，空间简单度低。

微软笔试题：计算nbit的整数中有多少bit为1

设此整数为x。

方法1：

让此整数除以2，假如余数为1，说明最终一位是1，统计值加1。

将除得的结果进行上面运算，直到结果为0。

方法2：

考虑除法简单度有些高，可以使用移位操作代替除法。

将x和1进行按位与操作(x1)，假如结果为1，说明最终一位是1，统计值加1。

将x向右一位(x1)，重复上面过程，直到移位后结果为0。

方法3：

假如需要统计许多数字，并且内存足够大，可以考虑将每个数对应的bit为1的数量记录下来，这样每次计算只是一次查找操作。

快速求取一个整数的7倍

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

可以将此整数先左移三位(8)然后再减去原值：X3-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为质数的