Menu
A was asked an interesting question on an interview lately.
Do I know him? question for each couple of users. A user "knows" another one, if they are connected through 6 levels of friends.E.g. A is friend of B, B is a friend of C, C is 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 can't to solve this problem efficiently using BFS or other standard traversing technic. The question is - how to store this data structure in DB and how to quickly perform this search.
726
The fastest O(n) algorithm for six-degrees of separation would probably be finding the sets of all users 1-step away from UserX and UserY, and finding the intersection of those two sets. If none, then add the users 2-steps from UserX and intersect; then add users 2-steps from UserY and intersect; etc. up to 3.
6 Degrees of Separation Example You start with a random actor, then name another actor from one of her movies, then name an actor who has been in a movie with that second actor, and continue until you get to someone who's shared the screen with Bacon — trying to make the connection in six steps or less.
Six degrees of separation is the theory that any person on the planet can be connected to any other person on the planet through a chain of acquaintances that has no more than five intermediaries.
The idea that anyone on the planet is connected to any other person through a chain of acquaintances with no more than five links (six degrees) has been referred to as "six degrees of separation" as well as the "small world" phenomenon.
What's wrong with BFS?
Execute three steps of BFS from the first node, marking accessible users by flag 1. It requires 10^9 steps.
Execute three steps of BFS from the second node, marking accessible users by flag 2. If we meet mark 1 - bingo.
168
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
