Uber Freight Software Engineer Interview Experience — DSA, a File System LLD, and a URL Shortener Design

Round 1 — DSA

There is a car and N riders. Each rider has two constraints:

1. L[i] — the minimum number of other riders this rider is willing to share the ride with.
2. H[i] — the maximum number of other riders this rider is willing to share the ride with.

If k riders are selected, every selected rider must satisfy L[i] <= k - 1 <= H[i].

The goal is to maximize the number of riders who can ride together (i.e. maximize k).

Example:

N = 5
L = [0, 1, 1, 2, 2]
H = [1, 2, 2, 4, 4]
Output: 3

The required time complexity is O(N).

Round 2 — LLD

Design a basic file system that supports mkdir and ls. The interviewer mostly cared about the design and the approach, and I did not need to write complete runnable code. I had to draw an entity/class diagram and explain the design. The discussion covered:

1. File and Directory entities
2. Directory hierarchy
3. How to represent parent-child relationships
4. How mkdir creates a directory
5. How ls traverses/lists contents
6. Entity/class relationships

Round 3 — System Design

Design a distributed URL shortener. We discussed the overall distributed architecture and how it runs at scale, with these areas to focus on:

1. URL shortening API
2. Redirect API
3. Unique short-code generation
4. Database/storage
5. Caching
6. Distributed ID generation
7. Read/write scalability
8. Handling very high redirect traffic
9. Availability and fault tolerance
10. Expiration of URLs
11. Collision handling
12. Database partitioning/sharding