Uber·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

May 2026

Summary

Uber system design round for a software engineering role. The whole session was basically one big distributed systems problem about scheduling data at scale. Pretty intense if you haven't touched MapReduce in a while.

Questions Asked (1)

Design a MapReduce pipeline that takes large-scale user scheduling data (busy time intervals) and computes common free time slots of at least a given duration d for a specified group of users. Walk through the map outputs, partitioning strategy, reduce logic, time discretization, handling data skew, and how you'd validate correctness at scale.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

This was a lot to hold in your head at once.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then outline a MapReduce pipeline that discretizes time into slots, maps each user's busy intervals to slot-level busy markers, and reduces to find slots where all users are free. Discuss partitioning, skew handling, and validation strategies to ensure scalability and correctness.

Pro tip: Mention that you would use a composite key (user group + time slot) to ensure all relevant data for a slot goes to the same reducer, and consider using a combiner to pre-aggregate busy counts per slot per user to reduce shuffle size.

1. Clarify Requirements and Assumptions

Ask about data scale, time granularity, definition of 'free' (e.g., no busy intervals overlapping), and whether the group of users is fixed or dynamic. Confirm that duration d is in the same units as the time slots.

2. Design Time Discretization and Map Phase

Discretize time into fixed-size slots (e.g., 15 minutes) and map each user's busy interval to all overlapping slots, emitting (slot, user_id) as key-value pairs. Alternatively, emit (user_id, slot) and use a secondary sort, but ensure all users for a slot are processed together.

3. Partitioning and Reduce Logic

Partition by time slot (or a composite key of group and slot) so that all busy markers for a slot go to the same reducer. In the reducer, count distinct users busy in that slot; if count < total users in group, the slot is free for all. Then, post-process to find contiguous free slots of length >= d.

4. Handle Data Skew and Optimizations

Address skew from popular slots or users by using a combiner to pre-aggregate per user per slot, or by salting keys. Consider using a two-stage MapReduce: first compute per-user free slots, then intersect across users.

5. Validation and Scalability

Validate correctness by comparing with a brute-force approach on small data, and use unit tests for edge cases (e.g., overlapping intervals, d=0). At scale, monitor reducer times, use sampling, and consider incremental updates if data changes frequently.

Key Points to Mention

Time discretization: choose slot size based on required precision and d; ensure intervals are handled correctly at boundaries.
Map output: emit (slot, user_id) or (user_id, slot) with careful design to avoid missing users in a slot.
Partitioning: use time slot as partition key to group all users for a slot; consider composite key if multiple groups.
Reduce logic: count distinct busy users per slot; free if count < group size; then find contiguous free slots >= d.
Skew handling: use combiners, salting, or two-stage aggregation to mitigate hot keys.
Validation: unit tests, brute-force comparison on small data, and monitoring for performance at scale.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.