资源预览内容
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
亲,该文档总共7页全部预览完了,如果喜欢就下载吧!
资源描述
IT 名企面试:微软笔试题(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 = GetDepth(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 克了.第二种方法:1.先把 140 克盐分为两份,每份 70 克2.在把 70 克分为两份,每份 35 克3.然后把两个砝码放在天平两边,把 35 克面粉分成两份也放在两边(15+7=20+2)现在有四堆面粉 70,35,15,20,分别组合得到70+20=9035+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 之间的差值。微软笔试题:将一个句子按单词反序将一个句子按单词反序。比如 “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:让此整数除以 2,如果余数为 1,说明最后一位是 1,统计值加 1。将除得的结果进行上面运算,直到结果为 0。方法 2:考虑除法复杂度有些高,可以使用移位操作代替除法。将 x 和 1 进行按位与操作(xwhile (x) xx = x 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(n2),其中 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) 。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号