Grokking Amazon Coding Interview

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Smoke

· 4 years ago

Introduction/Solution lacks additional explanation. Why use DFS/BFS? What is the connection to those technique is not explained at all.

M

Mikhail Putilov

· 4 years ago

Why space complexity for BFS is min (M*N) ? what does it even mean?

Show 3 replies
R

Runyao Fan

· 4 years ago

Why is it that the BFS solution has a space complexity of O(min(M, N))? Why doesn't the queue size grow beyond min(M, N)?

Show 7 replies
M

Mike Xu

· 3 years ago

To clarify the space complexity of BFS traversal of a matrix:

When you start traversing a matrix from the corner, the maximum number of cells/nodes you can have in the queue is k where k is the number of cells on a diagonal line in the matrix, which means k = min(M, N).

When you start traversing a matrix from the centre, the maximum number of cells/nodes you can have in the queue is {1, 4, 8, 12, 16, ..., 4i} where i is the i-th layer. And such cells fit in a matrix of min size {1, 4, 9, 16, 25, ..., i*i} respectively. We know that i is min(M, N), so yet again we have space complexity of O(4 * min(M, N)) which is O(min(M,N)).

https://stackoverflow.com/a/75422161/9406517

E

evmorov

· 3 years ago

When can BFS be useful? For me, it looks like a more complicated version of DFS.

Show 2 replies
S

Sheen Goh

· 4 years ago

Hello

S

sweetykumari

· 3 years ago

Hi , pls anyone share BFS code in C#.

M

Manthan

· 4 years ago

can someone please explain what does this do and why are we doing this? Queue neighbors = new LinkedList(); neighbors.add(new int[] { x, y }); while (!neighbors.isEmpty()) { int row = neighbors.peek()[0]; int col = neighbors.peek()[1]; neighbors.remove();

Show 1 reply
R

Richard Yuan

· 4 years ago

Is there a specific reason why you used neighbors.extend() for a deque rather than neighbors.append()? The iterable only contains a single tuple in this case.

Show 3 replies
A

Anand Mohan

· 3 years ago

Given :

DFS recursion stack can go  deep when the whole matrix is filled with '1's. Hence, the space complexity will be , where ‘M’ is the number of rows and 'N' is the number of columns of the input matrix.

All the matrix element will not be in one recursion stack. It will part of call back to left and right sub-path. So, the space complexity should be less then (M*N)

I think for DFS as well the Space Complexity would be O(min(M, N))

Please correct me If I am wrong.

Show 3 replies