Nerd Paradise : Coding Interview 11: Where is the Restroom?

Nerd Paradise : Coding Interview 11: Where is the Restroom?

Given a list of restroom locations (some struct with an x and y coordinte) return the closest restroom to a given point.

Part 1: Find the closest restroom to a point

Simple enough. Loop through the list of coordinates and use the distance formula. Keep track of the lowest distance you find and the restroom associated with it.

function distance(x, y, restroom):
    dx = restroom.x - x
    dy = restroom.y - y
    return sqrt(dx * dx + dy * dy)

function find_closest(x, y, restroom_list):
    min_distance = distance(x, y, restroom_list[0])
    min_restroom = restroom_list[0]
    for i in [1 .. restroom_list.length):
        d = distance(x, y, restroom_list[i])
        if d < min_distance:
            min_distance = d
            min_restroom = restroom_list[i]
    return min_restroom

But life isn't that easy. Unless of course you're in an open field with toilets randomly dotting the landscape. Surely this is not the case.

Part 2: Closest restroom in a building with obstructing walls

This is a simple and unashamed breadth-first-search problem. It's best to be sure you know this in-and-out before walking into any interview.

Now we have a grid as input where each node in the grid has five bools. 4 for representing if the grid square has a connection to its north, south, east, and west neighbors and a boolean indicating whether there is a restroom at that grid location.

function find_closest_rr(x, y, grid):
    q = new Queue()
    traversed = new Hashset()

    q.enqueue(grid[x,y])
    traversed.add(grid[x,y])

    while queue.length > 0:
        next = q.pop()

        if next.has_restroom:
            return next
        
        if next.to_north and !traversed.contains(next):
            q.enqueue(grid[next.x, next.y - 1])
            traversed.add(next)
        
        if next.to_south and !traversed.contains(next):
            q.enqueue(grid[next.x, next.y + 1])
            traversed.add(next)
        
        if next.to_east and !traversed.contains(next):
            q.enqueue(grid[next.x + 1, next.y])
            traversed.add(next)
        
        if next.to_west and !traversed.contains(next):
            q.enqueue(grid[next.x - 1, next.y])
            traversed.add(next)

    return null

Part 3: Find the closest restroom instantly

In general, toilets don't move. Therefore it is conceivable to generate an instant lookup table that can be re-used multiple times. Although if you approach this by running the above function on each grid cell to populate this table in an interview, you won't do so well.

Take the opposite approach. Start from the toilets and trace outwards. Each time you enqueue a grid cell, tag it with the grid cell you enqueued it from.

Assume there is an additional field on each grid cell that represents the closest restroom that you are to populate.

function populate_lookup_table(grid):
    
    toilet_list = []
    for y in [0 .. grid.height):
        for x in [0 .. grid.width):
            if grid[x, y].has_restroom:
                grid[x, y].closest_restroom = grid[x, y]
                toilet_list.add(grid[x, y])

    queue = new Queue()
    queue.enqueue_all(toilet_list)

    while queue.length > 0:
        next = queue.pop()
        
        if next.to_north:
            neighbor = grid[x, y - 1]
            if neighbor.closest_restroom == null:
                neighbor.closest_restroom = next
                queue.enqueue(neighbor)
        if next.to_south:
            neighbor = grid[x, y + 1]
            if neighbor.closest_restroom == null:
                neighbor.closest_restroom = next
                queue.enqueue(neighbor)
        if next.to_east:
            neighbor = grid[x + 1, y]
            if neighbor.closest_restroom == null:
                neighbor.closest_restroom = next
                queue.enqueue(neighbor)
        if next.to_west:
            neighbor = grid[x - 1, y]
            if neighbor.closest_restroom == null:
                neighbor.closest_restroom = next
                queue.enqueue(neighbor)

And now, find_closest_rr becomes:

function find_closest_rr(x, y, grid):
    return grid[x, y].closest_restroom

Read full article from Nerd Paradise : Coding Interview 11: Where is the Restroom?