← All mock interviewsHints used: 0

Search in Rotated Sorted Array Mock Interview

  1. ✓Problem→
  2. 2Clarifying Questions→
  3. 3Constraints→
  4. 4Brute Force→
  5. 5Complexity Analysis→
  6. 6Pattern Recognition→
  7. 7Optimized Solution→
  8. 8Implementation→
  9. 9Testing→
  10. 10Follow-Up→
  11. 11Evaluation
Problem

An ascending sorted array of distinct integers has been rotated at some unknown pivot, so [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2]. Given the rotated array nums and a target, return the index of target or -1 if it is not present. Your algorithm must run in O(log n) time.

Constraints
  • 1 ≤ n ≤ 5·10^3
  • -10^4 ≤ nums[i], target ≤ 10^4
  • all values are distinct
  • rotation offset is unknown and may be 0
Example
in: nums = [4,5,6,7,0,1,2], target = 0
out: 4

Clarify

Before choosing anything: what would you ask the interviewer? What assumptions are you making? (Duplicates? Empty input? Value ranges? What to return when there is no answer?)