Implement a CSAT Sliding Window Tracker
DecagonSoftware Engineer · Technical ScreenLast updated
This question evaluates the ability to design and implement efficient data structures and algorithms for a sliding time-window tracker, covering time-based expiration, stateful updates, rolling averages with rounding, and nearest-rank percentile computation.
Design and implement a class that tracks customer satisfaction scores over a sliding time window.
A customer support conversation has:
conversation_id: str: a unique identifier for the conversation.score: int: an integer score from1to5, inclusive.timestamp: int: an integer timestamp. Calls torecordare made with strictly increasing timestamps.
The class should support the following API:
class CSATTracker:
def __init__(self, window_size: int):
pass
def record(self, conversation_id: str, score: int, timestamp: int) -> None:
pass
def get_average(self, current_time: int) -> float:
pass
def update(self, conversation_id: str, score: int) -> None:
pass
def get_percentile(self, current_time: int, p: int) -> int | None:
pass
Requirements:
__init__(window_size)initializes the tracker. A conversation is considered active at timecurrent_timeifcurrent_time - timestamp <= window_size.record(conversation_id, score, timestamp)records a new conversation. You may assume eachconversation_idis recorded at most once.get_average(current_time)returns the average score among all active conversations atcurrent_time, rounded to two decimal places usinground(x, 2). If there are no active conversations, return0.0.update(conversation_id, score)updates the score of an existing conversation only if that conversation is still active according to the latest time observed by the tracker. Updating a score must not change the original timestamp or ordering. If the conversation does not exist or has expired, do nothing.get_percentile(current_time, p)returns the score at percentilepamong active conversations atcurrent_time, where1 <= p <= 100. Use the nearest-rank definition: sort active scores in ascending order and return the element at indexceil(p / 100 * n) - 1. If there are no active conversations, returnNone.
Optimize for efficient expiration of old conversations and efficient queries.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.