Interview Question: Data structure for a large social network [closed]

Question

Another interesting interview question that I stumbled upon -

Design the data structures for a very large social network (Facebook, LinkedIn, etc)?

Also, design an algorithm to show the connection, or path, between two people (e.g. me->foo->bar->rob->ron)

Answer 1

I would probably consider an undirected graph of some variety, probably stored as a sparse adjacency matrix. As far as finding the shortest path between two people, since the cost of edges is uniform, I would consider going with a bidirectional search.

Basically, go out in concentric circles centered around each person, where each circle is the person himself, then his friends, then his friends-of-friends, etc., at each step testing if there is any person in both circles. Follow the path from the first person you find inward toward the center of each person, and you've found the shortest path.

You could try other shortest-path algorithms, but in general, most shortest-path algorithms only give you the distance and not the actual path.

Answer 2

You could use a graph database like neo4j