Unit 4 Session 2 Standard (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Iterate through the sorted list of timestamps and calculate the difference between each consecutive pair of timestamps. Track the maximum difference found.
1) Initialize a variable `max_gap` to 0.
2) Iterate through the list of `timestamps` using a loop:
a) For each pair of consecutive timestamps, calculate the gap as `timestamps[i + 1] - timestamps[i]`.
b) If the calculated gap is greater than `max_gap`, update `max_gap` to this value.
3) Return `max_gap` after the loop completes.
**⚠️ Common Mistakes**
- Forgetting that the list is already sorted and attempting unnecessary sorting operations.
- Not correctly updating the `max_gap` when a larger gap is found.
- Assuming that there will always be more than one timestamp in the list without considering edge cases.
def find_longest_gap(timestamps):
# Initialize variables to keep track of the maximum gap
max_gap = 0
n = len(timestamps)
# Two-pointer approach: start with two pointers
i, j = 0, 1
while j < n:
# Calculate the gap between the current pair of timestamps
gap = timestamps[j] - timestamps[i]
# Update max_gap if the current gap is larger
if gap > max_gap:
max_gap = gap
# Move the pointers to the next pair of timestamps
i += 1
j += 1
return max_gap
Example Usage:
timestamps1 = [30, 50, 70, 100, 120, 150]
print(find_longest_gap(timestamps1))
# Output: 30
timestamps2 = [10, 20, 30, 50, 60, 90]
print(find_longest_gap(timestamps2))
# Output: 30
timestamps3 = [5, 10, 15, 25, 35, 45]
print(find_longest_gap(timestamps3))
# Output: 10