## Amazon Interview Question for SDE-3s

• 1
of 1 vote

Country: United States

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

We need a node of bfs like
Node{
int row, col;
boolean flipped;
}

and visited boolean will be a 3D array
boolean visited[][][] = new boolean[rows][cols];

If we are on a node we will visit all the neighbors which are not visited and mark the visited [row][col] as done and also visit all the neighbours which are zero and push these node as flipped in queue. When visiting these nodes we need to check if visited[row][col] is done or not.

At the end we will reach with the minimum steps to reach the destination.

Note that the same problem can be done for k flips allowed as well, we will just need to increase the first dimension to k instead of 2 and similarly check for the destination.

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

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

When is visited[row][col] set?

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

``````MAX_FLIPS = 1
START,END = (0,0),(2,1)
INP = ["101",
"101",
"101",
"111"]
N,M = len(INP), len(INP)

cells = [(0,0)]*(N+2)*(M+2) # add border for simpler checks
for i,r in enumerate(INP):
for j,x in enumerate(r):
cells[(i+1)*(N+2)+j+1] = (int(x),0) # (cell_val, cell_state)
# i-bit set in cell_state means the cell was visited after i flipps

starti = START+1 + (START+1)*(N+2)
endi = END+1 + (END+1)*(N+2)

q = [(starti, 0, 0)] # (pos, steps, flips)
while q:
(pos, steps, flips) = q.pop()
cell_val, cell_state = cells[pos]
if (pos % (N+2)) in [0, N+1] or (pos / (N+2)) in [0, M+1]: # skip border
continue
if cell_state & ((1 << (flips+1)) - 1) or flips == MAX_FLIPS and cell_val == 0:
continue
flips += (1-cell_val)
cell_state |= (1 << flips)
if pos == endi:
print (steps)
break
cells[pos] = (cell_val, cell_state)
q = [(pos-1, steps+1, flips),
(pos+1, steps+1, flips),
(pos-N-2, steps+1, flips),
(pos+N+2, steps+1, flips)] + q``````

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

``````#include <iostream>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;

// M x N matrix
#define M 10
#define N 10

// queue node used in BFS
struct Node
{
// (x, y) represents matrix cell coordinates
// dist represent its minimum distance from the source
int x, y, dist;
};

// Below arrays details all 4 possible movements from a cell
int row[] = { -1, 0, 0, 1 };
int col[] = { 0, -1, 1, 0 };

// Function to check if it is possible to go to position (row, col)
// from current position. The function returns false if (row, col)
// is not a valid position or has value 0 or it is already visited
bool isValid(int mat[][N], bool visited[][N], int row, int col)
{
return (row >= 0) && (row < M) && (col >= 0) && (col < N)
&& mat[row][col] && !visited[row][col];
}

// Find Shortest Possible Route in a matrix mat from source
// cell (i, j) to destination cell (x, y)
void BFS(int mat[][N], int i, int j, int x, int y)
{
// construct a matrix to keep track of visited cells
bool visited[M][N];

// initially all cells are unvisited
memset(visited, false, sizeof visited);

// create an empty queue
queue<Node> q;

// mark source cell as visited and enqueue the source node
visited[i][j] = true;
q.push({i, j, 0});

// stores length of longest path from source to destination
int min_dist = INT_MAX;

// run till queue is not empty
while (!q.empty())
{
// pop front node from queue and process it
Node node = q.front();
q.pop();

// (i, j) represents current cell and dist stores its
// minimum distance from the source
int i = node.x, j = node.y, dist = node.dist;

// if destination is found, update min_dist and stop
if (i == x && j == y)
{
min_dist = dist;
break;
}

// check for all 4 possible movements from current cell
// and enqueue each valid movement
for (int k = 0; k < 4; k++)
{
// check if it is possible to go to position
// (i + row[k], j + col[k]) from current position
if (isValid(mat, visited, i + row[k], j + col[k]))
{
// mark next cell as visited and enqueue it
visited[i + row[k]][j + col[k]] = true;
q.push({ i + row[k], j + col[k], dist + 1 });
}
}
}

if (min_dist != INT_MAX)
cout << "The shortest path from source to destination "
"has length " << min_dist;
else
cout << "Destination can't be reached from given source";
}

// Shortest path in a Maze
int main()
{
// input maze
int mat[M][N] =
{
{ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
{ 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 },
{ 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },
{ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
{ 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 },
};

// Find shortest path from source (0, 0) to
// destination (7, 5)
BFS(mat, 0, 0, 7, 5);

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.