Amazon Interview Question
Country: India
doesn't sound like O(grid size).
the queue first have n^2 candidate(if all are doors). for each candidate in node, BFS will not be const time.
There is only 1 BFS. It just starts at all the door positions simultaneously. If there were O(n^2) doors, the BFS actually would be constant time per door when amortized over all doors. By O(grid size), I mean O(m*n) on an m x n grid. Maybe I should have said "grid area" or "size of input".
@gs: Not so. Please provide a justification for your analysis. The justification for the O(m*n) runtime is that it's no different from a regular BFS, with an initial O(m*n) pass to find all the doors with which to initialize the queue.
Think about this way:
Imagine you have one "magic" door outside the grid that connects and only connects to all the doors inside the grid. Thus, a shortest path P from the magic door to a cell x must contain a shortest path Q from some door to the cell x, with Q = P-1.
Then we just do one pass BFS from the magic door to find the ways to all empty cells.
This solution is O(grid_size + 1) time.
1. Pick one door position.
2. Do Breadth-first search. While doing BFS, update the empty locations with distance from the door.
3. If a location has a distance marked already: Add the location to BFS queue only if the distance from current door is lesser than the distance marked on the location.
4. If the location is empty: Add the location to BFS queue.
5. Stop the BFS if queue is empty.
6. Pick the next door and repeat 2-5.
Hi I did not get the BFS part. How to implement BFS in this case. Can you plz make it more clear. Code would be a great help. Thanks :)
Code for this solution...-2 represents door and -3 represents wall
import java.util.Arrays;
import java.util.LinkedList;
public class game
{
public static void gameplay(int a[][])
{
int m = a.length - 1;
int n = a[0].length - 1;
LinkedList<pointnode> queue = new LinkedList<pointnode>();
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (a[i][j] == -2)
{
queue.add(new pointnode(i, j));
}
}
}
while (!queue.isEmpty())
{
pointnode d = queue.remove();
LinkedList<pointnode> queue2 = new LinkedList<pointnode>();
queue2.add(d);
while (!queue2.isEmpty())
{
pointnode current = queue2.remove();
int dist = a[current.a][current.b];
if (dist <= 0) dist = 0;
// move up
if (current.a > 0 && a[current.a - 1][current.b] >= 0)
{
if (a[current.a - 1][current.b] == 0
|| dist < a[current.a - 1][current.b])
{
a[current.a - 1][current.b] = dist + 1;
queue2.add(new pointnode(current.a - 1, current.b));
}
}
// move left
if (current.b > 0 && a[current.a][current.b - 1] >= 0)
{
if (a[current.a][current.b - 1] == 0
|| dist < a[current.a][current.b - 1])
{
a[current.a][current.b - 1] = dist + 1;
queue2.add(new pointnode(current.a, current.b - 1));
}
}
// move down
if (current.a < m && a[current.a + 1][current.b] >= 0)
{
if (a[current.a + 1][current.b] == 0
|| dist < a[current.a + 1][current.b])
{
a[current.a + 1][current.b] = dist + 1;
queue2.add(new pointnode(current.a + 1, current.b));
}
}
// move right
if (current.b < n && a[current.a][current.b + 1] >= 0)
{
if (a[current.a][current.b + 1] == 0
|| dist < a[current.a][current.b + 1])
{
a[current.a][current.b + 1] = dist + 1;
queue2.add(new pointnode(current.a, current.b + 1));
}
}
dist++;
}
}
}
public static void main(String[] args)
{
int a[][] =
{
{ 0, 0,-3,-2, 0 },
{-3,-2, 0, 0, 0 },
{ 0, 0,-3, 0, 0 },
{-3,-3, 0,-2, 0 },
{ 0,-3, 0, 0,-2 }
};
gameplay(a);
System.out.println();
for (int d[] : a)
{
System.out.println(Arrays.toString(d));
}
}
}
My proposal in C++:
{
#include <iostream>
using namespace std;
enum obstacles {door, wall};
class Grid
{
private:
char ** spaces;
int size_y;
int size_x;
public:
Grid(int y, int x) : size_y(y), size_x(x)
{
spaces = new char*[size_y];
for(int i = 0; i < size_y; i++)
spaces[i] = new char[size_x];
for(int i = 0; i < size_y; i++)
for(int j = 0; j < size_x; j++)
spaces[i][j] = '?';
}
void printGrid()
{
for(int y = 0; y < size_y; y++)
{
cout << "|";
for(int x = 0; x < size_x; x++)
cout << spaces[y][x] << "|";
cout << endl;
}
}
void addPoint(int y, int x, obstacles o)
{
if(o == door)
spaces[y][x] = 'D';
else
spaces[y][x] = 'W';
}
void spread(int y, int x, int value, bool flag)
{
if(y >= size_y || y < 0 || x >= size_x || x < 0)
return;
if(flag)
{
flag = false;
goto special;
}
if(spaces[y][x] != 'D' && spaces[y][x] != 'W' && value < spaces[y][x])
{
spaces[y][x] = value;
special:
{}
spread(y + 1, x, value + 1, flag);
spread(y - 1, x, value + 1, flag);
spread(y, x + 1, value + 1, flag);
spread(y, x - 1, value + 1, flag);
}
}
void fillTable()
{
for(int y = 0; y < size_y; y++)
{
for(int x = 0; x < size_x; x++)
{
if(spaces[y][x] == 'D')
{
spread(y, x, '0', true);
}
}
}
}
};
int main()
{
Grid g(5, 5);
g.addPoint(2, 1, door);
g.addPoint(2, 2, wall);
g.addPoint(2, 3, wall);
g.addPoint(1, 3, wall);
g.addPoint(0, 4, door);
g.printGrid();
g.fillTable();
cout << endl;
g.printGrid();
}
}
Output:
|?|?|?|?|D|
|?|?|?|W|?|
|?|D|W|W|?|
|?|?|?|?|?|
|?|?|?|?|?|
|3|2|2|1|D|
|2|1|2|W|1|
|1|D|W|W|2|
|2|1|2|3|3|
|3|2|3|4|4|
int findNearestDoor(char a[][3],int size,int i,int j,int num,bool marker[][3])
{
if(i < 0 || j< 0 || i>=size ||j>=size) return 999;
if(a[i][j] == 'W') return 999;
if(a[i][j] == 'D') return num;
if(marker[i][j] == true) return 999;
marker[i][j] = true;
return min( findNearestDoor(a,size,i+1,j,num+1,marker),
findNearestDoor(a,size,i,j+1,num+1,marker),
findNearestDoor(a,size,i-1,j,num+1,marker),
findNearestDoor(a,size,i,j-1,num+1,marker) );
}
void fillEmptyCells(char a[][3],int size)
{
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
if(a[i][j] == 'X')
{
bool marker[3][3] = { {false},{false},{false} };
int num = findNearestDoor(a,size,i,j,0,marker);
a[i][j] = num + '0';
}
}
}
}
int main()
{
char a[3][3]={
{'X','W','W'},
{'X','X','D'},
{'X','X','X'}
};
int size = 3;
fillEmptyCells(a,size);
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
cout<<a[i][j]<<"\t";
}
cout<<endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
string mat[10];
int n;
queue<pair<int,int> > q;
int isSafe(int i,int j)
{
return (i >= 0 && i < n && j >= 0 && j < n && mat[i][j] == '.');
}
int main(void)
{
int dist=0,cnt;
cin >> n;
for(int i=0;i<n;i++)
cin >> mat[i];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(mat[i][j] == 'D')
q.push(make_pair(i,j));
}
}
while(true)
{
cnt=q.size();
if(cnt==0)
break;
while(cnt)
{
auto it=q.front();
q.pop();
if(isSafe(it.first+1,it.second))
q.push(make_pair(it.first+1,it.second));
if(isSafe(it.first-1,it.second))
q.push(make_pair(it.first-1,it.second));
if(isSafe(it.first,it.second+1))
q.push(make_pair(it.first,it.second+1));
if(isSafe(it.first,it.second-1))
q.push(make_pair(it.first,it.second-1));
if(mat[it.first][it.second] == '.')
mat[it.first][it.second]=(char)(dist+48);
cnt--;
}
dist++;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout << mat[i][j] << " ";
cout << "\n";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
string mat[10];
int n;
queue<pair<int,int> > q;
int isSafe(int i,int j)
{
return (i >= 0 && i < n && j >= 0 && j < n && mat[i][j] == '.');
}
int main(void)
{
int dist=0,cnt;
cin >> n;
for(int i=0;i<n;i++)
cin >> mat[i];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(mat[i][j] == 'D')
q.push(make_pair(i,j));
}
}
while(true)
{
cnt=q.size();
if(cnt==0)
break;
while(cnt)
{
auto it=q.front();
q.pop();
if(isSafe(it.first+1,it.second))
q.push(make_pair(it.first+1,it.second));
if(isSafe(it.first-1,it.second))
q.push(make_pair(it.first-1,it.second));
if(isSafe(it.first,it.second+1))
q.push(make_pair(it.first,it.second+1));
if(isSafe(it.first,it.second-1))
q.push(make_pair(it.first,it.second-1));
if(mat[it.first][it.second] == '.')
mat[it.first][it.second]=(char)(dist+48);
cnt--;
}
dist++;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout << mat[i][j] << " ";
cout << "\n";
}
return 0;
}
You can just do BFS with multiple sources. This works in exactly the same way as regular BFS, but instead of starting with just one node, you would put all your sources (doors) in the queue at the beginning. That is, make an initial pass over the grid to find all doors and start your BFS queue with all of them at distance 0. Then proceed with BFS as normal. This solution is O(grid size), which is optimal because you have to look at all the input.
- eugene.yarovoi May 25, 2014