Calculate your Social Graph Klout Score

Problem Statement

Write the algorithm that LinkedIn.com uses to tell you how many professionals you have access to, at up to three nodes away in your social network. For example, you might have 100 friends, 10,000 friends of friends and 1,000,000 friends of friends of friends. The answer is less than 1,010,100 considering how a friend could also be a friend of a friend. Keep in mind that anybody might be anybody else's friend.

Evaluation

• The idea to correctly use some kind of a recursive tree-traversal algorithm (25%)


• Handling graph cycles and writing a program that actually terminates (25%)


• The idea to use breadth-first traversal to avoid painting intermediate nodes as leafs (25%)


• The idea to cache (index) every recursive result in a hash-table to optimize requests from other users (25%)

References

Chris is one of the first 4 engineers at Lionside, a Bay Area gaming startup. He asked me this question during an interview.