Uber Interview Question for SDE-3s


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 3 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.

- rexwulf October 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 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]

- Rajat.nitp December 13, 2018 | Flag Reply
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.

- gDeepS July 04, 2018 | Flag Reply
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?

- nitinsharma021 October 15, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More