Saturday, October 13, 2012

Facebook has a feature which allows to discover the friends in common among two users.

 How would you implement it in a social graph?

1 comment:

  1. List firendsOfA = getNeigh(A);
    List firendsOfB = getNeigh(B);

    return firendsOfA.intersect(firendsOfB);

    Assuming that getNeigh() returns the sorted list of neighbors the function intersect() can be implemented in an efficient way.

    getNeigh() of course returns the list of friends (nodes) directly connected to the input node (the row for the node in the adjacent matrix).

    Am I missing something?