Spreading Message To Everyone In A Social Network
Application of Topological Sort, Strongly Connected Components and Tarjan's Algorithm
-
Algorithms and Data Structures: TheAlgorist.com
-
System Design: DistributedComputing.dev
-
Low Level Design: LowLevelDesign.io
-
Frontend Engineering: FrontendEngineering.io
Problem Statement: In a certain social network, when someone gets a message he/she sends that message to all of his/her followers.
Now, I am considering to spread a promotion message across all people in that social network.
Your task is to find the minimum number of people to reach out (for example, who doesn't follow anyone etc) so that my promotion message spreads out across entire social network.
We need to consider loops like, if A follows B, B follows C, C follows D, D follows A (A -> B -> C -> D -> A) then reaching only one of them is sufficient to spread your message.
Input: List of followers for every user in the social network:
1: 3, 4 2: 3: 1 4: 3
Here, user 1 has user 3 and 4 as followers. User 2 has no followers. User 3 has user 1 s follower. User has user 3 as follower.
Output: Minimal list of people to be reached to spread out message across everyone in the network.
Tag(s): #facebook_interview
Solution:
Algorithm:
This is a Premium content.
Please subscribe to the Algorithms course to access the detailed Algorithm discussion.
Working Solution:
Java code:This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Don't forget to take a look at other interesting Graph Problems:
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
