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 Google.

What role is this question designed for?

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

Find Containing Range | Google Coding Question

Find Containing Range

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design a class that supports efficient point queries over a set of integer ranges. You are given a collection of inclusive, non-overlapping integer ranges, such as `[[1, 3], [50, 100]]`. Implement a class with: - A constructor that receives the list of ranges. - A method `query(x)` that returns the range containing integer `x`, or `null` / `None` if no range contains `x`. Example: ```text ranges = [[1, 3], [50, 100]] query(2) -> [1, 3] query(50) -> [50, 100] query(10) -> null ``` Assume ranges are inclusive. If the input ranges are not already sorted, your class should preprocess them so that each query can be answered efficiently.

Quick Answer: This question evaluates the ability to design appropriate data structures and apply algorithmic reasoning for efficient interval containment queries, emphasizing preprocessing, correctness, and time-space trade-offs.

You are given a collection of inclusive, non-overlapping integer ranges, but the ranges may not be sorted. A point query asks which range contains a given integer x. Design the preprocessing/query logic so queries are efficient after an initial setup step. For this problem, implement a function `solution(ranges, queries)` that simulates building the class once from `ranges` and then answering every value in `queries`. For each query value, return the inclusive range `[start, end]` that contains it, or `None` if no range contains that value. Example: - ranges = `[[1, 3], [50, 100]]` - queries = `[2, 50, 10]` - result = `[[1, 3], [50, 100], None]`

Constraints

0 <= len(ranges) <= 200000
0 <= len(queries) <= 200000
Each range is `[l, r]` where `l <= r`
Range endpoints and query values are integers in the range [-10^9, 10^9]
The input ranges are inclusive and pairwise non-overlapping

Examples

Input: ([[1, 3], [50, 100]], [2, 50, 10])

Expected Output: [[1, 3], [50, 100], None]

Explanation: 2 lies in [1, 3], 50 lies in [50, 100], and 10 is not inside any range.

Input: ([[5, 8], [-10, -5], [0, 0]], [-7, 0, 8, 9, -11])

Expected Output: [[-10, -5], [0, 0], [5, 8], None, None]

Explanation: The ranges must be sorted first. -7 is in [-10, -5], 0 is in the single-point range [0, 0], 8 is in [5, 8], while 9 and -11 are outside all ranges.

Input: ([], [1, -1, 0])

Expected Output: [None, None, None]

Explanation: With no ranges, every query returns None.

Input: ([[2, 2]], [2, 1, 3])

Expected Output: [[2, 2], None, None]

Explanation: The range [2, 2] contains only the value 2.

Input: ([[100, 200], [-3, -1], [10, 20]], [-1, 10, 200, 21, 10])

Expected Output: [[-3, -1], [10, 20], [100, 200], None, [10, 20]]

Explanation: Queries can repeat. Boundary values like -1, 10, and 200 are included because the ranges are inclusive.

Hints

If the ranges are not sorted, sort them by their starting value first.
For each query x, find the rightmost range whose start is less than or equal to x, then check whether x is at most that range's end.

Quick Overview

This question evaluates the ability to design appropriate data structures and apply algorithmic reasoning for efficient interval containment queries, emphasizing preprocessing, correctness, and time-space trade-offs.