Katkat
Back

Process Calendar Events with Deletion, Pagination, and Overlap Queries

Lead BankSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manage a dynamic set of time-interval events using a data structure that allows for logarithmic insertions, deletions, and efficient range-based queries.

Problem Statement

You are tasked with building an in-memory calendar system that tracks events defined by a start time and an end time. Each event is stored as a half-open interval [start, end).

Implement the Calendar class with the following methods:

  1. add_event(event_id: str, start: int, end: int): Adds an event. If an event with the same ID already exists, update its interval.
  2. delete_event(event_id: str): Removes the event with the given ID. If the ID does not exist, do nothing.
  3. get_overlaps(start: int, end: int): Returns a list of all event_ids that overlap with the provided [start, end) range. An overlap occurs if max(start, event_start) < min(end, event_end).
  4. get_page(page_number: int, page_size: int): Returns a list of event IDs for the specified page. Events must be ordered primarily by start time (ascending), and secondarily by event_id (alphabetical) for stability.

Constraints

  • start and end are integers in the range [0, 10^9].
  • page_number is 0-indexed.
  • Total number of events N can reach 10^5.

Examples

# Example 1
cal = Calendar()
cal.add_event("A", 10, 20)
cal.add_event("B", 15, 25)
cal.get_overlaps(12, 18) # Returns ["A", "B"]
cal.delete_event("A")
cal.get_overlaps(12, 18) # Returns ["B"]

Edge Cases

  • Zero-length intervals or inverted intervals.
  • Large number of events resulting in many pages.
  • Overlaps exactly on the boundaries (note: the interval is half-open).

Hints

Hint 1

Use a dictionary to map `event_id` to its interval for O(1) deletions and lookups.

Hint 2

For overlap queries, a Segment Tree or an Interval Tree can efficiently handle range searching in O(log N + K) time.

Hint 3

For pagination, maintain a sorted structure (like a SortedList or a balanced BST) that stores tuples of `(start, event_id)` to allow for efficient slicing.

Follow-up questions

  • How would your architecture change if the calendar needed to support recurring events (e.g., repeating every Monday)?
  • If the calendar is heavily read-optimized with infrequent writes, how could you pre-calculate the pagination pages?
  • How would you handle thread safety if multiple users add and delete events simultaneously?