讨论一个算法，GOOGLE的一个面试题

stormspire

浏览: 14677 次
性别:
来自: 上海

最近访客更多访客>>

kanghonghai

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

other

算法 Google 面试 C C++

这个是google的一个面试题，觉得挺有意思的，问题是这样的：一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问最少得比多少场才能知道跑得最快的5匹马。[也许至少会产生误解，换成最少，就是考虑你的算法的最坏情况下]

以上就是这个问题。其实拿起笔来，仔细看看倒是不是很难。 (后来仔细想了想，其实并不简单)

如果推而广之，有N匹马，有M个赛道，试问要至少多少场比赛才能知道跑得最快的Y匹马。

在CSDN上看到另外一个题，http://topic.csdn.net/u/20081017/14/826303de-1871-4e50-89e8-47ed56f49acc.html
实际上就是把N换成256， M换成2， Y换成3
-----
另外有个朋友提出的描述方法浅显易懂，反正25匹马要分5组的，大家在下列统一的马匹归类下讨论比较容易

前5轮应该没有什么争议，就是5个队都比一场，暂且这样排名，名字在前面的快些。
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 B5
C组 C1 C2 C3 C4 C5
D组 D1 D2 D3 D4 D5
E组 E1 E2 E3 E4 E5

第6轮目前比较统一的做法是让每个组的第一，即A1,B1,C1,D1, E1比一场，假设 A1>B1>C1>D1>E1 那么这个时候可以淘汰一些马了，淘汰的用--表示，如下:
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 --
C组 C1 C2 C3 -- --
D组 D1 D2 -- -- --
E组 E1 -- -- -- --

分歧就在第7轮了，我也没想清楚最佳方法，我就不在第一个帖子说了。

分享到：

portet建立遇到的问题集锦 1 | 武汉江滩

2008-10-21 17:50
浏览 4645
评论(122)
论坛回复 / 浏览 (118 / 60053)
分类:编程语言
查看更多

102 楼 zhanglubing927 2008-11-27

我的答案是:至少7场,最多10场.
我相信这个应该是正确答案,毕竟我看来前面所有人都分析.

但我开始也很疑惑,我看题目就想到了外部排序,准备使用归并排序来做.
把25匹马分成5组,分别排序(比赛),然后把有序的5组两两合并.最后合并为一个有序的组.然后取前5名.搞定问题.

不过当我写出归并排序后,再看题意,感觉不应该这样做,毕竟是最好的方式找到前5名.而不是一个排序的问题.至少不需要知道所有的名次.

改变思路后,发现留言已经到了11页.哈哈...我就不多说了,高兴自己还是想出来了.

随便把归并的代码贴上来吧

package com.jason.stu.algorithm;

import java.util.Arrays;

/**
 * 归并排序
 * 
 * @author Jason
 * 
 */
public class MergeSort {

	public static int[] merge(int[] a, int[] b) {

		int m = 0, n = 0, i = 0;
		int size = a.length + b.length;
		int[] result = new int[size];

		while (m < a.length && n < b.length) {
			result[i++] = (a[m] < b[n]) ? a[m++] : b[n++];
		}

		if (m == a.length)
			for (int t = n; t < b.length; t++)
				result[i++] = b[t];
		else if (n == b.length)
			for (int t = m; t < a.length; t++)
				result[i++] = a[t];

		return result;
	}

	public static void main(String[] args) {
		int[] data1 = { 0, 6, 2, 3, 4 };
		int[] data2 = { 1, 7, 8, 5 };

		Arrays.sort(data1);
		Arrays.sort(data2);

		for (int n : merge(data1, data2))
			System.out.println(n);
	}
}

101 楼 qinjim1986 2008-11-26

前五轮，不用我多说了。关键是下来的。
分析：
如果有可能，总的前五名中,最多会有几个每一轮的第五名。答案很显然是1个。那么第四，第三，第二，第一呢。分别是，一个，一个，两个,五个。
问题的关键出现了。就因为第三名最多只会出现一个，如果把所有的第三名都比一下的话，比的结果是，只取其中的第一名，以外的马都可以排除，这样我们就可以排除12匹马。
如图：(第六轮结果)
1 1 1 1 1
2 2 2 2 2
3 * * * *
4 * * * *
5 * * * *
同理我们如果在第六轮比的是所有的第二名的话，也会排除(12匹)。
1 1 1 1 1
2 2 * * *
3 3 * * *
4 4 * * *
5 5 * * *
（小小的一个发现，就当抛砖引玉。我还没得出最终结论！）

