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
public int LongestGap(List<int> timestamps) {
}Worked examples
| Call | Result |
|---|---|
LongestGap(new List<int> { 100, 130, 200, 205 }) | 70 |
LongestGap(new List<int> { 205, 100, 200, 130 }) | 70 |
LongestGap(new List<int> { 10, 20 }) | 10 |
LongestGap(new List<int> { 42 }) | 0 |
Hint
Sort first. Without that, "next to each other" means nothing.
Reference solution in C#
public int LongestGap(List<int> timestamps) {
if (timestamps.Count < 2) return 0;
var s = new List<int>(timestamps);
s.Sort();
int worst = 0;
for (int i = 1; i < s.Count; i++) worst = Math.Max(worst, s[i] - s[i - 1]);
return worst;
}