Quick Overview

A coding question that gives each agent's active periods as inclusive start and end times with a chat count, and asks for the highest total load across all agents and the earliest time it occurs. It tests interval processing over large time ranges, inclusive boundaries and tie handling.

Peak Concurrent Chat Load From Agents' Inclusive Active Periods

Company: Cresta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a dictionary that maps each agent's id to the list of that agent's active periods. Each period is a triple `[start, end, chats]`: at every integer time `t` with `start <= t <= end` (both ends inclusive), that period contributes `chats` to the load. The load at time `t` is the sum of `chats` over all periods, from all agents, that contain `t`. Return the maximum load over all times, together with the earliest time at which that maximum occurs. ### Function Signature ```python def peak_chat_load(agent_periods: dict[str, list[list[int]]]) -> list[int]: ``` ### Rules - Time takes integer values only, and the load is defined at every integer time. - Both `start` and `end` belong to the period: a period `[3, 5, c]` adds `c` at times 3, 4 and 5. - Periods of the same agent may overlap; every period counts separately. - Return `[max_load, time]`, where `max_load` is the largest load at any time and `time` is the smallest integer time whose load equals `max_load`. - An agent may have an empty list of periods. ### Constraints - `1 <= number of agents <= 10^4` - `1 <= total number of periods across all agents <= 10^5` - `0 <= start <= end <= 10^9` - `1 <= chats <= 10^4` - Agent ids are non-empty strings. - The maximum load is at most `10^9`, which fits in a signed 32-bit integer. ### Examples **Example 1** ```text Input: agent_periods = {"a1": [[1, 5, 2], [8, 10, 1]], "a2": [[3, 9, 3]]} Output: [5, 3] ``` The load is 2 at times 1 and 2, 5 at times 3 to 5, 3 at times 6 and 7, 4 at times 8 and 9, and 1 at time 10. The maximum 5 first occurs at time 3. **Example 2** ```text Input: agent_periods = {"a1": [[1, 3, 2]], "a2": [[3, 4, 5]]} Output: [7, 3] ``` Both periods include time 3, because each end is inclusive, so the load there is `2 + 5 = 7`. **Example 3** ```text Input: agent_periods = {"a1": [[4, 6, 3], [10, 12, 4]], "a2": [[1, 2, 4]], "a3": []} Output: [4, 1] ``` The load reaches 4 at times 1 and 2 and again at times 10 to 12; the earliest of these is 1.

Overview: A coding question that gives each agent's active periods as inclusive start and end times with a chat count, and asks for the highest total load across all agents and the earliest time it occurs. It tests interval processing over large time ranges, inclusive boundaries and tie handling.

Read the full Cresta Software Engineer interview experience this question came from

You are given a dictionary `agent_periods` that maps each agent's id to the list of that agent's active periods. Each period is a triple `[start, end, chats]`: at every integer time `t` with `start <= t <= end` (both ends inclusive), that period contributes `chats` to the load. The load at time `t` is the sum of `chats` over all periods, from all agents, that contain `t`. Return the list `[max_load, time]`, where `max_load` is the largest load at any integer time and `time` is the smallest integer time whose load equals `max_load`. ### Rules - Time takes integer values only, and the load is defined at every integer time. - Both `start` and `end` belong to the period: a period `[3, 5, c]` adds `c` at times 3, 4 and 5. - Periods of the same agent may overlap; every period counts separately. - An agent may have an empty list of periods. ### Example 1 ```text Input: agent_periods = {"a1": [[1, 5, 2], [8, 10, 1]], "a2": [[3, 9, 3]]} Output: [5, 3] ``` The load is 2 at times 1 and 2, 5 at times 3 to 5, 3 at times 6 and 7, 4 at times 8 and 9, and 1 at time 10. The maximum 5 first occurs at time 3. ### Example 2 ```text Input: agent_periods = {"a1": [[1, 3, 2]], "a2": [[3, 4, 5]]} Output: [7, 3] ``` Both periods include time 3, because each end is inclusive, so the load there is 2 + 5 = 7. ### Constraints - `1 <= number of agents <= 10^4` - `1 <= total number of periods across all agents <= 10^5` - `0 <= start <= end <= 10^9` - `1 <= chats <= 10^4` - Agent ids are non-empty strings (in this console: printable ASCII, at most 20 characters). - The maximum load is at most `10^9`, which fits in a signed 32-bit integer. Neither returned value can exceed 2^31 - 1: both `max_load` and `time` are at most 10^9, so 32-bit integers hold the result.

Constraints

  • 1 <= number of agents <= 10^4
  • 1 <= total number of periods across all agents <= 10^5
  • 0 <= start <= end <= 10^9
  • 1 <= chats <= 10^4
  • Agent ids are non-empty strings (in this console: printable ASCII, at most 20 characters)
  • An agent's list of periods may be empty
  • The maximum load is at most 10^9, which fits in a signed 32-bit integer

Examples

Input: ({'a1': [[1, 5, 2], [8, 10, 1]], 'a2': [[3, 9, 3]]},)

Expected Output: [5, 3]

Explanation: Source example 1: the load is 5 at times 3 to 5, first reached at time 3.

