Difficulty: Easy | Acceptance: 60.30% | Paid: No Topics: Database
Table: Users
+-------------+---------+ | Column Name | Type | +-------------+---------+ | user_id | int | | user_name | varchar | +-------------+---------+ user_id is the primary key (column with unique values) of this table. Each row of this table contains the name and the id of the user.
Table: Register
+-------------+---------+ | Column Name | Type | +-------------+---------+ | contest_id | int | | user_id | int | +-------------+---------+ (contest_id, user_id) is the primary key (combination of columns with unique values) of this table. Each row of this table indicates that the user with user_id attended the contest with contest_id.
Write a solution to find the percentage of the users registered in each contest. Round the percentage to the nearest two decimals.
Return the result table ordered by percentage in descending order, and in case of a tie, by contest_id in ascending order.
The result format is in the following example.
- Examples
- Constraints
- Subquery Approach
- Cross Join Approach
- Left Join Approach
Examples
Example 1
Input: Users table: +---------+-----------+ | user_id | user_name | +---------+-----------+ | 6 | Alice | | 2 | Bob | | 7 | Alex | +---------+-----------+
Register table: +------------+---------+ | contest_id | user_id | +------------+---------+ | 215 | 6 | | 209 | 2 | | 208 | 2 | | 210 | 6 | | 208 | 6 | | 209 | 7 | | 209 | 6 | | 208 | 7 | | 210 | 2 | | 207 | 7 | | 209 | 5 | +------------+---------+
Output: +------------+------------+ | contest_id | percentage | +------------+------------+ | 208 | 100.0 | | 209 | 100.0 | | 210 | 66.67 | | 215 | 33.33 | | 207 | 33.33 | +------------+------------+
Explanation:
- All the users (Alice, Bob, and Alex) attended contests 208 and 209.
- Alice and Alex attended contest 210. Percentage is 66.67.
- Alice attended contest 215. Percentage is 33.33.
- Alex attended contest 207. Percentage is 33.33.
Constraints
1 <= user_id <= 1000
1 <= contest_id <= 10000
1 <= number of rows in Users <= 1000
1 <= number of rows in Register <= 10000
Subquery Approach
Intuition Calculate the total number of users using a subquery, then count unique users per contest and compute the percentage by dividing by the total.
Steps
- Get total user count from Users table using a subquery
- Group Register table by contest_id and count distinct user_id
- Calculate percentage as (count * 100.0) / total_users
- Round to 2 decimal places and order by percentage DESC, contest_id ASC
import pandas as pd
def users_percentage(users: pd.DataFrame, register: pd.DataFrame) -> pd.DataFrame:
total_users = len(users)
contest_counts = register.groupby('contest_id')['user_id'].nunique().reset_index()
contest_counts['percentage'] = round(contest_counts['user_id'] * 100.0 / total_users, 2)
contest_counts = contest_counts.sort_values(by=['percentage', 'contest_id'], ascending=[False, True])
return contest_counts[['contest_id', 'percentage']]Complexity
- Time: O(n + m) where n is number of users and m is number of registrations
- Space: O(k) where k is number of unique contests
- Notes: Simple and readable approach with clear separation of concerns
Cross Join Approach
Intuition Use CROSS JOIN to combine each contest with the total user count, then calculate percentages in a single pass without nested subqueries.
Steps
- Create a subquery to get total user count
- CROSS JOIN this with Register table to make total available for each row
- Group by contest_id and count distinct users
- Calculate percentage and round to 2 decimals
- Order by percentage DESC, contest_id ASC
import pandas as pd
def users_percentage(users: pd.DataFrame, register: pd.DataFrame) -> pd.DataFrame:
total_users = len(users)
result = register.merge(pd.DataFrame({'total': [total_users]}), how='cross')
contest_counts = result.groupby('contest_id').agg(
user_count=('user_id', 'nunique'),
total=('total', 'first')
).reset_index()
contest_counts['percentage'] = round(contest_counts['user_count'] * 100.0 / contest_counts['total'], 2)
contest_counts = contest_counts.sort_values(by=['percentage', 'contest_id'], ascending=[False, True])
return contest_counts[['contest_id', 'percentage']]Complexity
- Time: O(n + m) where n is number of users and m is number of registrations
- Space: O(k) where k is number of unique contests
- Notes: CROSS JOIN creates a Cartesian product but with single-row subquery, it’s efficient
Left Join Approach
Intuition Use LEFT JOIN with a constant condition to make total user count available for all rows, then aggregate by contest to calculate percentages.
Steps
- LEFT JOIN Register with Users using ON 1=1 (cartesian join)
- Group by contest_id and count distinct users from Register
- Count distinct users from Users to get total
- Calculate percentage and round to 2 decimals
- Order by percentage DESC, contest_id ASC
import pandas as pd
def users_percentage(users: pd.DataFrame, register: pd.DataFrame) -> pd.DataFrame:
total_users = len(users)
contest_counts = register.groupby('contest_id')['user_id'].nunique().reset_index()
contest_counts['percentage'] = round(contest_counts['user_id'] * 100.0 / total_users, 2)
contest_counts = contest_counts.sort_values(by=['percentage', 'contest_id'], ascending=[False, True])
return contest_counts[['contest_id', 'percentage']]Complexity
- Time: O(n × m) in worst case due to cartesian join, but optimized by SQL engines
- Space: O(k) where k is number of unique contests
- Notes: Less efficient than subquery approach for large datasets due to cartesian product