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:
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 <= 1002 <= logs[i].length <= 30logs[i] is of the form "A B duration".A and B are phone numbers consisting of digits.0 <= duration <= 1000When 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:
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:
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_callersTo 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:
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| Case | How to Handle |
|---|---|
| Null or empty names array | Return an empty list immediately as there are no callers to process. |
| Null or empty times array | Return an empty list immediately as there are no call durations to process. |
| Names and times arrays have different lengths | Throw an IllegalArgumentException or return an empty list, indicating invalid input. |
| All call times are zero | Return all names sorted lexicographically, as they all have the same (longest) call duration. |
| Integer overflow in cumulative call duration | Use a data type with a larger range (e.g., long) for cumulative durations to prevent overflow. |
| Large input arrays causing memory issues | 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 | 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 | Throw an IllegalArgumentException or treat them as zero, logging a warning in either case. |