Design rolling-window conversation score tracker
Company: Decagon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Design a class that tracks conversation scores over a rolling time window.
## Requirements
You are given a window size `W` (in seconds) at initialization time.
Each conversation event has:
- `conversation_id` (string/int, unique)
- `timestamp` (integer seconds)
- `score` (integer in `[1, 5]`)
Implement the following operations:
1. `record(conversation_id, timestamp, score)`
- Records a new conversation score.
- Assume calls to `record` arrive with **non-decreasing** `timestamp`.
2. `get_average(now)`
- Returns the average score of all conversations with timestamps in the **active window**:
- `(now - W, now]` (i.e., strictly greater than `now-W` and up to `now`, inclusive).
- If there are no active conversations, return `0` (or specify a reasonable alternative).
3. `update(conversation_id, new_score, now)`
- Updates the score for `conversation_id` **only if** that conversation is currently in the active window at time `now`.
- If the conversation is not active (expired or missing), ignore or return an error indicator (define your choice).
4. `get_top_percentile_nth_score(p, n, now)`
- Consider only active-window conversations at time `now`.
- Let `m` be the number of active conversations.
- Define the **top `p` percentile** as the highest-scoring `k = ceil(p/100 * m)` conversations.
- Sort active conversations by `(score DESC, timestamp ASC, conversation_id ASC)`.
- Return the **score** of the `n`-th conversation (1-indexed) within that top-percentile subset.
- If `m = 0` or `n > k`, return `null` (or a sentinel).
## Constraints (for design purposes)
- Up to ~`2e5` total operations.
- `W` can be large.
- Scores are integers in `[1,5]`.
Explain any additional assumptions you make and discuss expected time/space complexity for each operation.
Quick Answer: This question evaluates a candidate's ability to design efficient data structures and algorithms for time-windowed streaming data, including maintaining rolling aggregates, supporting in-window updates, and computing order-statistics such as top-percentile scores.