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

SeniorPrefer not to say

May 2026

Summary

Google system design round for a software engineering role. The whole session was basically one big question about ad serving, and they kept pushing on follow-ups until I ran out of things to say.

Questions Asked (1)

Design an ad serving system with a get_ads(k) method that returns the top-k ads ranked by some priority score. Walk through your class design, how you'd maintain the heap on inserts and updates, and what trade-offs you'd make around retrieval complexity.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

I went straight for a max-heap and started talking through Ad and AdStore classes before I'd even pinned down what the scoring function looked like.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements: scale, update frequency, latency, and whether k is fixed or variable. Then propose a class design with a max-heap (or min-heap of size k) for efficient top-k retrieval, and discuss how to handle inserts and updates (e.g., lazy deletion or decrease-key). Finally, analyze trade-offs between retrieval complexity and update complexity, and suggest optimizations like caching or bucketing for high-throughput scenarios.

Pro tip: Emphasize that in real ad systems, updates (e.g., bid changes) are frequent, so a pure heap with O(log n) updates may be too slow; consider a hybrid approach like a heap with lazy updates or a bucketed priority queue to balance read and write performance.

1. Clarify Requirements

Ask about scale (number of ads, QPS), update frequency, latency requirements, and whether k is fixed or variable. This determines the appropriate data structure and trade-offs.

2. Design Class Interface

Define the Ad class (id, score, metadata) and the AdServer class with methods: insert(ad), update(ad_id, new_score), and get_ads(k). Consider thread-safety if needed.

3. Choose Data Structure

Use a max-heap for O(1) access to top ad and O(log n) insert/update. For get_ads(k), either extract k elements (O(k log n)) or maintain a sorted structure. Discuss alternatives like balanced BST or skip list.

4. Handle Updates Efficiently

For score updates, use a hash map to locate the ad in the heap, then perform decrease-key/increase-key (O(log n)). Alternatively, use lazy deletion: mark old entries as stale and skip them during retrieval.

5. Analyze Trade-offs and Optimize

Compare retrieval vs update complexity. If reads dominate, consider a sorted array with O(1) retrieval but O(n) updates. If updates dominate, use a heap with lazy updates. For high throughput, propose caching top-k results or bucketing by score ranges.

Key Points to Mention

Heap operations: insert O(log n), get top O(1), extract top O(log n), update O(log n) with decrease-key.
Lazy deletion: avoid O(n) removal by marking stale entries and skipping them during retrieval.
Trade-offs: heap gives O(k log n) for get_ads(k) but O(log n) updates; sorted array gives O(1) retrieval but O(n) updates.
Alternative data structures: balanced BST (O(log n) all ops), skip list, or bucketed priority queue for approximate top-k.
Scalability: sharding ads by category or using a distributed cache for top-k results.
Concurrency: use read-write locks or lock-free data structures if multiple threads access the heap.

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