A Meta data pipeline processes real-time clickstream data, needing to identify unique visitors within a 15-minute rolling window. How would you design a data structure and algorithm to efficiently track unique visitor IDs, supporting both additions and automatic expiration?
The most efficient way to track unique visitor IDs within a rolling time window, supporting both additions and automatic expiration, involves combining a hash map (dictionary) with a deque (double-ended queue). The hash map, let’s call it active_visitor_counts, will store visitor_id -> count_of_active_events, tracking how many times each unique visitor has appeared within the current window. The deque, event_queue, will store (timestamp, visitor_id) tuples in chronological order, representing all events that have occurred.
Sliding Window Mechanism
When a new clickstream event (timestamp, visitor_id) arrives, it is appended to the event_queue. Concurrently, the count for visitor_id in active_visitor_counts is incremented. After adding the new event, the system checks the front of the event_queue. Any event (old_timestamp, old_visitor_id) whose old_timestamp is outside the current window (i.e., old_timestamp <= current_timestamp - window_duration) is removed from the event_queue. For each removed event, the count for old_visitor_id in active_visitor_counts is decremented. If a visitor's count in active_visitor_counts drops to zero, that visitor_id is entirely removed from the map, indicating they are no longer active within the window. The total number of unique active visitors at any point is simply the size of the active_visitor_counts hash map.
Best Practice
Ensure that timestamp consistency is maintained. All timestamps should be in a common unit, for example milliseconds since epoch, and monotonically increasing. For production systems, consider using a high-resolution, consistent time source. If events can arrive significantly out of order, this design might need a buffering layer before the windowing logic, or a more advanced time-windowing library that handles lateness. For single machine, in-memory scenarios, Python's collections.deque and a standard dictionary are highly efficient.
Edge Case Interviewers Probe For
Interviewers will often ask about memory constraints. If the number of unique visitors or the event velocity is extremely high, the active_visitor_counts map or event_queue could consume too much memory. Discuss strategies like using approximate data structures, for example HyperLogLog for unique counts if exactness is not critical, or partitioning the data across multiple machines if distributed processing is an option. They might also ask how to handle a visitor whose activity temporarily drops out of the window and then reappears. The current design correctly handles this by re-adding them to the active_visitor_counts map when they reappear.
Common Mistake
A common mistake is incorrectly decrementing counts or removing visitors from the active_visitor_counts map. Simply removing a visitor when their first entry in the queue expires is incorrect if they have other, more recent activities within the window. The count_of_active_events mechanism ensures that a visitor is only considered inactive when all their activities within the window have expired. Another mistake is not considering the overhead of managing the queue and map for extremely high event rates, leading to performance bottlenecks.
What the interviewer is checking
The interviewer is evaluating your ability to combine fundamental data structures to solve a real-world problem with specific constraints like real-time, sliding window, and expiration. They are looking for understanding of time and space complexity (O(1) average for add/remove operations in hash map and deque, O(W) for cleanup where W is the number of events in the window), handling dynamic data, and considering system design implications such as memory and concurrency for large-scale data processing.
Imagine you are running a popular coffee shop, and you want to know how many unique customers have visited in the last 15 minutes to adjust staffing. You cannot just count people coming in, because some might leave and come back, or stay longer than 15 minutes. To solve this, you set up two things: a "Customer Order Log" (your deque) and a "Current Active Customers Board" (your hash map).
Every time a customer places an order, you write down their name and the exact time in the Customer Order Log. If it is their first time ordering in the last 15 minutes, you also add their name to the Current Active Customers Board. If they have ordered before, you just increment a little tally next to their name on the board. Periodically, you look at the oldest entries in your Customer Order Log. If an order was placed more than 15 minutes ago, you erase it from the logbook and decrement the tally next to that customer's name on the Current Active Customers Board. If their tally on the board hits zero, it means all their recent orders have expired, so you erase them completely from the board. The number of names currently on the Current Active Customers Board tells you your unique customer count in the last 15 minutes!
Why interviewers ask this
Interviewers use this question to assess your foundational understanding of data structures and algorithms, specifically how to combine them to solve dynamic, real-time problems. It tests your ability to manage state over time, handle data expiration, and consider the performance implications of your choices at scale.
What a strong answer signals
A strong answer demonstrates clear thinking, knowledge of appropriate data structures (hash maps and deques), correct handling of the sliding window logic, and the ability to articulate time and space complexity. It also shows you can identify edge cases and discuss real-world considerations like memory limits and potential for out-of-order events.
Common follow-ups
- How would you handle events arriving significantly out of order, and how would that change your data structure design?
- What if the exact count is not required, but an approximate count is sufficient to save memory for extremely high cardinality? Which data structures would you consider?
- How would you scale this solution across multiple machines or a distributed streaming system like Apache Flink or Spark Streaming?
Advanced variation
Design a system to not just count unique visitors, but also identify the top N most frequent visitors within the same sliding window, while maintaining efficient updates and expiration. This would typically involve combining the current approach with a min-heap or a similar data structure to keep track of top frequencies dynamically.
An e-commerce platform wants to show real-time personalized recommendations based on products viewed by unique visitors within the last hour. Without an efficient sliding window unique tracker, recalculating unique users and their viewed products every minute would be computationally expensive. By employing the described data structure, the platform can continuously maintain an up-to-date count of unique active shoppers and their most recent interactions, allowing for immediate adjustments to recommendation algorithms or dynamic pricing strategies.
import collections
import time
class SlidingWindowUniqueTracker:
def __init__(self, window_duration_ms: int):
self.window_duration_ms = window_duration_ms # Window size in milliseconds
self.event_queue = collections.deque() # Stores (timestamp, visitor_id)
self.active_visitor_counts = collections.defaultdict(int) # visitor_id -> count of active events
def add_event(self, visitor_id: str, current_timestamp_ms: int):
# Add new event to the queue
self.event_queue.append((current_timestamp_ms, visitor_id))
self.active_visitor_counts[visitor_id] += 1
# Clean up expired events
self._clean_expired(current_timestamp_ms)
def _clean_expired(self, current_timestamp_ms: int):
while self.event_queue and self">.event_queue[0][0] <= current_timestamp_ms - self.window_duration_ms:
expired_timestamp, expired_visitor_id = self.event_queue.popleft()
self">.active_visitor_counts[expired_visitor_id] -= 1
if self">.active_visitor_counts[expired_visitor_id] == 0:
del self">.active_visitor_counts[expired_visitor_id]
def get_unique_count(self) -> int:
# The number of unique visitors is the size of the map
return len(self.active_visitor_counts)- 1Combine a hash map and a deque for efficient sliding window unique tracking.
- 2The deque maintains events in chronological order for time-based expiration.
- 3The hash map tracks active unique IDs and their event counts within the window.
- 4Cleanup involves popping expired events from the deque and decrementing counts in the map.
- 5The final unique count is simply the size of the hash map, offering O(1) retrieval.