100 楼 hurricane1026 2008-11-26

phpxer 写道

看到最后，有点失望。如果换成是5000匹马，取最快的2000批，按照上面列位的穷举法... 怎么就没有人把这个算法用算数式表达出来呢？

这里的同志哥大多都把cs专业学没了。

99 楼 kingre79 2008-11-26

应该9场就可以出来
前5场：
A1>A2>A3>A4>A5
B1>B2>B3>B4>B5
C1>C2>C3>C4>C5
D1>D2>D3>D4>D5
E1>E2>E3>E4>E5
第6场：A3>B3>C3>D3>E3,剩下
A1>A2>A3>A4>A5
B1>B2
C1>C2
D1>D2
E1>E2
第7场：A3,B1,C1,D1,E1比较，有下面几个结果：
1）A3>B1>C1>D1>E1，结果为
A1>A2>A3>A4>A5
B1>B2
C1
此时再比一场即共8场结果就出来了。
2）B1>A3>C1>D1>E1，结果也为
A1>A2>A3>A4>A5
B1>B2
C1
3）B1>C1>A3>D1>E1，结果为
A1>A2>A3
B1>B2
C1>C2
再比一场也出来了
4）B1>C1>D1>A3>E1，结果为
A1>A2
B1>B2
C1>C2
D1>D2
也是再比一场出结果
5）B1>C1>D1>E1>A3，结果为
A1>A2
B1>B2
C1>C2
D1>D2
E1>E2
此时需再比两场即共9场才能出结果

98 楼 lenj 2008-11-26

shiwei2006 写道

10场是正确的。一匹马只要在横向和竖向都排第一，一定是这个矩阵中最快的，被选出来。

[有N匹马，有M个赛道，试问要至少多少场比赛才能知道跑得最快的Y匹马。]

A1 A2 A3 A4 A5
B1 B2 B3 B4 B5
C1 C2 C3 C4 C5
D1 D2 D3 D4 D5
E1 E2 E3 E4 E5

int c1 = N % M ==0 ? N / M : N / M + 1; //经过c1轮比赛得到一个矩阵.
int count = c1 + Y; //再经过Y次比赛找到最快的. 每次从最左竖列开始，选中一个后其所在横列顺序补上.
需要count次。(最多也就需要count次就可以了.)

我也觉得需要10场

97 楼 shiwei2006 2008-11-25

96 楼 luck_donkey 2008-11-25

给一个比赛的办法：

1) 1-5轮，分成5组分别比赛，按照比赛结果从快到慢排成5组

2) 从5组中抽出最快进行比赛，把最快的放到一边去，它肯定是第一，是前5名之内的；最慢的所对应的那一组的余下4匹被淘汰，因为比它快的就有5个，肯定是在前5名之外。把余下的4匹按照从快到慢的顺序马排成一组，进入被淘汰的那一组的位置。

3) 重复上面的方法4次，得到5匹最快的马。

95 楼 jasongreen 2008-11-24

复杂的问题，挺不容易，所谓的正解，有些牵强

94 楼 gogon1111 2008-11-24

1－5轮：分成5组分别比赛。（不是最好，但最简化）
6轮 ：每组的第2名比赛。从快到慢（从小到大）依次命名为a2,b2,c2,d2,e2。按照这个规则给所有的马命名。
 此时a1肯定入围，其余争夺前4。将a1排出讨论。
 b4比a2,b1,b2,b3都大，所以不可能入围。
 c2比b1,c1,a2,b2都大，也不可能入围。
 所以只有剩下的a2,a3,a4,a5,b1,b2,b3,c1,d1,e1争夺前4。其中a2<a3<a4<a5，b1<b2<b3， a2<b2

