You Know Invitation Based System. on Google+, Gmail,Yahoo,Facebook etc...users can add their friends by emailing a . We want to determine a user’s influence on the system by determining how many users he is responsible for. A user’s influence is calculated by giving him 1 point for every user he’s added in addition to the sum of the influence scores of each user that he’s added.
Example: User 0 adds User 1 and User 2. User 1 adds User 3.
User 0’s influence score is 3. (He added two users and one of them added added a third user.)
User 1's is 1.
User 2’s is 0.
User 3’s is 0.
P.S.:One of The Question Asked By Google M.V. From Me. :)
User 1's is 1.
User 2’s is 0.
User 3’s is 0.
P.S.:One of The Question Asked By Google M.V. From Me. :)
The above scenario is represented by the following input file. Line i is user ID i and position j within the line is marked with an X if user ID iadded user ID j. Both row and column indicies are 0-based:
OXXO
OOOX
OOOO
OOOO
2 comments :
The problem is similar to find out top 3 rank -nodes in an acyclic Graph , where rank is defined as no of successor of that node [Successor of a graph is defined as a node is reachable from that Node ]
The Algorithms as follows:
1. Find out topological sort to find dependency btwn nodes.-->O(n)
. find rank of each node in that DAG --> UsE DP O(n2)
3. find out top 3 rank nodes in all nodes==>O(n)
Note : Step2 and 3 can be combined..
Comments
--Dipankar
The problem is similar to find out top 3 rank -nodes in an acyclic Graph , where rank is defined as no of successor of that node [Successor of a graph is defined as a node is reachable from that Node ]
The Algorithms as follows:
1. Find out topological sort to find dependency btwn nodes.-->O(n)
. find rank of each node in that DAG --> UsE DP O(n2)
3. find out top 3 rank nodes in all nodes==>O(n)
Note : Step2 and 3 can be combined..
Comments
--Dipankar
Post a Comment