Medium

Google-styleAmazon-style

Search in a Rotated Sorted Array DSA Interview

Given an array of distinct integers that was originally sorted ascending and then rotated at an unknown pivot, determine the index of a target value or report that it is absent.

Mock Interview with AI

1. Problem Statement

You are given an array of distinct integers that was sorted ascending and then rotated at some unknown pivot, and a target value. Return the index of the target, or -1 if it is not present.

2. Live Coding Format

Choose Python, JavaScript, Java, or C++, then solve while explaining your reasoning to the live interviewer.

Validation uses handwritten tests only. The MVP does not compile or run code, and it does not provide AI algorithm completion.

3. Key Focus Areas

1
Problem clarification and contract
2
Approach exploration and optimality
3
Think-aloud communication and pacing
4
Implementation correctness
5
Code quality and language fluency
6
Handwritten tests and dry run
7
Debugging and self-correction
8
Complexity analysis
9
Follow-up performance

4. What Strong Candidates Should Demonstrate

✓Clarify uniqueness of values, rotation guarantees, and no-match behavior before coding.
✓Explain a linear-scan baseline and improve to a modified binary search.
✓Think aloud while implementing careful boundary and midpoint logic.
✓Validate with explicit expected outputs and a top-to-bottom handwritten dry run.
✓Analyze time and space complexity and handle a bounded follow-up modification.

Evaluation Guide

This is an evaluation framework, not a single model answer. Strong designs may make different choices when their assumptions and trade-offs are explicit.

Problem clarification and contract

10%

Senior signals

✓Clarifies that values are distinct, confirms the array may not be rotated at all, and asks what to return when the array is empty.
✓Confirms whether only one occurrence of the target can exist, given distinct values.

Staff-level signals

◆Asks about expected input size to justify requiring logarithmic time.

Common red flags

×Codes immediately while assuming the array is always rotated without confirming.

Approach exploration and optimality

20%

Senior signals

✓Explains a linear scan baseline, identifies that it ignores the available sortedness structure, and improves to a modified binary search that determines which half is properly sorted at each step.
✓Explains how to decide, from the midpoint and boundary values, whether the target could lie in the sorted half.

Staff-level signals

◆Discusses how the approach must change if duplicate values were allowed, without being asked yet.

Common red flags

×Starts implementation without explaining an approach even after one interviewer prompt.
×Proposes finding the pivot first with a separate full binary search without recognizing it can be combined into one pass.

Think-aloud communication and pacing

10%

Senior signals

✓Explains the plan before coding and narrates which half is sorted at each step while implementing.
✓Paces the core solution to leave time for validation and the follow-up.

Common red flags

×Writes substantial code silently and cannot explain what the code is doing.

Implementation correctness

25%

Senior signals

✓Implements a correct modified binary search with proper boundary updates based on which half is sorted and whether the target falls within that half's range.
✓Handles a non-rotated array, a single-element array, the target at the pivot, and target absence.
✓Provides a convincing invariant argument for why the search space is halved correctly at each step.

Common red flags

×Uses an incorrect comparison that assumes the whole array is sorted, causing failures on rotated inputs.
×Final code contains a material correctness bug that the candidate does not identify.

Code quality and language fluency

15%

Senior signals

✓Produces readable, language-appropriate code with clear boundary variables and no off-by-one drift.

Common red flags

×Contains infinite-loop risks from incorrect boundary updates or syntax-level incoherence that prevents credible reasoning.

Handwritten validation, dry run, and debugging

10%

Senior signals

✓Provides explicit inputs and expected outputs before tracing the code from top to bottom.
✓Covers a non-rotated array, rotation at various points, target at the pivot, and target absence.
✓Finds and fixes an error independently, then re-validates the affected path.

Common red flags

×Claims the code works without a representative trace.

Complexity analysis and follow-up

10%

Senior signals

✓States logarithmic time and constant auxiliary space and compares them with the linear-scan baseline.

Staff-level signals

◆Discusses how the presence of duplicates could degrade worst-case time to linear.

Common red flags

×Cannot state the complexity of the implemented solution.
×Fails a reasonable follow-up despite having at least five minutes and receiving bounded clarification.

Trade-offs to articulate

A linear scan is simple and handles any input shape but costs linear time, ignoring the sortedness structure.
Finding the pivot first with one binary search and then searching with a second binary search is correct but does double the necessary work compared to a single combined pass.
A single modified binary search achieves logarithmic time by determining the sorted half at each step.

Practice follow-up questions

1.Coding follow-up: modify the solution to handle possible duplicate values in the rotated array, and explain the resulting change in worst-case complexity.
2.Verbal extension: how would the approach change if you needed to find the index of the rotation pivot itself, not a target value?

Want interactive feedback?

Practice this problem in the live coding workspace while the interviewer probes your clarification, algorithm, implementation, complexity, and handwritten tests.

Start Interview

Core Concepts

Binary SearchArraysComplexity Analysis