Disagreeing with CtCI answers

Pinger / Eng create💻
Jan 20 11 Comments

I've got the 5th edition and just went over the answer for this question:

> 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 connection, or path, between two people (e.g., Me -> Bob -> Susan -> Jason -> You).

The answer provided is basically distributed BFS, which is fine.

But the answer doesn't address at all a) limiting the search to a few degrees of separation or b) doing the BFS in real-time vs pre-computing it.

If you do the BFS in real-time when the user is loading someone's profile page, potentially searching millions of nodes, it's too slow. If you pre-compute the paths, then you need to consider how to store them and when to pre-calculate them.

Does the answer for this one miss the mark?

comments

Want to comment? LOG IN or SIGN UP
TOP 11 Comments
  • Microsoft Y33T
    Zuck actually delivered a lecture on this and how FB solve, look up CS50 on YouTube
    Jan 20 0
  • Google alumnius
    I always assumed this was why LinkedIn limits to 3rd degree connections. Does a bloom filter help here at all?
    Jan 20 5
    • Pinger / Eng create💻
      OP
      I'll have to read up on bloom filters -- not sure yet 😱
      Jan 20
    • McMaster-Carr GlOn52
      Bloom filters only support insertions no deletions. At least vanilla version.
      Jan 20
    • Google alumnius
      Not quite. It can only tell you something might exist in a set, but can't definitively test for nonexistence
      Jan 20
    • McMaster-Carr GlOn52
      Yes it's a space efficient 1-sided probabilistic set membership. But what I said is something different: it only supports insertions no deletions. You can't delete an element after inserting it because the bits are shared. If you use it to represent a set of connections then you can't unfriend someone without rebuilding the whole bloom filter for all affected users.
      Jan 20
    • Google alumnius
      Well, you can still use the filter, it has the same properties, it's less accurate if you don't rebuild after a deletion
      Jan 20
  • LinkedIn oCKT78
    I also wouldn't expect an interviewee to on the spot design an highly optimized version. But I would expect some discussion of aspects that need to be improved and how might do it.
    Jan 21 0
  • Amazon / Eng
    Ctci is inadequate for system design topics. Look elsewhere
    Jan 20 0
  • Microsoft 2B|!2B=?
    About 5 years ago I emailed the author a list of errors I found in the book. You can reach out to her and she will gladly fix them in the next edition.
    Jan 20 0
  • Tableau krxi15
    You know its just speculation from her side right? How Facebook actually does it is way more complicated and proprietary knowledge. What she is proposing and what you are talking about might not be the case of reality at all.
    Jan 20 0