How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Decagon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Decagon during technical interviews.

Implement CSAT tracking and call timing

Company: Decagon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You were asked to solve two coding problems. ### Problem 1: Implement a rolling CSAT tracker Implement a class `CSATTracker` for customer-satisfaction scores. Each recorded score: - belongs to a unique `conversation_id` - is an integer from 1 to 5 - has an integer timestamp The tracker uses a rolling window of size `window_size`. A record is active at time `t` if `record_timestamp >= t - window_size`. Implement: 1. `__init__(window_size: int)` 2. `record(conversation_id: str, score: int, timestamp: int) -> None` - Insert the score. - After insertion, evict any records that are no longer in the active window relative to `timestamp`. 3. `get_average(current_time: int) -> Optional[float]` - Before computing the result, evict any records older than the active window relative to `current_time`. - Return the average active score rounded to 2 decimal places. - Return `None` if there are no active records. 4. `update(conversation_id: str, score: int) -> None` - Update the score for an existing active conversation. - If that conversation has already been evicted, do nothing. - Updating a score must not change its timestamp or its position in eviction order. Assumptions: - `conversation_id` values passed to `record` are unique. - Calls to `record` and `get_average` occur in non-decreasing timestamp order. - The goal is to support these operations efficiently without scanning all stored records on every call. ### Problem 2: Compute exclusive runtime from nested call logs A single-threaded CPU runs `n` functions identified by IDs `0` to `n - 1`. You are given a list of execution logs sorted by timestamp. Each log has the form `function_id:start:timestamp` or `function_id:end:timestamp`. Rules: - A function may call another function, which pauses the currently running one. - Functions may be nested multiple levels deep. - An `end` event at time `t` means the function finishes at the end of time unit `t`, so that unit counts toward the function's runtime. Return an array `answer` where `answer[i]` is the exclusive execution time of function `i`, excluding time spent in any child calls. You may assume the logs are valid and represent a properly nested execution trace.

Quick Answer: This question evaluates skills in designing efficient streaming/rolling-window data structures and stateful updates for real-time metrics, alongside parsing and simulating nested function call logs to compute exclusive runtimes.

Rolling CSAT Tracker

Implement a rolling customer-satisfaction (CSAT) tracker. Each recorded score belongs to a unique `conversation_id`, is an integer from 1 to 5, and carries an integer timestamp. The tracker keeps a rolling window of size `window_size`: a record is active at time `t` if `record_timestamp >= t - window_size`. Because designing a live class is hard to grade directly, you will implement a single driver function `solution(window_size, operations)` that replays a list of operations and returns the list of results produced by every `get_average` call (in order). Each element of `operations` is a list whose first element is the op name: - `["record", conversation_id, score, timestamp]` — insert the score, then evict any records no longer in the active window relative to `timestamp` (evict when `timestamp - record_ts > window_size`). - `["get_average", current_time]` — first evict records older than the active window relative to `current_time`, then append the average active score rounded to 2 decimals to the result list, or `None` if there are no active records. - `["update", conversation_id, score]` — set a new score for an existing active conversation. If it has already been evicted, do nothing. Updating must NOT change the record's timestamp or its eviction order. Assumptions: `conversation_id` values passed to `record` are unique; `record` and `get_average` calls arrive in non-decreasing timestamp order. Aim for amortized work proportional to the number of evicted records, not a full scan on every call. Return the list of `get_average` results.

Constraints

1 <= window_size
score is an integer in [1, 5]
conversation_id values passed to record are unique
record and get_average timestamps are non-decreasing
update on an evicted or unknown conversation is a no-op

Examples

Input: (3, [['record','conv0',1,1],['record','conv1',5,2],['get_average',3],['record','conv2',4,3],['get_average',4],['record','conv3',3,4],['get_average',4],['record','conv4',1,5],['get_average',5]])

Expected Output: [3.0, 3.33, 3.25, 3.25]

Explanation: At t=3 window is ts>=0 -> [1,5] avg 3.0. At t=4 window ts>=1 -> [1,5,4] avg 3.33, then [1,5,4,3] avg 3.25. record(ts=5) evicts conv0 (ts=1, 5-1>3); at t=5 window ts>=2 -> [5,4,3,1] avg 3.25.