Input: ({'a1': [[1, 3, 2]], 'a2': [[3, 4, 5]]},)

Expected Output: [7, 3]

Explanation: Source example 2: inclusive ends make the periods overlap at time 3, load 2 + 5 = 7.

Hints

  1. Times go up to 10^9, so checking every integer time one by one is too slow; think about at which times the load can actually change.
  2. Both ends are inclusive: a period [start, end, chats] still counts at time end and stops counting only at time end + 1.
  3. Several separate stretches of time can share the maximum load; the answer is the smallest such time, regardless of the order in which agents or periods are listed.

Peak Concurrent Chat Load Across Agents

mediumCrestaSoftware Engineer

You are given a dictionary agent_periods that maps each agent's id to the list of that agent's active periods. Each period is a triple [start, end, chats]: at every integer time t with start <= t <= end (both ends inclusive), that period contributes chats to the load. The load at time t is the sum of chats over all periods, from all agents, that contain t.

Return the list [max_load, time], where max_load is the largest load at any integer time and time is the smallest integer time whose load equals max_load.

Rules

  • Time takes integer values only, and the load is defined at every integer time.
  • Both start and end belong to the period: a period [3, 5, c] adds c at times 3, 4 and 5.
  • Periods of the same agent may overlap; every period counts separately.
  • An agent may have an empty list of periods.

Example 1

Input:  agent_periods = {"a1": [[1, 5, 2], [8, 10, 1]], "a2": [[3, 9, 3]]}
Output: [5, 3]

The load is 2 at times 1 and 2, 5 at times 3 to 5, 3 at times 6 and 7, 4 at times 8 and 9, and 1 at time 10. The maximum 5 first occurs at time 3.

Example 2

Input:  agent_periods = {"a1": [[1, 3, 2]], "a2": [[3, 4, 5]]}
Output: [7, 3]

Both periods include time 3, because each end is inclusive, so the load there is 2 + 5 = 7.

Constraints

  • 1 <= number of agents <= 10^4
  • 1 <= total number of periods across all agents <= 10^5
  • 0 <= start <= end <= 10^9
  • 1 <= chats <= 10^4
  • Agent ids are non-empty strings (in this console: printable ASCII, at most 20 characters).
  • The maximum load is at most 10^9, which fits in a signed 32-bit integer.

Neither returned value can exceed 2^31 - 1: both max_load and time are at most 10^9, so 32-bit integers hold the result.

Examples

Example 1
Input
({'a1': [[1, 5, 2], [8, 10, 1]], 'a2': [[3, 9, 3]]},)
Output
[5, 3]
Notes
Source example 1: the load is 5 at times 3 to 5, first reached at time 3.
Example 2
Input
({'a1': [[1, 3, 2]], 'a2': [[3, 4, 5]]},)
Output
[7, 3]
Notes
Source example 2: inclusive ends make the periods overlap at time 3, load 2 + 5 = 7.

Constraints

  • •1 <= number of agents <= 10^4
  • •1 <= total number of periods across all agents <= 10^5
  • •0 <= start <= end <= 10^9
  • •1 <= chats <= 10^4
  • •Agent ids are non-empty strings (in this console: printable ASCII, at most 20 characters)
  • •An agent's list of periods may be empty
  • •The maximum load is at most 10^9, which fits in a signed 32-bit integer

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def peak_chat_load(agent_periods: dict[str, list[list[int]]]) -> list[int]:
Sample call
peak_chat_load({'a1': [[1, 5, 2], [8, 10, 1]], 'a2': [[3, 9, 3]]})
Language
Case 1
Input
({'a1': [[1, 5, 2], [8, 10, 1]], 'a2': [[3, 9, 3]]},)
Expected
[5, 3]
Case 2
Input
({'a1': [[1, 3, 2]], 'a2': [[3, 4, 5]]},)
Expected
[7, 3]

Browse More Questions

Show the approach

Approach

Sweep over the times where the load changes. A period [start, end, chats] raises the load by chats at time start and lowers it by chats at time end + 1, the first time after its inclusive end. Between two consecutive change times the load is constant, and it is 0 before the first change and after the last one. Collect these change events from every agent, sort them by time, and apply all events that share a time together before looking at the running sum. Invariant: after the events at time t are applied, the running sum equals the load at t and stays equal to it until the next change time. Track the largest running sum, replacing it only when a strictly larger value appears. Times are visited in increasing order and the load is constant on each segment, so the first change time that reaches the maximum is the smallest integer time with the maximum load. Applying all events of one time before comparing matters: a period ending at t - 1 and another starting at t do not overlap, so the drop at t must count before the load at t is compared. Edge cases: agents with empty lists add no events; identical periods each add their own events; a single-point period [t, t, c] adds at t and drops at t + 1; the maximum can sit at time 0 or at time 10^9 (end + 1 is at most 10^9 + 1, and the running sums use 64-bit arithmetic in Java and C++). Because there is at least one period and chats >= 1, the maximum load is at least 1, so the answer is always a time inside some period.

Time complexity:
O(P log P), where P is the total number of periods
Space complexity:
O(P)