mbs729
BAN USER- 0of 0 votes
AnswersPhone interview question from January.
We have a maze with three types of spaces:
1. Walls
2. Offices
3. Hallway space
Given a maze, determine which non-wall space would minimize the sum of all distances between that space and every office. You can only move up, down, left, and right.
(Edit: ChrisK described the problem more clearly than I did: "find the field that minimizes the sum of the shortest path[s] from this field to each office space.")
Example:WWWWWWWW WWW O WW WWW OW WWW WWWW WO WWWW WWW WWWW WO W WWWWWWWW
O = office, W = wall, spaces are hallway spaces
- mbs729 in United States
You can represent the maze however you want. That is, you can use any data structures you want, and you don't necessarily have to use O for office, W for Wall, and spaces for hallways.
(I'm not sure if you can actually start from an office space, but that should be a trivial issue because you can always just start a position adjacent to an office.)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm