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 Take-home Project rounds at Google.

What role is this question designed for?

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

Consolidate On-Call Rotation Segments | Google Coding Question

Consolidate On-Call Rotation Segments

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given an array of on-call rotation intervals. Each interval has the form: ```text {name: string, start: int, end: int} ``` Each interval is half-open: `[start, end)`, meaning the person is on call starting at `start` and stops being on call at `end`. Produce a consolidated on-call schedule. Each output segment should be a maximal contiguous time range during which the exact set of people on call does not change. Output segments must be sorted by `start`. Time gaps where nobody is on call should be omitted. Each output segment should have the form: ```text {start: int, end: int, names: set<string>} ``` If `names` must be rendered as a list, use any deterministic order, such as lexicographic order. Example: Input: | name | start | end | |---|---:|---:| | A | 10 | 50 | | B | 20 | 60 | | C | 30 | 40 | | D | 30 | 40 | Output: | start | end | names | |---:|---:|---| | 10 | 20 | {A} | | 20 | 30 | {A, B} | | 30 | 40 | {A, B, C, D} | | 40 | 50 | {A, B} | | 50 | 60 | {B} | Implement a function that returns this consolidated schedule for any valid list of intervals.

Quick Answer: This question evaluates proficiency with interval manipulation, set management, sorting and event ordering, and the use of appropriate data structures in the Coding & Algorithms domain.

You are given a list of on-call rotation intervals. Each interval is a dictionary with keys `name`, `start`, and `end`, representing a half-open interval `[start, end)`. Produce a consolidated on-call schedule where each output segment is a maximal non-empty time range during which the exact set of people on call does not change. Output segments must be sorted by `start`, and any time range where nobody is on call must be omitted. If the same person appears in multiple overlapping or duplicate intervals, they should appear only once in the output `names` for any time they are active. If two adjacent ranges have the same active set, they must be merged into one maximal segment. Return each output segment as a dictionary with keys `start`, `end`, and `names`, where `names` is a lexicographically sorted list of unique names.

Constraints

0 <= len(intervals) <= 100000
-10^9 <= start < end <= 10^9
`name` is a non-empty string
Intervals may overlap, touch at boundaries, or contain duplicate rows

Examples

Input: [{'name': 'A', 'start': 10, 'end': 50}, {'name': 'B', 'start': 20, 'end': 60}, {'name': 'C', 'start': 30, 'end': 40}, {'name': 'D', 'start': 30, 'end': 40}]

Expected Output: [{'start': 10, 'end': 20, 'names': ['A']}, {'start': 20, 'end': 30, 'names': ['A', 'B']}, {'start': 30, 'end': 40, 'names': ['A', 'B', 'C', 'D']}, {'start': 40, 'end': 50, 'names': ['A', 'B']}, {'start': 50, 'end': 60, 'names': ['B']}]

Explanation: This is the sample scenario. The active set changes only at times 10, 20, 30, 40, 50, and 60.

Input: []

Expected Output: []

Explanation: With no intervals, there is no on-call coverage to report.

Input: [{'name': 'A', 'start': 1, 'end': 3}, {'name': 'A', 'start': 3, 'end': 5}]

Expected Output: [{'start': 1, 'end': 5, 'names': ['A']}]

Explanation: Because intervals are half-open, A is active continuously from 1 to 5. The two adjacent ranges must be merged into one maximal segment.

Input: [{'name': 'A', 'start': 1, 'end': 4}, {'name': 'A', 'start': 1, 'end': 4}, {'name': 'B', 'start': 2, 'end': 3}]

Expected Output: [{'start': 1, 'end': 2, 'names': ['A']}, {'start': 2, 'end': 3, 'names': ['A', 'B']}, {'start': 3, 'end': 4, 'names': ['A']}]

Explanation: The duplicate A interval should not cause A to appear twice. B is only active from 2 to 3.

Input: [{'name': 'X', 'start': -5, 'end': -1}, {'name': 'Y', 'start': -3, 'end': 2}, {'name': 'Z', 'start': 4, 'end': 6}]

Expected Output: [{'start': -5, 'end': -3, 'names': ['X']}, {'start': -3, 'end': -1, 'names': ['X', 'Y']}, {'start': -1, 'end': 2, 'names': ['Y']}, {'start': 4, 'end': 6, 'names': ['Z']}]

Explanation: This checks negative times, overlap, and that the uncovered gap from 2 to 4 is omitted.

Hints

Think of each interval as creating two events: one that adds a name at `start`, and one that removes a name at `end`.
The active on-call set can only change at event times. Sweep through times in sorted order, and track counts per name so overlapping intervals for the same person are handled correctly.

Quick Overview

This question evaluates proficiency with interval manipulation, set management, sorting and event ordering, and the use of appropriate data structures in the Coding & Algorithms domain.