How many readings fall in the band
A sorted column of measurements is checked against a tolerance band, and the report wants the count inside it — over millions of rows, so scanning is out.
- The readings arrive sorted ascending.
- Both ends of the band are inclusive.
- A band that runs backwards contains nothing.
- Return how many readings fall inside.
countInBand(readings: list<int>, low: int, high: 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 countInBand(readings []int, low int, high int) int {
}Worked examples
| Call | Result |
|---|---|
countInBand([]int{1, 3, 5, 7, 9}, 3, 7) | 3 |
countInBand([]int{1, 3, 5, 7, 9}, 4, 4) | 0 |
countInBand([]int{2, 2, 2, 2}, 2, 2) | 4 |
countInBand([]int{1, 2, 3}, 3, 1) | 0 |
Hint
Two binary searches: the first position not below the low end, and the first position above the high end. The gap between them is the answer.
Reference solution in Go
func countInBand(readings []int, low int, high int) int {
if low > high {
return 0
}
lowerBound := func(target int) int {
lo, hi := 0, len(readings)
for lo < hi {
mid := (lo + hi) / 2
if readings[mid] < target {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
return lowerBound(high+1) - lowerBound(low)
}