## Uber Interview Question

SDE-3s**Country:**India

**Interview Type:**In-Person

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.

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]

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

- gDeepS July 04, 2018