微软笔试题目分享

时间:2015-01-26 编辑:1081 手机版

  微软笔试题目分享(一)

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

  2、F(n)=1 n>8 n<12

  F(n)=2 n<2

  F(n)=3 n=6

  F(n)=4 n=other

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

  sign(n)=0 n=0

  sign(n)=-1 n<

  sign(n)=1 n>0

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

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

  前提:

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

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

  提示:

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

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

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

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

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

  问:谁养鱼?

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

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

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

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

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

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

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

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

  7.绿房子的人养狗。

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

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

  微软笔试题分享(二)

  写程序找出二叉树的深度

  一个树的深度等于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=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之间的差值。

  将一个句子按单词反序

  将一个句子按单词反序。比如 “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 进行按位与操作(x&1),如果结果为1,说明最后一位是1,统计值加1。

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

  方法3:

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

  快速求取一个整数的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(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:

  也可以不用除法,而用加法。

  申请一个足够大的空间,每个bit对应一个整数,开始将所有的bit都初始化为0。

  对于已知的质数(开始时只有2),将此质数所有的倍数对应的bit都改为1,那么最小的值为0的bit对应的数就是一个质数。对新获得的质数的倍数也进行标注。

  对这样获得的质数序列累加就可以获得质数和。

  空间复杂度为O(n),时间负责度为O(n),其中n为需要找到的最大质数值(例子对应的值为17)。

本文已影响
微软笔试题目分享相关推荐