-1

This was an interview question I have been asked. It involves a 2D grid that consists of empty and occupied spots (0s and 1s if you will) of infinite size. The input contains the coordinates of the occupied spots and it asks me to return the closest empty spot for each occupied spot. You can go through the occupied spots during traversal. This was a free-form coding challenge, it doesn't involve a method signature to begin with.

I am experienced in algorithms and have solved similar problems before, finding the nearest location questions usually involves BFS on the given graph. However, the grid being of infinite size complicated the matter, now that I know I won't be able to store the entire grid on a matrix structure. Nevertheless, I went with BFS method in the end. One problem emerged at this point was how to check whether the current spot is occupied or not. Going through each spot in the input for each visited node doesn't seem like a very good option since it is too slow. So I have suggested that if I can somehow map the occupied spots into a hashmap, then the check operation can be done in constant time. The interviewer told me to assume I have a hash function for the coordinates and my final solution was something like this:

for each occupied spot in the input
    create a queue and push the current spot into the queue
    while queue is not empty
        get the first element from the queue
        if the spot is not occupied and not marked
            add the spot into result list and break the while loop
        else if spot is not marked
            push its neighbors into queue and mark it

The outer for loop takes O(n) time for each spot in the input. The BFS algorithm runs in O(v + e), the interviewer suggested that it can be represented as O(n). In the worst case scenario, it visits every occupied spot, so it is indeed O(n). My final algorithm runs in O(n^2).

As you can expect I failed the interview, otherwise I wouldn't be posting this question. Can you point me to my mistakes? I thought the interview went well and couldn't find anything on the internet search on how to solve the question on an infinite grid. Maybe I should have started by clarifying how to store an infinite grid but couldn't think at that moment.

Can Bayar
  • 497
  • 4
  • 16
  • A guess: for each occupied spot, the closest unoccupied is N, S, E, or W from that spot. _Unless_ N, S, E, or W is occupied (by a different coordinate in the input). In that case, the next-closest unoccupied is any remaining unoccupied NSEW, union the NSEW from the second occupied spot that you ran into. (And for that second spot, its closest are NSEW, delta the first spot, union the first spot's remaining closest.) So perhaps you could make domains: solitary spots have simple NSEW closest. Clustered spots have partially overlapping nearest unoccupied sets. – Dave M. May 26 '22 at 14:22
  • Maybe but would it perform better than the BFS algorithm? It doesn't seem like a feasible solution for a 30-minutes long interview. – Can Bayar May 26 '22 at 14:33

2 Answers2

0

I'm guessing that what they wanted you to do was loop in a spiral with the center starting from each known occupied spot. So something like:

Distance = 1;
foreach(occupiedSpace)
{
occupied = true; // my own position is occupied by definition
While (!occupied) // loop in a spiral and check for an open space
{
 for(possibleXPosition = -1* distance + occupiedSpace.x to distance + occupiedSpace.x)
    for(possibleYPosition = (-1)+distance + occupiedSpace.y to distance + occupiedSpace.y ){
    occupied = check( array[possibleXPosition, possibleYPosition])
    if(!occupied){ 
    output.print(closest position to (occupiedSpace is possibleXPosition, 
                 possibleYPosition)
}
}
  
distance++;
}}

There are some real implementations here: Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin

Banjo Batman
  • 159
  • 11
  • Spiral search seems like it would be a reasonable approach. I think the "infinite grid" thing is a red herring -- maybe it's impossible to allocate a bitmap for the whole thing, but on the flip side, if you don't have the bitmap, then you need to store all the individual points in a data structure that allows you to _pretend_ that you have an X-Y-addressable bitmap. So that part of the problem is just a data-representation question. Then, as @Banjo Batman says, you iterate spirally for each point. – Dave M. May 26 '22 at 16:10
  • Spiral search also would not perform better and is harder to implement than BFS. Also, the algorithm stops when an unoccupied spot is found so there is no point in continuing from there. – Can Bayar May 26 '22 at 19:37
0

Look at LeetCode #286 Walls and Gates. This is a variation of the BFS solution to that problem.

However, instead of adding gates when you initialize the queue, you would be adding occupied spots that are next to an unoccupied spot to it. You would be starting BFS at once from every one of those spots.

Hope this hint helps.

user5875820
  • 21
  • 2