Requirements describe
In the recommendation business scenario, there will be some applications recommended by friends, such as QQ friend recommendation now. So in earlier years, the algorithm question about mutual friends is realized by MR, which is also a big factory interview question. Yesterday, I talked to my friends about this topic, how to use SQL to achieve? So let’s look at the description of this problem, and the extension problem. Problem Description: For example, a social networking company wants to implement a function to recommend friends to users. For example, Xiao Ming and Xiao Zhang are not friends, but they have a mutual friend, Xiao Wang, so we can recommend Xiao Ming to Xiao Zhang and Xiao Zhang to recommend Xiao Ming. When making recommendations, the company will decide the order of recommendation based on the number of mutual friends. We now have the following table structure, assuming the data is as follows:
| User user | Friend_list |
|---|---|
| Xiao Ming | Xiao Zhang, Xiao Li and Xiao Sun |
| Xiao zhang, | Xiao Ming, Xiao Li |
| Xiao li | Xiao Ming, Xiao Zhang and Xiao Sun |
| Note: | Xiao Ming, Xiao Li and Xiao Wang |
| wang | Note: |
So the demand comes in,Now we need to count the number of mutual friendsThe output contains the following three fields (the number of friends shared by user1 and user2 is mutual_friends_cnt) :
For example, if Xiao Ming has Xiao Li and Xiao Zhang among his friends, and Xiao Zhang also has Xiao Li among his friends, then Xiao Ming and Xiao Zhang have xiao Li as their mutual friend.
| user1 | user2 | mutual_friends_cnt |
|---|---|---|
| Xiao Ming | Xiao zhang, | 1 |
| Xiao Ming | Xiao li | 2 |
| Xiao Ming | Note: | 1 |
| Xiao zhang, | Xiao Ming | 1 |
| Xiao zhang, | Xiao li | 1 |
| Xiao li | Xiao Ming | 2 |
| Xiao li | Xiao zhang, | 1 |
| Xiao li | Note: | 1 |
| Note: | Xiao Ming | 1 |
| Note: | Xiao li | 1 |
| Extension problem |
||
| So based on the above requirements, let’s extend it again,Count the number of common friends among non-friends, that is, if Xiao Ming and Xiao Sun are good friends, and Xiao Sun has Wang among his good friends, and Xiao Wang and Xiao Ming are not good friends, then the mutual friend between Xiao Wang and Xiao Ming is Xiao Sun. So when recommending, they will recommend Xiao Wang to Xiao Ming, and Xiao Ming to Xiao Wang. | ||
 |
||
| The final result is shown as: |
||
| User user1 | User user2 | Number of mutual friends |
| ——— | ——— | ———- |
| Xiao Ming | wang | 1 |
| Xiao zhang, | Note: | 2 |
| Xiao li | wang | 1 |
| Note: | Xiao zhang, | 2 |
| wang | Xiao Ming | 1 |
| wang | Xiao li | 1 |
Analysis of the
This analysis process may not be the optimal solution. If readers have good ideas, they can enter the group discussion according to the two-dimensional code at the bottom.
1. Analyze the number of common friends between friends
1.1. Based on the existing table structure, it is necessary to find the corresponding friend list B_list of each friend iteratively according to the friend list A_list of each user
1.2. Compare the elements in B_list and A_list of each friend to find the intersection of the two lists.
See the following figure for example steps:
2. Analyze the number of common friends among non-friends
2.1. Based on the existing table structure, it is necessary to find the corresponding friend list B_list of each friend iteratively according to the friend list A_list of each user
2.2. Compare the elements in B_list and A_list of each friend to find the elements that are not in A_list
2.3. Combine the user corresponding to friend list A_list and the user not in A_list but in B_list to get the list of common friends between two unrelated users
See the following figure for example steps:
implementation
1. Analyze the number of common friends between friends
2. Analyze the number of common friends among non-friends
