Google Interview Question for Software Engineer / Developers
- 0of 0 votes
Phone interview question from January.
We have a maze with three types of spaces:
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.")
WWWWWWWW WWW O WW WWW OW WWW WWWW WO WWWW WWW WWWW WO W WWWWWWWW
O = office, W = wall, spaces are hallway spaces- mbs729 July 13, 2017 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
Interview Type: Phone Interview