0

I recently encountered this question in an interview and did pretty bad at it. 

Setup:
Assume primitive Facebook. FB has Members.

class Member {
String name;
String email;
List<Member> friends;
}

Question: Code printSocialGraph(Member m). Direct friends of m are Level 1 friends. Friends of friends are level 2 friends.....and so on Print level 1 friends first. Then print level 2 friends....and so on

void printSocialGraph (Member m){
//Your code here
}

I tried to maintain a queue for storing the friends at each level but I did not get it very far. Any idea how we could go about solving it with all error checking conditions ?

noobcoder
  • 11,983
  • 10
  • 39
  • 62
  • 2
    http://en.wikipedia.org/wiki/Breadth-first_search – SLaks Jan 05 '14 at 01:49
  • Any complete implementations that would be a learning for the future interviews ? – noobcoder Jan 05 '14 at 01:52
  • 3
    @noobcoder You have pretty good username. Don't go to work! ;) – Adam Stelmaszczyk Jan 05 '14 at 01:52
  • @AdamStelmaszczyk It is still not better than your picture ;) – noobcoder Jan 05 '14 at 01:53
  • 1
    Either BFS or DFS will work. If you don't know how to implement BFS/DFS you have a bigger problem than this question. Further, memorizing answers will not help you pass job interviews. I'm not writing it to annoy you - that's a friendly advice (I've been through several job interviews as well in the last few months). – Nir Alfasi Jan 05 '14 at 01:59
  • @alfasin: no offence taken. I pretty much understand your advice. However, I am not trying to memorize the answer but trying to understand the concept so I can try implementing it too. – noobcoder Jan 05 '14 at 02:01
  • 1
    @noobcoder if that's the case, do some reading and make sure you know how to implement BFS/DFS - those are two basic algorithms which you should be able implement easily when you're interviewing. Once you've mastered BFS and DFS it'll be very easy for you to solve this question . Trust me on this one! – Nir Alfasi Jan 05 '14 at 02:03
  • @alfasin: Do you mind if I add you on Linkedin ? I liked your blog very much and would like to be in touch, if you don't mind – noobcoder Jan 05 '14 at 02:07
  • You can find **many** of implementations of BFS around, most using a structure very similar to the one you provided. See [this answer](http://stackoverflow.com/a/20902375/1711796) if you want to separate the friends into levels. – Bernhard Barker Jan 05 '14 at 02:15

1 Answers1

6

Just add new children at the end of the search queue until there are no more. Since the graph can contain cycles, you must also break these with a "visited" set.

void printSocialGraph (Member m) {
  Queue<Member> queue = new LinkedList<>();
  Set<Member> visited = new HashSet<>();
  queue.add(m);
  while (!queue.isEmpty()) {
    Member member = queue.getFirst();
    if (!visited.contains(member)) {
      visited.add(member);
      System.out.println(member.name + ' ' + member.email);
      if (member.friends != null) {
        queue.addAll(member.friends);
      }  
    }
  }   
}

If you also need to print out which level a member is on, then the simplest is probably to use two queues: one for the current level and another for the next, swapping queues between.

Gene
  • 46,253
  • 4
  • 58
  • 96
  • 1
    Even though I look forward to an enhanced solution which prints the levels as well, I think you should select this as a valid answer to the interview question. Considering that in actual production, you would want to limit the number of iterations or levels, I would like to provide a solution of my own as an alternative but I can't because such an interesting question has been shot down by trigger happy moderators. – RHT Apr 16 '14 at 15:17