7轮 ：将a3,b2,c1,d1,e1比赛。此次比赛的第一名直接入围，剩下的角逐前3。因为c1,d1,e1的等价性，不妨根据比赛结果设c1<d1<e1。然后分情况讨论：

 引论甲：如果b3要入围，那么入围人选只能是a1,b1,a2,b2,b3。所以这场比赛b2,a2分别占据前二才行。

 如果a3排第一。那么a2,a3直接入围。此次比赛的第二名，第三名和b1,a4,a5决出最后2名入围者。总共是8。
 如果a3排第二，c1第一。比a3快的只可能c1,a2,b1，所以a2,a3直接入围。剩下的a4,a5,b1和这轮第三名，第四名争夺最后一名入围者。总共8轮。如果a3排第二,b2第一。b1,b2,a2直接入围。最后一个名额由a3,b3和刚才第三名争夺产生。总共8轮。
 如果a3排第三。那么刚才比赛最后2名直接失去比赛资格。可能比a2小的只有前2名和b1，所以a2直接入围。再加上前两名直接入围。第6轮结束剩下的10名选手中，3名入围，2名失去资格，剩下的5名选手刚好可以一场比赛决出最后一个名额。总共8轮。
 如果a3排第四。a3，a4,a5都失去资格。根据引论甲，b3也失去资格。只剩下有a2,b1和刚才的前三名，5人只需要一场比赛即可。总计8轮。
 如果a3第五。a3,a4,a5失去资格。根据引论甲，b3失去资格。比赛前2名直接入围。剩下的4人再进行一场比赛即可。总计8轮。

 所以按照这种算法，最多8轮就可以决出前5名。

93 楼 blunder 2008-11-22

晕，啥时代了？连个计时器都没有啊？

92 楼 piglol 2008-11-22

六次就ok了

91 楼 zlxia0013 2008-11-21

apptech 写道

必须进行的五场比赛就不说了。从第六场比赛开始吧：在每组的第一名进行第六场的比赛，然后第一名直接晋级，再由第一名所在对的下一名和剩下的四匹马进行比赛，以此类推，五轮比赛后即可得出跑的最快的无匹马。

正解啊

90 楼 phpxer 2008-11-19

看到最后，有点失望。如果换成是5000匹马，取最快的2000批，按照上面列位的穷举法... 怎么就没有人把这个算法用算数式表达出来呢？

89 楼 reciting 2008-11-18

想想应该最多9轮： 前5轮没有悬念，分5组各自组内跑一轮 A组 A1 A2 A3 A4 A5 B组 B1 B2 B3 B4 B5 C组 C1 C2 C3 C4 C5 D组 D1 D2 D3 D4 D5 E组 E1 E2 E3 E4 E5 第六轮，各组的第3名比(粗体表示)，那么非第一名所在组的第3、4、5名均被淘汰（加删除线），理由很简单，如果B3在前5名的话，比其快的还有A1、A2、A3 B2 B3，再加上自己已经6匹，不可能：
A组 A1 A2 A3 A4 A5 B组 B1 B2 B3 B4 B5 C组 C1 C2 C3 C4 C5 D组 D1 D2 D3 D4 D5 E组 E1 E2 E3 E4 E5
 
第七轮，上一轮跑第1名的组再次用该组的第3名A3和其它组的第二名比，结果可能以下几种，最坏的情况是第一种，仅淘汰3匹（淘汰分析原因同上），下一轮以第一种情况为例说明，其它情况更好只会更少轮数
A组 A1 A2 A3 A4 A5 B组 B1 B2 C组 C1 C2 D组 D1 D2 E组 E1 E2 
 
 B组 B1 B2 
A组 A1 A2 A3 A4 A5 C组 C1 C2 D组 D1 D2 E组 E1 E2 
 
B组 B1 B2 C组 C1 C2 
A组 A1 A2 A3 A4 A5 D组 D1 D2 E组 E1 E2 
 

B组 B1 B2 C组 C1 C2 
D组 D1 D2 
A组 A1 A2 A3 A4 A5 E组 E1 E2 

 

B组 B1 B2 C组 C1 C2 
D组 D1 D2 
E组 E1 E2 
A组 A1 A2 A3 A4 A5 

 
第八轮，还用最快的一组的第3名和其它组的第一名比，情况可能如下，第一种情况最坏，还剩下7个，第5种情况次之，科还剩下6个，其它三种情况仅剩下5个，结果已确定，下一轮以第一种情况为例讨论：
A组 A1 A2 A3 A4 A5 B组 B1 C组 C1 D组 D1 E组 E1 
 
 B组 B1 
A组 A1 A2 A3 A4 A5 C组 C1 D组 D1 E组 E1 
 

B组 B1 
C组 C1 
A组 A1 A2 A3 A4 A5 D组 D1 E组 E1 

 

