Idle GPU Days FAANG Python Interview Question

At your big-tech company, teams are fighting tooth and nail to train their AI models on the company’s shiny new NVIDIA GPUs. It’s like the Hunger Games but with less archery and more coding.

The GPUs are in such high demand that some teams “accidentally” (totally on purpose) overlap their training sessions. It’s chaos. The GPU cluster is booked for days on end, and now everyone’s looking for gaps to squeeze in their own usage.

Unlike those greedy GPU hogs, your team has been given strict instructions: you can only run your training on days when nobody else is using the GPUs. Your VP made it crystal clear that overlapping sessions are not an option.

You’re given two things:

1. An integer days, representing the total number of days the GPUs are available (from day 1).
2. A 2D array training_sessions where training_sessions[i] = [start_i, end_i] shows when team i is hogging the GPUs.

Your mission is to figure out how many days the GPUs are sitting idle so that your team can swoop in and get some guilt-free training time.

Example #1

Input: training_sessions = [[2, 4], [1, 5], [7, 8]], days = 9
Output: 2

Explanation:
Day 6 and day 9 are the only days when the GPUs are free.

Example #2

Input: training_sessions = [[1, 4]], days = 4
Output: 0

Explanation:
The GPUs didn’t get a single day off. Your team will just have to wait patiently until the chaos subsides.

If training sessions never overlapped, we could simply calculate how many days each session would take by using the start and end date of each session, summing this, and then subtracting the total from the given number of days to determine how many days the GPUs are idle.

Here’s the process we would have followed (if sessions did not overlap):

1. Iterate over the training sessions and calculate how many days each session would take. For example, let’s say the 0th session has an interval of [1, 3]; this would be a total of 3 - 1 + 1 (we add 1 because the interval is inclusive).
2. Add the total number of days for each session.
3. Subtract this total from the given number of days to get the idle days.

However, sessions can overlap. This causes issues because overlapping intervals could lead to double-counting of GPU usage, which would result in inaccurate idle day calculations. To solve this, we need to merge overlapping intervals and then calculate the total days the GPUs are being used.

Here’s the updated process:

1. Sort the intervals so that overlapping intervals are next to each other. This allows us to merge them easily.
2. Iterate through the sorted intervals. For each interval, check if it overlaps with the last merged interval. If they overlap, update the ending of the last merged interval to the maximum of the two intervals' endings. If they don’t overlap, append the current interval to the list of merged intervals.
3. After merging, iterate through the merged intervals and calculate how many days the GPUs are being used.
4. Subtract the total from step 3 from the given number of days to calculate the idle days.

Here is the code:

def gpu_idle_days(days, training_sessions):
    # Step 1: Sort the intervals
    training_sessions.sort()
    
    # Step 2: Merge overlapping intervals
    merged_sessions = []
    start, end = training_sessions[0]
    
    for s, e in training_sessions:
        if start <= s <= end:  # Overlap detected
            end = max(end, e)  # Merge by extending the interval
        else:
            merged_sessions.append([start, end])
            start, end = s, e
    
    # Don't forget to add the last interval
    merged_sessions.append([start, end])
    
    # Step 3: Calculate total days the GPUs are in use
    total_used_days = 0
    for s, e in merged_sessions:
        total_used_days += (e - s + 1)
    
    # Step 4: Subtract total used days from total available days
    return days - total_used_days
    

Space-Optimized Approach

The only reason we collected the merged sessions earlier was to count the total number of days the sessions are scheduled. Instead, we can calculate the total days directly while merging intervals, avoiding extra space.

Here’s the plan:

1. Iterate over the sorted training sessions:
   • If there’s an overlap, merge by extending the interval.
   • If there’s no overlap, update the total number of days the GPU was in use by end - start + 1 (add 1 because the end day is inclusive).
2. Return the difference between the total days given and the total days the GPUs were in use.

Here’s the code:

def gpu_idle_days(days, training_sessions):
    # Step 1: Sort the intervals
    training_sessions.sort()
    
    # Step 2: Merge overlapping intervals while counting days
    total_used_days = 0
    start, end = training_sessions[0]
    
    for s, e in training_sessions:
        if start <= s <= end:  # Overlap detected
            end = max(end, e)  # Merge by extending the interval
        else:
        	# Add the current interval's days
            total_used_days += (end - start + 1)  
            start, end = s, e
   
    # Add the last interval
    total_used_days += (end - start + 1)
    
    return days - total_used_days