Katkat
Back

Find Containing Range

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize interval lookup operations by preprocessing data into an efficient search structure to handle containment queries in sub-linear time.

Problem Statement

You are given a collection of intervals represented as pairs of integers [start, end]. An interval A is said to contain interval B if A.start = B.end.

Design a data structure that supports the following operations:

  1. add_interval(start, end): Adds a new interval to the collection.
  2. find_containing(start, end): Returns an interval from the existing collection that contains the query interval [start, end]. If multiple intervals contain the query, you may return any one of them. If none exist, return null.

Constraints

  • The number of operations can be up to 10^5.
  • Coordinates are within the range [-10^9, 10^9].
  • start <= end for all intervals.

Example

# Initialization
intervals = IntervalContainer()
intervals.add_interval(1, 10)
intervals.add_interval(2, 5)

# Queries
intervals.find_containing(3, 4) # Returns [1, 10] or [2, 5]
intervals.find_containing(0, 11) # Returns null
intervals.find_containing(2, 5)  # Returns [2, 5] or [1, 10]

Edge Cases

  • The query interval is identical to an existing interval.
  • Intervals with the same start or end points.
  • Queries that are completely outside all stored intervals.

Hints

Hint 1

Consider how sorting the intervals by start time might help narrow down the search space.

Hint 2

If you sort by start time, you only need to check intervals where `start <= query.start`, but you also need to satisfy the `end` condition.

Hint 3

A balanced binary search tree or a segment tree could store the end coordinates, allowing you to query for a minimum or maximum value efficiently.

Follow-up questions

  • How would your solution change if you needed to return ALL intervals that contain the query interval instead of just one?
  • What is the time complexity of your `add_interval` and `find_containing` operations?
  • How would you handle the case where the intervals are provided as a static batch rather than an incremental stream?