微软笔试题：利用天平砝码，三次将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的数量记录下来，这样每次计算只是一次查找操作。

微软笔试题：判断一个数是不是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）。

Google:

谷歌笔试题：判断一个自然数是否是某个数的平方。当然不能使用开方运算。

假设待判断的数字是 N。

方法1：

遍历从1到N的数字，求取平方并和N进行比较。

如果平方小于N，则继续遍历；如果等于N，则成功退出；如果大于N，则失败退出。

复杂度为O(n^0.5)。

方法2：

使用二分查找法，对1到N之间的数字进行判断。

复杂度为O(log n)。

方法3：

由于

(n+1)^2 =n^2 + 2n + 1， = ... = 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)

注意到这些项构成了等差数列（每项之间相差2）。

所以我们可以比较 N-1， N - 1 - 3， N - 1 - 3 - 5 ... 和0的关系。

如果大于0，则继续减；如果等于0，则成功退出；如果小于 0，则失败退出。

复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法，所以速度会更快些。

谷歌笔试题：如何随机选取1000个关键字

给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？

定义长度为1000的数组。

对于数据流中的前1000个关键字，显然都要放到数组中。

对于数据流中的的第n（n>1000）个关键字，我们知道这个关键字被随机选中的概率为 1000/n。所以我们以 1000/n 的概率用这个关键字去替换数组中的随机一个。这样就可以保证所有关键字都以 1000/n的概率被选中。

对于后面的关键字都进行这样的处理，这样我们就可以保证数组中总是保存着1000个随机关键字。

谷歌笔试题：将下列表达式按照复杂度排序

将下列表达式按照复杂度排序

2^n

n^Googol (其中 Googol = 10^100)

n!

n^n

按照复杂度从低到高为

n^Googol

2^n

n!

n^n

谷歌笔试题：在半径为1的圆中随机选取一点

假设圆心所在位置为坐标元点(0, 0)。

方法1.

在x轴[-1, 1]，y轴[-1, 1]的正方形内随机选取一点。然后判断此点是否在圆内（通过计算此点到圆心的距离）。如果在圆内，则此点即为所求；如果不在，则重新选取直到找到为止。

正方形的面积为4，圆的面积为pi，所以正方形内的随机点在圆内的概率是 pi / 4。

方法2.

从[0, 2*pi)中随机选一个角度，对应于圆中的一条半径，然后在此半径上选一个点。但半径上的点不能均匀选取，选取的概率应该和距圆心的长度成正比，这样才能保证随机点在圆内是均匀分布的。

谷歌笔试题：给定一个未知长度的整数流，如何随机选取一个数

方法1.

将整个整数流保存到一个数组中，然后再随机选取。

如果整数流很长，无法保存下来，则此方法不能使用。

方法2.

如果整数流在第一个数后结束，则我们必定会选第一个数作为随机数。

如果整数流在第二个数后结束，我们选第二个数的概率为1/2。我们以1/2的概率用第2个数替换前面选的随机数，得到满足条件的新随机数。

....

如果整数流在第n个数后结束，我们选第n个数的概率为1/n。我们以1/n的概率用第n个数替换前面选的随机数，得到满足条件的新随机数。

....

利用这种方法，我们只需保存一个随机数，和迄今整数流的长度即可。所以可以处理任意长的整数流。

谷歌笔试题：设计一个数据结构，其中包含两个函数，1.插入一个数字，2.获得中数。并估计时间复杂度。

1. 使用数组存储。

插入数字时，在O(1)时间内将该数字插入到数组最后。

获取中数时，在O(n)时间内找到中数。（选数组的第一个数和其它数比较，并根据比较结果的大小分成两组，那么我们可以确定中数在哪组中。然后对那一组按照同样的方法进一步细分，直到找到中数。）

2. 使用排序数组存储。

插入数字时，在O(logn)时间内找到要插入的位置，在O(n)时间里移动元素并将新数字插入到合适的位置。

获得中数时，在O(1)复杂度内找到中数。

3. 使用大根堆和小根堆存储。

使用大根堆存储较小的一半数字，使用小根堆存储较大的一半数字。

插入数字时，在O(logn)时间内将该数字插入到对应的堆当中，并适当移动根节点以保持两个堆数字相等（或相差1）。

获取中数时，在O(1)时间内找到中数。

给定一个固定长度的数组，将递增整数序列写入这个数组。当写到数组尾部时，返回数组开始重新写，并覆盖先前写过的数。

请在这个特殊数组中找出给定的整数。

假设数组为a[0, 1, ..., N-1]。

我们可以采用类似二分查找的策略。

首先比较a[0]和a[N/2]，如果a[0] < a[N/2]，则说明a[0,1,...,N/2]为递增子序列，否则另一部分是递增子序列。

然后判断要找的整数是否在递增子序列范围内。如果在，则使用普通的二分查找方法继续查找；如果不在，则重复上面的查找过程，直到找到或者失败为止。

给定两个已排序序列，找出共同的元素。

不妨假设序列是从小到大排序的。定义两个指针分别指向序列的开始。

如果指向的两个元素相等，则找到一个相同的元素；如果不等，则将指向较小元素的指针向前移动。

重复执行上面的步骤，直到有一个指针指向序列尾端。

谷歌笔试题：找到链表的倒数第m个节点。

方法1：

首先遍历链表，统计链表的长度N。

然后再次遍历链表，找到第N-m个节点，即为倒数第m个节点。

方法2：

