## Uber Interview Question for SDE-3s

Country: India
Interview Type: In-Person

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

Whether path exists or not, and the shortest path can be found using BFS.

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

In order to find the cell (x,y) to toggle so that we get the shortest path, let the source be (sx,sy) and destination be (dx,dy):

1. calculate dp1 from (sx,sy) to every cell (x,y) storing the shortest path.
2. calculate dp2 from (dx,dy) to every cell(x,y) storing the shortest path.
3. create a variable shortest_path = INF.
4. Traverse through the matrix and if for that cell, dp1+dp2 < shortest_path, update shortest_path.

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

How does this ensure that only one cell value was toggled since while reaching a specific 1 i.e. blocked cell we maybe have reached there by toggling multiple cell values?

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

Question 1 and question 2 are easy. Just simple BFS will do the trick.
Now comes the third part. For that let we define dp[x][y][z] where the value of z is either 0 or 1. Value 0 means that the path till (x,y) does not have a toggled bit while 1 means that path till (x, y) have some bit toggled. If the bit is toggled, then we cannot toggle it again, while if the bit is not toggled we can move ahead by toggling it or not toggling it.

Instead of pushing coordinate (x, y) in the queue we will now push (x, y, 0/1). 0 will denote (x, y) is visited via normal bfs while 1 will denote it is visited by toggled path.

Now we start the bfs from source and visit neighboring cells. Let's say we are at (x1, y1) and we are looking at (x2, y2). Now there are only possibilities. (x2, y2) is 0 or (x2, y2) is 1. If (x2, y2) is 0 then we continue our normal bfs by inserting (x2, y2, 0) and update dp[x2][y2][0], but if (x2, y2) is 1 then we will first see if (x1, y1) has been through a toggled path or not. If it is from a toggled path then we dont visit (x2, y2) while if it is not then we update dp[x2][y2][1] and insert (x2, y2, 1).

final ans will be min of dp[dx][dy][0] and dp[dx][dy][1]

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.