Taro Logo

Find Longest Calls

Medium
Asked by:
Profile picture
43 views
Topics:
ArraysStringsTwo Pointers

You are given a data log of phone calls, represented as an array of strings logs, where each string logs[i] represents a phone call. Each phone call has the format "A B duration", where:

  • A is the caller's phone number.
  • B is the recipient's phone number.
  • duration is the length of the call in minutes.

All phone numbers are strings consisting of digits '0'-'9'.

You want to find the phone number(s) that made or received the longest call(s). Return the phone number(s).

Notes:

  • There could be multiple phone numbers that made the longest call(s).
  • The returned list should be sorted lexicographically and have no duplicate entries.

Example 1:

Input: logs = ["123 456 100","234 456 200","123 234 500"]
Output: ["123","234"]
Explanation:
Phone number 123 made calls for 100 + 500 = 600 minutes.
Phone number 456 made calls for 100 + 200 = 300 minutes.
Phone number 234 made calls for 200 + 500 = 700 minutes.
So phone numbers 123 and 234 are the ones with the longest calls.

Example 2:

Input: logs = ["00 44 500","00 66 600","11 44 500","55 44 500"]
Output: ["00","11","55"]
Explanation:
Phone number 00 made calls for 500 + 600 = 1100 minutes.
Phone number 44 made calls for 500 + 500 + 500 = 1500 minutes.
Phone number 66 made calls for 600 minutes.
Phone number 11 made calls for 500 minutes.
Phone number 55 made calls for 500 minutes.
So phone numbers 00, 11, and 55 are the ones with the longest calls.
Note that we do not include 44 since it is not the longest call.

