## Motorola Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

If 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.

Comment hidden because of low score. Click to expand.
0

@eugene.yarovoi: your explanation is always clear. This problem requires lot of preprocessing though for forming a graph.

Comment hidden because of low score. Click to expand.
0

@eugene.yarovoi : Thanks for your explaination. Can you please explain more on how you will handle the existence of walls in your DS.

Comment hidden because of low score. Click to expand.
0

@Park: walls would be taken into account when building the graph. Normally vertices that represent adjacent areas will have an edge between them, but not if there's a wall in between them.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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..

Comment hidden because of low score. Click to expand.
0

Shouldn't BFS be used...??...Since the closest cubicle to the coffee is been asked to find using BFS would give us the result easily...Of course even DFS would...but we need to explore all routes to find the shortest path....Correct me if i am wrong...

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Shouldn't a

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.