Uber·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026Remote

Summary

Uber SWE interview that was pretty much a single system design coding question with a meaty follow-up. The core problem was straightforward but the scaling discussion is where things got real and I felt underprepared.

Questions Asked (1)

Design and implement an ExpiringCounter class with an increment(key) method that records a timestamped event, and a getCount(key, windowSeconds) method that returns how many events occurred within the last N seconds. Then discuss how you'd scale this to handle 1 million increments per second.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

I got the basic class working fine.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (e.g., exact window semantics, memory constraints, concurrency) and then design a simple in-memory solution using a hash map of deques or a circular buffer per key. After implementing the basic version, discuss scaling to 1M increments/sec by sharding, using approximate algorithms like count-min sketch with time buckets, and leveraging distributed systems like Kafka and Redis.

Pro tip: Demonstrate awareness of the trade-off between accuracy and scalability: for 1M ops/sec, exact counting per key is infeasible, so propose probabilistic data structures or time-bucketed aggregation with eventual consistency.

1. Clarify Requirements

Ask about window semantics (sliding vs. tumbling), expected number of keys, memory limits, and consistency requirements. This shows you think before coding.

2. Design Single-Node Solution

Propose a hash map where each key maps to a deque of timestamps or a circular buffer of time buckets. Explain how increment adds a timestamp and getCount prunes old entries.

3. Implement and Analyze

Write pseudocode for the class, ensuring O(1) amortized increment and O(1) getCount (with pruning). Discuss time and space complexity, and potential optimizations like bucketing.

4. Scale to 1M ops/sec

Discuss partitioning by key across multiple nodes, using a distributed queue (e.g., Kafka) for increments, and approximate counting (e.g., count-min sketch) or pre-aggregation with time buckets to reduce memory and compute.

5. Address Trade-offs and Edge Cases

Talk about consistency vs. availability, latency, memory overhead, and handling hot keys. Mention monitoring and backpressure.

Key Points to Mention

Sliding window vs. tumbling window semantics and their impact on implementation.
Data structures: deque, circular buffer, time-bucketed counters, and their trade-offs.
Concurrency control (locks, sharding) for thread-safe increments.
Approximate counting algorithms (count-min sketch, HyperLogLog) for scalability.
Distributed architecture: sharding by key, using Kafka for ingestion, Redis for storage.
Trade-offs between accuracy, memory, and latency in large-scale systems.

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