Table: RequestAccepted
+----------------+---------+ | Column Name | Type | +----------------+---------+ | requester_id | int | | accepter_id | int | | accept_date | date | +----------------+---------+ (requester_id, accepter_id) is the primary key (combination of columns with unique values) for this table. This table contains the ID of the user who sent the request, the ID of the user who received the request, and the date when the request was accepted.
Write a solution to find the people who have the most friends and the most friends number.
The test cases are generated so that only one person has the most friends.
The result format is in the following example.
Example 1:
Input: RequestAccepted table: +--------------+-------------+-------------+ | requester_id | accepter_id | accept_date | +--------------+-------------+-------------+ | 1 | 2 | 2016/06/03 | | 1 | 3 | 2016/06/08 | | 2 | 3 | 2016/06/08 | | 3 | 4 | 2016/06/09 | +--------------+-------------+-------------+ Output: +----+-----+ | id | num | +----+-----+ | 3 | 3 | +----+-----+ Explanation: The person with id 3 is a friend of people 1, 2, and 4, so he has three friends in total, which is the most number than any others.
Follow up: In the real world, multiple people could have the same most number of friends. Could you find all these people in this case?
In #602 Friend Requests II: Who Has the Most Friends, the goal is to determine which user has the highest number of friends based on accepted friend requests. Each row in the table represents a confirmed friendship between a requester_id and an accepter_id. Since friendships are mutual, both users should be counted toward each other's total.
A practical strategy is to normalize the relationships by treating both columns as individual user entries. This can be achieved by combining the requester_id and accepter_id columns using a UNION ALL. After transforming the data into a single list of user IDs, you can apply GROUP BY to count how many times each user appears, which corresponds to their number of friends.
Finally, sort the counts in descending order and return the user with the highest value. This approach efficiently aggregates friendship counts using SQL grouping and sorting operations, making it scalable even for larger datasets.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| UNION ALL with GROUP BY aggregation | O(n) | O(n) |
Everyday Data Science
Use these hints if you're stuck. Try solving on your own first.
Being friends is bidirectional. If you accept someone's adding friend request, both you and the other person will have one more friend.
The main idea here is to see every occurrence of an ID as a friendship connection, whether it appears as a requester or an accepter. We'll thus aggregate the ID counts to find out who has the maximum number of occurrences, meaning the maximum number of friends.
First, we can treat requesters and accepters separately and count how many times a person appears as a requester or an accepter, then sum these counts to get the total number of friends for each ID. Finally, we can select the ID with the maximum sum of appearances.
Time Complexity: O(n log n) due to sorting operation. Space Complexity: O(n) for storing the consolidated list of all IDs.
1SELECT id, num FROM ( SELECT id, COUNT(id) as num FROM ( SELECT requester_id as id FROM RequestAccepted UNION ALL SELECT accepter_id as id FROM RequestAccepted ) as friends GROUP BY id ) as counts ORDER BY num DESC LIMIT 1;We first create a subquery to combine all requesters and accepters into a single list using UNION ALL. We then count the occurrences of each individual in this list, which represents the number of friendships they have. Finally, we sort these counts in descending order and select the top result.
This approach can be employed in programming languages such as Python, Java, and C# where dictionaries (or hashmaps) are effective for counting occurrences.
For each row in the data, increment the friendship count for both the requester and the accepter in a dictionary (or hashmap). After processing, iterate through the dictionary to find the ID with the maximum count.
Time Complexity: O(n) since we pass through the data once and dictionary operations are generally O(1). Space Complexity: O(n) for storing the friend counts.
1def find_most_friends(requests):
2Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
UNION ALL is used to merge requester_id and accepter_id into one list without removing duplicates. This ensures every accepted friendship contributes correctly to each user's total friend count.
Yes, similar SQL aggregation and relationship-counting problems are common in FAANG-style interviews. They test your ability to manipulate relational data, normalize relationships, and use grouping and sorting effectively.
The optimal approach is to combine requester_id and accepter_id into a single column using UNION ALL, then group by the user ID to count friendships. Sorting the counts in descending order helps identify the user with the maximum number of friends.
SQL aggregation using GROUP BY is the key concept for this problem. By transforming both columns into a unified list of user IDs, you can efficiently count friendships and determine which user appears most frequently.
Using the Python defaultdict, we initialize counts to zero and update them by iterating over each friendship in the list. After updating, we calculate the maximum count and figure out which person has this maximum count.