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 Technical Screen rounds at Pinterest.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Pinterest during technical interviews.

Implement and extend My Calendar III | Pinterest Coding Question

Quick Overview

This question evaluates competency in designing and implementing efficient dynamic interval data structures, handling correctness for duplicate and nested intervals, extending APIs with cancellation and point queries, and performing rigorous worst-case time/space analysis and resource-adaptation.

Implement and extend My Calendar III

Company: Pinterest

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement a booking system like LeetCode 732 (My Calendar III). Provide a class with methods: book(start, end) using half-open intervals [start, end) where 0 ≤ start < end ≤ 1e9. After each call, return the maximum number of concurrent bookings seen so far. Constraints: up to 100,000 operations; target O(log n) amortized per update and O(n) space. (1) Implement using either (a) a sweep-line difference map over a balanced BST (ordered map) or (b) a segment tree with lazy propagation and coordinate compression—explain your choice and prove correctness. (2) Precisely handle duplicate and nested intervals; state your inclusive/exclusive boundary convention and provide unit tests that expose off-by-one bugs (e.g., book(10,20), book(20,30), book(15,25)). (3) Follow-up: add cancel(start, end) that removes a previously booked interval and keeps the returned max-k correct for all future calls; also add query(t) that returns the number of active bookings at time t in O(log n). (4) Analyze worst-case time/space, show how your data structure avoids O(n) per operation in adversarial sequences (e.g., many overlapping single-point intervals), and discuss how you would adapt it if recursion limits or memory fragmentation become an issue.

Quick Answer: This question evaluates competency in designing and implementing efficient dynamic interval data structures, handling correctness for duplicate and nested intervals, extending APIs with cancellation and point queries, and performing rigorous worst-case time/space analysis and resource-adaptation.

Part 1: My Calendar III - Maximum Concurrent Bookings After Each Insert

You are given all booking requests up front as a list of half-open intervals `[start, end)`. Process them in order. After each booking, return the maximum number of concurrent bookings seen so far. Because times are as large as `1e9`, a dense timeline is impossible. Implement an efficient solution using coordinate compression plus a lazy segment tree. In an interview setting, you should also be able to justify why updating the compressed elementary segments preserves the true overlap counts.

Constraints

`0 <= len(bookings) <= 100000`
`0 <= start < end <= 10^9`
Use half-open intervals: `[start, end)`

Examples

Input: [[10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

Expected Output: [1, 1, 2, 3, 3, 3]

Explanation: Standard My Calendar III example. The peak overlap becomes 3 after booking `[5, 15)`.

Input: [[10, 20], [20, 30], [15, 25]]

Expected Output: [1, 1, 2]

Explanation: Because intervals are half-open, `[10, 20)` and `[20, 30)` do not overlap at time 20.

Hints

Compress all distinct start and end coordinates first. Each leaf can represent one elementary segment between consecutive coordinates.
A booking `[s, e)` adds `+1` to every compressed segment from `index[s]` through `index[e] - 1`.

Part 2: Calendar Overlap with Half-Open Boundaries, Duplicates, and Nested Intervals

Given a list of booking intervals, compute the maximum number of active bookings at any time. Intervals use half-open semantics `[start, end)`, so an interval ending at time `t` is not active at `t`, while one starting at `t` is active at `t`. Your solution must correctly handle duplicate intervals and nested intervals. The goal is to avoid off-by-one mistakes.

Constraints

`0 <= len(intervals) <= 100000`
`0 <= start < end <= 10^9`
Intervals are half-open: `[start, end)`

Examples

Input: [[10, 20], [20, 30], [15, 25]]

Expected Output: 2

Explanation: Touching intervals do not overlap at 20, but `[15, 25)` overlaps with each of the other two on different subranges.

Input: [[10, 20], [10, 20], [10, 20]]

Expected Output: 3

Explanation: Duplicate intervals all count separately.

Hints

A difference map works well: add `+1` at each start and `-1` at each end, then sweep from left to right.
With half-open intervals, events at the same coordinate can cancel out naturally in the difference map.

Part 3: Extended Calendar with book, cancel, and query

Design a calendar that supports three operations on half-open intervals `[start, end)`: `book(start, end)`, `cancel(start, end)`, and `query(t)`. A `book` adds one copy of the interval. A `cancel` removes one previously booked copy of the same interval; every cancel operation is guaranteed to be valid. After each `book` or `cancel`, output the current maximum overlap among all active bookings. For `query(t)`, output the number of active bookings at time `t`. Process all operations in order.

Constraints

`0 <= len(operations) <= 100000`
`0 <= start < end <= 10^9`
`0 <= t <= 10^9`
Every `cancel(start, end)` refers to an interval that is currently booked at least once
Intervals are half-open: `[start, end)`

Examples

Input: [['book', '10', '20'], ['book', '15', '25'], ['query', '10'], ['query', '20'], ['cancel', '10', '20'], ['query', '15'], ['book', '20', '30']]

Expected Output: [1, 2, 1, 1, 1, 1, 2]

Explanation: Shows both half-open behavior and that cancel correctly updates future max values and point queries.

Input: [['book', '5', '10'], ['book', '5', '10'], ['query', '7'], ['cancel', '5', '10'], ['query', '7'], ['cancel', '5', '10'], ['query', '7']]

Expected Output: [1, 2, 2, 1, 1, 0, 0]

Explanation: Duplicate bookings are tracked independently, and cancel removes one copy at a time.

Hints

Use the same compressed elementary segments as in My Calendar III, but allow both `+1` and `-1` range updates.
For `query(t)`, find which compressed segment contains `t`, then read the point value on that segment.

Part 4: Non-Recursive My Calendar III for Adversarial Inputs

You must process a large sequence of half-open bookings `[start, end)` and return the maximum overlap after each insertion. This version is designed for adversarial inputs, such as many highly overlapping intervals, and for environments where deep recursion or recursive tree allocation is undesirable. Implement the calendar using coordinate compression and an iterative lazy segment tree. In an interview, explain why this avoids O(n) work per operation and how it helps with recursion-limit concerns.

Constraints

`0 <= len(bookings) <= 100000`
`0 <= start < end <= 10^9`
Intervals are half-open: `[start, end)`
Use a non-recursive approach for the segment tree updates

Examples

Input: [[10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

Expected Output: [1, 1, 2, 3, 3, 3]

Explanation: Same benchmark sequence as the classic problem.

Input: [[0, 1000000000], [0, 1000000000], [0, 1000000000], [0, 1000000000]]

Expected Output: [1, 2, 3, 4]

Explanation: Adversarial-style heavy overlap: every interval covers the full range.

Hints

Coordinate compression still turns huge times into a compact index range over elementary segments.
In an iterative lazy segment tree, after applying updates to cover nodes, rebuild only the ancestors of the touched boundary leaves.