Get suggested friends is one of a coding question in social network applications. The data structures for social network is usually a graph. In the graph, you can use depth first search(DFS) or breadth first search(BFS) to find the connections between people. Alternatively, you 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.
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
Many times, adjacent list is used to model the unweighted undirected graph. If there are connection between two people, addFriendship (ie addEdge) is called. Then you can use dfs to traverse all reachable nodes in the graph, and build the connected groups. When using dfs, apply memoization so that the time complexity is Linear O(V+E).
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | import java.util.*; public class GetSuggestedFriends<T> { private HashMap<T, ArrayList<T>> adj = new HashMap<>(); //graph private List<Set<T>> groups = new ArrayList<>(); //Time O(1), Space O(1) public void addFriendship(T src, T dest) { adj.putIfAbsent(src, new ArrayList<T>()); adj.get(src).add(dest); adj.putIfAbsent(dest, new ArrayList<T>()); adj.get(dest).add(src); } //Find group by connections, DFS wrapper, Time O(V+E), Space O(V) //V is total number of people, E is number of connections private void findGroups() { Map<T, Boolean> visited = new HashMap<>(); for (T t: adj.keySet()) visited.put(t, false); for (T t:adj.keySet()) { if (!visited.get(t)) { Set<T> group = new HashSet<>(); dfs(t, visited, group); groups.add(group); } } } //DFS + memoization, Time O(V+E), Space O(V) private void dfs(T v, Map<T, Boolean> visited, Set<T> group ) { visited.put(v,true); group.add(v); for (T x : adj.get(v)) { if (!visited.get(x)) dfs(x, visited, group); } } //Find suggest friends, Time O(V+E), Space O(V) public Set<T> getSuggestedFriends (T a) { if (groups.isEmpty()) findGroups(); Set<T> res = new HashSet<>(); for (Set<T> t : groups) { if (t.contains(a)) { res = t; break; } } if (res.size() > 0) //remove himself from result res.remove(a); for (T t : adj.get(a)) //remove already known friends from result res.remove(t); return res; } public static void main(String[] args) { GetSuggestedFriends<String> g = new GetSuggestedFriends<>(); g.addFriendship("Amy", "Chris"); g.addFriendship("Sarah", "Joshua"); g.addFriendship("Joshua", "Zoe"); g.addFriendship("Sarah", "Jess"); g.addFriendship("Amy", "Sam"); String name = "Zoe"; System.out.println("Suggestion friends of " + name + ": " + g.getSuggestedFriends(name)); name = "Sam"; System.out.println("Suggestion friends of " + name + ": " + g.getSuggestedFriends(name)); } } |
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | class GetSuggestFriends { //Constructor, Time O(1) Space O(1) constructor() { this.adj = new Map(); this.groups = new Set(); } //Add edges, Time O(1) Space O(1) addFriendship(a, b) { if (this.adj.get(a) == null) this.adj.set(a, new Array()); if (this.adj.get(b) == null) this.adj.set(b, new Array()); this.adj.get(a).push(b); this.adj.get(b).push(a); } //Find group by connections, DFS wrapper, //Time O(V+E), Space O(V), V is total number of people, E is number of connections findGroups() { var visited = new Map(); for (let entry of this.adj.entries()) { let t = entry[0] if (visited.get(t) == null) { let group = new Set(); this.dfs(t, visited, group); this.groups.add(group); } } } //DFS + memoization, Time O(V+E), Space O(V) dfs(v, visited, group) { visited.set(v, true); group.add(v); for (let ne of this.adj.get(v)) { if (visited.get(ne) == null) this.dfs(ne, visited, group); } } //Find suggest friends, Time O(V+E), Space O(V) getSuggestedFriends (a) { if (this.groups.size == 0) this.findGroups(); var res = new Set(); for (let t of this.groups) { if (t.has(a)) { res = t; break; } } if (res.size > 0) //remove himself from suggested friends res.delete(a); for (let t of this.adj.get(a)) //remove already known friends from result res.delete(t); return res; } } let g = new GetSuggestFriends(); g.addFriendship("Amy", "Chris"); g.addFriendship("Sarah", "Joshua"); g.addFriendship("Joshua", "Zoe"); g.addFriendship("Sarah", "Jess"); g.addFriendship("Amy", "Sam"); var givenName = "Zoe"; console.log("Suggestion friends of " + givenName + ":"); console.log(g.getSuggestedFriends(givenName)); givenName = "Sam"; console.log("Suggestion friends of " + givenName + ":"); console.log(g.getSuggestedFriends(givenName)); |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | class GetSuggestedFriends: #Constructor, Time O(1) Space O(1) def __init__(self) : self.adj = {} self.groups = [] #Add edges, Time O(1) Space O(1) def addFriendship(self, a, b) : if a not in self.adj: self.adj[a] = [] if b not in self.adj: self.adj[b] = [] self.adj[a].append(b) self.adj[b].append(a) # Find groups by connections, DFS, Time O(V+E), Space O(V) def findGroups(self) : visited = {} for t in self.adj.keys(): if visited.get(t) == None: group = set() self.dfs(t, visited, group) self.groups.append(group) #DFS helper, Time O(V+E), Space O(V) def dfs(self, v, visited, group) : visited[v] = True group.add(v) for ne in self.adj[v] : if ne not in visited: self.dfs(ne, visited, group) #Find suggested friends, Time O(V+E), Space O(V) def getSuggestedFriends (self, a) : if len(self.groups) == 0: self.findGroups() res = set() for t in self.groups: if a in t: res = t; break if len(res) > 0: #remove himself from suggested friends res.remove(a) for t in self.adj.get(a): res.remove(t) return res g = GetSuggestedFriends() g.addFriendship("Amy", "Chris") g.addFriendship("Sarah", "Joshua") g.addFriendship("Joshua", "Zoe") g.addFriendship("Sarah", "Jess") g.addFriendship("Amy", "Sam") name = "Zoe" print("Suggestion friends of " + name + ": ") print(g.getSuggestedFriends(name)); name = "Sam" print("Suggestion friends of " + name + ": ") print(g.getSuggestedFriends(name)); |
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 is to use union and find methods in a data structure a disjointed set. Behind the scene, it is a forest structure. A disjoint set contains a set of elements that can be partitioned into subsets. All the elements in one subset has one root.
In this implementation, you use path compression and union by rank to optimize the tree’s depth. So that the time complexity is from O(n) to O(α(n)), α(n) is the inverse ackermann function. By finding which group the element belongs, you can find the suggested friends. Here are the implementation of suggested friends in Java, JavaScript and Python.
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | import java.util.*; public class GetFriendsCircule<T> { private Map<T, T> parent = new HashMap<>(); private Map<T, Integer> rank = new HashMap<>(); //stores depth private Map<T, Set<T>> groups = new HashMap<>(); //<parent, set> pair //Union by rank, Time O(logn), Space O(logn), n is total number of people public void addFriendship(T a, T b){ parent.putIfAbsent(a, a); //make set rank.putIfAbsent(a, 0); parent.putIfAbsent(b, b); //make set rank.putIfAbsent(b, 0); T x = find(a); //union T y = find(b); if (x == y) { return; } if (rank.get(x) > rank.get(y)) { parent.put(y, x); } else if (rank.get(x) < rank.get(y)) { parent.put(x, y); } else { parent.put(x, y); rank.put(y, rank.get(y) + 1); } } //Find the top rank, recursion, Time O(logn), Space O(logn) private T find(T k){ if (parent.get(k) != k) { parent.put(k, find(parent.get(k))); } return parent.get(k); } //Separate groups by parent, Time O(n*logn), Space O(n) private void findGroups() { for (T i : parent.keySet()) { T p = find(i); groups.putIfAbsent(p, new HashSet<T>()); groups.get(p).add(i); } } //Find belonging group, Time O(n*logn), Space O(n) public Set<T> getFriendsCircle (T a) { if (groups.isEmpty()) findGroups(); Set<T> res = new HashSet<>(); for (Set<T> t: groups.values()) { if (t.contains(a)) { res = t; break; } } return res; } public static void main(String[] args){ GetFriendsCircule<String> g = new GetFriendsCircule<>(); g.addFriendship("Amy", "Chris"); g.addFriendship("Sarah", "Joshua"); g.addFriendship("Joshua", "Zoe"); g.addFriendship("Sarah", "Jess"); g.addFriendship("Amy", "Sam"); String name = "Zoe"; System.out.println("Friends circle of " + name + ": " + g.getFriendsCircle(name)); name = "Sam"; System.out.println("Friends circle of " + name + ": " + g.getFriendsCircle(name)); } } |
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | class GetFriendsCircleUnionFind { //Tim O(1), Space O(1) constructor() { this.parent = new Map(); this.rank = new Map(); //stores depth this.groups = new Map(); //<parent, set> pair } //Union by rank, Time O(logn), Space O(logn), n is total number of people addFriendship(a, b){ if (this.parent.get(a) == null) { //make set this.parent.set(a, a); this.rank.set(a, 0); } if (this.parent.get(b) == null) { //make set this.parent.set(b, b); this.rank.set(b, 0); } var x = this.find(a); //union var y = this.find(b); if (x == y) { return; } if (this.rank.get(x) > this.rank.get(y)) { this.parent.set(y, x); } else if (this.rank.get(x) < this.rank.get(y)) { this.parent.set(x, y); } else { this.parent.set(x, y); this.rank.set(y, this.rank.get(y) + 1); } } //Find the top level, recursion,Time O(logn), Space O(logn) find(k){ if (this.parent.get(k) != k) { this.parent.set(k, this.find(this.parent.get(k))); } return this.parent.get(k); } //Separate group by parent, Time O(n*logn), Space O(n) findGroups() { for (let entry of this.parent.entries()) { let i = entry[0] let p = this.find(i); if (this.groups.get(p) == null) this.groups.set(p, new Set()); this.groups.get(p).add(i); } } //Find belonging group, Time O(n*logn), Space O(n) getFriendsCircle (a) { if (this.groups.size == 0) this.findGroups(); var res = new Set(); for (let entry of this.groups.entries()) { let t = entry[1] if (t.has(a)) { res = t; break; } } return res; } } let g = new GetFriendsCircleUnionFind(); g.addFriendship("Amy", "Chris"); g.addFriendship("Sarah", "Joshua"); g.addFriendship("Joshua", "Zoe"); g.addFriendship("Sarah", "Jess"); g.addFriendship("Amy", "Sam"); var givenName = "Zoe"; console.log("Friends circle of " + givenName + ":"); console.log(g.getFriendsCircle(givenName)); var givenName = "Sam"; console.log("Friends circle of " + givenName + ":"); console.log(g.getFriendsCircle(givenName)); |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | class GetFriendsCircle : def __init__(self) : self.parent = {} self.rank = {} #stores depth self.groups = {} #<parent, set> pair #Union by rank, Time O(logn), Space O(logn), n is total number of people def addFriendship(self, a, b): if self.parent.get(a) == None : #make set self.parent[a] = a self.rank[a] = 0 if self.parent.get(b) == None : #make set self.parent[b] = b self.rank[b] = 0 x = self.find(a) #union y = self.find(b) if x == y : return if self.rank.get(x) > self.rank.get(y) : self.parent[y] = x elif (self.rank.get(x) < self.rank.get(y)) : self.parent[x] = y else : self.parent[x] = y self.rank[y]= self.rank.get(y) + 1 #Find the top rank, recursion, Time O(logn), Space O(logn) def find(self, k): if self.parent.get(k) != k: self.parent[k] = self.find(self.parent.get(k)) return self.parent.get(k) #Separte group by parent, Time O(n*logn), Space O(n) def findGroups(self) : for i in self.parent.keys(): p = self.find(i) if self.groups.get(p) == None: self.groups[p] = set() self.groups.get(p).add(i); #Find belonging group, Time O(n*logn), Space O(n) def getFriendsCircle (self, a) : if len(self.groups) == 0: self.findGroups() res = set() for t in self.groups.values(): if a in t: res = t break return res g = GetFriendsCircle() g.addFriendship("Amy", "Chris") g.addFriendship("Sarah", "Joshua") g.addFriendship("Joshua", "Zoe") g.addFriendship("Sarah", "Jess") g.addFriendship("Chris", "Sam") name = "Zoe" print("Friends circle of " + name + ": ") print(g.getFriendsCircle(name)); name = "Sam" print("Friends circle of " + name + ": ") print(g.getFriendsCircle(name)); |
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)
What are the algorithms to find connections between friends in social networks?
Depth first search(DFS), breadth first search(BFS), union find/disjoint set.
