Katkat
Back

Design rolling-window conversation score tracker

DecagonSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Design a rolling-window tracker for streaming conversation scores that supports score updates, rolling average calculation, and maximum score queries.

Problem Statement

In customer support AI platforms, conversations are continuously monitored and assigned quality scores. Design a class RollingConversationTracker that tracks conversation quality scores over a rolling time window of W seconds.

Timestamps are given in whole seconds and are guaranteed to arrive in monotonically non-decreasing order.

Implement the following methods:

  • RollingConversationTracker(window_seconds: int): Initializes the tracker with a sliding time window of window_seconds.
  • record_score(timestamp: int, conversation_id: str, score: int) -> None: Records or updates the score of a conversation. If conversation_id was already recorded within the active window, its score and timestamp should be updated to the new values.
  • get_average_score(timestamp: int) -> float: Returns the average score across all distinct active conversations in the window (timestamp - window_seconds, timestamp]. If there are no active conversations, return 0.0. Round the result to two decimal places if needed.
  • get_max_score(timestamp: int) -> int: Returns the maximum score among all active conversations in the window (timestamp - window_seconds, timestamp]. If there are no active conversations, return -1.

Example

tracker = RollingConversationTracker(window_seconds=10)

tracker.record_score(1, "conv_A", 80)
tracker.record_score(3, "conv_B", 90)

# Active window at t=5 is (5 - 10, 5] = [-5, 5]. Both conv_A (80) and conv_B (90) are active.
tracker.get_average_score(5)  # returns 85.0
tracker.get_max_score(5)      # returns 90

# conv_A receives an updated score at t=8
tracker.record_score(8, "conv_A", 95)
tracker.get_average_score(8)  # returns (95 + 90) / 2 = 92.5

# At t=12, window is (2, 12]. conv_B (t=3) is active, conv_A (t=8) is active.
tracker.get_max_score(12)     # returns 95

# At t=14, window is (4, 14]. conv_B (t=3) expired. Only conv_A (t=8) remains.
tracker.get_average_score(14) # returns 95.0
tracker.get_max_score(14)     # returns 95

Constraints

  • 1 <= window_seconds <= 86400 (up to 24 hours)
  • 1 <= timestamp <= 10^9
  • timestamps in calls are monotonically non-decreasing: t_prev <= t_curr
  • 1 <= len(conversation_id) <= 32
  • 0 <= score <= 100
  • At most 100,000 total method calls.

Hints

Hint 1

Maintain a queue of timestamps or events to easily evict conversations that fall outside `timestamp - window_seconds`.

Hint 2

Because a conversation's score can be updated, keep a hash map storing each conversation's latest timestamp and current score to invalidate older entries lazily or eagerly.

Hint 3

Since the score range is small and bounded (0 to 100), a frequency array of score counts allows you to compute running sums and find the maximum score in O(1) time.

Follow-up questions

  • How would you support returning arbitrary percentiles (e.g., p95) within the rolling window?
  • If score values were arbitrary unbounded floating-point numbers instead of integers from 0 to 100, how would you maintain the maximum score efficiently?
  • How would you handle out-of-order events arriving with at most K seconds of network delay?