FastPrepSearch in a Rotated Sorted Array
Problems/Search in a Rotated Sorted Array

Search in a Rotated Sorted Array

Nutanix logoNutanix● MediumINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A late-2018 report from a Nutanix intern phone interview names only the topic of its coding question: binary search on an array that was sorted and then rotated. It gives no further detail about that question.

The report gives no statement, signature, limits or examples. The exact task is ours: find a target value and return its index, or -1 when it is missing. The values being distinct, the limits (1 to 10^4 values from -10^4 to 10^4), the O(log n) goal and the examples are also ours.

Our version is about 65% the same as the reported question.

An array of distinct integers was sorted in increasing order and then rotated: some number of elements were moved, keeping their order, from the front of the array to the back. For example, [2, 5, 8, 11, 14] rotated by 2 becomes [8, 11, 14, 2, 5]. The rotation may be 0, so the array may still be fully sorted.

You are given the rotated array nums and an integer target. Return the index of target in nums, or -1 if target is not in nums.

Try to use O(log n) time, where n is the length of nums.

Function

searchRotated(nums: int[], target: int) → int

Examples

Example 1

nums = [15,18,22,3,7,9,12]target = 7return = 4

This is the sorted array [3, 7, 9, 12, 15, 18, 22] rotated so that 15 comes first. The value 7 sits at index 4, so the answer is 4.

Example 2

nums = [8,11,2,5]target = 10return = -1

In sorted order 10 would sit between 8 and 11, but it is not in the array, so the answer is -1.

Example 3

nums = [1,4,9,13]target = 13return = 3

This array was rotated by 0, so it is still fully sorted. 13 is the last value, at index 3.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • -10^4 <= target <= 10^4
  • All values in nums are distinct.
  • nums is an increasing array rotated by some amount from 0 to nums.length - 1.

More Nutanix Phone Screen questions

  • Swap Adjacent Linked List NodesPHONE SCREEN · Seen Mar 2025
  • Top K Most Frequent ValuesPHONE SCREEN · Seen Mar 2025
  • Unique Triplets Summing to ZeroPHONE SCREEN · Seen Sep 2024
  • Find the Duplicate in a Read-Only ArrayPHONE SCREEN · Seen Apr 2021
  • Kth Largest Element in an ArrayPHONE SCREEN · Seen Feb 2020
  • Kth Smallest Element in a BSTPHONE SCREEN · Seen Feb 2020
  • Outline of a Binary TreePHONE SCREEN · Seen Jan 2020
  • Print All File and Folder PathsPHONE SCREEN · Seen Dec 2019
  • Inorder Predecessor in a BSTPHONE SCREEN · Seen Jan 2019
  • K Largest and K Smallest ValuesPHONE SCREEN · Seen Jan 2019

Similar questions at other companies

  • Longest Increasing SubsequenceByteDance · PHONE SCREENByteDance interview questions
  • Koko Eating BananasThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
  • Find First and Last Position in a Sorted ArrayInstacart · PHONE SCREENInstacart interview questions
  • Random Pick with Weight Using Recorded DrawsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
  • Longest Increasing SubsequenceAngel One · PHONE SCREEN
  • Aggressive CowsAmazon · PHONE SCREEN
  • Find First and Last Position of Element in Sorted ArrayEPAM · PHONE SCREENEPAM interview questions
  • Find K Closest Elements in a Sorted ArrayNavi · PHONE SCREEN
  • Search in Rotated Sorted ArrayZoomInfo · PHONE SCREEN
  • Find a Peak ElementFox Corporation · PHONE SCREEN

Interview reports that mention this question

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)

Nutanix interview experiences

  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
  • Nutanix Intern Debugging Round and Interviews: 25 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
class Solution {
    public int searchRotated(int[] nums, int target) {
        // Write your code here.
    }
}
Checking account…