# The Overwritten Hour > The log wrapped on itself. The order is still there, just not where you would look. Canonical URL: Domain: Python · Difficulty: medium · Seniority: mid ## 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. ## 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. > **Trick to solving** > > At any midpoint, at least one of the two halves is contiguously sorted (no pivot inside it). Compare `readings[lo]` to `readings[mid]` to find which half that is, then use that half's clean min and max to test whether `target` lives there. That single decision tells you which way to move. --- ### 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** ```python 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 ``` > **Complexity** > > O(log n) time and O(1) space: every iteration discards half the window, exactly like an unrotated binary search. A one-million-slot buffer is resolved in about 20 probes. A linear scan would be correct too but O(n), which is the entire reason this structure keeps its ordering instead of being a hash set. > **Interviewers watch for** > > Whether you locate the sorted half in one comparison rather than first hunting for the pivot with a separate search and then binary-searching inside it. The one-pass version is the same complexity but shows you understand that the invariant (one half is always sorted) can be maintained as the window shrinks. > **Common pitfall** > > Writing `readings[lo] < target` instead of `readings[lo] <= target`. That strict inequality skips the value sitting exactly at lo, so a target that happens to be the smallest element in the sorted half is reported as absent. The equality check at the top of the loop is what lets the range tests be careful about the mid side. **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 - What changes if the timestamps can repeat, so readings may contain duplicates? _(Duplicates break the `readings[lo] <= readings[mid]` test (both sides can be equal), forcing a lo += 1 fallback and pushing the worst case to O(n).)_ - How would you find the pivot index (the smallest element) instead of a specific target? _(Tests whether the candidate can adapt the same invariant to search for a structural boundary rather than a value.)_ - Several threads probe this buffer concurrently while one writer appends. Does the GIL make this safe, and what would you still guard? _(Ties to CPython's GIL: individual list index reads are atomic, but a read racing a rotation or rewrite still needs a snapshot or lock for a consistent view.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the-overwritten-hour) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.