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
C++ 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(std::vector<int> readings) {
}Worked examples
| Call | Result |
|---|---|
oldestReading(std::vector<int>{4, 5, 6, 7, 0, 1, 2}) | 0 |
oldestReading(std::vector<int>{1, 2, 3}) | 1 |
oldestReading(std::vector<int>{3, 1, 2}) | 1 |
oldestReading(std::vector<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 C++
int oldestReading(std::vector<int> readings) {
if (readings.empty()) return 0;
int lo = 0, hi = static_cast<int>(readings.size()) - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (readings[mid] > readings[hi]) lo = mid + 1;
else hi = mid;
}
return readings[lo];
}