Amazon SDE-1 Test

general
1

Hello I gave amazon sde-1 test although i am certain i won’t be selected because i couldn’t solve the below problem but can you please guide me how such problems should be approached.

There are servers in 2-D grid with 0 denoting not-updated server and 1 denoting updated server.Each Updated server can push update to it’s adjacent not-updated servers(Which is either above,below,left or right a given server) in a single day.Find mininum number of days it will take to get all servers updated or return -1 if all servers can’t be updated

I/P :
5,5
[[1,0,0,0,0],
[0,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,0],
[0,0,0,0,1]]

O/P - > 4

1 Like
2

Use queue.

3

what was the time complexity

5

Can you please tell how can we solve this using queue.

6

I don’t know bro it was not mentioned.

7

Use graph traversal such as bfs which involves Q . Whenever u find 1 check all 4 adjacent and make 0 as -1 . And Mark as visited , in a single traversal do it for all 1s
Now check for all -1 and make them 1 and repeat above process

The number of traversal will be answer

8

Use multi source BFS.

9

can someone please suggest me a matrix in which all the servers don’t get updated ? i’m having problem visualizing one …please suggest a matrix other than one having all zeros

10

Classic BFS question.
Push every position of 1 in the queue, then start BFS and keep picking min of all 4 directional path. I hope this helps.

11

I think the answer is the cell which has all 1’s far from it .

12

Classic BFS. I got similar one in Freshworks interview asking how many days it’ll take to get all people’s infected in a 2d-grid.

1 Like
13

Find minimum Manhattan distance from all positions of 1s to the adjacent blocks of all four corners of the matrix and store them in four different arrays then find minimum from each array and answer will be maximum of these four minimums +1.
In the given eg.
let a1,a2,a3 and a4 store the minimum Manhattan distances from positions of ones to adjacent cells of top left,top right,bottom left and bottom right corners.
Therefore
a1={1,1,3,5,7}
a2={3,3,3,3,3}
a3={3,3,3,3,3}
a4={1,1,3,5,7}
ans=max(min(a1),min(a2),min(a3),min(a4))+1
=max(1,3,3,3)+1
=3+1
=4

14

Smilar to this.