Disagreeing with CtCI answers

Pinger / Eng
createπŸ’»

Go to company page Pinger Eng

createπŸ’»
Jan 20, 2019 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
  • Zuck actually delivered a lecture on this and how FB solve, look up CS50 on YouTube
    Jan 20, 2019 0
  • Google
    alumnius

    Go to company page Google

    alumnius
    I always assumed this was why LinkedIn limits to 3rd degree connections. Does a bloom filter help here at all?
    Jan 20, 2019 5
    • 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, 2019
    • Google
      alumnius

      Go to company page 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, 2019
  • 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, 2019 0
  • Amazon / Eng
    ♀

    Go to company page Amazon Eng

    ♀
    Ctci is inadequate for system design topics. Look elsewhere
    Jan 20, 2019 0
  • 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, 2019 0