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.
oldestReading(readings: list<int>) → int
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func oldestReading(readings []int) int {
}Worked examples
| Call | Result |
|---|---|
oldestReading([]int{4, 5, 6, 7, 0, 1, 2}) | 0 |
oldestReading([]int{1, 2, 3}) | 1 |
oldestReading([]int{3, 1, 2}) | 1 |
oldestReading([]int{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 Go
func oldestReading(readings []int) int {
if len(readings) == 0 {
return 0
}
lo, hi := 0, len(readings)-1
for lo < hi {
mid := (lo + hi) / 2
if readings[mid] > readings[hi] {
lo = mid + 1
} else {
hi = mid
}
}
return readings[lo]
}