Search a rotated schedule

binary search

Search a rotated schedule

Uber Python Interview Question

Uber's shuttle schedule is a list of departure minutes in increasing order, but it starts partway through the day and wraps around, like [600, 720, 900, 60, 180]. The list has no repeats.

Write a function search_rotated(times, target) that returns the position of the target time, or -1 if it is not in the list. Aim to do better than checking every time.

Asked of

  • Data Analyst
  • Data Engineer
  • Data Scientist
  • ML Engineer
  • AI Engineer

Example 1

Input

times = [600, 720, 900, 60, 180], target = 60

Output

3

Example 2

Input

times = [600, 720, 900, 60, 180], target = 300

Output

-1

Explanation

In the first example, the list is sorted from 600 up to 900, then wraps around to 60 and 180. The time 60 is at position 3. In the second example, 300 does not appear, so the answer is -1.

Submit also runs 6 hidden test cases that check edge cases.