Popularity Percentage

Problem

Table: Friends

1
2
3
4
5
6
7
8


+-------------+------+
| Column Name | Type |
+-------------+------+
| user1       | int  |
| user2       | int  |
+-------------+------+
(user1, user2) is the primary key (combination of unique values) of this table.
Each row contains information about friendship where user1 and user2 are friends.

Write a solution to find the popularity percentage for each user on Meta/Facebook. The popularity percentage is defined as the total number of friends the user has divided by the total number of users on the platform, then converted into a percentage by multiplying by 100, rounded to 2 decimal places.

Return the result table ordered by user1 inascending order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


Input:  
Friends table:
+-------+-------+
| user1 | user2 | 
+-------+-------+
| 2     | 1     | 
| 1     | 3     | 
| 4     | 1     | 
| 1     | 5     | 
| 1     | 6     |
| 2     | 6     | 
| 7     | 2     | 
| 8     | 3     | 
| 3     | 9     |  
+-------+-------+
Output:  
+-------+-----------------------+
| user1 | percentage_popularity |
+-------+-----------------------+
| 1     | 55.56                 |
| 2     | 33.33                 |
| 3     | 33.33                 |
| 4     | 11.11                 |
| 5     | 11.11                 |
| 6     | 22.22                 |
| 7     | 11.11                 |
| 8     | 11.11                 |
| 9     | 11.11                 |
+-------+-----------------------+
Explanation:  
There are total 9 users on the platform.
- User "1" has friendships with 2, 3, 4, 5 and 6. Therefore, the percentage popularity for user 1 would be calculated as (5/9) * 100 = 55.56.
- User "2" has friendships with 1, 6 and 7. Therefore, the percentage popularity for user 2 would be calculated as (3/9) * 100 = 33.33.
- User "3" has friendships with 1, 8 and 9. Therefore, the percentage popularity for user 3 would be calculated as (3/9) * 100 = 33.33.
- User "4" has friendships with 1. Therefore, the percentage popularity for user 4 would be calculated as (1/9) * 100 = 11.11.
- User "5" has friendships with 1. Therefore, the percentage popularity for user 5 would be calculated as (1/9) * 100 = 11.11.
- User "6" has friendships with 1 and 2. Therefore, the percentage popularity for user 6 would be calculated as (2/9) * 100 = 22.22.
- User "7" has friendships with 2. Therefore, the percentage popularity for user 7 would be calculated as (1/9) * 100 = 11.11.
- User "8" has friendships with 3. Therefore, the percentage popularity for user 8 would be calculated as (1/9) * 100 = 11.11.
- User "9" has friendships with 3. Therefore, the percentage popularity for user 9 would be calculated as (1/9) * 100 = 11.11.
user1 is sorted in ascending order.

Solution

Method 1 - Union & Aggregation (COUNT DISTINCT)

Intuition

Each user can appear as user1 or user2. For each user, count unique friends, divide by total users, and multiply by 100. Use UNION to get all users, and COUNT(DISTINCT ...) for friends.

Approach

Get all users from user1 and user2 columns (UNION ALL, then DISTINCT) into a user list.
For each user, count unique friends (from both user1 and user2 columns) into friend_count.
Compute percentage as (friend_count / total) * 100, rounded to 2 decimals.
Order by user1 ascending.

Complexity

⏰ Time complexity: O(N) where N is the number of rows in Friends.
🧺 Space complexity: O(U) where U is the number of unique users.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


WITH AllUsers AS (
  SELECT user1 AS user FROM Friends
  UNION
  SELECT user2 AS user FROM Friends
),
UserFriends AS (
  SELECT user1 AS user, user2 AS friend FROM Friends
  UNION ALL
  SELECT user2 AS user, user1 AS friend FROM Friends
),
FriendCounts AS (
  SELECT user, COUNT(DISTINCT friend) AS friend_count
  FROM UserFriends
  GROUP BY user
)
SELECT a.user AS user1,
       ROUND(f.friend_count / t.total * 100, 2) AS percentage_popularity
FROM AllUsers a
JOIN FriendCounts f ON a.user = f.user
JOIN (SELECT COUNT(DISTINCT user) AS total FROM AllUsers) t
ORDER BY a.user;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


WITH AllUsers AS (
  SELECT user1 AS user FROM Friends
  UNION
  SELECT user2 AS user FROM Friends
),
UserFriends AS (
  SELECT user1 AS user, user2 AS friend FROM Friends
  UNION ALL
  SELECT user2 AS user, user1 AS friend FROM Friends
),
FriendCounts AS (
  SELECT user, COUNT(DISTINCT friend) AS friend_count
  FROM UserFriends
  GROUP BY user
)
SELECT a.user AS user1,
       ROUND(f.friend_count::numeric / t.total * 100, 2) AS percentage_popularity
FROM AllUsers a
JOIN FriendCounts f ON a.user = f.user
JOIN (SELECT COUNT(DISTINCT user) AS total FROM AllUsers) t
ORDER BY a.user;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


import pandas as pd

# Assume df is the Friends DataFrame
def popularity_percentage(df: pd.DataFrame) -> pd.DataFrame:
    users = pd.unique(df[['user1', 'user2']].values.ravel())
    friends = pd.concat([
        df[['user1', 'user2']],
        df[['user2', 'user1']].rename(columns={'user2': 'user1', 'user1': 'user2'})
    ])
    friend_counts = friends.groupby('user1')['user2'].nunique()
    total = len(users)
    result = pd.DataFrame({'user1': friend_counts.index, 'percentage_popularity': (friend_counts / total * 100).round(2)})
    return result.sort_values('user1').reset_index(drop=True)

Problem#

Examples#

Solution#

Method 1 - Union & Aggregation (COUNT DISTINCT)#

Intuition#

Approach#

Complexity#

Code#