使用两个指针，并使它们指向的节点相距m-1个。

然后同时向前移动两个指针，当一个指针指最后一个节点时，第二个指针指向倒数第m个节点。

两个方法的复杂度都是O(n)。

但是当N较大而m较小时，方法2可能会更快一些。因为方法2能更好利用CPU的缓存。

更多阅读：

http://baike.baidu.com/view/2089.htm CPU -> 缓存

谷歌笔试题：给定一个排序数组，如何构造一个二叉排序树？

采用递归算法。

选取数组中间的一个元素作为根节点，左边的元素构造左子树，右边的节点构造有子树。

谷歌笔试题：数组中是否有两个数的和为10

1.比较任意两个数的和是否为10。如

for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { .... }}

复杂度为O(n*n)。

2.将数组排序后，对每个数m，使用二分查找在数组中寻找10-m。

复杂度为O(nlogn)。

3.将数组存储到hash_set中去，对每个数m，在hash_set中寻找10-m。

复杂度为O(n)。

4.如果数组很大，超过内存的容量，可以按照hash(max(m, 10-m))%g，将数据分到g个小的group中。然后对每个小的group进行单独处理。

复杂度为O(n)。

IBM:

IBM笔试题：有一座山，山上有座庙，只有一条路可以从山上的庙到山脚，每周一早上8点，有一个聪明的小和尚去山下化缘，周二早上8点从山脚回山上的庙里，小和尚的上下山的速度是任意的，在每个往返中，他总是能在周一和周二的同一钟点到达山路上的同一点。例如，有一次他发现星期一的8点30和星期二的8点30他都到了山路靠山脚的3/4的地方，问这是为什么？

答案一：

可以用画图法来解释：

在一个平面上，x 轴代表从8点开始的时间，y 轴代表距庙的距离。那么从庙到山脚就是一条从左下到右上的一条曲线，从山脚到庙就是一条从左上到右下的一条曲线。考虑到两条曲线的起始点和终点，两线必定交于一点。

答案二：

还有一种更简单的解释，是让两个人从山顶和山脚同时相向而行，一定有一个时刻相遇，这样就证

没有直线时有一个空间；（1）

1条直线时，这条这些可以将这个空间分成两个；（1+1）

2条直线时，第二条直线可以和第一条直线相交，这样第二条直线可以将两个空间分成四个；（1+1+2）

....

注意到画每条直线时能增加多少个空间，取决于此直线从多少个空间中通过。

而从多少个空间中通过，取决于和多少条直线相交。

例如，如果一条直线和其它5条直线相交，那么最大可以通过6个空间，此直线可以增加6个子空间。

画每条直线时，能相交的直线数为总的已经画过的直线。

所以总的空间数最多为

1+1+2+3+...+1999 = 1999001

IBM笔试题：不均匀分布的香，每根香烧完的时间是一个小时，你能用什么方法来确定一段15分钟的时间？

第一根点燃两头，第二根只点一头。

当第一根烧完时，时间过去了30分钟，所以第二根还能烧30分钟。这时点燃第二根的另外一头，第二根香还能烧的时间就是15分钟。

IBM笔试题：有27个人去买矿泉水，商店正好在搞三个空矿泉水瓶可以换一瓶矿泉水的活动，他们至少要买几瓶矿泉水才能每人喝到一瓶矿泉水？

答案一：

如果开始买3瓶，那么可以四个人喝，并且还能剩一个空瓶。

如果开始买9瓶，可以13个人喝，最后还剩一个空瓶。

如果开始买18瓶，那么26个人喝，可以剩下两个空瓶。

如果开始买19瓶，那么27个人喝，最后剩下三个空瓶。所以最少买19瓶。

如果可以向商店先欲借一个空瓶，那么买18瓶，最后一个人喝完再将空瓶还给商店。

那么买18瓶也可以满足要求。

答案二：

x + x/3 + x/3^2 + ... = x/(1-1/3)=27

x=18;

IBM笔试题：c++中引用和指针有什么不同？指针加上什么限制等于引用？

引用不是一个变量，它只表示该引用名是目标变量名的一个别名，它本身不是一种数据类型，因此引用本身不占存储单元，系统也不给引用分配存储单元。引用一经确定就不能修改。

指针是一个变量，需要在内存中分配空间，此空间中存储所指对象的地址。由于指针是一个普通变量，所以其值还可以通过重新赋值来改变。

把指针定义为const后，其值就不能改变了，功能和引用类似，但有本质的区别。

IBM笔试题：一普查员问一女人，“你有多少个孩子，他们多少岁？”

女人回答：“我有三个孩子，他们的岁数相乘是36，岁数相加就等于旁边屋的门牌号码。“普查员立刻走到旁边屋，看了一看，回来说：“我还需要多少资料。”女人回答：“我现在很忙，我最大的孩子正在楼上睡觉。”普查员说：”谢谢，我己知道了。”

问题：那三个孩子的岁数是多少。

36 = 1 × 2 × 2 × 3 × 3

所有的可能为

1，1，36；sum = 38

1，2，18；sum = 21

1，3，12；sum = 16

1，4，9；sum = 14

1，6，6；sum = 13

2，2，9；sum = 13

2，3，6；sum = 11

3，3，4；sum = 10

由于普查员知道了年龄和之后还是不能确定每个孩子的年龄，所以可能性为

1，6，6；sum = 13

2，2，9；sum = 13

由于最大（暗含只有一个最大）的孩子在睡觉，所以只可能是

2，2，9；sum = 13