首页 > 剑指offer > 程序员有趣的面试智力题
2014
01-10

程序员有趣的面试智力题

        偶然间在网上看到几个原来没见过的面试智力题,有几个题目在国内流传相当广,什么n个人怎么分饼最公平,屋里的三个灯泡分别由哪个开关控制,三架飞机环游世界,用火柴和两根绳子测量45分钟之类的题目,火星得已经可以考古了,这里就不再说了。

     1、考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币,每次必需且只能放置一枚硬币,要求硬币完全置于桌面内(不能有一部分悬在桌子外面),并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币,谁就输了。游戏的先行者还是后行者有必胜策略?这种策略是什么?
答案:先行者在桌子中心放置一枚硬币,以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样,只要后行者能放,先行者一定也有地方放。先行者必胜。

    2、 用线性时间和常数附加空间将一篇文章的单词(不是字符)倒序。
答案:先将整篇文章的所有字符逆序(从两头起不断交换位置相对称的字符);然后用同样的办法将每个单词内部的字符逆序。这样,整篇文章的单词顺序颠倒了,但单词本身又被转回来了。

    3、 用线性时间和常数附加空间将一个长度为n的字符串向左循环移动m位(例如,”abcdefg”移动3位就变成了”defgabc”)。
答案:把字符串切成长为m和n-m的两半。将这两个部分分别逆序,再对整个字符串逆序。

    4、一个矩形蛋糕,蛋糕内部有一块矩形的空洞。只用一刀,如何将蛋糕切成大小相等的两块?
答案:注意到平分矩形面积的线都经过矩形的中心。过大矩形和空心矩形各自的中心画一条线,这条线显然把两个矩形都分成了一半,它们的差当然也是相等的。

    5、 一块矩形的巧克力,初始时由N x M个小块组成。每一次你只能把一块巧克力掰成两个小矩形。最少需要几次才能把它们掰成N x M块1×1的小巧克力?
答案: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组:12,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名的候选竞争者就可以了。

     19、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

20、有7克、2克砝码各一个,天平一只,如何只用这些物品三次将140克的盐分成50、90克各一份?
答:第一步:把140克盐分成两等份,每份70克。
第二步:把天平一边放上2+7克砝码,另一边放盐,这样就得到9克和61克分开的盐。
第三步:将9克盐和2克砝码放在天平一边,另一边放盐,这样就得到11克和50克。于是50和90就分开了。

     21、有三筐水果,一筐装的全是苹果,第二筐装的全是橘子,第三筐是橘子与苹果混在一起。筐上的标签都是骗人的,(比如,如果标签写的是橘子,那么可以肯定筐里不会只有橘子,可能还有苹果)你的任务是拿出其中一筐,从里面只拿一只水果,然后正确写出三筐水果的标签。
答:从贴有苹果和橘子标签的筐中拿出一个水果,如果是苹果,说明这个筐中全是苹果,那么贴苹果标签的筐里装的全是桔子,则贴有桔子标签的筐中装的苹果和桔子;如果拿出的一个水果是桔子,说明这个筐中全是桔子,那么贴桔子标签的筐里装的全是苹果,贴苹果标签的筐里装的是苹果和桔子。

      22、题目如下:
0 1 2 3 4 5 6 7 8 9
_ _ _ _ _ _ _ _ _ _

在横线上填写数字,使之符合要求。
要求如下:对应的数字下填入的数,代表上面的数在下面出现的次数,比如3下面是1,代表3要在下面出现一次。

正确答案是:0 1 2 3 4 5 6 7 8 9
6 2 1 0 0 0 1 0 0 0

我的思路是:因为第二行的数字是第一行的数在下面出现的次数,下面10个格子,总共10次。。。所以第2排数字之和为10。

首先从0入手,先填9,肯定不可能,9下面要是1,只剩8个位填0,不够填8,8下面要填1,1要至少填2,后面不用再想,因为已经剩下7个位置,不够填0……如此类推。到0下面填6的时候就得到我上面的答案了。。

其实可以推出这个题目的两个关键条件:
1、第2排数字之和为10。
2、两排数字上下相乘之和也是10!
满足这两个条件的就是答案,下面来编写程序实现!

//原始数值: 0,1,2,3,4,5,6,7,8,9
//出现次数: 6,2,1,0,0,0,1,0,0,0
#include "iostream"
using namespace std;
#define len 10
class NumberTB
{
private:
    int top[len];
    int bottom[len];
    bool success;
public:
    NumberTB();
    int *getBottom();
    void setNextBottom();
    int getFrequecy(int num);
};
NumberTB::NumberTB()
{
    success = false;
    //format top
    for(int i = 0; i < len; i++)
    {
        top[i] = i;
    }
}
int *NumberTB::getBottom()
{
    int i = 0;
    while(!success)
    {
        i++;
        setNextBottom();
    }
    return bottom;
}
//set next bottom
void NumberTB::setNextBottom()
{
    bool reB = true;
    for(int i = 0; i < len; i++)
    {
        int frequecy = getFrequecy(i);
        if(bottom[i] != frequecy)
        {
            bottom[i] = frequecy;
            reB = false;
        }
    }
    success = reB;
}
//get frequency in bottom
int NumberTB::getFrequecy(int num) //此处的num 即指上排的数i
{
    int count = 0;
    for(int i = 0; i < len; i++)
    {
        if(bottom[i] == num)
            count++;
    }
    return count; //cout 即对应frequecy
}
int main(void)
{
	int i;
    NumberTB nTB;
    int *result = nTB.getBottom();
	cout<<"原始数值:";
	for(i=0;i<10;i++)
		cout<<i<<"  ";
	cout<<endl;
	cout<<"出现次数:";
    for(i = 0; i < len; i++)
    {
        cout << *result++ <<"  ";
    }
	cout<<endl;
	system("pause");
    return 0;
}

原文地址:http://blog.csdn.net/hackbuteer1/article/details/6726419


  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. 第一题还有个解释:没说桌子有多大,可以假设桌子和硬币一样大,肯定是先手胜