Katkat
Back

Clarify and Design a Streaming Top-K Tracker

NVIDIASoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This question tests the ability to design an efficient data structure for maintaining the top-K elements in a high-throughput stream with time-windowing requirements.

Problem Statement

You are tasked with designing a system that tracks the 'Top-K' most frequent events (e.g., search queries) from a continuous stream of data.

Requirements

  1. High Throughput: The system must process millions of events per second.
  2. Time Window: The 'Top-K' calculation should be based on a sliding window of the last T minutes.
  3. Memory Efficiency: You cannot store the full history of every event; memory usage must be bounded.
  4. Interface: Provide an API track(event_id) to ingest data and get_top_k() to retrieve the current rankings.

Design Constraints

  • The system must handle high update frequency with low latency.
  • Explain how you would handle 'ties' (e.g., if two events have the same count).
  • Describe the trade-offs between a exact count approach versus an approximate count approach (e.g., Count-Min Sketch or Heavy Hitters).

Task

  1. Propose a data structure design that balances memory usage and query performance.
  2. Explain how you would implement the time-window expiration logic.
  3. Analyze the computational complexity of track() and get_top_k() operations under your proposed design.

Hints

Hint 1

Consider using a hash map to track counts paired with a min-heap, but reflect on how the heap would perform with frequent updates and expiration.

Hint 2

For the time-window requirement, look into partitioning the data into smaller time-buckets or using a decaying counter approach to avoid full re-calculations.

Hint 3

Evaluate if an approximate algorithm like Space-Saving or Count-Min Sketch could significantly reduce memory footprint while maintaining acceptable accuracy for top-K elements.

Follow-up questions

  • How would your design change if the total number of unique elements is significantly larger than the available RAM?
  • What modifications are necessary if the system needs to support distributed processing across multiple nodes?
  • How would you handle cold-start issues where the system has not yet received enough data to fill the window?