微软笔试题目

1、微软笔试题目微软在 IT 界依然是数一数二的企业了， 不少人的梦想都是进入 微软公司。 那么在这之前的以及就需要进行一下准备了。 那么这里就 来看看小编为大家总结的微软吧。微软笔试题：写程序找出二叉树的深度一个树的深度等于 max（左子树深度，右子树深度 ）+1 。可以使 用递归实现。假设节点为定义为struct Node Node* left; Node* right;int GetDepth(Node* root) if (NULL = root) return 0;int left_depth = GetDepth(root- left);int right_depth = GetDep

2、th(root- right);return left_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 克了 .第

3、二种方法：1. 先把 140 克盐分为两份，每份 70 克2. 在把 70 克分为两份，每份 35 克3. 然后把两个砝码放在天平两边， 把 35 克面粉分成两份也放在两边(15+7=20+2)现在有四堆面粉 70，35，15，20 ，分别组合得到70+20=9035+15=50微软笔试题：地球上有多少个满足这样条件的点站在地球上的某一点，向南走一公里，然后向东走一公里，最后向北走一公里，回到了原点。地球上有多少个满足这样条件的点北极点满足这个条件距离南极点很近的一个圈上也满足这个条件。在这个圆圈上， 向南走一公里， 然后向东走一公里恰好绕南极点一圈， 向北走一公里 回到原点。所以地球上总共有

4、无数点满足这个条件。或者首先，在地球表面上，南北走向是沿着经度方向，东西是沿着 纬度方向。如果你一直往北走就会达到北极点， 往南走就到了南极点。 因此，向南走一公里，然后向东走一公里，最后向北走一公里，回到 了原点，一种情况就是，出发点是在北极点，这样向南走一公里，然 后向东走任意几公里，最后向北走一公里，最后都会回到北极点 ;其次，可以这么认为如果从 A 点向南走一公里到达 B 点，那么 若向东走一公里能回到 B，那么最后向北走一公里，就能回到了原点A。这样就可以先找出在南北极点附近找出绕一周只有 1 公里的圈， 那么这个圈落在南极附近时， 只要往北推 1 公里，此时该圈上的点都 能满足 ;

5、若这个圈落在北极附近时，能不能往北推 1 公里我就不分析 了。反正在南极附近能找到任意多个点就能回到这个问题了微软笔试题：正确标注水果篮有三个水果篮。其中一个里面只有苹果，一个里面只有橘子， 另外一个既有苹果又有橘子。 每个水果篮上都有标签， 但标签都是错 的。如何检查某个水果篮中的一个水果，然后正确标注每个水果篮从标注成既有苹果也有橘子的水果篮中选取一个进行检查。如果是橘子，则此篮中只有橘子 ;标有橘子的水果篮中只有苹果 标有苹果的水果篮中既有苹果也有橘子。如果是苹果，则此篮中只有苹果 ;标有苹果的水果篮中只有橘子标有橘子的水果篮中既有苹果也有橘子。微软笔试题：不利用浮点运算，画一个圆不利用

6、浮点运算，在屏幕上画一个圆 （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 之间的差值。微软笔试题：将一个句子按单

7、词反序将一个句子按单词反序。比如 hi baidu com mianshiti，反序后变为 mianshiti com baidu hi。可以分两步走：第 一 步 按 找 字 母 反 序 ， hi baidu com mianshiti 变 为 itihsnaim moc udiab ih 。第二部将每个单词中的字母反序， itihsnaim moc udiab ih 变成 mianshiti com baidu hi 。这个方法可以在原字符串上进行，只需要几个整数变量来保持指针即可，空间复杂度低微软笔试题：计算 n bit 的整数中有多少 bit 为 1设此整数为 x方法 1：让此整数除以

8、2 ，如果余数为 1，说明最后一位是 1，统计值加1。将除得的结果进行上面运算，直到结果为 0方法 2：10考虑除法复杂度有些高，可以使用移位操作代替除法将 x 和 1 进行按位与操作 (x 1)，如果结果为 1，说明最后一位是 1，统计值加 1 。将 x 向右一位 (x 1) ，重复上面过程，直到移位后结果为 0 。 方法 3： 如果需要统计很多数字，并且内存足够大，可以考虑将每个数对应的 bit 为 1 的数量记录下来，这样每次计算只是一次查找操作。 微软笔试题：快速求取一个整数的 7 倍11乘法相对比较慢，所以快速的方法就是将这个乘法转换成加减法和移位操作可以将此整数先左移三位 ( 8)

