Uber | L4 | India | Reject

The recruiter reached out to me through LinkedIn.

Both rounds were coding rounds scheduled over Zoom.

1st Round

The interviewer was extremely friendly. He asked me to calm myself down and said I could grab coffee/tea if I wanted. Only one question was asked. The interviewer told me that he was not expecting an answer or the most optimized answer, but would look at my approach. I missed the optimization part of not putting the cell in the grid if we have reached it with a bigger value of K. Shortest Path in a Grid with Obstacles Elimination (Leetcode)

2nd Round

Given a continuous input stream of data:

User City Event Timestamp user1 Blgr RIDE_REQUESTED timestamp1 user2 Blgr RIDE_REQUESTED timestamp3 user1 Blgr RIDE_CANCELLED timestamp2 user1 Blgr COMPLETED timestamp4

The input stream is not ordered based on timestamp, as in an event occurring later can come first. You have to put this in a data structure to support timestamp-based queries, like "Give a list of RIDE_REQUESTED for the Blgr city from [timestamp1,.. timestamp5]"

Solutions discussed:

1. I suggested using an ordered map, but the interviewer said that the data was too much and insertion in an ordered map would take log n, which is not feasible.
2. Next, I suggested using an unordered map and using a for loop to run on timestamps. He rejected this saying, if the range asked is 1 to 1000 timestamps and there are very few entries for this timestamp, then your for loop will be inefficient.
3. After this, I discussed B+ Tree, segment tree, using the array's index and doing binary search over it.
4. In the end, he asked me to implement a segment tree, which I was not confident of from an implementation perspective, so I implemented the unordered_map solution.

Throughout the interview, the interviewer kept suggesting I use basic data structures and think about what the STL library actually uses to implement a Map. I really enjoyed this round because of the discussion that happened and how good the interviewer was at quickly grasping whatever solution I was suggesting.