b**d
发帖数: 1174 | 1 2个机器人从直升机上跳下，在一个无限长的一维坐标轴上移动，设计一个算法，可以
使它们相遇。
已知条件：
1。落地后，不知道2个机器人各自面对的方向，也就是说可以是相对、相背或者都面朝
同一个方向。
2。机器人走路的速度可随便控制，方向也可变。
虽然拿到了offer，但面试的时候被问到了这个题，当时没有完全回答出来，只说了改
变其中一方的速度，可以使它们在相对和同向的情况下可以碰头，但相背的情况下不知
道怎么整了，也不知道interviewer是不是漏了什么条件。
看到版上曾经有人被考到，但没有说答案。有高人能指点一下么？ |
T******e
发帖数: 157 | 2 说个笨办法，抛砖引玉，左走一步，右走两步，左走三步...反正每次换方向，比上一
次多走一步 |
b**d
发帖数: 1174 | 3 像左右震荡似的，但因为2个机器人不知道相对的位置，如果它们都向一个方向震，最
终应该还是不能碰到吧？
【在 T******e 的大作中提到】
: 说个笨办法，抛砖引玉，左走一步，右走两步，左走三步...反正每次换方向，比上一
: 次多走一步
|
p***e
发帖数: 111 | 4 速度可以调的话，让一个机器人静止不动。另一个先随机向一个方向走1步，没有碰到
一起的话，接着向反方向走2不. 循环直到碰到一起，每次变方向走的步数加倍。初始
距离是L步的话，复杂度是O(2log(L)).
【在 b**d 的大作中提到】
: 像左右震荡似的，但因为2个机器人不知道相对的位置，如果它们都向一个方向震，最
: 终应该还是不能碰到吧？
|
b**d
发帖数: 1174 | 5 豁然开朗啊！多谢！
【在 p***e 的大作中提到】
: 速度可以调的话，让一个机器人静止不动。另一个先随机向一个方向走1步，没有碰到
: 一起的话，接着向反方向走2不. 循环直到碰到一起，每次变方向走的步数加倍。初始
: 距离是L步的话，复杂度是O(2log(L)).
|
s******s
发帖数: 84 | |
h*d
发帖数: 19309 | 7 好像是编程之美那个书里面的？
【在 p***e 的大作中提到】
: 速度可以调的话，让一个机器人静止不动。另一个先随机向一个方向走1步，没有碰到
: 一起的话，接着向反方向走2不. 循环直到碰到一起，每次变方向走的步数加倍。初始
: 距离是L步的话，复杂度是O(2log(L)).
|
p***e
发帖数: 111 | 8 拿到offer的牛人客气了，恭喜了。
【在 b**d 的大作中提到】
: 豁然开朗啊！多谢！
|
p***e
发帖数: 111 | 9 书名听上去不错，里面内容怎样? 好的话就去找来看看。
【在 h*d 的大作中提到】
: 好像是编程之美那个书里面的？
|
j******a
发帖数: 55 | 10 我面groupon的时候遇到过这个题，当时状态特别好，秒解了，结果interviewer以为我
见过，真心无语。。。
我怎么没在编程之美上见过这题？ |
b**d
发帖数: 1174 | 11 应该先装傻充愣一会儿，再慢慢解。
我被问了5个算法题，4个都是做过的，每个都磨了最少3分钟，先给错误、猥琐的答案
，再给出最优解。没办法，有时候面试就像演戏，即使大家心里都有数，面子上也得过
得去。
【在 j******a 的大作中提到】
: 我面groupon的时候遇到过这个题，当时状态特别好，秒解了，结果interviewer以为我
: 见过，真心无语。。。
: 我怎么没在编程之美上见过这题？
|
