Katkat
Back

Design a top-build target tracker

NVIDIASoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests object-oriented design and data structure proficiency by requiring the implementation of a tracker that maintains the top-K most frequent entities within a sliding time window of events.

Problem Statement

Design a TopTracker class that tracks the frequency of unique entity IDs (represented as strings) received over a sliding window of time. The tracker should support reporting the top-K most frequent entities currently active in the window.

Requirements

Implement the following interface:

class TopTracker:
    def __init__(self, window_size_ms: int, k: int):
        """Initializes the tracker with a time window and result size."""

    def record_event(self, entity_id: str, timestamp_ms: int) -> None:
        """Records an occurrence of an entity at a specific time."""

    def get_top_k(self, current_timestamp_ms: int) -> List[str]:
        """Returns the top-K entities based on frequency in the window [current_timestamp - window_size, current_timestamp]."""

Constraints

  • Events may arrive with non-monotonic timestamps, but they must be processed relative to the provided current_timestamp_ms during queries.
  • If multiple entities have the same frequency, break ties by selecting the lexicographically smaller ID.
  • Efficiency is critical: queries should be faster than a full scan of the event history.

Example

tracker = TopTracker(window_size_ms=1000, k=2)
tracker.record_event("A", 1000)
tracker.record_event("B", 1200)
tracker.record_event("A", 1500)
# get_top_k(1800) -> ["A", "B"] (A: 2, B: 1)

Edge Cases

  • The window contains no events.
  • Fewer than K unique entities exist in the window.
  • Multiple entities share the exact same frequency count.

Hints

Hint 1

Use a queue or a similar structure to store events to efficiently expire those that fall outside the current sliding window.

Hint 2

Maintain a hash map to keep track of the current frequency counts of all active entities.

Hint 3

Consider using a combination of a hash map for counts and a balanced BST or a sorted data structure to maintain the top-K list with efficient updates.

Follow-up questions

  • How would you optimize the `get_top_k` operation if K is significantly smaller than the number of unique entities?
  • How would the design change if the incoming event stream was multi-threaded and required thread safety?
  • If memory is extremely constrained and you only need an approximate top-K, what data structure could you use to replace the exact frequency counter?