First and last position in a sorted list
Python data engineering interview problem. Difficulty: intermediate. Pattern: Binary Search. About 14 minutes. Part of the Pro drill bank.
Find the first and last index of a target in a sorted list with duplicates, in logarithmic time. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.
A sorted index lets a report find the full range of a repeated id quickly, even when the list is large. Return the lowest and highest index containing target. Use logarithmic binary searches and return [-1, -1] if target is absent. Write search_range(nums: list[int], target: int) -> list[int]. In [5, 7, 7, 8, 8, 10], the two 8s occupy indexes 3 and 4, so return [3, 4]. The starter file already contains the function name, harness and print lines. Keep them and fill only the function body.
Requirements
- Use the sorted order for binary search.
- Find both boundaries, not only one occurrence.
- Return [-1, -1] when no match exists.
Constraints
- nums is sorted ascending and may contain duplicates.
- The return type is a 2-item list and the expected work is O(log n).
Examples
Input: search_range([5, 7, 7, 8, 8, 10], 8) Output: [3, 4] 8 first appears at index 3 and last at index 4.
Topics: lakebench, python, sorted, boundaries, log n.
More Python interview questions · All interview problems · Learn data engineering
First and last position in a sorted list
Interview-style drill: Find the first and last index of a target in a sorted list with duplicates, in logarithmic time.
Implement `search_range(nums: list[int], target: int) -> list[int]`. `nums` is sorted in ascending order and may contain duplicates. Return `[first, last]`, the lowest and highest index where `target` occurs. Return `[-1, -1]` if it does not occur. The list can hold 100,000 elements, so the work should grow with the logarithm of its length, not with its length.