B组 B1 
C组 C1 
D组 D1 
A组 A1 A2 A3 A4 A5 E组 E1 

 

B组 B1 
C组 C1 
D组 D1 
E组 E1 
A组 A1 A2 A3 A4 A5 

 
第九轮，前轮第一名的组的前3名必是前五名，仅需要对其它4匹马比较，再取前两名即可确定最后结果
 
A组 A1 A2 A3 A4 A5 B组 B1 C组 C1 D组 E组

88 楼 apha 2008-11-18

一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。

假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问最少得比多少场才能知道跑得最快的5匹马。[也许至少会产生误解，换成最少，就是考虑你的算法的最坏情况下]
-------------------------------
1. 不考虑算法:
最少应该是在6场,
前五场是没问题的,第六场是A5和B1,C1,D1,E1跑一场,A5第一,第六场出结果.

2. 考虑算法:

前五场是一样的,第六场:A2,B2,C2,D2,E2跑一场.
同样也可以得出A2>B2>C2>D2>E2的结果;
最后的筛选得出有机会的马为:
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3
C组 C1
D组 D1
E组 E1

待续......

87 楼 wuhua 2008-11-17

我的算法是
先跑第1轮
那么结果是
A1 A2 A3 A4 A5
B1 B2 B3 B4 B5
C1 C2 C3 C4 C5
D1 D2 D3 D4 D5
E1 E2 E3 E4 E5

上面是第1轮跑出的结果，跑第2轮的时候得出的结果是：
找出第2轮跑的最慢的马，然后跟第2梯队进行比赛。
我们假设跑的最慢的是
Horse slow = getSlowHorse();
Horse secondFast = getSecondFast(); // 获取第2梯队跑的最慢的马
slow 跟secondFast 进行比赛如果slow比secondFast 快，那么结果就出来了。7场就可以出结果了，5+1+1；
如果慢的话，则淘汰slow的那5匹马。
如此循环，直到筛选出最快的5匹马，最后的情况就是全面进行遍历筛选了。
剩下，不好算啊。
呵呵。复杂。

不过话又说回来，google的题，应该是发散的。
因为在赛场上，什么结果都会出现，真实客观的来说，没法得出结果。
如果全部一起跑哪还知道，没匹马跑出的速度在每场比赛得出的速度都不一样

86 楼 wuhua 2008-11-17

superloafer 写道

应该是要7场。首先至少每一匹马都要比赛，所以一开始就先比五场；每一场比完后分别将当时那场的马按快慢顺序排好队。然后第六场每对最快的马比。这一场过后，将跑得最慢的那匹马的所在的队伍整队都淘汰掉（无需比了，最快的都跑得比别人慢），同时将第六场跑得最快的那个队的第二名拉出来比(因为只有这个队的马才有可能挤进第二到第五名之间）。第七场会出现几种情况：
1。在第六场才加进来的马在第七场正好跑了第五名，那么结果出来了
2.第二三四名的话，都还要继续比，不一一列举。但可以给个场次最多的，就是跑得最快的马都是同一个队的，要10场比赛才能见分晓。

然后第六场每对最快的马比。这一场过后，将跑得最慢的那匹马的所在的队伍整队都淘汰掉（无需比了，最快的都跑得比别人慢）
这个不一定吧。
可能跑的最慢的也比最快的队伍中第2名的要快

85 楼 Julien 2008-11-14

楼上Good Job！

84 楼 mayday85 2008-11-14

跑完6次后的结果（A到E、1到5）
A1 B1 C1 D1 E1
A2 B2 C2 D2 E2
A3 B3 C3 D3 E3
A4 B4 C4 D4 E4
A5 B5 C5 D5 E5
然后可以pass掉将近一半的马
B1 C1 D1 E1
A2 B2 C2 D2
A3 B3 C3
A4 B4
A5
为什么可以pass掉？比如C4，肯定比C4快的有C1C2C3A1B1，超过5匹，其它的自己去想
A1肯定最快也去掉了
第7场比较A2 B1 A3 B2 C1(斜线)
可以确定前3
第8场是第6场的后3、4名加上第6场的第2名后面的3匹

最多8场

83 楼 vivid_gxp 2008-11-12

superloafer 写道

分析结果漏洞百出。

其实赛5场就够了。弄个秒表计下。（玩笑）

« 上一页 1 2 3 … 6 7 下一页 »

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论