Find Peak Memory Usage Across Process Intervals

Question

The candidate is asked to write a function that determines the peak memory usage across a series of process intervals.

Codemia · Accepted Answer

To find the peak memory usage across process intervals, we can utilize a timeline approach. We will create events for the start and end of each interval, then iterate through these events to calculate the current memory usage at each point in time.

1. Create a list of events from the process intervals, where each start time adds memory and each end time subtracts memory.  
2. Sort the events by time. If two events have the same time, process the end event before the start event to avoid counting memory usage at the exact moment an interval ends.  
3. Initialize a variable to track current memory usage and another to track peak memory usage.  
4. Iterate through the sorted events, updating current memory usage and checking if it exceeds peak memory usage.

The time complexity of this approach is O(n log n) due to the sorting of events, where n is the number of intervals. The space complexity is O(n) for storing the events.

```python
def find_peak_memory_usage(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))  # Memory starts being used
        events.append((end, -1))    # Memory stops being used
    
    events.sort(key=lambda x: (x[0], x[1]))  # Sort by time, then by type
    
    current_memory = 0
    peak_memory = 0
    
    for _, change in events:
        current_memory += change
        peak_memory = max(peak_memory, current_memory)
    
    return peak_memory
```

Consider scenarios such as overlapping intervals, intervals that start and end at the same time, and intervals with zero duration. Ensure to test these cases to validate the robustness of the solution.

Find Peak Memory Usage Across Process Intervals

Nutanix

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Nutanix Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string