All geek questions in one place

N degree separation problm interview

Recently, an interesting question has been asked.

  • You have 1 million users.
  • Each user has 1 thousand friends.
  • Your system should effectively answer the question Do I know him? for each pair of users. The user "knows" the other if he is connected through 6 levels of friends.

eg. A is a friend of B , B is a friend of C , C is a friend of D , D is a friend of E , E is a friend of F , so we can say that A knows F

Obviously, you cannot effectively solve this problem using BFS or other standard moving techniques. The question is how to save this data structure in the database and how to quickly perform this search.

I did not find the answer, maybe someone has an idea?

+5
source share
2 answers

What happened to BFS?

Complete the three BFS steps from the first node, flagging available users with flag 1. This requires 10 ^ 9 steps.

Perform the three BFS steps from the second node, noting the accessibility of users by flag 2. If we meet mark 1 - bingo.

+6
source

How to store data as 1 million x 1 million matrix A, where A [i] [j] is the minimum number of steps for access from user i to user j. Then you can request it almost instantly. However, updating is more expensive.

0
source

Source: https://habr.com/ru/post/1271454/

More articles:


All Articles