Problem

Table: Follow

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| followee    | varchar |
| follower    | varchar |
+-------------+---------+
(followee, follower) is the primary key (combination of columns with unique values) for this table.
Each row of this table indicates that the user follower follows the user followee on a social network.
There will not be a user following themself.

A second-degree follower is a user who:

  • follows at least one user, and
  • is followed by at least one user.

Write a solution to report the second-degree users and the number of their followers.

Return the result table ordered by follower in alphabetical 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

Input: 
Follow table:
+----------+----------+
| followee | follower |
+----------+----------+
| Alice    | Bob      |
| Bob      | Cena     |
| Bob      | Donald   |
| Donald   | Edward   |
+----------+----------+
Output: 
+----------+-----+
| follower | num |
+----------+-----+
| Bob      | 2   |
| Donald   | 1   |
+----------+-----+
Explanation: 
User Bob has 2 followers. Bob is a second-degree follower because he follows Alice, so we include him in the result table.
User Donald has 1 follower. Donald is a second-degree follower because he follows Bob, so we include him in the result table.
User Alice has 1 follower. Alice is not a second-degree follower because she does not follow anyone, so we don not include her in the result table.

Solution

Method 1 - Self Join and Grouping

Intuition

A second-degree follower is someone who both follows someone and is followed by someone. We can find all users who are followers (appear in the follower column) and are also followees (appear in the followee column), then count their followers.

Approach

  1. Find all users who are both a follower and a followee.
  2. For each such user, count how many times they appear as a followee (i.e., how many followers they have).
  3. Return the result ordered by follower name.

Code

1
2
3
4
5

SELECT follower, COUNT(*) AS num
FROM Follow
WHERE follower IN (SELECT DISTINCT followee FROM Follow)
GROUP BY follower
ORDER BY follower ASC;
1
2
3
4
5

SELECT follower, COUNT(*) AS num
FROM Follow
WHERE follower IN (SELECT DISTINCT followee FROM Follow)
GROUP BY follower
ORDER BY follower ASC;
1
2
3
4
5
6
7
8
9

# Follow is a pandas DataFrame
import pandas as pd
def second_degree_follower(Follow):
    followees = set(Follow['followee'])
    mask = Follow['follower'].isin(followees)
    res = Follow[mask].groupby('follower').size().reset_index(name='num')
    res = res.sort_values('follower').reset_index(drop=True)
    return res
# result = second_degree_follower(Follow)

Complexity

  • ⏰ Time complexity: O(N) (N = number of rows in Follow)
  • 🧺 Space complexity: O(U) (U = number of unique users)