1407. Top Travellers
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 84.0%
Problem Breakdown
The problem “Top Travellers” requires us to determine the total distance traveled by each user from a given table of trips. The input consists of two tables: Users and Trips. The Users table contains user IDs and names, while the Trips table contains trip IDs, user IDs, and distances traveled for each trip. The output should be a list of users sorted by their total distance traveled in descending order.
Inputs:
Users: A table with columnsid(user ID) andname(user name).Trips: A table with columnsid(trip ID),user_id(user ID), anddistance(distance traveled).
Outputs:
- A list of users sorted by their total distance traveled in descending order, along with the total distance.
Implicit Constraints/Edge Cases:
- The
Tripstable might be empty. - Users might not have any trips recorded.
- Duplicate entries in the
Tripstable should be considered only once for each user.
Intuition
A brute-force approach would involve iterating over each user, summing up their distances from the Trips table, and then sorting the results. However, this approach is inefficient with a time complexity of O(n^2) due to nested loops (one for users and one for trips).
The key insight is to leverage SQL aggregation functions to efficiently compute the total distance traveled by each user in a single pass through the data. This reduces the time complexity to O(n), where n is the number of trips.
Approach
- Join Tables: Perform an inner join between the
UsersandTripstables on theuser_idcolumn to associate each trip with its corresponding user. - Aggregate Data: Use the
GROUP BYclause to group the results by user ID, allowing us to sum up the distances for each user. - Sort Results: Order the aggregated results by the total distance in descending order using the
ORDER BYclause. - Select Columns: Select only the required columns (
nameand the summeddistance) for the final output.
Complexity Analysis
- Time Complexity: O(n), where n is the number of trips. The SQL query efficiently processes each trip once.
- Space Complexity: O(m), where m is the number of unique users, as we store the aggregated results for each user.
Solution
import pandas as pd
def top_travellers(users: pd.DataFrame, trips: pd.DataFrame) -> pd.DataFrame:
# Join Users and Trips tables on user_id
merged_df = pd.merge(users, trips, left_on='id', right_on='user_id', how='left')
# Group by user_id and sum the distances
aggregated_df = merged_df.groupby('name')['distance'].sum().reset_index()
# Rename columns for clarity
aggregated_df.columns = ['name', 'total_distance']
# Sort by total distance in descending order
sorted_df = aggregated_df.sort_values(by='total_distance', ascending=False)
return sorted_df
Edge Cases Handled
- Empty Trips Table: If the
Tripstable is empty, the result will be an empty DataFrame since no distances are summed. - Users with No Trips: Users without any trips will not appear in the final output as they have a sum of zero distance.
- Duplicate Entries: The use of
GROUP BYensures that duplicate entries for the same user and trip are considered only once.