How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Microsoft during technical interviews.

Implement rotated array binary search with duplicates

Quick Overview

This question evaluates algorithm design and analysis skills, focusing on binary-search variants, handling duplicates in rotated non-decreasing arrays, rotation-index reasoning, and rigorous edge-case analysis; domain: Coding & Algorithms, specifically search algorithms and array manipulation.

Company: Microsoft

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given an integer array nums that is a non-decreasing array rotated an unknown number of times. Duplicates may exist. Implement a function that returns a pair: (rotation_count, leftmost_index_of_target) where rotation_count is the index of the rotation point and leftmost_index_of_target is the smallest index i such that nums[i] == target or -1 if absent. Definitions and constraints: - Rotation point is the smallest index r such that nums[r] < nums[(r-1+n)%n]. If no such r exists (array already sorted or all equal), rotation_count = 0. - Time: O(log n) expected; discuss and handle worst-case O(n) when duplicates make direction ambiguous. - Space: O(1). - Edge cases: all elements equal; target duplicated across the rotation boundary; n=1; empty array. - Example: nums = [4,5,5,6,6,1,2,3,3], target=3 → rotation_count=5, leftmost_index_of_target=7. - Provide: (a) algorithm idea; (b) correctness argument; (c) complexity; (d) thorough unit tests covering edge cases.

Quick Answer: This question evaluates algorithm design and analysis skills, focusing on binary-search variants, handling duplicates in rotated non-decreasing arrays, rotation-index reasoning, and rigorous edge-case analysis; domain: Coding & Algorithms, specifically search algorithms and array manipulation.

Given an integer array `nums` that is a non-decreasing array rotated an unknown number of times (duplicates may exist), return a pair `(rotation_count, leftmost_index_of_target)`. - `rotation_count` is the rotation point: the smallest index `r` such that `nums[r] < nums[(r-1+n)%n]`. If no such `r` exists (the array is already sorted or all elements are equal), `rotation_count = 0`. This equals the index of the minimum element (the wrap point). - `leftmost_index_of_target` is the smallest index `i` such that `nums[i] == target`, or `-1` if `target` is absent. Return the answer as a two-element pair/array `[rotation_count, leftmost_index_of_target]`. Algorithm idea: The wrap point is the unique 'drop' where a later element is smaller than the element before it; a modified binary search on `nums` locates it in O(log n) expected time, falling back to a linear scan in the worst case when duplicates make the comparison `nums[mid] == nums[hi]` ambiguous (you must then shrink the window by one, giving O(n) worst case — e.g. `[2,2,2,0,2]`). The leftmost occurrence of `target` can be found with a leftmost-binary-search within the appropriate rotated half, again degrading to O(n) with heavy duplicates. Example: `nums = [4,5,5,6,6,1,2,3,3]`, `target = 3` → `rotation_count = 5`, `leftmost_index_of_target = 7`.

Constraints

0 <= n <= 10^5
Duplicates may exist in nums
nums is a non-decreasing array rotated an unknown number of times
If the array is already sorted or all elements are equal, rotation_count = 0
Return -1 for leftmost_index_of_target when target is absent
Target space complexity O(1)

Examples

Input: ([4,5,5,6,6,1,2,3,3], 3)

Expected Output: (5, 7)

Explanation: Drop occurs at index 5 (1 < 6), so rotation_count=5. Threes are at indices 7 and 8; leftmost is 7.

Input: ([1,2,3,4,5], 3)

Expected Output: (0, 2)

Explanation: Already sorted, no drop, so rotation_count=0. Target 3 is at index 2.

Input: ([2,2,2,2], 2)

Expected Output: (0, 0)

Explanation: All equal — no drop — rotation_count=0. Leftmost 2 is index 0.

Input: ([5,5,5,1,2,3,4,5], 5)

Expected Output: (3, 0)

Explanation: Drop at index 3 (1 < 5), rotation_count=3. Leftmost 5 is index 0 (across the boundary).

Input: ([], 1)

Expected Output: (0, -1)

Explanation: Empty array: rotation_count=0 by definition, target absent so -1.

Input: ([7], 7)

Expected Output: (0, 0)

Explanation: n=1: no rotation, target present at index 0.

Input: ([7], 3)

Expected Output: (0, -1)

Explanation: n=1: no rotation, target absent.

Input: ([3,4,5,1,2], 6)

Expected Output: (3, -1)

Explanation: Drop at index 3 (1 < 5), rotation_count=3. Target 6 absent, so -1.

Input: ([6,7,8,1,2,3,3], 3)

Expected Output: (3, 5)

Explanation: Drop at index 3 (1 < 8), rotation_count=3. Threes at indices 5 and 6; leftmost is 5.

Input: ([2,2,2,0,1,2], 2)

Expected Output: (3, 0)

Explanation: Duplicate-heavy wrap: drop at index 3 (0 < 2), rotation_count=3. Leftmost 2 is index 0.

Hints

The rotation point is the unique index where a value drops below its predecessor (cyclically). It is the index of the minimum element. If there is no drop, the array is sorted and rotation_count = 0.
With duplicates, a binary search can hit nums[mid] == nums[hi], making it impossible to tell which half holds the wrap point — shrink the window by one (hi -= 1) and continue. This is what forces O(n) worst case.
For the leftmost occurrence of target, do not stop at the first match found by binary search; keep searching to the left (continue toward lower indices) until you find the smallest matching index.

Quick Overview