微软谷歌笔试题目.docx

微软谷歌笔试题目微软谷歌笔试题目微软和谷歌公司是我国的著名公司，微软和谷歌公司的笔试题目有哪些呢?微软笔试题：地球上有多少个满足这样条件的点站在地球上的某一点，向南走一公里，然后向东走一公里，最后向北走一公里，回到了原点。地球上有多少个满足这样条件的点?北极点满足这个条件。距离南极点很近的一个圈上也满足这个条件。在这个圆圈上，向南走一公里，然后向东走一公里恰好绕南极点一圈，向北走一公里回到原点。所以地球上总共有无数点满足这个条件。或者首先，在地球表面上，南北走向是沿着经度方向，东西是沿着纬度方向。如果你一直往北走就会达到北极点，往南走就到了南极点。因此，向南走一公里，然后向东走一公里，最后向北走一公里，回到了原点，一种情况就是，出发点是在北极点，这样向南走一公里，然后向东走任意几公里，最后向北走一公里，最后都会回到北极点;其次，可以这么认为如果从A点向南走一公里到达B点，那么若向东走一公里能回到B，那么最后向北走一公里，就能回到了原点A。这样就可以先找出在南北极点附近找出绕一周只有1公里的圈，那么这个圈落在南极附近时，只要往北推1公里，此时该圈上的点都能满足;若这个圈落在北极附近时，能不能往北推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微软笔试题：正确标注水果篮有三个水果篮。其中一个里面只有苹果，一个里面只有橘子，另外一个既有苹果又有橘子。每个水果篮上都有标签，但标签都是错的。如何检查某个水果篮中的一个水果，然后正确标注每个水果篮?从标注成既有苹果也有橘子的水果篮中选取一个进行检查。如果是橘子，则此篮中只有橘子;标有橘子的水果篮中只有苹果;标有苹果的水果篮中既有苹果也有橘子。如果是苹果，则此篮中只有苹果;标有苹果的水果篮中只有橘子;标有橘子的水果篮中既有苹果也有橘子。微软笔试题：不利用浮点运算，画一个圆不利用浮点运算，在屏幕上画一个圆(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。这个方法可以在原字符串上进行，只需要几个整数变量来保持指针即可，空间复杂度低。微软笔试题：计算nbit的整数中有多少bit为1设此整数为x。方法1：让此整数除以2，如果余数为1，说明最后一位是1，统计值加1。将除得的结果进行上面运算，直到结果为0。方法2：考虑除法复杂度有些高，可以使用移位操作代替除法。将x和1进行按位与操作(x&1)，如果结果为1，说明最后一位是1，统计值加1。将x向右一位(x>>1)，重复上面过程，直到移位后结果为0。方法3：如果需要统计很多数字，并且内存足够大，可以考虑将每个数对应的bit为1的数量记录下来，这样每次计算只是一次查找操作。微软笔试题：判断一个数是不是2的n次幂设要判断的数是无符号整数X。首先判断X是否为0，如果为0则不是2的n次幂，返回。X和X-1进行按位与操作，如果结果是0，则说明这个数是2的n次幂;如果结果非0，则说明这个数不是2的n次幂。证明：如果是2的n次幂，则此数用二进制表示时只有一位是1，其它都是0。减1后，此位变成0，后面的位变成1，所以按位