The longest silence between heartbeats
A service sends a heartbeat every so often. The longest gap between two of them is how long it might have been down without anyone noticing.
- Timestamps arrive in any order and are in seconds.
- The answer is the largest difference between two heartbeats that are next to each other in time.
- Fewer than two heartbeats means no gap at all: return 0.
longestGap(timestamps: 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 longestGap(std::vector<int> timestamps) {
}Worked examples
| Call | Result |
|---|---|
longestGap(std::vector<int>{100, 130, 200, 205}) | 70 |
longestGap(std::vector<int>{205, 100, 200, 130}) | 70 |
longestGap(std::vector<int>{10, 20}) | 10 |
longestGap(std::vector<int>{42}) | 0 |
Hint
Sort first. Without that, "next to each other" means nothing.
Reference solution in C++
int longestGap(std::vector<int> timestamps) {
if (timestamps.size() < 2) return 0;
std::vector<int> s = timestamps;
std::sort(s.begin(), s.end());
int worst = 0;
for (size_t i = 1; i < s.size(); i++) worst = std::max(worst, s[i] - s[i - 1]);
return worst;
}