s*i
发帖数: 388 | 1 系里的一个印度铁哥们透露给我的，他签了nda所以我就不透露是哪家了，大家应该也
能猜到。
software dev position。
how to design an algorithm to solve this problem:
given a house with several rooms, and a moving enemy, and your robot. the
path
and timing of the enemy is known. try to design a path for your robot that
can
traverse all rooms (can be visited several times) and avoid the enemy. that
is, your robot can not be in the same room at any time during your
traversal.
example: a 2x2 matrix is the house, and each cell is a room. the enemy start
from (1,1), and keep going to (1,2), (2,2), (2,1) then back to (1,1), each
step takes 1 second. your bot starts at a different cell as the enemy and
one strategy is synchronizing with the enemy.
what data structure
what algorithm
how do u improve the total traversing time?
45 min to solve, white board for pseudo code. | g*********s
发帖数: 1782 | 2 what kind of layout for all rooms in this house, a grid?
the
that
that
traversal.
【在 s*i 的大作中提到】
: 系里的一个印度铁哥们透露给我的，他签了nda所以我就不透露是哪家了，大家应该也
: 能猜到。
: software dev position。
: how to design an algorithm to solve this problem:
: given a house with several rooms, and a moving enemy, and your robot. the
: path
: and timing of the enemy is known. try to design a path for your robot that
: can
: traverse all rooms (can be visited several times) and avoid the enemy. that
: is, your robot can not be in the same room at any time during your
| s*i
发帖数: 388 | 3 yes
【在 g*********s 的大作中提到】
: what kind of layout for all rooms in this house, a grid?
:
: the
: that
: that
: traversal.
| B********n
发帖数: 384 | 4 robot起始位置可以随便选吗?如果可以的话,只要选择奇偶与enemy相反就可以任意走了.
start point enemy (a, b), robot (x, y), as long as (x+y) % 2 != (a+b) % /2
that
【在 s*i 的大作中提到】
: 系里的一个印度铁哥们透露给我的，他签了nda所以我就不透露是哪家了，大家应该也
: 能猜到。
: software dev position。
: how to design an algorithm to solve this problem:
: given a house with several rooms, and a moving enemy, and your robot. the
: path
: and timing of the enemy is known. try to design a path for your robot that
: can
: traverse all rooms (can be visited several times) and avoid the enemy. that
: is, your robot can not be in the same room at any time during your
| l*********r
发帖数: 674 | 5 可以假设只能沿着grid移动把，（1，1）to (2,2) not allowed.
【在 s*i 的大作中提到】
: yes
| l*********r
发帖数: 674 | 6 如果是沿着grid走的话，每一步奇偶性都会变一下。这样robot只要比enemy晚一步出门
就可以直接遍历所有room了。
不知道对面走允不允许，比如说enemy在(1,2)的时候robot start from (1,1）下一步
他们互换位置。
了.
【在 B********n 的大作中提到】
: robot起始位置可以随便选吗?如果可以的话,只要选择奇偶与enemy相反就可以任意走了.
: start point enemy (a, b), robot (x, y), as long as (x+y) % 2 != (a+b) % /2
:
: that
| c******w
发帖数: 1108 | 7 万一enemy有一步是停在一个房间不动呢?
了.
【在 B********n 的大作中提到】
: robot起始位置可以随便选吗?如果可以的话,只要选择奇偶与enemy相反就可以任意走了.
: start point enemy (a, b), robot (x, y), as long as (x+y) % 2 != (a+b) % /2
:
: that
| s*i
发帖数: 388 | 8 it seems that they are looking for graph search algorithm | l*****a
发帖数: 14598 | 9 那就先把别的屋遍历了，
等他一出来就进去
【在 c******w 的大作中提到】
: 万一enemy有一步是停在一个房间不动呢?
:
: 了.
|
|
