n******r
发帖数: 1247 | 1 1.一个0/1序列，长度为N（say N=1000）0/1出现的概率均为1/2 求出现的最长
continuous序列的expected长度（连续的0或连续的1均可，只要最长）。now
repeat it for any 0
2.49 辆赛车. Assume for each one, it travels the track in the same
amount of time every time. Also assume no two finish the track in the
same amount of time. Suppose you have 7 tracks, but no timer. Design
races to find the 25-th fastest with minimal number of races. |
k***e
发帖数: 556 | 2 第一题以前好像讨论过 结果在一篇paper里
现在是一点想不起来了：）
【在 n******r 的大作中提到】
: 1.一个0/1序列，长度为N（say N=1000）0/1出现的概率均为1/2 求出现的最长
: continuous序列的expected长度（连续的0或连续的1均可，只要最长）。now
: repeat it for any 0: 2.49 辆赛车. Assume for each one, it travels the track in the same
: amount of time every time. Also assume no two finish the track in the
: same amount of time. Suppose you have 7 tracks, but no timer. Design
: races to find the 25-th fastest with minimal number of races.
|
H*M
发帖数: 1268 | 3 the second one was discussed before here or in programming...no agreed
answer.
【在 n******r 的大作中提到】
: 1.一个0/1序列，长度为N（say N=1000）0/1出现的概率均为1/2 求出现的最长
: continuous序列的expected长度（连续的0或连续的1均可，只要最长）。now
: repeat it for any 0: 2.49 辆赛车. Assume for each one, it travels the track in the same
: amount of time every time. Also assume no two finish the track in the
: same amount of time. Suppose you have 7 tracks, but no timer. Design
: races to find the 25-th fastest with minimal number of races.
|
m*****f
发帖数: 1243 | 4 这个49辆赛车有肯定的答案吗?
我只听说过25匹赛马...
【在 H*M 的大作中提到】
: the second one was discussed before here or in programming...no agreed
: answer.
|
g*******y
发帖数: 1930 | 5 第二题有个类似脑筋急转弯的solution，有巧妙之处也有不合情理的地方: 就是允许多
匹马share一个track。
【在 H*M 的大作中提到】
: the second one was discussed before here or in programming...no agreed
: answer.
|
c*********n
发帖数: 1057 | 6 可能可以提，但肯定不是面试官想要的答案
【在 g*******y 的大作中提到】
: 第二题有个类似脑筋急转弯的solution，有巧妙之处也有不合情理的地方: 就是允许多
: 匹马share一个track。
|
k***e
发帖数: 556 | 7 不是很懂你说的啊？
我干脆就说其实扩充了pariwize comparison to 7wise comparison
如果考虑排序的话，complexity 没有变
然后开始说这个和linear selection很像，先把linear selection写出来，分析复杂度，
然后往上套，哈哈
其实最后还是没有得到最优解
【在 g*******y 的大作中提到】
: 第二题有个类似脑筋急转弯的solution，有巧妙之处也有不合情理的地方: 就是允许多
: 匹马share一个track。
|
H*M
发帖数: 1268 | 8 i paid attention last time..no definite answer.
The only answer I verifed is something like 21(?), but many guys claims he g
ot it less than 10.
【在 m*****f 的大作中提到】
: 这个49辆赛车有肯定的答案吗?
: 我只听说过25匹赛马...
|
|
H*M
发帖数: 1268 | 9 please post it here! hehe
but i think it is not permitted to share a track
【在 g*******y 的大作中提到】
: 第二题有个类似脑筋急转弯的solution，有巧妙之处也有不合情理的地方: 就是允许多
: 匹马share一个track。
|
n******r
发帖数: 1247 | 10 25匹马的原题谁贴一下？我看到过也忘记了
【在 m*****f 的大作中提到】
: 这个49辆赛车有肯定的答案吗?
: 我只听说过25匹赛马...
|
|
|
g*******y
发帖数: 1930 | 11 是我一个同学告诉我的
先分成7组跑7场
然后，每组share一个赛道再跑一场。share赛道的时候，把该组中快的放前面，这样就
不会在一个赛道上出现超车。最后这场可以把所有49匹马的顺序都排出来
度，
【在 k***e 的大作中提到】
: 不是很懂你说的啊？
: 我干脆就说其实扩充了pariwize comparison to 7wise comparison
: 如果考虑排序的话，complexity 没有变
: 然后开始说这个和linear selection很像，先把linear selection写出来，分析复杂度，
: 然后往上套，哈哈
: 其实最后还是没有得到最优解
|
H*M
发帖数: 1268 | 12 There are 25 horses, and you can race 5 of them at a time. Strangely, you ha
ve no stopwatch, but the horses always run exactly the same in every race. H
ow many races does it take to figure out:
* the fastest horse? ->6
* the top three fastest? ->7
【在 n******r 的大作中提到】
: 25匹马的原题谁贴一下？我看到过也忘记了
|
m*****f
发帖数: 1243 | 13 这个解法倒是有趣.
【在 g*******y 的大作中提到】
: 是我一个同学告诉我的
: 先分成7组跑7场
: 然后，每组share一个赛道再跑一场。share赛道的时候，把该组中快的放前面，这样就
: 不会在一个赛道上出现超车。最后这场可以把所有49匹马的顺序都排出来
:
: 度，
|
k***e
发帖数: 556 | 14 晕 如果我定义a match就是7匹马跑一次 然后要求min match 。。。
不过够狡猾
【在 m*****f 的大作中提到】
: 这个解法倒是有趣.
|
H*M
发帖数: 1268 | 15 this is funny! haha
【在 g*******y 的大作中提到】
: 是我一个同学告诉我的
: 先分成7组跑7场
: 然后，每组share一个赛道再跑一场。share赛道的时候，把该组中快的放前面，这样就
: 不会在一个赛道上出现超车。最后这场可以把所有49匹马的顺序都排出来
:
: 度，
|
n******r
发帖数: 1247 | 16 Thanks!
ha
H
【在 H*M 的大作中提到】
: There are 25 horses, and you can race 5 of them at a time. Strangely, you ha
: ve no stopwatch, but the horses always run exactly the same in every race. H
: ow many races does it take to figure out:
: * the fastest horse? ->6
: * the top three fastest? ->7
|
o********r
发帖数: 79 | 17 这个倒是挺简单的
ha
H
【在 H*M 的大作中提到】
: There are 25 horses, and you can race 5 of them at a time. Strangely, you ha
: ve no stopwatch, but the horses always run exactly the same in every race. H
: ow many races does it take to figure out:
: * the fastest horse? ->6
: * the top three fastest? ->7
|
o********r
发帖数: 79 | 18 赞思路
【在 m*****f 的大作中提到】
: 这个解法倒是有趣.
|
