Facebook Interview Question
SDE1sCountry: United States
Is the question to find *immediate* friends only? Then its trivial.
private static List<Integer> getFriends(Iterator<List<Integer>> relations, int id) {
List<Integer> friends = new ArrayList<>();
while(relations.hasNext()) {
List<Integer> relation = relations.next();
if (relation.get(0) == id)
friends.add(relation.get(1));
else if (relation.get(1) == id)
friends.add(relation.get(0));
}
return friends;
}
}
However, if the problem is to include friends-of-friends as well, then we need to store all the friendships as they arrive
public class FriendshipStream {
public static void main(String[] args) {
List<List<Integer>> relations = new ArrayList<>();
relations.add(Arrays.asList(1, 2));
relations.add(Arrays.asList(2, 3));
relations.add(Arrays.asList(1, 3));
relations.add(Arrays.asList(2, 4));
relations.add(Arrays.asList(5, 6));
printFriendCircle(relations.iterator(), 1);
}
private static void printFriendCircle(Iterator<List<Integer>> relations, int id) {
Map<Integer, List<Integer>> friendships = buildMap(relations);
List<Integer> allFriends = findAllFriends(friendships, id);
for(int friend : allFriends)
System.out.println(friend);
}
private static Map<Integer, List<Integer>> buildMap(Iterator<List<Integer>> relations) {
Map<Integer, List<Integer>> friendships = new HashMap<>();
while(relations.hasNext()) {
List<Integer> relation = relations.next();
addFriendship(friendships, relation.get(0), relation.get(1));
addFriendship(friendships, relation.get(1), relation.get(0));
}
return friendships;
}
private static void addFriendship(Map<Integer, List<Integer>> friendships, int a, int b) {
List<Integer> friends = friendships.computeIfAbsent(a, k -> new ArrayList<>());
friends.add(b);
}
private static List<Integer> findAllFriends(Map<Integer, List<Integer>> friendships, int id) {
List<Integer> friends = new ArrayList<>();
List<Integer> next = Collections.singletonList(id);
while(!next.isEmpty()) {
List<Integer> curr = new ArrayList<>();
for(int friend : next) {
List<Integer> friendsOfFriend = friendships.getOrDefault(friend, Collections.emptyList());
for(int fOfF : friendsOfFriend)
if (!friends.contains(fOfF) && fOfF != id)
curr.add(fOfF);
}
friends.addAll(curr);
next = curr;
}
return friends;
}
}
To show friends or friends, build Graph with edges between relations.
Get the node with the id to be searched and traverse children. Mark nodes as 'traversed' once printed to prevent infinite loop.
Here is the code:
- krupen.ghetiya July 22, 2017