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?
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.
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.
Time Complexity: O(n log n) due to sorting operation. Space Complexity: O(n) for storing the consolidated list of all IDs.
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.
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.
C++
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.
| Approach | Complexity |
|---|---|
| SQL Aggregation and Joined Count | Time Complexity: |
| Use of Dictionary (HashMap) to Count Friends | Time Complexity: |
FACEBOOK/META LeetCode Medium “Friend Requests II" 602 Interview SQL Question Explanation | EDS • Everyday Data Science • 4,653 views views
Watch 9 more video solutions →Practice Friend Requests II: Who Has the Most Friends with our built-in code editor and test cases.
Practice on FleetCode