PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • easy
  • Decagon
  • Coding & Algorithms
  • Software Engineer

Implement a CSAT Sliding Window Tracker

Company: Decagon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

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 from `1` to `5`, inclusive. - `timestamp: int`: an integer timestamp. Calls to `record` are made with strictly increasing timestamps. The class should support the following API: ```python 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: 1. `__init__(window_size)` initializes the tracker. A conversation is considered active at time `current_time` if `current_time - timestamp <= window_size`. 2. `record(conversation_id, score, timestamp)` records a new conversation. You may assume each `conversation_id` is recorded at most once. 3. `get_average(current_time)` returns the average score among all active conversations at `current_time`, rounded to two decimal places using `round(x, 2)`. If there are no active conversations, return `0.0`. 4. `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. 5. `get_percentile(current_time, p)` returns the score at percentile `p` among active conversations at `current_time`, where `1 <= p <= 100`. Use the nearest-rank definition: sort active scores in ascending order and return the element at index `ceil(p / 100 * n) - 1`. If there are no active conversations, return `None`. Optimize for efficient expiration of old conversations and efficient queries.

Quick Answer: 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 a sliding-window customer satisfaction tracker. Each conversation has: - `conversation_id: str` - `score: int` in the range `1` to `5` - `timestamp: int` A conversation is active at time `current_time` if `current_time - timestamp <= window_size`. For this problem, implement a function `solution(window_size, operations)` that simulates the following API: - `record(conversation_id, score, timestamp)`: record a new conversation. Each `conversation_id` is recorded at most once. - `get_average(current_time)`: return the average score of all active conversations, rounded with `round(x, 2)`. If there are no active conversations, return `0.0`. - `update(conversation_id, score)`: update the score of an existing conversation only if it is still active according to the latest time observed by the tracker. Updating does not change its original timestamp or order. - `get_percentile(current_time, p)`: among active conversations, sort scores in ascending order and return the nearest-rank percentile: the element at index `ceil(p / 100 * n) - 1`. If there are no active conversations, return `None`. The function receives a list of operations and must return the outputs of all query operations (`get_average` and `get_percentile`) in order.

Constraints

  • `0 <= window_size <= 10^9`
  • `0 <= len(operations) <= 2 * 10^5`
  • `1 <= score <= 5`
  • Each `conversation_id` appears in at most one `record` operation
  • `1 <= p <= 100` for percentile queries
  • All operations with a time argument (`record`, `get_average`, `get_percentile`) are given in non-decreasing time order; `record` timestamps are strictly increasing

Examples

Input: (5, [("record", "c1", 5, 1), ("record", "c2", 3, 2), ("get_average", 2), ("get_percentile", 2, 50), ("update", "c1", 1), ("get_average", 2), ("get_percentile", 2, 50), ("get_average", 8), ("update", "c2", 5), ("get_percentile", 8, 90)])

Expected Output: [4.0, 3, 2.0, 1, 0.0, None]

Explanation: At time 2, active scores are [5, 3], so average is 4.0 and the 50th percentile is 3. After updating c1 to 1, active scores are [1, 3]. By time 8 both conversations have expired, so the average is 0.0 and percentile is None. The update to c2 at time 8 does nothing because it is expired.

Input: (0, [("record", "a", 4, 10), ("get_average", 10), ("get_percentile", 10, 100), ("get_average", 11), ("update", "a", 1), ("get_percentile", 11, 1)])

Expected Output: [4.0, 4, 0.0, None]

Explanation: With a window size of 0, a conversation is active only at its exact timestamp. So score 4 is active at time 10, but expired by time 11. The update at time 11 has no effect.

Input: (3, [("record", "x", 2, 1), ("record", "y", 2, 2), ("record", "z", 5, 4), ("get_percentile", 4, 75), ("update", "y", 4), ("get_average", 4), ("get_percentile", 4, 75), ("get_average", 6)])

Expected Output: [5, 3.67, 5, 5.0]

Explanation: At time 4, active scores are [2, 2, 5], so the 75th percentile is 5. After updating y to 4, the scores become [2, 4, 5], giving average 3.67. By time 6, only z remains active, so the average is 5.0.

Input: (4, [("get_average", 1), ("get_percentile", 1, 30)])

Expected Output: [0.0, None]

Explanation: No conversations were recorded, so the average is 0.0 and the percentile query returns None.

Hints

  1. Because time only moves forward, you can keep conversations in a queue and expire old ones from the front.
  2. Scores only range from 1 to 5, so percentile queries can be answered from score frequencies instead of sorting every time.
Last updated: May 12, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement a Recipe Cart - Decagon (medium)
  • Enumerate 4x4 Tic-Tac-Toe Games - Decagon (medium)
  • Design rolling-window conversation score tracker - Decagon (easy)
  • Compute exclusive CPU time from nested logs - Decagon (medium)
  • Design a Tic-Tac-Toe Engine - Decagon (medium)