The Overwritten Hour

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
mid
Asked in
Qube Research & Technologies

Problem

A fixed-size ring buffer stores tick timestamps in ascending order, but once the writer looped back to the start it overwrote the head, so the values now read as one ascending run that wraps around a single pivot. Given readings in that wrapped order and a target, return the index where target sits, or -1 if it is not present. The values are distinct, and the buffer is large enough that a probe should lean on its ordering rather than touch every slot.

The log wrapped on itself. The order is still there, just not where you would look.

Example 1

Input:

target = 12, readings = [40,55,70,5,12,28]

Output:

4

Example 2

Input:

target = 99, readings = [40,55,70,5,12,28]

Output:

-1

Worked solution and explanation

Why this problem exists in real interviews

This is binary search wearing a costume. The ring buffer wrapped, so readings is sorted but not from index 0: there is one pivot where a high value is followed by the lowest. The skill being probed is whether you can still halve the search space when the global sort is broken. Anyone can write a textbook binary search. The trick is that comparing target to readings[mid] alone is not enough, because either side of mid might straddle the pivot. Treat it as an ordinary sorted array and you follow the wrong half past the wrap and report -1 for values that are sitting right there. Fall back to scanning every slot and you are correct but you have thrown away the ordering the whole structure exists to give you.

Break down the requirements

Step 1: Identify the sorted half

With lo, mid, hi in hand, check readings[lo] <= readings[mid]. If true, the left half from lo to mid is sorted and the pivot (if any) is on the right. If false, the pivot is on the left and the right half from mid to hi is the sorted one.

Step 2: Ask if the target is inside the clean half

The sorted half has an unambiguous range. For a sorted left half, test readings[lo] <= target < readings[mid]. If the target falls in that window, discard the right half (hi = mid - 1); otherwise the target must be in the messy half, so lo = mid + 1. Mirror the logic when the right half is the sorted one.

Step 3: Mind the boundary comparisons

Use <= on the endpoint that includes readings[lo] (or readings[hi]) and strict < on the side touching readings[mid], which you already handled with the equality check at the top. Getting one of these wrong drops the element sitting exactly on a boundary and turns a present value into a -1.

Step 4: Terminate cleanly

Loop while lo <= hi. Return mid the moment readings[mid] equals target. If the window collapses without a hit, the value is not in the buffer, so return -1. This also handles the empty buffer for free: hi starts at -1 and the loop never runs.

The solution

Rotation-aware binary search
def find_reading(readings, target):
    lo, hi = 0, len(readings) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if readings[mid] == target:
            return mid
        if readings[lo] <= readings[mid]:
            # left half [lo, mid] is sorted
            if readings[lo] <= target < readings[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # right half [mid, hi] is sorted
            if readings[mid] < target <= readings[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1
Plain binary search
Compares target to readings[mid] and moves left or right on that alone. Correct only when the array is sorted from index 0. Cross the pivot and it steers into the wrong half, missing present values.
Rotation-aware
First asks which half is sorted, then uses that half's clean bounds to decide direction. Correct for any rotation amount, including a rotation of zero (already sorted) and a single element.

Common follow-up questions