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
Java 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
int oldestReading(List<Integer> readings) {
}Worked examples
| Call | Result |
|---|---|
oldestReading(Main.<Integer>ls(4, 5, 6, 7, 0, 1, 2)) | 0 |
oldestReading(Main.<Integer>ls(1, 2, 3)) | 1 |
oldestReading(Main.<Integer>ls(3, 1, 2)) | 1 |
oldestReading(Main.<Integer>ls(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 Java
int oldestReading(List<Integer> readings) {
if (readings.isEmpty()) return 0;
int lo = 0, hi = readings.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (readings.get(mid) > readings.get(hi)) lo = mid + 1;
else hi = mid;
}
return readings.get(lo);
}