Find Longest Consecutive Listen Gaps - codepath/compsci_guides GitHub Wiki

Unit 4 Session 2 Standard (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the goal of the problem?
  • A: The goal is to find the longest gap between consecutive episode listen timestamps.
• Q: What are the inputs?
  • A: The input is a list of integers representing the timestamps of episode listens in minutes since midnight, sorted in ascending order.
• Q: What are the outputs?
  • A: The output is an integer representing the longest gap in minutes between consecutive listens.
• Q: Are there any assumptions about the input?
  • A: The list of timestamps is sorted in ascending order and contains valid integer values representing minutes since midnight.

P-lan

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.

I-mplement

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