Uber Interview Question
SDE-3sCountry: India
Interview Type: In-Person
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]
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):
- rexwulf October 02, 20181. 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.