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

Q: Implement and extend My Calendar III

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.

Input: [[0, 1000000000]]

Expected Output: [1]

Explanation: Single booking over the full allowed range.

Input: []

Expected Output: []

Explanation: Edge case: no bookings.

Solution

def solution(bookings):
    if not bookings:
        return []

    coords = sorted({x for start, end in bookings for x in (start, end)})
    index = {x: i for i, x in enumerate(coords)}
    seg_count = len(coords) - 1

    tree = [0] * (4 * seg_count)
    lazy = [0] * (4 * seg_count)

    def update(node, left, right, ql, qr, delta):
        if ql <= left and right <= qr:
            tree[node] += delta
            lazy[node] += delta
            return

        mid = (left + right) // 2
        if ql <= mid:
            update(node * 2, left, mid, ql, qr, delta)
        if qr > mid:
            update(node * 2 + 1, mid + 1, right, ql, qr, delta)

        tree[node] = lazy[node] + max(tree[node * 2], tree[node * 2 + 1])

    answer = []
    for start, end in bookings:
        l = index[start]
        r = index[end] - 1
        update(1, 0, seg_count - 1, l, r, 1)
        answer.append(tree[1])

    return answer

Time complexity: O(n log n), where n is the number of bookings. Coordinate compression costs O(n log n), and each update is O(log n).. Space complexity: O(n) for compressed coordinates and the segment tree..

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.

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

Expected Output: 2

Explanation: At time 20, `[15, 20)` has already ended, so the answer is 2, not 3.

Input: [[1, 10], [2, 9], [3, 8], [4, 7]]

Expected Output: 4

Explanation: All four intervals overlap on `[4, 7)`.

Input: []

Expected Output: 0

Explanation: Edge case: no intervals.

Solution

def solution(intervals):
    diff = {}

    for start, end in intervals:
        diff[start] = diff.get(start, 0) + 1
        diff[end] = diff.get(end, 0) - 1

    active = 0
    best = 0
    for x in sorted(diff):
        active += diff[x]
        if active > best:
            best = active

    return best

Time complexity: O(n log n) due to sorting event coordinates.. Space complexity: O(n) for the difference map..

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.

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

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

Explanation: At time 20, only `[20, 30)` is active before it is canceled.

Input: []

Expected Output: []

Explanation: Edge case: no operations.

Solution

def solution(operations):
    from bisect import bisect_right

    if not operations:
        return []

    coords = []
    for op in operations:
        kind = op[0]
        if kind == 'book' or kind == 'cancel':
            start = int(op[1])
            end = int(op[2])
            coords.append(start)
            coords.append(end)

    coords = sorted(set(coords))
    seg_count = max(0, len(coords) - 1)
    index = {x: i for i, x in enumerate(coords)}

    tree = [0] * max(1, 4 * seg_count)
    lazy = [0] * max(1, 4 * seg_count)

    def update(node, left, right, ql, qr, delta):
        if ql <= left and right <= qr:
            lazy[node] += delta
            tree[node] += delta
            return

        mid = (left + right) // 2
        if ql <= mid:
            update(node * 2, left, mid, ql, qr, delta)
        if qr > mid:
            update(node * 2 + 1, mid + 1, right, ql, qr, delta)

        tree[node] = lazy[node] + max(tree[node * 2], tree[node * 2 + 1])

    def point_query(node, left, right, idx, carry):
        carry += lazy[node]
        if left == right:
            return carry

        mid = (left + right) // 2
        if idx <= mid:
            return point_query(node * 2, left, mid, idx, carry)
        return point_query(node * 2 + 1, mid + 1, right, idx, carry)

    answer = []

    for op in operations:
        kind = op[0]

        if kind == 'book':
            start = int(op[1])
            end = int(op[2])
            if seg_count:
                update(1, 0, seg_count - 1, index[start], index[end] - 1, 1)
                answer.append(tree[1])
            else:
                answer.append(0)

        elif kind == 'cancel':
            start = int(op[1])
            end = int(op[2])
            if seg_count:
                update(1, 0, seg_count - 1, index[start], index[end] - 1, -1)
                answer.append(tree[1])
            else:
                answer.append(0)

        else:
            t = int(op[1])
            if not seg_count or t < coords[0] or t >= coords[-1]:
                answer.append(0)
            else:
                pos = bisect_right(coords, t) - 1
                if 0 <= pos < seg_count:
                    answer.append(point_query(1, 0, seg_count - 1, pos, 0))
                else:
                    answer.append(0)

    return answer

Time complexity: O(m log m + q log m), where `m` is the number of distinct endpoints from book/cancel operations and `q` is the number of operations.. Space complexity: O(m) for compression and the segment tree..

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.

Input: [[1, 2], [2, 3], [3, 4]]

Expected Output: [1, 1, 1]

Explanation: Touching intervals do not overlap under half-open semantics.

Input: [[1, 10], [2, 9], [3, 8], [4, 7]]

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

Explanation: Nested intervals steadily raise the peak overlap.

Input: []

Expected Output: []

Explanation: Edge case: no bookings.

Solution

def solution(bookings):
    if not bookings:
        return []

    coords = sorted({x for start, end in bookings for x in (start, end)})
    index = {x: i for i, x in enumerate(coords)}
    seg_count = len(coords) - 1

    size = 1
    while size < seg_count:
        size <<= 1

    tree = [0] * (2 * size)
    lazy = [0] * (2 * size)

    def apply(node, delta):
        tree[node] += delta
        lazy[node] += delta

    def rebuild(node):
        while node > 1:
            node //= 2
            tree[node] = max(tree[node * 2], tree[node * 2 + 1]) + lazy[node]

    def range_add(left, right, delta):
        left += size
        right += size
        left0, right0 = left, right

        while left <= right:
            if left & 1:
                apply(left, delta)
                left += 1
            if not (right & 1):
                apply(right, delta)
                right -= 1
            left //= 2
            right //= 2

        rebuild(left0)
        rebuild(right0)

    answer = []
    for start, end in bookings:
        l = index[start]
        r = index[end] - 1
        range_add(l, r, 1)
        answer.append(tree[1])

    return answer

Time complexity: O(n log n) overall: O(n log n) for coordinate compression and O(log n) per booking.. Space complexity: O(n) for compressed coordinates and the iterative tree arrays..

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.

Quick Overview

Quick Overview