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
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 longestGap(List<Integer> timestamps) {
}Worked examples
| Call | Result |
|---|---|
longestGap(Main.<Integer>ls(100, 130, 200, 205)) | 70 |
longestGap(Main.<Integer>ls(205, 100, 200, 130)) | 70 |
longestGap(Main.<Integer>ls(10, 20)) | 10 |
longestGap(Main.<Integer>ls(42)) | 0 |
Hint
Sort first. Without that, "next to each other" means nothing.
Reference solution in Java
int longestGap(List<Integer> timestamps) {
if (timestamps.size() < 2) return 0;
List<Integer> s = new ArrayList<>(timestamps);
Collections.sort(s);
int worst = 0;
for (int i = 1; i < s.size(); i++) worst = Math.max(worst, s.get(i) - s.get(i - 1));
return worst;
}