Motorola Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
@eugene.yarovoi: your explanation is always clear. This problem requires lot of preprocessing though for forming a graph.
@eugene.yarovoi : Thanks for your explaination. Can you please explain more on how you will handle the existence of walls in your DS.
Appears to be related to searching a maze. In such a case, a graph becomes a natural choice to model the situation. Coffee rooms are special in the sense, we can start DFS from such nodes.
Walls can be modeled as nodes that block the path from a cubicle to a coffee room. The DFS has to be modified to bypass the blocked nodes(i,e walls) and starting from coffee rooms, search to find a cubicle node that is empty..
How about a minimum priority queue and a linked list????
A min priority queue with the priority being the distance to the coffee room and the data being the cubicle number.
A linked list to keep track of occupied cubicles. When a cubicle becomes empty it is removed from the lined list and added to the min priority queue.
A reasonable approach would be to model the workplace as a graph, using the walls and the geography of the office to determine which cubicles, spaces, areas, etc. are adjacent to each other and creating edges between them in the graph. Once we've built the graph, we can do either breadth-first search or Dijkstra's algorithm, depending on whether it's reasonable to treat all distances between adjacent areas as equal (say in the case that we have everything on a uniform grid) or not. We'd want to start the search simultaneously from all coffee rooms; that way, as we reach each cubicle during the search, we will have found the shortest distance to *any one of* the coffee rooms. Once we've calculated this distance for all cubicles and excluded any already-occupied cubicles from consideration, we can place the free cubicles into a min-heap ordered by coffee room distance. We can now remove-min from the heap when assigning a new cubicle.
- eugene.yarovoi February 06, 2014If a new empty cubicle is added to the office, hopefully it's placed in some previously existing space whose distance to coffee we calculated during the preprocessing, and we can just add the cubicle to the heap. Similarly, when an engineer leaves the company and their cubicle becomes available, we can also add it to the heap.
If we don't care about supporting the scenario of adding cubicles, we can use a sorted array instead of a min-heap. We can make a stack of the cubicles, with the ones closest to coffee on top. Getting the next cubicle is just an O(1) pop now.