A.逻辑推理题
1.你让工人为你工作7天，给工人的回报是金条。金条分为连接的7段 ，你必须在每天结束时给他们一条金条。如果你只能断两次金条，你怎么给你？ 工人付费？
2.请把一盒蛋糕切成8份，分给8个人，但蛋糕盒里一定要留一份。
小明一家过桥，过桥时是黑夜，所以一定要有灯。现在小明过桥需要1秒钟， 小明的弟弟要3秒，小明的父亲要6秒，小明的母亲要8秒，小明的祖父要12秒。 这座桥最多可以穿过两个人，过桥的速度取决于过桥最慢的速度，灯点燃后30秒就会亮起 熄灭。问：小明一家怎么过桥？
4.一群人开舞会，每个人头上都戴着帽子。帽子只有黑白两种，至少是黑色的。 有一个。每个人都能看到别人帽子的颜色，却看不到自己的。主持人先让大家看看。 看别人头上戴什么帽子，然后关灯。如果有人认为他们戴黑帽子，他们会打自己 一记耳光。第一次关灯，没有声音。所以再开灯，大家再看一遍，关灯的时候还是鸦。 雀无声。直到第三次关灯，才有劈劈啪啪的声音。问有多少人戴着黑色的衣服。 帽子？
5.请估计CN TOWER电视塔的质量。
6.从一楼到十楼的每层电梯门口都有一颗不同尺寸的钻石。你坐电梯 从一楼到十楼，每层电梯门都会打开一次，只能拿一次钻石，问怎么才能得到最好的 大的一颗？
7、U2合唱团必须在17分钟内到达音乐会场，途中必须穿过一座桥，四个人从桥上走过 从同一端开始，你必须帮助他们到达另一端，天很黑，他们只有一个手电筒。 次同时最多可以有两人一起过桥，而过桥的时候必须持有手电筒，所以就得有人把 手电筒带走，来回桥两端。手电筒不能丢失。四个人走路 速度各不同，若两人同行则以较慢者的速度为准。Bono过桥需要1分钟，Edge需花 2分钟过桥，Adam过桥需要5分钟，Larry过桥需要10分钟。他们如何在17分钟内 过桥呢？
8.烧一根不均匀的绳子需要一个小时。如何判断半小时？ ?
为什么下水道的盖子是圆的？
美国有多少加油站(汽车)？
11.每个重量有7克和2克，平衡一个。如何只用这些物品三次盐140克？ 一份分为50克和90克？
12.一列火车以每小时15公里的速度离开洛杉矶，直奔纽约，另一列火车以第一列 从纽约到洛杉矶每小时20公里。如果有一只鸟，每小时30公里以外的速度和 两列火车现在启动，从洛杉矶出发，遇到另一辆车后返回，依次飞往两列火车 行，火车在直道两侧相遇。这只鸟飞了多久？
13.你有两个罐子，50个红色弹球，50个蓝色弹球，随机选择一个罐子。 选择一个放在罐子里的弹球，如何给红色弹球最大的选择机会？在你的计划中，得到它 红球的准确率是多少？
14.想象一下你在镜子前，为什么镜子里的图像可以左右颠倒，但不能颠倒？ 上下？
15.你有四个人装药丸的罐子，每个药丸都有一定的重量。被污染的药丸没有被污染 污染的重量 1.只称一次，如何判断哪罐药被污染？
16.如果你有无限的水，一个3夸脱和一个5夸脱桶，你怎么能准确地说出来？ 4夸脱的水？
17.你有一桶果冻，包括黄色、绿色和红色。闭上眼睛，选择相同的颜色 两个，两个相同颜色。你可以确定你必须有两个相同颜色的水果 冻？
18.将车钥匙插入车门，向哪个方向旋转，打开车锁？
19.如果你能去掉50个州的任何一个，你能去掉哪一个，为什么？
20.一批编号为1~100 所有开关朝上打开的灯操作如下 凡是1 倍数反向拨打一次开关2 倍数反向拨打另一个开关3 倍数反方向 再次拨打开关。 最后询问关闭状态的灯号。
假设一个圆盘像唱机上的唱盘一样旋转。一半是黑色的，一半是白色的 。假设你有一些无限的颜色传感器。为了确定圆盘旋转的方向，你需要在它周围 围摆多少个颜色传感器？它们应该被摆放在什么位置？
假设时钟到了12点。注意时针和分针重叠。一天之内，时针和分针 针重叠多少次？你知道它们重叠的具体时间吗？
中间只有一个数字的两个奇数被称为奇数对，如17和19。证明奇数对 数字之间的数字总能被6整除(假设这两个奇数都大于6)。现在证明不是由三个奇数组成的 的奇数对。
24.一个房间有一扇门(门是关着的)和三盏电灯。屋外有三个开关，分别与之相处 三盏灯相连。您可以随意操作这些开关，但一旦您打开门，您就无法更换开关。 确定每个开关具体管哪盏灯。
25、假设你有8个球，其中一个略微重一些，但是找出这个球的惟一方法是将 将两个球放在天平上进行比较。至少要多少次才能找到这个重球？
下面玩一个拆字游戏，所有字母的顺序都被打乱了。你必须判断这个词是什么 。假设被拆开的字符由五个字母组成： 1.有多少种可能的组合方式？ 2.如果我们知道是哪五个字母，会发生什么？ 3.找出解决这个问题的方法。
27.有四个女人要过桥。他们都站在桥的一边，让他们在17分钟内完成 通过这座桥。那是晚上。他们只有一个手电筒。最多只能让两个人同时过桥。 无论是谁过桥，不管是一两个人，都要带手电筒。手电筒必须传来 传递，不能扔过去。每个女人过桥的速度都不一样，两个人的速度一定要慢。 过桥的速度。 第一个女人：过桥需要1分钟； 第二个女人：过桥需要2分钟； 第三个女人：过桥需要5分钟； 第四个女人：过桥需要10分钟。 例如，如果第一个女人和第四个女人首先过桥，当她们过去时，她们已经过去了10次 分钟。如果让第四个女人把手电筒送回去，那么当她到达桥的另一端时，她会一起去 20分钟后，行动失败了。如何让这四个女人在17分钟内过桥？还有什么其他的？ 法？
28.如果你有两个桶，一个的颜料，另一个是蓝色的颜料。 从蓝色颜料桶中舀一杯，倒入红色颜料桶中，再从红色彩料桶中舀一杯，倒入蓝色彩料桶中 。两桶中红蓝颜料的比例哪个更高？算术证明了这一点。
B：疯狂计算
29、已知两个1~30之间的数字，A知道两数之和，B知道两数之积。 甲问乙："你知道是哪两个数吗？"乙说：不知道； 乙问甲："你知道是哪两个数吗？"甲说：也不知道； 于是，B说：那我就知道了； 后来甲也说：那我也知道； 这两个数是什么？
30、4、4、10、10、加减乘除，怎么出24点？
31、1000！有几位数，为什么？
32、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<0 sign(n)=1 n>0
33.编程求质数的和例F(7)=1 3 5 7 11 13 17=58
34。。。 请只用一支笔画，四条直线，上图9 各点全部连接
三层四层二叉树有多少？
36、1–100000 数列按一定顺序排列，有数字排错，怎么纠错？ 方法。两个数字呢？
链接表和数组有什么区别？
为什么要选择一个链接表？
39.选择算法整理链接表。你为什么选择这种方法？ O(n)时间来做。
说说各种股票分类算法的优缺点。
41.用算法颠倒链接表的顺序。现在不用递归式再做一次 。 42.在循环链接表中插入中插入节点，但不得穿越链接表。
43.用算法整理数组。你为什么选择这种方法？
44、用一种算法使通用字符串相匹配。
45.逆转字符串，优化速度和空间。
46.颠倒句子中单词的顺序，比如"我叫克丽丝"转换为"克丽丝叫我"， 实现最快，移动最少。
47.找到子字符串，优化速度和空间。
48.比较两个字符串，使用O(n)时间和恒量空间。
假设你有一个由1001个整数组成的数组，这些数组是任意排列的，但你 知道所有的整数都在1000(包括1000)之间。另外，除了一个数字出现两次， 所有其他数字只出现一次。假设你只能处理这个数组一次，用算法找出重量 复合的数字。如果您在操作中使用辅助存储方法，您可以找到不使用此方法的方法 公式算法吗？
50.不乘法或加法增加8倍。现在用同样的方法增加7倍。
C：创造性应用
51、营业员小姐由于工作失误，将2万元的笔记本电脑以1.2万元错卖给李先生 ，王小姐的经理怎么写信给李先生，试图把钱还回来？
52.如何将计算机技术应用于100层办公楼的电梯系统？你怎么样？ 优化这个应用程序？工作日的交通、楼层或时间会有什么影响？
53.您如何实施可以随时存储在文件中或从因特网上复制的操作系统？ 防止非法复制保护措施？
54重新设计自动取款机？
假设我们想通过电脑操作微波炉，你会开发什么？样的软件来完成这 个任务？
56、你如何为一辆汽车设计一台咖啡机？
56、如果你想给微软的Word系统增加点内容，你会增加什么样的内容？
57、你会给只有一只手的用户设计什么样的键盘？
58、你会给失聪的人设计什么样的闹钟？
参考答案:
1、day1 给1 段， day2 让工人把1 段归还给2 段， day3 给1 段， day4 归还1 2 段，给4 段。 day5 依次类推……
2、面对这样的怪题，有些应聘者绞尽脑汁也无法分成；而有些应聘者却感到 此题实际很简单，把切成的8份蛋糕先拿出7份分给7人，剩下的1份连蛋糕盒一起分 给第8个人。
4、假如只有一个人戴黑帽子，那他看到所有人都戴白帽，在第一次关灯时就 应自打耳光，所以应该不止一个人戴黑帽子；如果有两顶黑帽子，第一次两人都只 看到对方头上的黑帽子，不敢确定自己的颜色，但到第二次关灯，这两人应该明白 ，如果自己戴着白帽，那对方早在上一次就应打耳光了，因此自己戴的也是黑帽子 ，于是也会有耳光声响起；可事实是第三次才响起了耳光声，说明全场不止两顶黑 帽，依此类推，应该是关了几次灯，有几顶黑帽。
5、比如你怎样快速估算支架和柱子的高度、球的半径，算出各部分的体积等 等。招聘官的说法："就CNTOWER这道题来说，它和一般的谜语或智力题还是有区别 的。我们称这类题为’快速估算题’，主要考的是快速估算的能力，这是开发软件 必备的能力之一。当然，题目只是手段，不是目的，最终得到一个结果固然是需要 的，但更重要的是对考生得出这个结果的过程也就是方法的考察。"Mr Miller为记 者举例说明了一种比较合理的答法，他首先在纸上画出了CN TOWER的草图，然后快 速估算支架和各柱的高度，以及球的半径，算出各部分体积，然后和各部分密度运 算，最后相加得出一个结果。 这一类的题目其实很多，如：“估算一下密西西比河里的水的质量。”“如果你 是田纳西州州长，请估算一下治理好康柏兰河的污染需要多长时间。” “估算一下一个行进在小雨中的人5分钟内身上淋到的雨的质量。” Mr Miller接着解释道：“像这样的题目，包括一些推理题，考的都是人的 ProblemSolving(解决问题的能力)，不是哪道题你记住了答案就可以了的。” 对于公司招聘的宗旨，Mr Miller强调了四点，这些是有创造性的公司普遍注 重的员工素质，是想要到知名企业实现自己的事业梦想的人都要具备的素质和能力 。 要求一：RawSmart（纯粹智慧），与知识无关。 要求二：Long-termPotential(长远学习能力)。 要求三：TechnicSkills(技能)。 要求四：Professionalism(职业态度)。
6、她的回答是：选择前五层楼都不拿，观察各层钻石的大小，做到心中有数 。后五层楼再选择，选择大小接近前五层楼出现过最大钻石大小的钻石。她至今也 不知道这道题的准确答案，"也许就没有准确答案，就是考一下你的思路，"她如是 说。
7、分析：有个康奈尔的学生写文章说他当时在微软面试时就是碰到了这道题 ，最短只能做出在19分钟内过桥。
8、两边一起烧。
9、答案之一：从麻省理工大学一位计算机系教授那里听来的答案，首先在同 等用材的情况下他的面积最大。第二因为如果是方的、长方的或椭圆的，那无聊之 徒拎起来它就可以直接扔进地下道啦！但圆形的盖子嘛，就可以避免这种情况了 )
10、这个乍看让人有些摸不着头脑的问题时，你可能要从问这个国家有多少小 汽车入手。面试者也许会告诉你这个数字，但也有可能说："我不知道，你来告诉 我。"那么，你对自己说，美国的人口是2.75亿。你可以猜测，如果平均每个家庭 （包括单身）的规模是2.5人，你的计算机会告诉你，共有1.1亿个家庭。你回忆起 在什么地方听说过，平均每个家庭拥有1.8辆小汽车，那么美国大约会有1.98亿辆 小汽车。接着，只要你算出替1.98亿辆小汽车服务需要多少加油站，你就把问题解 决了。重要的不是加油站的数字，而是你得出这个数字的方法。
12、答案很容易计算的： 假设洛杉矶到纽约的距离为s 那小鸟飞行的距离就是(s/(15+20))*30。
13、无答案，看你有没有魄力坚持自己的意见。
14、因为人的两眼在水平方向上对称。
15、从第一盒中取出一颗，第二盒中取出2 颗，第三盒中取出三颗。 依次类推，称其总量。
16、比较复杂： Ａ、先用3 夸脱的桶装满，倒入5 夸脱。以下简称3->5) 在5 夸脱桶中做好标记b1，简称b1)。 B、用3 继续装水倒满5 空3 将5 中水倒入3 直到b1 在3 中做标记b2 Ｃ、用5 继续装水倒满3 空5 将3 中水倒入5 直到b2 Ｄ、空3 将5 中水倒入3 标记为b3 Ｅ、装满5 空3 将5 中水倒入3 直到3 中水到b3 结束了，现在5 中水为标准的4 夸脱水。
20、素数是关，其余是开。
29、允许两数重复的情况下 答案为x=1，y=4；甲知道和A=x+y=5，乙知道积B=xy=4 不允许两数重复的情况下有两种答案 答案1：为x=1，y=6；甲知道和A=x+y=7，乙知道积B=xy=6 答案2：为x=1，y=8；甲知道和A=x+y=9，乙知道积B=xy=8 解： 设这两个数为x，y. 甲知道两数之和 A=x+y； 乙知道两数之积 B=xy； 该题分两种情况 ： 允许重复， 有(1 <= x <= y <= 30)； 不允许重复，有(1 <= x < y <= 30)； 当不允许重复，即(1 <= x < y <= 30)； 1)由题设条件：乙不知道答案 <=> B=xy 解不唯一 => B=xy 为非质数 又∵ x ≠ y ∴ B ≠ kk (其中k∈N) 结论(推论1)： B=xy 非质数且 B ≠ kk (其中k∈N) 即：B ∈(6，8，10，12，14，15，18，20…) 证明过程略。 2)由题设条件：甲不知道答案 <=> A=x+y 解不唯一 => A >= 5； 分两种情况： A=5，A=6时x，y有双解 A>=7 时x，y有三重及三重以上解 假设 A=x+y=5 则有双解 x1=1，y1=4； x2=2，y2=3 代入公式B=xy： B1=x1y1=14=4；(不满足推论1，舍去) B2=x2y2=23=6； 得到唯一解x=2，y=3即甲知道答案。 与题设条件：“甲不知道答案"相矛盾 ， 故假设不成立，A=x+y≠5 假设 A=x+y=6 则有双解。 x1=1，y1=5； x2=2，y2=4 代入公式B=xy： B1=x1y1=15=5；(不满足推论1，舍去) B2=x2y2=24=8； 得到唯一解x=2，y=4 即甲知道答案 与题设条件："甲不知道答案"相矛盾 故假设不成立，A=x+y≠6 当A>=7时 ∵ x，y的解至少存在两种满足推论1的解 B1=x1y1=2*(A-2) B2=x2y2=3(A-3) ∴ 符合条件 结论(推论2)：A >= 7 3)由题设条件：乙说"那我知道了” =>乙通过已知条件B=xy及推论(1)(2)可以得出唯一解 即： A=x+y， A >= 7 B=xy， B ∈(6，8，10，12，14，15，16，18，20…) 1 <= x < y <= 30 x，y存在唯一解 当 B=6 时：有两组解 x1=1，y1=6 x2=2，y2=3 (∵ x2+y2=2+3=5 < 7∴不合题意，舍去) 得到唯一解 x=1，y=6 当 B=8 时：有两组解 x1=1，y1=8 x2=2，y2=4 (∵ x2+y2=2+4=6 < 7∴不合题意，舍去) 得到唯一解 x=1，y=8 当 B>8 时：容易证明均为多重解 结论： 当B=6时有唯一解 x=1，y=6当B=8时有唯一解 x=1，y=8 4)由题设条件：甲说"那我也知道了" => 甲通过已知条件A=x+y及推论(3)可以得出唯一解 综上所述，原题所求有两组解： x1=1，y1=6 x2=1，y2=8 当x<=y时，有(1 <= x <= y <= 30)； 同理可得唯一解 x=1，y=4
31、 解：1000 Lg(1000!)=sum(Lg(n)) n=1 用3 段折线代替曲线可以得到 10(0+1)/2+90(1+2)/2+900(2+3)/2=2390 作为近似结果，好象1500~3000 都算对
32、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<0 ：sign(n)=1 n>0 解:只要注意[sign(n-m)*sign(m-n)+1]在n=m 处取1 其他点取0 就可以了
34、米字形的画就行了
59、答案是和家人告别.
二、18题 1、考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币，每次必需且只能放置一枚硬币，要求硬币完全置于桌面内（不能有一部分悬在桌子外面），并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币，谁就输了。游戏的先行者还是后行者有必胜策略？这种策略是什么？ 答案：先行者在桌子中心放置一枚硬币，以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样，只要后行者能放，先行者一定也有地方放。先行者必胜。
2、 用线性时间和常数附加空间将一篇文章的单词（不是字符）倒序。
答案：先将整篇文章的所有字符逆序（从两头起不断交换位置相对称的字符）；然后用同样的办法将每个单词内部的字符逆序。这样，整篇文章的单词顺序颠倒了，但单词本身又被转回来了。
3、 用线性时间和常数附加空间将一个长度为n的字符串向左循环移动m位（例如，"abcdefg"移动3位就变成了"defgabc"）。
答案：把字符串切成长为m和n-m的两半。将这两个部分分别逆序，再对整个字符串逆序。
4、一个矩形蛋糕，蛋糕内部有一块矩形的空洞。只用一刀，如何将蛋糕切成大小相等的两块？
答案：注意到平分矩形面积的线都经过矩形的中心。过大矩形和空心矩形各自的中心画一条线，这条线显然把两个矩形都分成了一半，它们的差当然也是相等的。
5、 一块矩形的巧克力，初始时由N x M个小块组成。每一次你只能把一块巧克力掰成两个小矩形。最少需要几次才能把它们掰成N x M块1x1的小巧克力？
答案：N x M - 1次显然足够了。这个数目也是必需的，因为每掰一次后当前巧克力的块数只能增加一，把巧克力分成N x M块当然需要至少掰N x M - 1次。
6、如何快速找出一个32位整数的二进制表达里有多少个"1"？用关于"1"的个数的线性时间？
答案1（关于数字位数线性）：for(n=0; b; b >>= 1) if (b & 1) n++;
答案2（关于"1"的个数线性）：for(n=0; b; n++) b &= b-1;
7、 一个大小为N的数组，所有数都是不超过N-1的正整数。用O(N)的时间找出重复的那个数（假设只有一个）。一个大小为N的数组，所有数都是不超过N+1的正整数。用O(N)的时间找出没有出现过的那个数（假设只有一个）。
答案：计算数组中的所有数的和，再计算出从1到N-1的所有数的和，两者之差即为重复的那个数。计算数组中的所有数的和，再计算出从1到N+1的所有数的和，两者之差即为缺少的那个数。
8、 给出一行C语言表达式，判断给定的整数是否是一个2的幂。
答案：(b & (b-1)) == 0
9、地球上有多少个点，使得从该点出发向南走一英里，向东走一英里，再向北走一英里之后恰好回到了起点？
答案：“北极点”是一个传统的答案，其实这个问题还有其它的答案。事实上，满足要求的点有无穷多个。所有距离南极点1 + 1/(2π)英里的地方都是满足要求的，向南走一英里后到达距离南极点1/(2π)的地方，向东走一英里后正好绕行纬度圈一周，再向北走原路返回到起点。事实上，这仍然不是满足要求的全部点。距离南极点1 + 1/(2kπ)的地方都是可以的，其中k可以是任意一个正整数。
10、A、B两人分别在两座岛上。B生病了，A有B所需要的药。C有一艘小船和一个可以上锁的箱子。C愿意在A和B之间运东西，但东西只能放在箱子里。只要箱子没被上锁，C都会偷走箱子里的东西，不管箱子里有什么。如果A和B各自有一把锁和只能开自己那把锁的钥匙，A应该如何把东西安全递交给B？
答案：A把药放进箱子，用自己的锁把箱子锁上。B拿到箱子后，再在箱子上加一把自己的锁。箱子运回A后，A取下自己的锁。箱子再运到B手中时，B取下自己的锁，获得药物。
11、 一对夫妇邀请N-1对夫妇参加聚会（因此聚会上总共有2N人）。每个人都和所有自己不认识的人握了一次手。然后，男主人问其余所有人（共2N-1个人）各自都握了几次手，得到的答案全部都不一样。假设每个人都认识自己的配偶，那么女主人握了几次手？
答案：握手次数只可能是从0到2N-2这2N-1个数。除去男主人外，一共有2N-1个人，因此每个数恰好出现了一次。其中有一个人(0)没有握手，有一个人(2N-2)和所有其它的夫妇都握了手。这两个人肯定是一对夫妻，否则后者将和前者握手（从而前者的握手次数不再是0）。除去这对夫妻外，有一个人(1)只与(2N-2)握过手，有一个人(2N-3)和除了(0)以外的其它夫妇都握了手。这两个人肯定是一对夫妻，否则后者将和前者握手（从而前者的握手次数不再是1）。以此类推，直到握过N-2次手的人和握过N次手的人配成一对。此时，除了男主人及其配偶以外，其余所有人都已经配对。根据排除法，最后剩下来的那个握手次数为N-1的人就是女主人了。
12、两个机器人，初始时位于数轴上的不同位置。给这两个机器人输入一段相同的程序，使得这两个机器人保证可以相遇。程序只能包含“左移n个单位”、“右移n个单位”，条件判断语句If，循环语句while，以及两个返回Boolean值的函数“在自己的起点处”和“在对方的起点处”。你不能使用其它的变量和计数器。
答案：两个机器人同时开始以单位速度右移，直到一个机器人走到另外一个机器人的起点处。然后，该机器人以双倍速度追赶对方。程序如下。
while(!at_other_robots_start) { move_right 1 } while(true) { move_right 2 }
13、 如果叫你从下面两种游戏中选择一种，你选择哪一种？为什么？
a. 写下一句话。如果这句话为真，你将获得10美元；如果这句话为假，你获得的金钱将少于10美元或多于10美元（但不能恰好为10美元）。
b. 写下一句话。不管这句话的真假，你都会得到多于10美元的钱。
答案：选择第一种游戏，并写下“我既不会得到10美元，也不会得到10000000美元”。
14、你在一幢100层大楼下，有21根电线线头标有数字1..21。这些电线一直延伸到大楼楼顶，楼顶的线头处标有字母A..U。你不知道下面的数字和上面的字母的对应关系。你有一个电池，一个灯泡，和许多很短的电线。如何只上下楼一次就能确定电线线头的对应关系？
答案：在下面把2,3连在一起，把4到6全连在一起，把7到10全连在一起，等等，这样你就把电线分成了6个“等价类”，大小分别为1, 2, 3, 4, 5, 6。然后到楼顶，测出哪根线和其它所有电线都不相连，哪些线和另外一根相连，哪些线和另外两根相连，等等，从而确定出字母A..U各属于哪个等价类。现在，把每个等价类中的第一个字母连在一起，形成一个大小为6的新等价类；再把后5个等价类中的第二个字母连在一起，形成一个大小为5的新等价类；以此类推。回到楼下，把新的等价类区别出来。这样，你就知道了每个数字对应了哪一个原等价类的第几个字母，从而解决问题。
15、某种药方要求非常严格，你每天需要同时服用A、B两种药片各一颗，不能多也不能少。这种药非常贵，你不希望有任何一点的浪费。一天，你打开装药片A的药瓶，倒出一粒药片放在手心；然后打开另一个药瓶，但不小心倒出了两粒药片。现在，你手心上有一颗药片A，两颗药片B，并且你无法区别哪个是A，哪个是B。你如何才能严格遵循药方服用药片，并且不能有任何的浪费？
答案：把手上的三片药各自切成两半，分成两堆摆放。再取出一粒药片A，也把它切成两半，然后在每一堆里加上半片的A。现在，每一堆药片恰好包含两个半片的A和两个半片的B。一天服用其中一堆即可。
16、 你在一个飞船上，飞船上的计算机有n个处理器。突然，飞船受到外星激光武器的攻击，一些处理器被损坏了。你知道有超过一半的处理器仍然是好的。你可以向一个处理器询问另一个处理器是好的还是坏的。一个好的处理器总是说真话，一个坏的处理器总是说假话。用n-2次询问找出一个好的处理器。
答案：给处理器从1到n标号。用符号a->b表示向标号为a的处理器询问处理器b是不是好的。首先问1->2，如果1说不是，就把他们俩都去掉（去掉了一个好的和一个坏的，则剩下的处理器中好的仍然过半），然后从3->4开始继续发问。如果1说2是好的，就继续问2->3，3->4，……直到某一次j说j+1是坏的，把j和j+1去掉，然后问j-1 -> j+2；或者从j+2 -> j+3开始发问，如果前面已经没有j-1了（之前已经被去掉过了）。注意到你始终维护着这样一个“链”，前面的每一个处理器都说后面那个是好的。这条链里的所有处理器要么都是好的，要么都是坏的。当这条链越来越长，剩下的处理器越来越少时，总有一个时候这条链超过了剩下的处理器的一半，此时可以肯定这条链里的所有处理器都是好的。或者，越来越多的处理器都被去掉了，链的长度依旧为0，而最后只剩下一个或两个处理器没被问过，那他们一定就是好的了。另外注意到，第一个处理器的好坏从来没被问过，仔细想想你会发现最后一个处理器的好坏也不可能被问到（一旦链长超过剩余处理器的一半，或者最后没被去掉的就只剩这一个了时，你就不问了），因此询问次数不会超过n-2。
17、一个圆盘被涂上了黑白二色，两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向？
答案：你可以把两个相机放在圆盘上相近的两点，然后观察哪个点先变色。事实上，只需要一个相机就够了。控制相机绕圆盘中心顺时针移动，观察颜色多久变一次；然后让相机以相同的速度逆时针绕着圆盘中心移动，再次观察变色的频率。可以断定，变色频率较慢的那一次，相机的转动方向是和圆盘相同的。
18、有25匹马，速度都不同，但每匹马的速度都是定值。现在只有5条赛道，无法计时，即每赛一场最多只能知道5匹马的相对快慢。问最少赛几场可以找出25匹马中速度最快的前3名？（百度2008年面试题）
每匹马都至少要有一次参赛的机会，所以25匹马分成5组，一开始的这5场比赛是免不了的。接下来要找冠军也很容易，每一组的冠军在一起赛一场就行了（第6场）。最后就是要找第2和第3名。我们按照第6场比赛中得到的名次依次把它们在前5场比赛中所在的组命名为A、B、C、D、E。即：A组的冠军是第6场的第1名，B组的冠军是第6场的第2名……每一组的5匹马按照他们已经赛出的成绩从快到慢编号：
A组：1，2，3，4，5 B组：1，2，3，4，5 C组：1，2，3，4，5 D组：1，2，3，4，5 E组：1，2，3，4，5
从现在所得到的信息，我们可以知道哪些马已经被排除在3名以外。只要已经能确定有3匹或3匹以上的马比这匹马快，那么它就已经被淘汰了。可以看到，只有上表中粗体的那5匹马是有可能为2、3名的。即：A组的2、3名；B组的1、2名，C组的第1名。取这5匹马进行第7场比赛，第7场比赛的前两名就是25匹马中的2、3名。故一共最少要赛7场。
这道题有一些变体，比如64匹马找前4名。方法是一样的，在得出第1名以后寻找后3名的候选竞争者就可以了。
三、16题 ◆1． 有一个长方形蛋糕，切掉了长方形的一块（大小和位置随意），你怎样才能直直的一刀下去，将剩下的蛋糕切成大小相等的两块？
答案：将完整的蛋糕的中心与被切掉的那块蛋糕的中心连成一条线。这个方法也适用于立方体！请注意，切掉的那块蛋糕的大小和位置是随意的，不要一心想着自己切生日蛋糕的方式，要跳出这个圈子。
◆2． 有三筐水果，一筐装的全是苹果，第二筐装的全是橘子，第三筐是橘子与苹果混在一起。筐上的标签都是骗人的，（比如，如果标签写的是橘子，那么可以肯定筐里不会只有橘子，可能还有苹果）你的任务是拿出其中一筐，从里面只拿一只水果，然后正确写出三筐水果的标签。
提示：从标着“混合”标签的筐里拿一只水果，就可以知道另外两筐装的是什么水果了。
◆3． 你有八个球。其中一个有破损，因此比其他球轻了一些。你有一架天平用来比较这些球的重量。如果只称两次，如何找出有破损的那个球？
◆4． 为什么下水道的井盖是圆的？
提示：方形的对角线比边长！
其他答案：1圆形的井盖可以由一个人搬动，因为它可以在地上滚。2圆形的井盖不必为了架在井口上而旋转它的位置。
◆5． 美国有多少辆车？
◆6． 你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。如果你只能将金条切割两次，你怎样分给这些工人？
◆7． 一列时速15英里的火车从洛杉矶出发，驶向纽约。另外一列时速20英里的火车从纽约出发，驶向洛杉矶。如果一只鸟以每小时25英里的速度飞行，在同一时间从洛杉矶出发，在两列火车之间往返飞行，到火车相遇时为止，鸟飞了多远？
提示：想想火车的相对速度。
◆8． 你有两个罐子，分别装着50个红色的玻璃球和50个蓝色的玻璃球。随意拿起一个罐子，然后从里面拿出一个玻璃球。怎样最大程度地增加让自己拿到红色球的机会？利用这种方法，拿到红色球的几率有多大？
◆9． 假设你站在镜子前，抬起左手，抬起右手，看看镜中的自己。当你抬起左手时，镜中的自己抬起的似乎是右手。可是当你仰头时，镜中的自己也在仰头，而不是低头。为什么镜子中的影像似乎颠倒了左右，却没有颠倒上下？
◆10． 你有5瓶药，每个药丸重10克，只有一瓶受到污染的药丸重量发生了变化，每个药丸重9克。给你一个天平，你怎样一次就能测出哪一瓶是受到污染的药呢？
答案：
1 给5个瓶子标上1、2、3、4、5。
2 从1号瓶中取1个药丸，2号瓶中取2个药丸，3号瓶中取3个药丸，4号瓶中取4个药丸，5号瓶中取5个药丸。
3 把它们全部放在天平上称一下重量。
4 现在用1×10＋2×10＋3×10＋4×10＋5×10的结果减去测出的重量。
5 结果就是装着被污染的药丸的瓶子号码。
◆11． 如果你有一个容量为5夸脱的水桶和一个容量为3夸脱的水桶，怎样准确地量出4夸脱的水？ 1.装满5夸脱水，并把部分水倒入3跨脱水桶，剩下2夸脱。 2.把3夸脱水倒掉 3.将5夸脱桶中的2夸脱水倒入3夸脱桶中。 4.将5夸脱桶再次装满 5.将5夸脱桶中的水倒入已有2夸脱水的3夸脱桶中，这样5夸脱桶中剩下的水刚好是4夸脱
◆12． 在开汽车的锁时，应该往哪个方向旋转钥匙？
◆13． 如果你可以移动50个州中的任何一个，你会挑哪个，为什么？
◆14． 有4条狗（4只蚂蚁或4个人）分别在一个广场的4个角落里。突然，它们同时以同样的速度追赶在自己顺时针方向的一个人，而且会紧追这个目标不放。它们需要多少时间才能相遇，相遇地点在哪里？
提示：它们将在广场中央相遇，所跑的距离与它们跑的路线无关。
◆15．从空中放下两列火车，每列火车都带着降落伞，降落到一条没有尽头的笔直的铁道上。两列火车之间的距离不清楚。两列车都面向同一个方向。在落地后，降落伞掉在地上，与火车分离。两列火车都有一个微芯片，可以控制它们的运动。两个芯片是相同的。两列火车都不知道自己的位置。你需要在芯片中写入编码，让这两列火车相遇。每行编码都有一定的执行命令的时间。
你能使用以下指令（而且只能用这些指令）：
MF—让火车朝前开
MB—让火车朝后开
IF（P）—如果火车旁边有降落伞，这个条件就得到了满足。
GOTO
答案：
A：MF
IF（P）
GOTO B
GOTO A
B：MF
GOTO B
解释：第一行只是让它们离开各自的降落伞。必须让它们离开自己的降落伞，这样后面的火车才能发现前面火车的降落伞，这样就满足了一个条件，它们就可以跳出起初遵守的编码。它们起初都在A这部分循环，直到后面的火车发现前面火车的降落伞，这时就转入B：并陷入B的循环。前面的火车还是没有找到降落伞，所以就不停地在A里面循环。由于每行编码都有一定的执行命令时间，完成A循环就比完成B费时，因此后面的火车（在B循环中）最终将赶上前面的火车。
16.有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐分成50、90克各一份？ （1） 把2克重的砝 放在天平左端，分盐于天平两端直到平衡，此时，左端有盐69克，右端有盐71克。（2）取下天平左端的2克砝码换上7克重的砝码， 端重（69+7）76克，右端仍重71克，从左端取出5克盐后，天平两端平衡，这时左端 余64克盐。在取下天平两端物品。 （3） 用刚才称出的5克盐当作砝码，与2克、7克砝码合成14克砝码。从64克盐 取出14克，恰好剩下50克盐。则其余盐的重量就是90克
四、18题
1.有A、B两个水杯，都没有刻度，也不允许做刻度。A杯装满水是5升，B杯装满水是3升。不借助别的任何工具，只用这两个杯子如何精确的得到4升水 1.先用B倒进A三升水 2.B再盛满，将A倒满：B内剩1升。 3.将A倒空：将B内的一升倒进A。 4.B再盛满3升。倒进A，则得4升。 2.给你一盒蛋糕，请你切成八份，分给在场的八个人，但蛋糕盒里还要有一份。 首先先把蛋糕切成八份，讲其中的七份分给在场的七个人，然后把蛋糕盒和其中的一分蛋糕分给没有蛋糕的人，就可以达到目的。
3.有一个说谎岛，上面居住着人还有吸血鬼，有一年岛上流行瘟疫，有一半的人和吸血鬼疯了，于是岛上有神志清醒的人和精神错乱的人，还有神志清醒的吸血鬼和精神错乱的吸血鬼，其中神志清醒的人和精神错乱的吸血鬼只说真话，而精神错乱的人和神志清醒的吸血鬼只说假话，并且他们回答问题只说“是”或“不是”；有一天岛上来了一位“逻辑博士”在岛上遇见了P，博士问了一个问题就分出他是人还是吸血鬼，博士又问了一个问题就分辨出他是神志清醒的还是精神错乱的。请写出博士问得两个问题；写出你的思路。 条件是：神志清醒的人和精神错乱的吸血鬼只说真话 精神错乱的人和神志清醒的吸血鬼之说假话 4.一天有个年轻人来到王老板店里买了一件礼物,这件礼物成本18元,标价21元。结果这个年轻人掏出100元来买这件礼物,王老板当时没有零钱,用那100元向街坊换了100元的零钱,找给年轻人79元,但是街坊后来发现那100元是**,王老板无奈还了街坊100元,问题是:王老板在这次交易中到底损失了多少钱??? 礼物成本价：18元 标 价：21元 老板找了79元给年轻人，而年轻人的100元是假的这样的话年轻人是得了一件成本价18元的礼物外加79元一共得到97元老板在这次的交易中损失了97元
5、一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少 有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看 看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自 己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦 雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑 帽子？ 假如只有一个人戴黑帽子，那他看到所有人都戴白帽，在第一次关灯时就 应自打耳光，所以应该不止一个人戴黑帽子；如果有两顶黑帽子，第一次两人都只 看到对方头上的黑帽子，不敢确定自己的颜色，但到第二次关灯，这两人应该明白 ，如果自己戴着白帽，那对方早在上一次就应打耳光了，因此自己戴的也是黑帽子 ，于是也会有耳光声响起；可事实是第三次才响起了耳光声，说明全场不止两顶黑 帽，依此类推，应该是关了几次灯，有几顶黑帽。 6.烧一根不均匀的绳要用一个小时，如何用它来判断半个小时 ? 两头一起烧、从绳子中间烧、将绳子对折烧
7.想象你在镜子前，请问，为什么镜子中的影像可以颠倒左右，却不能颠倒 上下？ 因为人的两眼在水平方向上对称
1．一个粗细均匀的长直管子，两端开口，里面有4个白球和4个黑球，球的直径、两端开口的直径等于管子的内径，现在白球和黑球的排列是wwwwbbbb，要求不取出任何一个球，使得排列变为bbwwwwbb。 2．一只蜗牛从井底爬到井口，每天白天蜗牛要睡觉，晚上才出来活动，一个晚上蜗牛可以向上爬3尺，但是白天睡觉的时候会往下滑2尺，井深10尺，问蜗牛几天可以爬出来？ 3．在一个平面上画1999条直线最多能将这一平面划分成多少个部分？ 4．在太平洋的一个小岛上生活着土人，他们不愿意被外人打扰，一天，一个探险家到了岛上，被土人抓住，土人的祭司告诉他，你临死前还可以有一个机会留下一句话，如果这句话是真的，你将被烧死，是假的，你将被五马分尸，可怜的探险家如何才能活下来？ 5．怎样种四棵树使得任意两棵树的距离相等。 6．27个小运动员在参加完比赛后，口渴难耐，去小店买饮料，饮料店搞促销，凭三个空瓶可以再换一瓶，他们最少买多少瓶饮料才能保证一人一瓶？ 7．有一座山，山上有座庙，只有一条路可以从山上的庙到山脚，每周一早上8点，有一个聪明的小和尚去山下化缘，周二早上8点从山脚回山上的庙里，小和尚的上下山的速度是任意的，在每个往返中，他总是能在周一和周二的同一钟点到达山路上的同一点。例如，有一次他发现星期一的8点30和星期二的8点30他都到了山路靠山脚的3/4的地方，问这是为什么？ 8．有两根不均匀分布的香，每根香烧完的时间是一个小时，你能用什么方法来确定一段15分钟的时间？ 英文面试题目 1. Describe your greatest achievement in the past 4-5 years? 2. What are your short & long term career objectives? What do you think is the most ideal job for you? 3. Why do you want to join IBM? What do you think you can contribute to IBM? [NextPage]
五、IBM笔试3题
字母矩阵题目（15分钟） 给你一个矩阵： （一） （二） （三） （四） （五） 1 a b c d e 2 b c a e d 3 c b e a d 4 c e d b a 5 e d a c b 回答以下问题。 （1）将第一行和第四行交换后，第一行第四个字母下面的左边的下面的右边的字母是 。 ①a ②b ③c ④d ⑤e （2）将所有出现在d左边的字母从矩阵中删掉。将所有出现在a左边的c字母从矩阵中删掉。如果矩阵中剩下的字母的种类的数目大于3，答案为原矩阵中左上方至右下方对角线上出现两次的字母。如果矩阵中剩下的字母的种类的数目小于或者等于3，答案为原矩阵中右上至左下对角线上出现4次的字母是 。 ①a ②b ③c ④d ⑤e （3）将所有的a用4替换，所有的d用2替换，哪一列的总和 最大 ①第1列 ②第2列 ③第3列 ④第4列 ⑤第五列 （4）从左上角的字母开始，顺时针沿矩阵外围，第4次出现的字母是 。 ①a ②b ③c ④d ⑤e （5）沿第5列从上到下，接着沿第3列从下到上，接着沿第4列从上到下，接着沿第1列从下到上，接着沿第2列从上到下，第1个出现5次的字母是 。 ①a ②b ③c ④d ⑤e （6）从左上角的字母开始，顺时针沿矩阵外围，第4次出现的字母是以下哪个 。 ①a ②b ③c ④d ⑤e 智力题 1．有50家人家，每家一条狗。有一天警察通知，50条狗当中有病狗，行为和正常狗不一样。每人只能通过观察别人家的狗来判断自己家的狗是否生病，而不能看自己家的狗，如果判断出自己家的狗病了，就必须当天一枪打死自己家的狗。结果，第一天没有枪声，第二天没有枪声，第三天开始一阵枪响，问：一共死了几条狗？ 2．已知两个数字为1~30之间的数字，甲知道两数之和，乙知道两数之积，甲问乙：“你知道是哪两个数吗？”乙说：“不知道”。乙问甲：“你知道是哪两个数吗？”甲说：“也不知道”。于是，乙说：“那我知道了”，随后甲也说：“那我也知道了”，这两个数是什么？ 3．一个经理有三个女儿，三个女儿的年龄加起来等于13，三个女儿的年龄乘起来等于经理自己的年龄。有一个下属已知道经理的年龄，但仍不能确定经理的三个女儿的年龄，这时经理说只有一个女儿的头发是黑的，然后这个下属就知道了经理的三个女儿的年龄。请问三个女儿的年龄分别是多少？为什么？ 答案： 1．死了3条（第几天枪响就有几条）。 简单分析：从有一条不正常的狗开始，显然第一天将会听到一声枪响。这里的要点是你只需站在那条不正常狗的主人的角度考虑。 有两条的话思路继续，只考虑有两条不正常狗的人，其余人无需考虑。通过第一天他们了解了对方的信息。第二天杀死自己的狗。换句话说每个人需要一天的时间证明自己的狗是正常的。有三条的话，同样只考虑那三个人，其中每一个人需要两天的时间证明自己的狗是正常的狗。 2．1和4，或者4和7。 3．分别是2，2，9。 简单分析： 1 1 11 11 伪穷举，呵呵 1 2 10 20 1 3 9 27 1 4 8 32 1 5 7 35 1 6 6 36 在所有的可能性中，只有这两个相同，如果经理的年龄为其他，则他下属就可以确定三个人分别为几岁了 2 2 9 36 所以只有两种可能：1，6，6或者2，2，9。如果是1，6，6的话，那么两个同样大的6岁的孩子应该都是黑头发 2 3 8 40 所以只有2，2，9比较合理，大的那个是黑头发，另外两个是黄毛丫头 2 4 7 56 2 5 6 60 3 3 7 42 3 4 6 72 3 5 5 75 4 4 5 80
六、 15个Google面试题以及答案 1、 村子里有100对夫妻，其中每个丈夫都瞒着自己的妻子偷情。村里的每个妻子都能立即发现除自己丈夫之外的其他男人是否偷情，唯独不知道她自己的丈夫到底有没有偷情。村里的规矩不容忍通奸。任何一个妻子，一旦能证明自己的男人偷情，就必须当天把他杀死。村里的女人全都严格照此规矩办事。一天，女头领出来宣布，村里至少有一个丈夫偷情。请问接下来会发生什么事？
答案：这是一个典型的递归问题。一旦所有的妻子都知道至少有一个男人出轨，我们就可以按递归方式来看待这个流程。先让我们假设只有一个丈夫偷情。则他的妻子见不到任何偷情的男人，因此知道这个人就是自己丈夫，她当天就会杀了他。假如有两个丈夫偷情，则他俩的妻子只知道不是自己丈夫的那一个男人偷情。因此她会等上一天看那个人有没有被杀死。假如第一天没人被杀死，她就能确定她自己的丈夫也偷了情。依此类推，假如有100个丈夫偷情，则他们能安全活上99 天，直到100天时，所有妻子把他们全都杀死。
应聘职位：产品经理
2、假设在一段高速公路上，30分钟之内见到汽车经过的概率是0.95。那么，在10分钟内见到汽车经过的概率是多少?(假设缺省概率固定)
答案：这题的关键在于0.95是见到一辆或多辆汽车的概率，而不是仅见到一辆汽车的概率。在30分钟内，见不到任何车辆的概率为0.05。因此在10分钟内见不到任何车辆的概率是这个值的立方根，而在10分钟内见到一辆车的概率则为1减去此立方根，也就是大约63%。
应聘职位：产品经理
3、有四个人要在夜里穿过一条悬索桥回到宿营地。可是他们只有一支手电，电池只够再亮17分钟。过桥必须要有手电，否则太危险。桥最多只能承受两个人 同时通过的重量。这四个人的过桥速度都不一样：一个需要1分钟，一个需要2分钟，一个需要5分钟，还有一个需要10分钟。他们如何才能在17分钟之内全部 过桥？
答案：1和2一起过(2分钟);1返回(3分钟);5和10一起过(13分钟);2返回(15分钟);1和2一起过(17分钟)。全体安全过桥。
应聘职位：产品经理
4、你和一个朋友去参加聚会。聚会算上你们一共10人。。。你的朋友想要跟你打个赌：你在这些人每找到一个和你生日相同的，你就赢1块钱。他在这些人里每找到一个和你生日不同的人，他就赢2块钱。你该不该打这个赌？
答案：不算闰年的话，别人跟你生日相同的概率是1/365;跟你生日不同的概率是364/365。因此不要打这个赌。
应聘职位：产品经理
5、如果你看到时钟上面的时间是3：15，那么其时针和分针之间的角度是多少？答案不是零)
答案：7.5度。时钟上每一分钟是6度(360度/60分钟)。时针每小时从一个数字走到下一个数字(此例中为从3点到4点)，也就是30度。因为此题中时间刚好走过1/4小时，因此时针走完30度的1/4，也就是7.5度。
应聘职位：产品经理
6、将一根木条折成3段之后，可以形成一个三角形的概率有多大?答案：因为题目中没有说要求木条必须首尾相连的做成三角形，因此答案是100%。任何长度的三根木条都可以形成一个三角形。
应聘职位：产品经理
7、南非有个延时问题。请对其加以分析。
答案：这显然是个非常模糊的问题，因此没有唯一的正确答案。比较好的回答应该是由被面试者展示自己对“延时”概念的熟悉程度以及发挥自己的想象力，构想出一个有趣的延时问题并对其提供一个有趣的解决方案。
应聘职位：产品经理
8、在一个两维平面上有三个不在一条直线上的点。请问能够作出几条与这些点距离相同的线？
答案：三条。将两点之间联成一条线段。在这条线段与第三点之间正中的位置，做一条与此线段平行的直线，即为一条距三点等距的线。然后按此方法对其余两点的组合做出另外两条来。
应聘职位：软件工程师
9、2的64次方是多少？
答案：如果你不是因为坐在面试室里，手边没有计算器的话，应该可以很容易找到答案，即1.84467441 乘以10的19次方。
应聘职位：软件工程
10、假设你在衣橱里挂满衬衫，很难从中挑出某一件来。请问你打算怎样整理一下，使得它们容易挑选？
答案：此题没有固定答案。考验的是被面试者在解决问题方面的想象力和创造性。我们觉得读者”Dude”的这个答案可能会给Google留下深刻印象：把它们按布料的种类进行哈希(HASH)组合。然后每类再按2-3-4树或红黑树(都是计算机算法)排序。
应聘职位：软件工程师
11、给你一副井字棋(Tic Tac Toe)。。。你来写一个程序，以整个游戏和一个玩家的名字为参数。此函数需返回游戏结果，即此玩家是否赢了。首先你要决定使用哪种数据结构处理游戏。你 还要先讲出使用哪种算法，然后写出代码。注意：这个游戏中的某些格子里可能是空的。你的数据结构需要考虑到这个条件。
答案：所需要的数据结构应为二元字符数列。调用此函数检查6种条件，判断是否有赢家。其中第6种条件就是看是否还有空格。如果有赢家，则字符判断玩家是X还是O。因此你需要一个旗标。如果有赢家则返回此值并结束游戏，如果没有则继续游戏。
应聘职位：软件工程师
12、为1万亿个数排序需要多长时间?请说出一个靠谱的估计。
答案：这又是一个没有标准答案的题目。目的是考察被面试者的创造性。我们倾向于两位读者给出的简单答案：用归并排序法(Merge Sort)排序。平均情况下为O(1,000,000,000,000 Log 1,000,000,000,000)。最差情况下为O(1,000,000,000,000 Log 1,000,000,000,000)。现在可以做到每秒10亿次的运算，所以大约应需要3000秒。
应聘职位：软件工程师
13、请设计一个“蛙跳”游戏的算法，并写出方案的代码。。。
答案：这个游戏的目标是引导一个青蛙避开来往车辆，横穿一条繁忙的公路。你可以用一个数列来代表一条车道。将方案简化成一条N车道的公路。我们只找到 一个对此问题的解答，它来自Glassdoor.com网站：“一个方法是写一个递归算法来决定何时等待，何时跳进下一个车道。这由下条车道中是否有逐渐 接近的障碍物来决定。”
应聘职位：软件工程师
14、Google每年收到多少份软件工程师的简历?这也是在考察应试者是否有能力把问题简单明确化，并提出创造性的解决方案。
答案：一个“量化报酬分析师”职位的求职者，应该知道2008年Google雇佣了3400人。估计其中75%，即2550人，应该是工程师，并且 Google和哈佛的录取率类似，即从申请人中取3%。由此可知应该收到大约85000简历(85000 x 3% = 2550)
应聘职位：量化报酬分析师
15、给你一个数字链表。链表到头之后又会从头开始(循环链表)。请写出寻找链表中最小数字的最高效算法。找出此链表中的任意给定数字。链表中的 数字总是不断增大的，但是你不知道循环链表从何处开始。例：38, 40, 55, 89, 6, 13, 20, 23, 36。
答案：我们最喜欢的答案来自读者”dude”：建立临时指针并从根上开始。(循环链表大多数情况下都有向前或向后指针。)判断是向前更大还是向后更 大。如果向前更大则知道已达到链表最后，又重新位于链表开始位置。如果向前更大，那你可以向后搜寻并进行数字比较。如果既没有根也没有指针指向链表，那么 你的数据就丢失在内存中了。
应聘职位：量化报酬分析师
七、微软面试智力题 (附答) 参考答案2
1、day1 给1 段， day2 让工人把1 段归还给2 段， day3 给1 段， day4 归还1 2 段，给4 段。 day5 依次类推…… 2、面对这样的怪题，有些应聘者绞尽脑汁也无法分成;而有些应聘者却感到 此题实际很简单，把切成的8份蛋糕先拿出7份分给7人，剩下的1份连蛋糕盒一起分 给第8个人。 4、假如只有一个人戴黑帽子，那他看到所有人都戴白帽，在第一次关灯时就 应自打耳光，所以应该不止一个人戴黑帽子;如果有两顶黑帽子，第一次两人都只 看到对方头上的黑帽子，不敢确定自己的颜色，但到第二次关灯，这两人应该明白 ，如果自己戴着白帽，那对方早在上一次就应打耳光了，因此自己戴的也是黑帽子 ，于是也会有耳光声响起;可事实是第三次才响起了耳光声，说明全场不止两顶黑 帽，依此类推，应该是关了几次灯，有几顶黑帽。 5、比如你怎样快速估算支架和柱子的高度、球的半径，算出各部分的体积等 等。招聘官的说法："就CNTOWER这道题来说，它和一般的谜语或智力题还是有区别 的。我们称这类题为’快速估算题’，主要考的是快速估算的能力，这是开发软件 必备的能力之一。当然，题目只是手段，不是目的，最终得到一个结果固然是需要 的，但更重要的是对考生得出这个结果的过程也就是方法的考察。"Mr Miller为记 者举例说明了一种比较合理的答法，他首先在纸上画出了CN TOWER的草图，然后快 速估算支架和各柱的高度，以及球的半径，算出各部分体积，然后和各部分密度运 算，最后相加得出一个结果。 这一类的题目其实很多，如：“估算一下密西西比河里的水的质量。”“如果你 是田纳西州州长，请估算一下治理好康柏兰河的污染需要多长时间。” “估算一下一个行进在小雨中的人5分钟内身上淋到的雨的质量。” Mr Miller接着解释道：“像这样的题目，包括一些推理题，考的都是人的 ProblemSolving(解决问题的能力)，不是哪道题你记住了答案就可以了的。” 对于公司招聘的宗旨，Mr Miller强调了四点，这些是有创造性的公司普遍注 重的员工素质，是想要到知名企业实现自己的事业梦想的人都要具备的素质和能力 。 要求一：RawSmart(纯粹智慧)，与知识无关。 要求二：Long-termPotential(长远学习能力)。 要求三：TechnicSkills(技能)。 要求四：Professionalism(职业态度)。 6、她的回答是：选择前五层楼都不拿，观察各层钻石的大小，做到心中有数 。后五层楼再选择，选择大小接近前五层楼出现过最大钻石大小的钻石。她至今也 不知道这道题的准确答案，"也许就没有准确答案，就是考一下你的思路，"她如是 说。 7、分析：有个康奈尔的学生写文章说他当时在微软面试时就是碰到了这道题 ，最短只能做出在19分钟内过桥。 8、两边一起烧。 9、答案之一：从麻省理工大学一位计算机系教授那里听来的答案，首先在同 等用材的情况下他的面积最大。第二因为如果是方的、长方的或椭圆的，那无聊之 徒拎起来它就可以直接扔进地下道啦!但圆形的盖子嘛，就可以避免这种情况了 ) 10、这个乍看让人有些摸不着头脑的问题时，你可能要从问这个国家有多少小 汽车入手。面试者也许会告诉你这个数字，但也有可能说："我不知道，你来告诉 我。"那么，你对自己说，美国的人口是2.75亿。你可以猜测，如果平均每个家庭 (包括单身)的规模是2.5人，你的计算机会告诉你，共有1.1亿个家庭。你回忆起 在什么地方听说过，平均每个家庭拥有1.8辆小汽车，那么美国大约会有1.98亿辆 小汽车。接着，只要你算出替1.98亿辆小汽车服务需要多少加油站，你就把问题解 决了。重要的不是加油站的数字，而是你得出这个数字的方法。 12、答案很容易计算的： 假设洛杉矶到纽约的距离为s 那小鸟飞行的距离就是(s/(15+20))*30。 13、无答案，看你有没有魄力坚持自己的意见。 14、因为人的两眼在水平方向上对称。 15、从第一盒中取出一颗，第二盒中取出2 颗，第三盒中取出三颗。 依次类推，称其总量。 16、比较复杂： A、先用3 夸脱的桶装满，倒入5 夸脱。以下简称3->5) 在5 夸脱桶中做好标记b1，简称b1)。 B、用3 继续装水倒满5 空3 将5 中水倒入3 直到b1 在3 中做标记b2 C、用5 继续装水倒满3 空5 将3 中水倒入5 直到b2 D、空3 将5 中水倒入3 标记为b3 E、装满5 空3 将5 中水倒入3 直到3 中水到b3 结束了，现在5 中水为标准的4 夸脱水。 20、素数是关，其余是开。
29、允许两数重复的