Python data engineering interview problem. Difficulty: intermediate. Pattern: Binary Search. About 16 minutes. Part of the Pro drill bank.
Find a value in an ascending list that was rotated at an unknown pivot. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.
Implement search_rotated(nums: list[int], target: int) -> int. nums held distinct values in ascending order, then was rotated at some pivot: [0, 1, 2, 4, 5, 6, 7] may have become [4, 5, 6, 7, 0, 1, 2]. Return the index of target, or -1 if it is not there. The list can hold 100,000 elements, so the work should grow with the logarithm of its length.
Input: search_rotated([4, 5, 6, 7, 0, 1, 2], 0) Output: 4 0 sits at index 4, after the rotation point.
Topics: lakebench, python, rotated, sorted, log n.
More Python interview questions · All interview problems · Learn data engineering
Interview-style drill: Find a value in an ascending list that was rotated at an unknown pivot.
Implement `search_rotated(nums: list[int], target: int) -> int`. `nums` held distinct values in ascending order, then was rotated at some pivot: `[0, 1, 2, 4, 5, 6, 7]` may have become `[4, 5, 6, 7, 0, 1, 2]`. Return the index of `target`, or `-1` if it is not there. The list can hold 100,000 elements, so the work should grow with the logarithm of its length.