Find the Maximum Number of Active Loans

Question

The question asks the candidate to determine the maximum number of active loans at any given time based on a list of loan intervals defined by their disbursal and closure days.

Codemia · Accepted Answer

To find the maximum number of active loans at any given time, we can use a sweep line algorithm. This involves creating events for each loan's disbursal and closure days. We will treat the disbursal day as an event that increases the count of active loans, and the closure day as an event that decreases it.

1. Create an event list from the loan intervals. For each loan interval [start, end), add a start event at 'start' and an end event at 'end'.
2. Sort the events first by time. If two events have the same time, prioritize end events over start events.
3. Initialize a counter for active loans and a variable to track the maximum count.
4. Iterate through the sorted events, updating the counter based on whether the event is a start or end event, and update the maximum count accordingly.

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

```python
def max_active_loans(loans):
    events = []
    for start, end in loans:
        events.append((start, 1))  # Start of a loan
        events.append((end, -1))    # End of a loan

events.sort(key=lambda x: (x[0], x[1]))

max_loans = 0
    current_loans = 0

for event in events:
        current_loans += event[1]
        max_loans = max(max_loans, current_loans)

return max_loans

# Example usage:
loans = [[1,5], [2,6], [4,8], [7,9]]
print(max_active_loans(loans))  # Output: 3
```

Interviewers will look for clarity in your explanation, the efficiency of your algorithm, and how well you handle edge cases. They will also assess your coding style and ability to communicate your thought process throughout the solution.

Find the Maximum Number of Active Loans

Tekion

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

Tekion 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