FB 08/2016 Phone interview Find 2nd degree connections


  • 1
    D

    Find 2nd degree connections ( friends’ friends), output these 2nd degree connections ranked by number of common friends (i.e 1st degree connections) with you, (example: if 2nd degree connection A has 10 common friends (1st degree connections) with you but 2nd degree connection B has 8 common friends (1st degree connections)with you, then A should be ranked first) Input is your connection graph represented by undirected graph nodes, output is list of 2nd degree connections represented by graph nodes

    public List<UndirectedGraphNode> findSecDegreeConnections(UndirectedGraphNode myself){

    }


  • 7
    N

    Could I just get the list of friends from myself and keep a HashMap count of friends of friend? If a friend of a friend doesn't exist in the hashmap, just add that person in, else increase the count. Then we can add all <k,v> pairs to a MaxHeap and get the top n times if we want the top n 2nd degree connections. Else, we can just add all <k,v> pairs to an array list and sort it based on value.


  • 1
    G

    @daniel.w.1
    Good way should be to get my 1st level friends in a set
    Then get a list of 2nd level firends
    Get thir kids (3rd level ) put them in a list of hashmaps with key= friend value =connections

    Run this list of hasmaps against a set created in step 1 and find the winner by using some sorting logic


  • 3
    H

    I think you can just apply BFS for two layers and for the node of second layer(2nd degree friends), count the number of 1st degree friends who expand to it. Then just sort the 2nd layer.


  • 2
    S

    Based on @houliang's suggestion:
    Create a set of first degree friends (nodes) called myFriends. Do BFS starting from mySelf and stop when you have 2nd degree nodes in q. Then count common friends by checking if myFriends contains friends of 2nd degree nodes. Once you have the counts bucket sort the nodes and add them to res in descending order.

        public List<UndirectedGraphNode> findSecDegreeConnections(UndirectedGraphNode myself){
            List<UndirectedGraphNode> res = new ArrayList<UndirectedGraphNode>();
            
            Set<UndirectedGraphNode> myFriends = new HashSet<UndirectedGraphNode>();
            for (UndirectedGraphNode friend : myself.neighbors) {
                myFriends.add(friend);
            }
            
            Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
            Set<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
            q.add(myself);
            visited.add(myself);
            int level = 0;
            while (!q.isEmpty() && level < 2) {
                level++;
                int size = q.size();
                while (size-- > 0) {
                    UndirectedGraphNode node = q.poll();
                    for (UndirectedGraphNode w : node.neighbors) {
                        if (!visited.contains(w)) {
                            q.offer(w);
                            visited.add(w);
                        }
                    }
                }
            }
            Map<UndirectedGraphNode, Integer> counts = new HashMap<UndirectedGraphNode, Integer>();
            for (UndirectedGraphNode fof : q) {
                int count = 0;
                for (UndirectedGraphNode friend : fof.neighbors) {
                    if (myFriends.contains(friend)) count++;
                }
                counts.put(fof, count);
            }
            Map<Integer, List<UndirectedGraphNode>> bucket = new HashMap<Integer, List<UndirectedGraphNode>>();
            for (UndirectedGraphNode n : counts.keySet()) {
                int count = counts.get(n);
                if (!bucket.containsKey(count)) bucket.put(count, new ArrayList<UndirectedGraphNode>());
                bucket.get(count).add(n);
            }
            for (int i = q.size(); i > 0; i--) {
                if (bucket.containsKey(i)) res.addAll(bucket.get(i));
            }
            return res;
        }
    

  • 0
    Z

    Is there anyone post a python version solution. Thanks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.