Design Social Network
How would you design the data structures for a very large social network like Face book or LinkedIn?
Describe how you would design an algorithm to show the shortest path between two people (e.g., Me -> Bob -> Susan -> Jason -> You).
Step 1: Simplify the problem - Start from simple case
First, let's forget that we're dealing with millions of users. Design this for the simple case.
We can construct a graph by treating each person as a node and letting an edge between two nodes indicate that the two users are friends.
To find the path between two people, I could start with one person and do a simple breadth-first search.
Why don't we use DFS?
- It won't find the shortest path
- It's not efficient
Alternatively, I could do what's called a bidirectional breadth-first search. This means doing two breadth-first searches, one from the source and one from the destination. When the searches collide, we know we've found a path.