Uber Interview experience

YOE: 5.5 years

Screening round

https://leetcode.com/problems/find-the-closest-palindrome/description
Verdict: Yes

DSA Round

There is a grid with police stations, 1 thief, and 1 bank. Every police station can patrol within k Manhattan distance. You need to determine if there is any path for the thief to reach the bank without encountering the police.

Approach: Multi-source BFS + DFS.

Follow-up: What if the value of k is different for every police station?

Approach: Dijkstra.

There was another follow-up that I don't remember. I was able to code both of the above approaches quickly, which is why we moved forward, but the interviewer said that this was not necessary.

Verdict: Strong Hire.

LLD Round

Design a data structure with time-to-live (TTL) where you receive (key, timestamp) pairs (in increasing order). You need to provide:
a) Count of all active keys
b) Count of active keys for a particular key
c) CRUD functions

Approach: Map<String, Queue>. At every function call, go through the map and remove expired keys. Also maintain global counters.

This approach worked, but the interviewer wanted something like a Queue where Pair = (timestamp, key). This way, instead of iterating over the map for every key, we can directly poll elements from the queue irrespective of the key, and update counts using Map<String, Integer> and a global totalCounter. The worst-case complexity is the same, but this is simpler and has better average-case complexity.

Verdict: Lean Hire.

HLD Round

Design a recommendation system for the Amazon homepage.

Approach: I converted this into a Top-K problem where I was tracking metrics like item view count and item buy count in Flink, then maintaining sorted sets and using these sets to get recommendations in real time.

I struggled with the following:
a) I was not able to calculate the scale estimations well.
b) I was only able to come up with two metrics to track, and then I mentioned comments/ratings, but I think the interviewer was expecting more metrics.
c) I did not consider that we need to have different sets for different countries.
d) My approach was maintaining different Redis caches for different metrics, so it lacked extensibility (I guess).

Verdict: Hire.

HM Round

Generic behavioral questions on past experiences and some hypothetical situations.

verdict: Strong Hire.