← Pinterest Interview Insights

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

Senior
May 2026

Summary

Pinterest system design round focused entirely on ad impression processing, building up from a batch query to a full streaming design with sliding windows. Pretty focused scope but the follow-up complexity caught me off guard.

Questions Asked (2)

Q1

Design a class that takes a list of ad impression log entries (each with an ad ID and timestamp) and returns the top-K ad IDs by total impression count.

Algorithms & Data StructuresSystem Design
Author's notes

Started with a hash map to count impressions per ad, then a min-heap of size K to track the top results.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (e.g., data size, whether the class processes logs in batches or streams, and if K is fixed). Then design a class that aggregates counts using a hash map and uses a min-heap of size K to efficiently find the top-K ad IDs, discussing time and space complexity.

Pro tip: Mention that for streaming data, you can maintain the heap incrementally, and for batch processing, consider using a hash map followed by a heap or quickselect. Also, discuss how to handle ties and the possibility of using a count-min sketch for approximate results if memory is constrained.

1. Clarify Requirements

Ask about input size, whether logs are processed in batches or as a stream, if K is fixed or variable, and if exact or approximate results are acceptable.

2. Design Data Structures

Use a hash map to count impressions per ad ID. For top-K, use a min-heap of size K to keep the K highest counts, or sort the counts if batch processing.

3. Define Class Interface

Outline methods: a constructor to initialize, a method to add a log entry (if streaming), and a method to get top-K ad IDs. Consider thread-safety if needed.

4. Analyze Complexity

Explain time complexity: O(N log K) for streaming with heap, O(N + M log M) for batch with sorting (M unique ads). Space complexity: O(M + K).

5. Discuss Optimizations and Trade-offs

Mention alternatives like quickselect for batch (O(N) average), using a count-min sketch for approximate top-K with limited memory, and handling ties or frequent updates.

Key Points to Mention

  • Hash map for frequency counting
  • Min-heap of size K for efficient top-K retrieval
  • Time and space complexity analysis
  • Handling streaming vs. batch processing
  • Tie-breaking and stability of results
  • Scalability considerations (e.g., distributed counting, approximate algorithms)

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

Q2

Extend the design into a streaming system: implement ingestImpressions(adId, timestamp) and getCommonAds(K, windowSeconds) that only counts impressions within the last N seconds. How do you evict stale data efficiently, and what are the time and space complexity tradeoffs?

System DesignAlgorithms & Data StructuresTechnical Trade-offs
Author's notes

This is where things got messy for me.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and constraints, then propose a sliding window approach using a time-ordered data structure like a deque or a circular buffer. Discuss how to efficiently evict stale data, either lazily on read or actively on write, and analyze the time and space complexity tradeoffs of your chosen design.

Pro tip: Mention that you can use a min-heap keyed by timestamp for eviction, but a deque is more efficient for FIFO eviction since timestamps are non-decreasing. Also, consider using a hash map from adId to a deque of timestamps for O(1) access to each ad's impressions.

1. Clarify Requirements and Constraints

Ask about the expected scale (number of ads, impressions per second), the definition of 'common ads' (top K by count?), and whether the window is fixed or sliding. Confirm that timestamps are monotonically increasing.

2. Design Data Structures

Propose a hash map from adId to a deque of timestamps for each ad's impressions within the window. Alternatively, use a global time-ordered structure like a deque of (timestamp, adId) pairs for eviction, combined with a count map.

3. Implement Ingest and Eviction

For ingestImpressions, append the timestamp to the ad's deque and update counts. For eviction, remove timestamps older than the window from the front of deques, either lazily during getCommonAds or actively on each ingest.

4. Implement getCommonAds

To get top K ads, maintain a count of impressions per ad within the window. Use a min-heap of size K or quickselect to find the top K ads by count. Ensure stale data is evicted before counting.

5. Analyze Complexity and Tradeoffs

Discuss time complexity: O(1) amortized for ingest and eviction, O(N) for getCommonAds if scanning all ads, or O(N log K) with heap. Space complexity: O(total impressions in window). Compare lazy vs active eviction and their impact on latency.

Key Points to Mention

  • Use a sliding window with a deque per ad to store timestamps, allowing O(1) amortized eviction of stale entries.
  • Lazy eviction (on read) vs active eviction (on write): tradeoff between write latency and read latency.
  • For getCommonAds, maintain a count map and use a heap or quickselect to find top K efficiently.
  • Time complexity: ingest O(1) amortized, getCommonAds O(N + N log K) where N is number of ads with impressions in window.
  • Space complexity: O(M) where M is total number of impressions within the window, which can be large; consider approximate methods if memory constrained.
  • Alternative: use a time-bucketed approach (e.g., per-second buckets) to reduce per-impression overhead and simplify eviction.

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