Constraints:

  • 1 <= logs.length <= 100
  • 2 <= logs[i].length <= 30
  • logs[i] is of the form "A B duration".
  • A and B are phone numbers consisting of digits.
  • 0 <= duration <= 1000

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the possible ranges and data types for the call durations in the `times` array? Could they be negative or zero?
  2. What is the expected behavior if either the `names` or `times` array is null or empty?
  3. Are the `names` and `times` arrays guaranteed to have the same length, and what should happen if they don't?
  4. If there are multiple callers with the same longest cumulative call duration, in what order should the names be sorted lexicographically (ascending or descending)?
  5. What is the maximum number of entries we might expect in the input arrays (e.g., can we assume it's small enough to fit comfortably in memory)?

Brute Force Solution

Approach

The brute force approach to finding the longest calls involves checking every single combination of calls to find the longest one. Think of it as comparing every call duration with every other call duration and their combinations.

Here's how the algorithm would work step-by-step:

  1. First, consider each call duration individually. This is your starting point.
  2. Then, consider every possible pair of call durations. Calculate the combined duration for each pair.
  3. Next, consider every possible group of three call durations, then four, and so on. Calculate the combined duration for each group.
  4. Continue this process until you have considered all possible groups of calls.
  5. Finally, compare all the durations you calculated (individual calls, pairs, groups of three, etc.) and select the longest duration.

Code Implementation

def find_longest_calls_brute_force(call_records):

    longest_duration = 0
    longest_callers = []

    for first_call_record in call_records:
        first_call_duration = first_call_record['end'] - first_call_record['start']

        # Loop through to compare against all other calls
        for second_call_record in call_records:
            second_call_duration = second_call_record['end'] - second_call_record['start']

            if first_call_duration > longest_duration:

                # Update the longest duration if a longer call is found
                longest_duration = first_call_duration
                longest_callers = [first_call_record['caller_id']]

            elif first_call_duration == longest_duration:

                # Add the caller to the list if duration matches
                if first_call_record['caller_id'] not in longest_callers:
                    longest_callers.append(first_call_record['caller_id'])

    # Return the callers associated with the longest calls
    return longest_callers

Big(O) Analysis

Time Complexity
O(2^n) – The brute force approach involves considering all possible subsets of the input call durations. For a set of n call durations, there are 2^n possible subsets (each element can either be included or excluded in a subset). Calculating the duration for each of these subsets takes O(1) time. Therefore, the overall time complexity is proportional to the number of subsets, which is O(2^n).
Space Complexity
O(1) – The provided brute force approach, as described, primarily involves iterating through combinations of call durations and calculating their sums. While it doesn't explicitly mention creating large data structures, the dominant space usage would stem from storing the longest duration found so far, which is a single variable. Regardless of the number of call durations (N), we only need a constant amount of extra memory to track the maximum duration seen so far. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To find the longest calls, we need to focus on sorting and efficiently comparing call durations. The key is to organize the calls and then quickly identify the ones with the highest durations. We can do this without needing to check every possible combination.

Here's how the algorithm would work step-by-step:

  1. First, organize the calls by their duration, from longest to shortest.
  2. Once the calls are organized, pick the call with the longest duration to begin.
  3. Keep track of all other calls that have the same maximum duration.
  4. Now you have a list of all the longest calls.

Code Implementation

def find_longest_calls(calls):
    sorted_calls = sorted(calls, key=lambda call: call['start_time'])

    longest_duration = 0
    longest_calls_group = []

    current_duration = 0
    current_calls_group = []

    if not sorted_calls:
        return []

    current_calls_group.append(sorted_calls[0])
    current_duration = sorted_calls[0]['duration']
    current_end_time = sorted_calls[0]['start_time'] + sorted_calls[0]['duration']

    for i in range(1, len(sorted_calls)):
        call = sorted_calls[i]

        # Check if the current call overlaps with the existing group
        if call['start_time'] <= current_end_time:

            current_calls_group.append(call)
            current_duration += call['duration']

            # Update the end time if the new call extends it
            current_end_time = max(current_end_time, call['start_time'] + call['duration'])

        else:
            # The current call does not overlap
            if current_duration > longest_duration:
                longest_duration = current_duration
                longest_calls_group = current_calls_group

            # Reset the current group with the current call
            current_calls_group = [call]
            current_duration = call['duration']
            current_end_time = call['start_time'] + call['duration']

    # Check if the last group is the longest
    if current_duration > longest_duration:
        longest_duration = current_duration
        longest_calls_group = current_calls_group

    return longest_calls_group

Big(O) Analysis

Time Complexity
O(n log n) – The dominant operation in this approach is sorting the calls by duration. Efficient sorting algorithms like merge sort or quicksort, which are commonly used in practice, have a time complexity of O(n log n), where n is the number of calls. The subsequent steps of identifying and collecting the longest calls involve iterating through the sorted list once, which takes O(n) time. Since O(n log n) grows faster than O(n), the overall time complexity is determined by the sorting step.
Space Complexity
O(N) – The algorithm sorts the calls by duration, which typically involves creating a sorted copy of the input data. If N is the number of calls, the sorted list will take O(N) auxiliary space. Additionally, the algorithm keeps track of calls with the maximum duration, potentially storing them in a list which could grow up to size N in the worst case where all calls have the same duration. Thus, the space complexity is O(N).

Edge Cases

Null or empty names array
How to Handle:
Return an empty list immediately as there are no callers to process.
Null or empty times array
How to Handle:
Return an empty list immediately as there are no call durations to process.
Names and times arrays have different lengths
How to Handle:
Throw an IllegalArgumentException or return an empty list, indicating invalid input.
All call times are zero
How to Handle:
Return all names sorted lexicographically, as they all have the same (longest) call duration.
Integer overflow in cumulative call duration
How to Handle:
Use a data type with a larger range (e.g., long) for cumulative durations to prevent overflow.
Large input arrays causing memory issues
How to Handle:
The solution should use a hash map to aggregate call durations, which has O(n) space complexity, making it scalable, but consider using external sorting if memory is extremely limited.
All names are the same
How to Handle:
Sum all the call times and associate it with the single name, then return a list containing only that name.
Negative call durations in the times array
How to Handle:
Throw an IllegalArgumentException or treat them as zero, logging a warning in either case.