微软笔试题目.docx

微软笔试题目
微软在IT界依然是数一数二的企业了，不少人的梦想都是进入 微软公司，
微软笔试题：写程序找出二叉树的深度
一个树的深度等于max(左子树深度，右子树深度)+1。可以使用 递归实现。
假设节点为定义为
structNode{
Node*left;Node*right;
};
intGetDepth(Node*root){
if(NULL==root){
return。；
}
intleft_depth=GetDepth(root->left);
intright_depth=GetDepth(root->right);
returnleft_depth>right—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^o
这个方法可以在原字符串上进行，只需要几个整数变量来保持指 针即可，空间复杂度低。
微软笔试题：计算nbit的整数中有多少bit为1
设此整数为x,
方法1：
让此整数除以2,如果余数为1,说明最后一位是1,统计值加1o
将除得的结果进行上面运算，直到结果为0o
方法2：
考虑除法复杂度有些高，可以使用移位操作代替除法。
将x和1进行按位与操作（x&1）,如果结果为1,说明最后一位
是1,统计值加1o
将x向右一位（x>>1），重复上面过程，直到移位后结果为0。
方法3：
如果需要统计很多数字，并且内存足够大，可以考虑将每个数对 应的bit为1的数量记录下来，这样每次计算只是一次查找操作。
微软笔试题：快速求取一个整数的7倍
乘法相对比较慢，所以快速的方法就是将这个乘法转换成加减法 和移位操作。
可以将此整数先左移三位（x8）然后再减去原值：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。那么三只蚂蚁 的状态可能为0, 1, ..., 110, 111中的任意一个，且为每种 状态的概率相等。在这8种状态中，只有0和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 (nM),其中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)。