The questions are still open and you can try them here.
The question was about finding the person who invited the largest number of users through TransferWise's invite program. This question can be generalized to finding the largest tree in an acyclic unidirectional disconnected graph. If you don't remember it, you can also find it below.
There are multiple ways to solve the first question including:
- Finding the root nodes of the trees by finding the nodes without parents
- Counting the number of nodes added to each tree while building the trees
- Using a disjoint-set data structure
- Using dynamic programming to keep track of how many descendants each node has
We will describe the first way (finding the root nodes), since it is one of the easiest ways of solving the problem.
The first thing we want to do is finding the nodes without parents. To do so, we can build two sets: the set of inviting users and the set of invited users. The difference between the set of inviting users and the set of invited users sets are the root nodes of our trees.
We will also need to save the input into a map to keep track of who invited who. The key of the map will be the inviting user and the value will be the set of invited users. In Java, it would be a Map<Integer, Set>.
For each of the root nodes of the trees, we can now apply a Breadth-First Search or Depth-First search to count the number of descendants in each tree. The tree with the largest number of descendants is our output.
In pseudo-code, it would look like this:
/*
For each input,
add the first value to the invited user set
add the second value to the inviting user set
add the edge from the second value to the first value into the edge map (Map<Integer, Set<Integer>>)
Compute the difference between the inviting user set and the invited user set and save it into an array of root nodes
For each root node,
apply BFS or DFS to count the number of descendants
save the result if it is the best result we have so far
Output the result
*/
To celebrate its 7-year anniversary, TransferWise would like to reward the customer who had the largest impact through the invite program.
We want to find which customer has invited the largest number of users, including indirectly invited users. For example, if user A invites user B, user B invites user C and D and user C invites user E, then the number of invited users by A is 4 (B, C, D and E).
We guarantee that the same user cannot be invited by multiple users, that there is always a unique winner and that there is no loop in the invites. For example, if user A invites user B and user B invites user C, user A cannot be invited by user C.
The first line is the number of invitations N. N lines follow. Each of the N lines contains two numbers separated by a space:
The first number, I, is the id of the invited user the second number, J, is the id of the inviting user.
1 <= N <= 1000000
1 <= I <= 10000000
1 <= J <= 10000000
We guarantee that the same user cannot be invited by multiple users, that there is always a unique winner and that there is no loop in the invites. For example, if user A invites user B and user B invites user C, user A cannot be invited by user C.
The expected output should contain two lines. The first line is the id of the user who invited the largest number of users. The second line is the number of invited users.
5
2 1
3 2
4 2
5 4
9 8
1
4
User 1 has invited 4 users indirectly: users 2, 3, 4 and 5.