Input: (3, [['record','conv0',1,1],['record','conv1',5,2],['record','conv2',4,3],['record','conv3',3,4],['update','conv2',2],['get_average',4],['record','conv4',1,5],['get_average',5],['update','conv0',5],['get_average',5]])

Expected Output: [2.75, 2.75, 2.75]

Explanation: After updating conv2 4->2 the window [1,5,2,3] averages 2.75. record(ts=5) evicts conv0; window [5,2,3,1] averages 2.75. update('conv0',5) is a no-op because conv0 was already evicted, so the average stays 2.75.

Input: (3, [['get_average',0]])

Expected Output: [None]

Explanation: No records have ever been inserted, so get_average returns None.

Input: (2, [['record','a',5,10],['get_average',10],['get_average',12],['get_average',13]])

Expected Output: [5.0, 5.0, None]

Explanation: Record a at ts=10 with window 2. At t=10 and t=12 it is active (12-10=2, not > 2) -> avg 5.0. At t=13, 13-10=3 > 2 so a is evicted, leaving the window empty -> None.

Input: (5, [['record','x',4,0],['update','x',2],['get_average',0],['update','y',5],['get_average',0]])

Expected Output: [2.0, 2.0]

Explanation: x is recorded with score 4 then updated to 2 -> avg 2.0. update('y',5) targets an id that was never recorded, so it is ignored and the average remains 2.0.

Hints

Keep a deque of (timestamp, conversation_id) in insertion (eviction) order plus a hash map conversation_id -> score and a running total. Evicting is then popping from the left while timestamp - oldest_ts > window_size.
update only mutates the score in the map and adjusts the running total by (new - old); it must never touch the deque, so timestamp and eviction order stay intact. If the id is absent from the map it was evicted (or never recorded) — do nothing.
Maintain total incrementally so get_average is O(1) plus the eviction it triggers; never re-sum the whole window.

Exclusive Time of Functions

A single-threaded CPU runs `n` functions identified by IDs `0` to `n - 1`. You are given a list of execution logs `logs`, sorted by timestamp. Each log is a string of the form `"function_id:start:timestamp"` or `"function_id:end:timestamp"`. Rules: - A function may call another function, which pauses the currently running one (calls can be nested arbitrarily deep, including recursively into the same id). - A `start` event at time `t` means the function begins at the START of time unit `t`. - An `end` event at time `t` means the function finishes at the END of time unit `t`, so that whole unit `t` counts toward the function's runtime. Return an array `answer` of length `n` where `answer[i]` is the exclusive execution time of function `i` — the total time it ran, excluding any time spent inside child calls. The logs are guaranteed valid and represent a properly nested execution trace.

Constraints

1 <= n
Each log is 'id:start:ts' or 'id:end:ts' with 0 <= id < n and ts an integer
logs are sorted by timestamp and form a valid, properly nested trace
An end at time t includes unit t in the runtime

Examples

Input: (2, ['0:start:0', '1:start:2', '1:end:5', '0:end:6'])

Expected Output: [3, 4]

Explanation: Func 0 runs units 0-1 (2 units) then 6 (1 unit) = 3. Func 1 runs units 2-5 = 4. The classic LeetCode example.

Input: (1, ['0:start:0', '0:start:2', '0:end:5', '0:start:6', '0:end:6', '0:end:7'])

Expected Output: [8]

Explanation: A function recursing into itself. All units 0..7 are charged to function 0: units 0-1 (2), 2-5 (4), 6 (1), 7 (1) = 8.

Input: (2, ['0:start:0', '0:start:2', '0:end:5', '1:start:6', '1:end:6', '0:end:7'])

Expected Output: [7, 1]

Explanation: Function 0 runs units 0-5 and 7 = 7 exclusive units; function 1 runs only unit 6 = 1.

Input: (1, ['0:start:0', '0:end:0'])

Expected Output: [1]

Explanation: Start and end at the same time unit 0: the end includes unit 0, so the runtime is 1.

Input: (3, ['0:start:0', '1:start:2', '2:start:4', '2:end:5', '1:end:6', '0:end:8'])

Expected Output: [4, 3, 2]

Explanation: 0 runs 0-1 (2) and 7-8 (2) = 4; 1 runs 2-3 (2) and 6 (1) = 3; 2 runs 4-5 = 2.

Hints

