Skip to content

Latest commit

 

History

History
13 lines (8 loc) · 843 Bytes

2.md

File metadata and controls

13 lines (8 loc) · 843 Bytes

How would you design the data structures for a very large social network like Facebook or LinkedIn? Describe how you would design an algorithm to show the connec- tion, or path, between two people (e.g., Me -> Bob -> Susan -> Jason -> You).

  1. Build the graph and run BFS.
  2. Too much data and one machine could not handle. So we can store machine ID and person ID, and search first by machine Id to find the machine and by person Id to find the person in that machine.

####Optimization :

  1. Search all my friends in the same machine just once, that is to say, if I have 10 frinds in machine n, then I get all their data once.
  2. Put people in same region/same university as a group in one machine.

######Problem : If we do BFS, we always mark a visited flag. What if there are multiple searches, how to handle?

We could use a hash table.