Amazon Interview Question
SDE-3sCountry: United States
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[2][rows][cols];
If we are on a node we will visit all the neighbors which are not visited and mark the visited [0][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[1][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.
MAX_FLIPS = 1
START,END = (0,0),(2,1)
INP = ["101",
"101",
"101",
"111"]
N,M = len(INP[0]), 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[0]+1 + (START[1]+1)*(N+2)
endi = END[0]+1 + (END[1]+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
- Nits August 15, 2019