First Index of a Target in a Strictly Rising-Then-Falling Array
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Overview: Google new-grad onsite coding problem: given an array that strictly rises to one peak and then strictly falls, return the smallest index holding a target value, or -1 if it is absent. Tests searching a non-monotonic array while reading far fewer elements than it holds.
Constraints
- 3 <= len(arr) <= 10^5
- 0 <= arr[i] <= 10^9
- 0 <= target <= 10^9
- arr is a mountain: there is a peak index i with 0 < i < len(arr) - 1, values strictly increase from arr[0] to arr[i] and strictly decrease from arr[i] to the last element
- Every value and the returned index fit in a 32-bit signed integer
Examples
Input: ([1, 3, 2], 1)
Expected Output: 0
Explanation: Minimum length 3; target at index 0, the start of the rising side.
Input: ([1, 3, 2], 3)
Expected Output: 1
Explanation: Minimum length 3; target equals the peak value at index 1.
Hints
- Each side of the peak is strictly monotonic: one side is sorted ascending and the other descending. Comparing an element with its right neighbour tells you which side it is on.
- Any occurrence on the rising side has a smaller index than any occurrence on the falling side, so the rising side decides the answer whenever it contains the target.
- Check the boundaries: the target may equal the peak value, or sit at index 0 or at the last index.