微软笔试题

                                        微软在 IT界依然是数一数二的企业了，不少人的梦想都是进入微软公司。那 么在这之前的面试以及笔试就需要进行一下准备了。那么这里就来看看小编为大 家 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 的微软笔试题吧。  微软笔试题：写程序找出二叉树的深度 一个树的深度等于 max（左子树深度，右子树深度）+1。可以使用递归实现。  假设节点为定义为  1. struct Node { 2. Node* left; 3. Node* right; 4. }; 5. int GetDepth(Node* root) { 6. if (NULL == root) { 7. return 0; 8. } 9. int left_depth = GetDepth(root->left); 10. int right_depth = GetDepth(root->right); 11. return left_depth > right_depth ? left_depth + 1 : right_depth + 1; 12. } 微软笔试题：利用天平砝码，三次将 140克的盐 分成 50、90克两份？ 有一个天平，2克和 7克砝码各一个。如何利用天平砝码在三次内将 140克 盐分成 50，90克两份。  第一种 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ：  第一次:先称  7+2克盐  (相当于有三个法码 2,7,9)  过来人求职论坛 http://bbs.guolairen.com/                                         第二次:称 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  微软笔试题：地球上有多少个满足这样条件的点 站在地球上的某一点，向南走一公里，然后向东走一公里，最后向北走一公 里，回到了原点。地球上有多少个满足这样条件的点?  北极点满足这个条件。  距离南极点很近的一个圈上也满足这个条件。在这个圆圈上，向南走一公里， 然后向东走一公里恰好绕南极点一圈，向北走一公里回到原点。  过来人求职论坛 http://bbs.guolairen.com/                                         所以地球上总共有无数点满足这个条件。  或者  首先，在地球 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 面上，南北走向是沿着经度方向，东西是沿着纬度方向。如 果你一直往北走就会达到北极点，往南走就到了南极点。因此，向南走一公里， 然后向东走一公里，最后向北走一公里，回到了原点，一种情况就是，出发点是 在北极点，这样向南走一公里，然后向东走任意几公里，最后向北走一公里，最 后都会回到北极点；  其次，可以这么认为如果从 A点向南走一公里到达 B点，那么若向东走一公 里能回到 B，那么最后向北走一公里，就能回到了原点 A。这样就可以先找出在 南北极点附近找出绕一周只有 1公里的圈，那么这个圈落在南极附近时，只要往 北推 1公里，此时该圈上的点都能满足；若这个圈落在北极附近时，能不能往北 推 1公里我就不 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 了。反正在南极附近能找到任意多个点就能回到这个问题了  微软笔试题：正确标注水果篮 有三个水果篮。其中一个里面只有苹果，一个里面只有橘子，另外一个既有 苹果又有橘子。每个水果篮上都有标签，但标签都是错的。如何检查某个水果篮 中的一个水果，然后正确标注每个水果篮？  从标注成既有苹果也有橘子的水果篮中选取一个进行检查。  如果是橘子，则此篮中只有橘子；标有橘子的水果篮中只有苹果；标有苹果 的水果篮中既有苹果也有橘子。  过来人求职论坛 http://bbs.guolairen.com/                                         如果是苹果，则此篮中只有苹果；标有苹果的水果篮中只有橘子；标有橘子 的水果篮中既有苹果也有橘子。  微软笔试题：不利用浮点运算，画一个圆 不利用浮点运算，在屏幕上画一个圆  (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之间的差值。  微软笔试题：将一个句子按单词反序 将一个句子按单词反序。比如 “hi baidu com mianshiti”，反序后变为  “mianshiti com baidu hi”。  可以分两步走：  第一步按找字母反序，“hi baidu com mianshiti” 变为 “itihsnaim moc udiab  ih”。  过来人求职论坛 http://bbs.guolairen.com/                                         第二部将每个单词中的字母反序，“itihsnaim moc udiab ih” 变成 “mianshiti  com baidu hi”。  这个方法可以在原字符串上进行，只需要几个整数变量来保持指针即可，空 间复杂度低。  微软笔试题：计算 n bit的整数中有多少 bit 为 1 设此整数为 x。  方法 1：  让此整数除以 2，如果余数为 1，说明最后一位是 1，统计值加 1。  将除得的结果进行上面运算，直到结果为 0。  方法 2：  考虑除法复杂度有些高，可以使用移位操作代替除法。  将  x 和  1 进行按位与操作（x&1），如果结果为 1，说明最后一位是 1，统 计值加 1。  将 x 向右一位（x >> 1），重复上面过程，直到移位后结果为 0。  方法 3：  如果需要统计很多数字，并且内存足够大，可以考虑将每个数对应的 bit为 1 的数量 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 下来，这样每次计算只是一次查找操作。  过来人求职论坛 http://bbs.guolairen.com/                                         1. int n = 0;while (x) 2. { 3. xx = x & (x - 1); 4. n++; 5. } 6. 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。  过来人求职论坛 http://bbs.guolairen.com/                                         微软笔试题：三只蚂蚁不相撞的概率是多少 在三角形的三个顶点上各有一只蚂蚁，它们向另一个顶点运动，目标随机（可 能为另外两个顶点的任意一个）。问三只蚂蚁不相撞的概率是多少？  如果蚂蚁顺时针爬行记为 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}，请写出一个高 效算法(时间比空间更重要)。  过来人求职论坛 http://bbs.guolairen.com/                                         建立一个 hash_map，key为链表中已经遍历的节点内容，开始时为空。  从头开始遍历链表中的节点：  ‐ 如果节点内容已经在 hash_map中存在，则删除此节点，继续向后遍历；  ‐ 如果节点内容不在 hash_map中，则保留此节点，将节点内容添加到 hash_map中，继续向后遍历。  微软笔试题：小明一家 5口如何过桥？ 小明一家过一座桥，过桥时是黑夜，所以必须有灯。现在小明过桥要 1秒， 小明的弟弟要 3秒，小明的爸爸要 6秒，小明的妈妈要 8秒，小明的爷爷要 12 秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后 30秒就会熄灭。问：小明一家如何过桥？  小明与弟弟过去，小明回来，用 4s；  妈妈与爷爷过去，弟弟回来，用 15s；  小明与弟弟过去，小明回来，用 4s；  小明与爸爸过去，用 6s；  总共用 29s。  题目的关键是让速度差不多的一起走，免得过于拖累较快的一个人。  微软笔试题：编一个程序求质数的和 过来人求职论坛 http://bbs.guolairen.com/                                         编一个程序求质数的和，例如 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：  过来人求职论坛 http://bbs.guolairen.com/                                         过来人求职论坛 http://bbs.guolairen.com/ 也可以不用除法，而用加法。  申请一个足够大的空间，每个 bit对应一个整数，开始将所有的 bit都初始化 为 0。  对于已知的质数（开始时只有 2），将此质数所有的倍数对应的 bit都改为 1， 那么最小的值为 0的 bit对应的数就是一个质数。对新获得的质数的倍数也进行 标注。  对这样获得的质数序列累加就可以获得质数和。  空间复杂度为 O(n)，时间负责度为 O(n)，其中 n为需要找到的最大质数值（例 子对应的值为 17）。