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
public int OldestReading(List<int> readings) {
}Worked examples
| Call | Result |
|---|---|
OldestReading(new List<int> { 4, 5, 6, 7, 0, 1, 2 }) | 0 |
OldestReading(new List<int> { 1, 2, 3 }) | 1 |
OldestReading(new List<int> { 3, 1, 2 }) | 1 |
OldestReading(new List<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#
public int OldestReading(List<int> readings) {
if (readings.Count == 0) return 0;
int lo = 0, hi = readings.Count - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (readings[mid] > readings[hi]) lo = mid + 1;
else hi = mid;
}
return readings[lo];
}