The smallest reading in a wrapped log
A ring buffer holds readings that were written in ascending order but wrapped around at some point. The oldest reading is the smallest one, and finding it should not cost a full scan.
- The readings were ascending before being rotated some number of places.
- All the values are distinct.
- A buffer that was not rotated at all is still valid input.
- An empty buffer has no smallest reading: return 0.
oldest_reading(readings: list<int>) → int
Where you start
def oldest_reading(readings: list[int]) -> int:
Worked examples
| Call | Result |
|---|---|
oldest_reading([4, 5, 6, 7, 0, 1, 2]) | 0 |
oldest_reading([1, 2, 3]) | 1 |
oldest_reading([3, 1, 2]) | 1 |
oldest_reading([2, 3, 4, 5, 1]) | 1 |
Hint
Compare the middle with the last entry. If the middle is larger, the wrap is to its right; otherwise the answer is the middle or to its left.
Reference solution in Python
def oldest_reading(readings: list[int]) -> int:
if not readings:
return 0
lo, hi = 0, len(readings) - 1
while lo < hi:
mid = (lo + hi) // 2
if readings[mid] > readings[hi]:
lo = mid + 1
else:
hi = mid
return readings[lo]