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:
|
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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
import java.util.*; public class SuggestFriendsDFS<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); } //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); } } //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) res.remove(a); return res; } public static void main(String[] args) { SuggestFriendsDFS<String> g = new SuggestFriendsDFS<>(); g.addFriendship("Ashley", "Christopher"); g.addFriendship("Ashley", "Emily"); g.addFriendship("Ashley", "Joshua"); g.addFriendship("Bart", "Lisa"); g.addFriendship("Bart", "Matthew"); g.addFriendship("Christopher", "Andrew"); g.addFriendship("Emily", "Joshua"); g.addFriendship("Jacob", "Christopher"); g.addFriendship("Jessica", "Ashley"); g.addFriendship("JorEl", "Zod"); g.addFriendship("KalEl", "JorEl"); g.addFriendship("Kyle", "Lex"); g.addFriendship("Kyle", "Zod"); g.addFriendship("Lisa", "Marge"); g.addFriendship("Matthew", "Lisa"); g.addFriendship("Michael", "Christopher"); g.addFriendship("Michael", "Joshua"); g.addFriendship("Michael", "Jessica"); g.addFriendship("Samantha", "Matthew"); g.addFriendship("Samantha", "Tyler"); g.addFriendship("Sarah", "Andrew"); g.addFriendship("Sarah", "Christopher"); g.addFriendship("Sarah", "Emily"); g.addFriendship("Tyler", "Kyle"); g.addFriendship("Stuart", "Jacob"); g.findGroups(); System.out.println(g.groups); String name = "Andrew"; System.out.println("Suggestion friends of " + name + ": " + g.getSuggestedFriends(name)); } } |
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:
|
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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
import java.util.*; public class SuggestFriendsUnionFind<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){ if (parent.get(a) == null) { parent.put(a, a); rank.put(a, 0); } if (parent.get(b) == null) { parent.put(b, b); rank.put(b, 0); } T x = Find(a); 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); } } //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); } //Time O(n*logn), Space O(n) private void findGroup() { for (T i : parent.keySet()) { T p = Find(i); groups.putIfAbsent(p, new HashSet<T>()); groups.get(p).add(i); } } //Time O(n*logn), Space O(n) public void printSets(){ if (groups.isEmpty()) findGroup(); for (Map.Entry<T,Set<T>> entry: groups.entrySet()) System.out.println(entry); } //O(n*logn), Space O(n) public Set<T> getSuggestedFriends (T a) { if (groups.isEmpty()) findGroup(); Set<T> res = new HashSet<>(); for (Set<T> t: groups.values()) { if (t.contains(a)) { res = t; break; } } if (res.size() > 0) res.remove(a); return res; } public static void main(String[] args){ SuggestFriendsUnionFind<String> g = new SuggestFriendsUnionFind<>(); g.addFriendship("Ashley", "Christopher"); g.addFriendship("Ashley", "Emily"); g.addFriendship("Ashley", "Joshua"); g.addFriendship("Bart", "Lisa"); g.addFriendship("Bart", "Matthew"); g.addFriendship("Christopher", "Andrew"); g.addFriendship("Emily", "Joshua"); g.addFriendship("Jacob", "Christopher"); g.addFriendship("Jessica", "Ashley"); g.addFriendship("JorEl", "Zod"); g.addFriendship("KalEl", "JorEl"); g.addFriendship("Kyle", "Lex"); g.addFriendship("Kyle", "Zod"); g.addFriendship("Lisa", "Marge"); g.addFriendship("Matthew", "Lisa"); g.addFriendship("Michael", "Christopher"); g.addFriendship("Michael", "Joshua"); g.addFriendship("Michael", "Jessica"); g.addFriendship("Samantha", "Matthew"); g.addFriendship("Samantha", "Tyler"); g.addFriendship("Sarah", "Andrew"); g.addFriendship("Sarah", "Christopher"); g.addFriendship("Sarah", "Emily"); g.addFriendship("Tyler", "Kyle"); g.addFriendship("Stuart", "Jacob"); g.printSets(); String name = "Andrew"; System.out.println("Suggestion friends of " + name + ": " + g.getSuggestedFriends(name)); } } |
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