9、然后再减去原值： X 3 - X微软笔试题：判断一个数是不是 2的n 次幂设要判断的数是无符号整数 X首先判断 X 是否为 0 ，如果为 0 则不是 2 的 n 次幂，返回X 和 X-1 进行按位与操作，如果结果是 0 ，则说明这个数是 2 的n 次幂;如果结果非 0，则说明这个数不是 2 的n次幂。证明：12如果是 2 的 n 次幂，则此数用二进制表示时只有一位是 1 ，其 它都是 0 。减 1 后，此位变成 0 ，后面的位变成 1，所以按位与后结 果是 0。如果不是 2 的 n 次幂，则此数用二进制表示时有多位是 1 。减1 后，只有最后一个 1 变成 0 ，前面的 1 还是 1 ，所以按

10、位与后结果 不是 0 。微软笔试题：三只蚂蚁不相撞的概率是多少 在三角形的三个顶点上各有一只蚂蚁， 它们向另一个顶点运动， 目标随机 （可能为另外两个顶点的任意一个 ）。问三只蚂蚁不相撞的概 率是多少 ?如果蚂蚁顺时针爬行记为 0，逆时针爬行记为 1 。那么三只蚂 蚁的状态可能为 000 ，001 ，.，110 ， 111 中的任意一个，且为每 种状态的概率相等。在这 8 种状态中，只有 000 和 111 可以避免相13撞，所以蚂蚁不相撞的概率是 1/4微软笔试题：判断数组中是否包含重复数字给定一个长度为 N 的数组，其中每个元素的取值范围都是 1 到N 。判断数组中是否有重复的数字。 （原

11、数组不必保留 ） 给定一个长度为 N 的数组，其中每个元素的取值范围都是 1 到N 。判断数组中是否有重复的数字。 （原数组不必保留 ） 微软笔试题：如何将蛋糕切成相等的两份 一块长方形的蛋糕，其中有一个小长方形的空洞 （角度任意 ）。使用一把直刀，如何一刀将蛋糕切成相等的两份 ? 通过长方形中心的的任意直线都能将长方形等分，所以连接两14个长方形的中心点的直线可以等分这个蛋糕一个没有排序的链表，比如 list=a,l,x,b,e,f,f,e,a,g,h,b,m ，请 去掉重复项，并保留原顺序，以上链表去掉重复项后为 newlist=a,l,x,b,e,f,g,h,m ，请写出一个高效算法 （

12、 时间比空间更重 要）。建立一个 hash_map ， key 为链表中已经遍历的节点内容，开 始时为空。从头开始遍历链表中的节点：- 如果节点内容已经在 hash_map 中存在，则删除此节点，继 续向后遍历 ;- 如果节点内容不在 hash_map 中，则保留此节点，将节点内15容添加到 hash_map 中，继续向后遍历微软笔试题：小明一家 5 口如何过桥 ?现在小明 ，小明的妈妈 而过桥的速 问：小明一小明一家过一座桥，过桥时是黑夜，所以必须有灯。 过桥要 1 秒，小明的弟弟要 3 秒，小明的爸爸要 6 秒 要 8 秒，小明的爷爷要 12 秒。每次此桥最多可过两人， 度依过桥最慢者而定

13、，而且灯在点燃后 30 秒就会熄灭 家如何过桥 ?小明与弟弟过去，小明回来，用 4s;妈妈与爷爷过去，弟弟回来，用 15s;小明与弟弟过去，小明回来，用 4s;16小明与爸爸过去，用 6s;总共用 29s 。题目的关键是让速度差不多的一起走，免得过于拖累较快的一个人。微软笔试题：编一个程序求质数的和编 一 个 程 序 求 质 数 的 和 ， 例 如 F(7) = 2+3+5+7+11+13+17=58 。方法 1：对于从 2 开始的递增整数 n 进行如下操作：17用 2 ，n-1 中的数依次去除 n，如果余数为 0 ，则说明 n 不 是质数 ;如果所有余数都不是 0 ，则说明 n 是质数，对其

14、进行加和。空间复杂度为 O(1) ，时间复杂度为 O(n )，其中n 为需要找到 的最大质数值 (例子对应的值为 17) 。方法 2：可以维护一个质数序列， 这样当需要判断一个数是否是质数时， 只需判断是否能被比自己小的质数整除即可。对于从 2 开始的递增整数 n 进行如下操作：用 2 ，n-1 中的质数 (2，3，5 ，7，开始时此序列为空 )依次 去除 n，如果余数为 0，则说明 n 不是质数 ;如果所有余数都不是 0， 则说明 n 是质数，将此质数加入质数序列，并对其进行加和。18空间复杂度为 O（m） ，时间复杂度为 O（mn） ，其中 m 为质数的 个数 （例子对应的值为 7），n 为需要找到的最大质数值 （例子对应的值 为 17） 。方法 3：也可以不用