Use a stack of currently-running function ids and a variable `prev` for the start of the next chargeable interval. The function on top of the stack is the one actually consuming CPU time.
On a start at time t: the function currently on top has run for (t - prev) exclusive units, so add that, then push the new id and set prev = t.
On an end at time t: the popped function ran for (t - prev + 1) units (the +1 because the end unit counts), then set prev = t + 1 since the next unit is the earliest the resumed parent can run.

Implement CSAT tracking and call timing

Company: Decagon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Rolling CSAT Tracker

Constraints

1 <= window_size
score is an integer in [1, 5]
conversation_id values passed to record are unique
record and get_average timestamps are non-decreasing
update on an evicted or unknown conversation is a no-op

Examples

Expected Output: [3.0, 3.33, 3.25, 3.25]

Expected Output: [2.75, 2.75, 2.75]

Input: (3, [['get_average',0]])

Expected Output: [None]

Explanation: No records have ever been inserted, so get_average returns None.

Input: (2, [['record','a',5,10],['get_average',10],['get_average',12],['get_average',13]])

Expected Output: [5.0, 5.0, None]

Explanation: Record a at ts=10 with window 2. At t=10 and t=12 it is active (12-10=2, not > 2) -> avg 5.0. At t=13, 13-10=3 > 2 so a is evicted, leaving the window empty -> None.

Input: (5, [['record','x',4,0],['update','x',2],['get_average',0],['update','y',5],['get_average',0]])

Expected Output: [2.0, 2.0]

Explanation: x is recorded with score 4 then updated to 2 -> avg 2.0. update('y',5) targets an id that was never recorded, so it is ignored and the average remains 2.0.

Hints

Keep a deque of (timestamp, conversation_id) in insertion (eviction) order plus a hash map conversation_id -> score and a running total. Evicting is then popping from the left while timestamp - oldest_ts > window_size.
update only mutates the score in the map and adjusts the running total by (new - old); it must never touch the deque, so timestamp and eviction order stay intact. If the id is absent from the map it was evicted (or never recorded) — do nothing.
Maintain total incrementally so get_average is O(1) plus the eviction it triggers; never re-sum the whole window.

Exclusive Time of Functions

Constraints

1 <= n
Each log is 'id:start:ts' or 'id:end:ts' with 0 <= id < n and ts an integer
logs are sorted by timestamp and form a valid, properly nested trace
An end at time t includes unit t in the runtime

Examples

Input: (2, ['0:start:0', '1:start:2', '1:end:5', '0:end:6'])

Expected Output: [3, 4]

Explanation: Func 0 runs units 0-1 (2 units) then 6 (1 unit) = 3. Func 1 runs units 2-5 = 4. The classic LeetCode example.

Input: (1, ['0:start:0', '0:start:2', '0:end:5', '0:start:6', '0:end:6', '0:end:7'])

Expected Output: [8]

Explanation: A function recursing into itself. All units 0..7 are charged to function 0: units 0-1 (2), 2-5 (4), 6 (1), 7 (1) = 8.

Input: (2, ['0:start:0', '0:start:2', '0:end:5', '1:start:6', '1:end:6', '0:end:7'])

Expected Output: [7, 1]

Explanation: Function 0 runs units 0-5 and 7 = 7 exclusive units; function 1 runs only unit 6 = 1.

Input: (1, ['0:start:0', '0:end:0'])

Expected Output: [1]

Explanation: Start and end at the same time unit 0: the end includes unit 0, so the runtime is 1.

Input: (3, ['0:start:0', '1:start:2', '2:start:4', '2:end:5', '1:end:6', '0:end:8'])

Expected Output: [4, 3, 2]

Explanation: 0 runs 0-1 (2) and 7-8 (2) = 4; 1 runs 2-3 (2) and 6 (1) = 3; 2 runs 4-5 = 2.

Hints

Use a stack of currently-running function ids and a variable `prev` for the start of the next chargeable interval. The function on top of the stack is the one actually consuming CPU time.
On a start at time t: the function currently on top has run for (t - prev) exclusive units, so add that, then push the new id and set prev = t.
On an end at time t: the popped function ran for (t - prev + 1) units (the +1 because the end unit counts), then set prev = t + 1 since the next unit is the earliest the resumed parent can run.

Quick Overview

Quick Overview