Get suggested friends (2 solutions) – DFS and Union Find

To design the data structures for social network, normally the answer is a 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 with 2 solutions: DFS and Union find in an unweighted graph.

Google Interview Question:
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.

Table of Content

Solution 1: DFS

Depth first search (DFS): In this implementation, adjacent list is used to model the unweighted undirected graph. If there are connection between two people, addFriendship (ie addEdge) is called. Then we can use dfs to traverse all reachable nodes in the graph, and build the connected groups. When using dfs, we apply memoization so that the Time complexity is Linear O(V+E).

Java

JavaScript

Python

Output:
Suggestion friends of Zoe: [Sarah, Jess]
Suggestion friends of Sam: [Chris]

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

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, JavaScript and Python.

Java

JavaScript

Python

Output:
Friends circle of Zoe: [Zoe, Sarah, Jess, Joshua]
Friends circle of Sam: [Chris, Amy, Sam]

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


Download

Download GetSuggestedFriend.java
Download GetSuggestFriends.js
Download GetSuggestedFriend.py
Java Coding Interview Pocket Book (2nd Edition)

Comments are closed