## Amazon Interview Question

Country: India

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

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.

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

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.

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

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

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

This will take O(n^3) if grid is n*n .

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

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

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

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.

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

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.

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

How do you handle walls?

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

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 :)

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

is this brutal force? you need to loop through all the door, right?

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

Code for this solution...-2 represents door and -3 represents wall

import java.util.Arrays;

public class game
{
public static void gameplay(int a[][])
{
int m = a.length - 1;
int n = a[0].length - 1;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (a[i][j] == -2)
{
}
}
}
while (!queue.isEmpty())
{
pointnode d = queue.remove();
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;
}
}
// 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;
}
}
// 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;
}
}
// 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;
}
}
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));
}
}
}

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

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')
{
}
}
}
}
};

int main()
{
Grid g(5, 5);
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|

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

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;
}

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

#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;
}

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

#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;
}

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.