Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Social graph - system design interview
This editor is synced in real time with your peer.
Use it to share thoughts and resources, such as:
- Features scope
- API design
- Pseudo code for specific components
- Data model/schema
- Back-of-the-envelope calculations
- Reference links
- Link to whiteboard or diagram such as https://sketchboard.me/new
Good luck!
Features: add freind
LOok up freind's freind
all you freind
termniate
Search - network, public figure - brute force
Closest_step
API design:
AddFriend
Terminate
GetAllFreinds
FindPathGivenTwoFreind()
Friend-UID , name,
FindPath - BFs -> shortest path - BFS - 200 social graph -> 200 -> friend - mark visit-> 200^5 = 10^10 -> billion
10% populatuion - 5 billion on this graph -
# source node (ID, name)
# friends (ID, name)
# Bob -> Andrew -> Dylan
search(Bob) -> [Bob -> Andrew -> Dylan]
search service -> all search queust -> Messge queue -> More than service, parsing, language, search search -> cache -> datbase / NO SLQ / oj
cache - shard -> consistent hashing -
single point failure - replication -> cache server ->
Static - CDN
CAP - reading - consistent -> latest / high availablity/ less consitent. partition tolerant ->
100 -> break new relationsip -> circle
search -> read service/ write service -> Message queue
Key - value -> a person with all friend
Facebok DAO -> Look aside - write through - make consistent - client
cache serve -> load datastore -> cache - DAO - memcache -
a user -> put level 3 freinds -> preprocess - level -> a node 200^3 = 800000 friend -> space sacrifice -> short -> search source/ destination -> optimize
Data model/ schema
Facebook - a freidn take picture at californai bridge - Alice likes the photo -> comment
freind/ picture/ calfifor bridge / comment/ phot
comment (useID, time , location, from, to )
a lot of edges in graph
graph model
so many friends -> inteligent -> brute force
multiple - time-close -> multiple - which one
Find name -> similar ->
search by name
advanced search -
Database -> use information - name, time to regist, location, email addre
NoSQL - graph -
static
Cache - 30 days - special
Analysis - search
API - search
query API - name -> last, firstname -> language, extra space, wrong char -> refine, -> name -> cache -> relation ship - by monthly
200 -> 200 -> 40000 -> Alice ->
https://www.geeksforgeeks.org/bidirectional-search/#:~:text=In%20normal%20graph%20search%20using,form%20source%20to%20goal%20vertex.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.