InternDoor

Friends of friends

Mediumdesign · union-find · graphsDesign a class

Reported in interviews at (where)

There are n people, numbered 1 to n. Friendship spreads: a friend of a friend, at any distance, is in the same group. Build FriendGroups to keep track of the groups.

FriendGroups(n) starts with every person in a group of their own.

befriend(a, b) makes a and b friends. If they were already in one group, nothing changes. a and b may be the same person.

total(a) returns how many people are in a's group, a included.

together(a, b) returns whether a and b are in the same group.

groups() returns how many groups there are.

Walking the friendships for every call is too slow for the largest tests: each call should take close to O(1) time.

Example 1
Input
["FriendGroups","befriend","befriend","total","together","groups","befriend","together","total","total","groups"]
[[5],[1,2],[4,5],[2],[1,4],[],[2,4],[1,5],[3],[5],[]]
Output
[null,null,null,2,false,3,null,true,1,4,2]

After the first two friendships the groups are {1, 2}, {4, 5} and {3}. Making 2 and 4 friends joins the first two: 1 and 5 are now friends of friends.

Example 2
Input
["FriendGroups","befriend","groups","befriend","befriend","groups","total"]
[[2],[1,1],[],[2,1],[1,2],[],[1]]
Output
[null,null,2,null,null,1,2]

Befriending yourself, or someone already in your group, changes nothing.

Limits

  • 1 <= n <= 100000
  • 1 <= a, b <= n
  • at most 20000 calls after the constructor

Hints

Hint 1

Give each group one leader. Each person points towards their leader; two people are together when they reach the same leader.

Hint 2

When joining two groups, point the smaller group's leader at the larger one's, and keep the size at the leader. Shortening the paths as you follow them keeps every call close to O(1).

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.