Calculate your Social Graph Klout Score

Write the algorithm that LinkedIn.com uses to tell you how many professionals you have access to.

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, one of the first 4 engineers at Lionside, a Bay Area gaming startup, asked me this during an interview

Recommended reading

  • Graph Cycle Detection

    You have a directed connected graph. Write an algorithm that detects any cycle, if one exists, and returns a list of its nodes.

  • Circular Linked List Detection

    A linked list is given. Write an algorithm that detects whether it's a singly linked list or a circularly linked list.

  • Breadth First Tree Traversal

    Write an algorithm that takes a tree data structure and writes out all the elements in a breadth-first traversal order.

  • Tree In-Order Traversal to Next Node

    Given a node in a binary tree, implement the algorithm for finding its next in-order node in the containing tree.

Author
Amin Ariana
Published
September 2010