Get suggested friends (2 solutions) – code

When you are asked to design the data structures for social network, normally the answer is graph. In the graph, We can use DFS or BFS to find the connections between people. Alternatively, we can also use Union find to group the people by their connections. Here we provide solutions to get suggested friends in Java with 2 solutions: DFS and Union find.
DFS has been explained in the post of Depth first search and adjacent matrix. First we add the people in a graph. In this implementation, adjacent list is used to model the graph. If there are connection between two people, addFriendship (ie addEdge) is called. Then we can use dfs to traverse all nodes in the graph, and build the connected group. When using dfs, we apply memoization so that the Time complexity is Linear O(V+E).

Union find has been explained in the post of Find Least common set with union find . It is the solution to build disjointed sets. Behind the scene, it is a tree structure. All the elements in one group has one root. In this implementation, we use “union by rank” to optimize the tree’s depth from O(n) to O(logn). By finding which group the element belongs, we can find the suggested friends. Here are the implementation of suggested friends in Java.

Google Interview Question (CareerCup):
You are in charge of designing a small, in-memory social network, with the basic functionality of adding friendship between two people via an AddFriendship function, and a GetSuggestedFriends function for a particular user in the network. The criteria is to pick someone with whom the given user has the most number of friends in common.
Start by discussing the most suitable data structure, and implement all the objects and functions.

Solution 1: DFS


Java Code:

Output:
[[Emily, Christopher, Sarah, Stuart, Andrew, Michael, Ashley, Jessica, Joshua, Jacob], [JorEl, KalEl, Kyle, Marge, Matthew, Samantha, Tyler, Lex, Zod, Bart, Lisa]]
Suggestion friends of Andrew: [Emily, Christopher, Sarah, Stuart, Michael, Ashley, Jessica, Joshua, Jacob]

O Notation:
Time complexity: O(V+E), V is total number of people, E is number of connections
Space complexity: O(V)

Solution 2: Union find


Java Code:

Output:
Christopher=[Emily, Christopher, Sarah, Stuart, Andrew, Michael, Ashley, Jessica, Joshua, Jacob]
Zod=[JorEl, KalEl, Kyle, Marge, Matthew, Samantha, Tyler, Zod, Bart, Lex, Lisa]
Suggestion friends of Andrew: [Emily, Christopher, Sarah, Stuart, Michael, Ashley, Jessica, Joshua, Jacob]

O Notation:
Time complexity: O(n*logn), n is total number of people
Space complexity: O(n)


Actionable:
Download SuggestedFriends.zip
Depth first search and adjacent matrix
Find Least common set with union find

Comments are closed