Algorithms you should know before you take system design interviews

[guhcampos]

I have used multiple of these in my career. I have implemented few of them. I never got asked about any of them in interviews.

I would not expect people to know or even be able to explain those by heart, either. You just don't use them or even think about them often enough to internalize them. Or any complex algorithm for the matter.

This kind of interview only tests how much a person has prepared for an interview, not how well they can apply this knowledge in real life, or think outside the box when required.

[jonathankoren]

This is kind of crap listicle.

From the title to the content, it's just bad.

A system design interview doesn't ask you algorithms. They're basically block diagrams. They're often the interview with the highest variance, because a successful one requires the interviewer to ask not only a fair question (e.g. isn't niche to their current job), but also recognize when a solution works, but isn't their implementation. This doesn't require any knowledge about algorithms beyond what types of algorithms exist. That's pretty much it. It's also the hardest to prepare for, because you could be asked pretty much anything, and there aren't very many medium level design docs out there for complex internet scale systems.

Now an algorithm design or coding interview will ask you to develop an algorithm with level of implementation, but if you not memorizing an algorithm is going to sink you, then you have crappy interviewer and shouldn't take the job anyway. A good interviewer doesn't want you to simply come in and spout out memorized factoids, they want you to develop it. A good interviewer will recognize that you memorized the answer, and ask a different question until you don't know it. Only then, will the interview be useful.

Everyone should get the solution by the end. It's just how many, and how explicit of hints you need.

The list of algorithms is a complete grab bag of random stuff. There's nothing tying them together.

[FabHK]

> A good interviewer will recognize that you memorized the answer, and ask a different question until you don't know it. Only then, will the interview be useful.

100%. You want to get to the boundary of the candidate's knowledge as quickly as possible.

[notyourwork]

TIL that rsync is an algorithm, not just a program that makes it easy to sync content across hosts.

[flakiness]

There is a paper called "The rsync algorithm" https://scholar.google.com/scholar?start=10&hl=en&as_sdt=0,5...

Just FYI ... Or just for trolling ;-)

[bogomipz]

It's worth noting that the source of this is a someone who is hawking a pricey "cracking the system design" type interview book. I feel like these types of posts are intended to create anxiety in the reader - "oh my god I had no idea what a quad tree even was?!" I think much of the cottage industry that has sprung up about "cracking interviews" is predicated on maintaining a constant state of anxiety as well. If you look at something like Leetcode it's the same thing, there's something like 2,000+ questions there. So many that you can never feel confident. The job of preparing is never done. As long as people have anxiety about everything they don't and can't have any sense of confidence, they will be inclined to fork over their money in an attempt to assuage that anxiety created by such material.

[fendy3002]

Having done several system design interviews, most of the time they're badly executed. When I asked for some detailed requirements they cannot disclosure them. However in the end they have those hidden requirements and I've failed because my system doesn't meet those requirements.

It's a bad way to conduct a system design interview by having a design in mind and hoping the candidates will reach that with limited knowledge / guidance.

[GaylordTuring]

I interviewed for a company once where I got a real dataset from their business and just a vague assignment to analyze the data and find something that could be optimized better. So I came up with a suggestion on how to improve factor A, but they told me later that what they were looking for was for the candidates to come up with suggestions on how to improve factor B.

Why factor B was deemed more important than factor A wasn’t something that possibly could have been understood from the dataset alone.

[btilly]

My solution is to produce a design in my head, and figure out its limitations. Then I ask for each limitation if this limitation will be a problem. If it is, then I figure out how to iterate the design to eliminate that limitation. Once I don't know of any unverified limits, then I start explaining my design, and explain how I know it will perform to spec.

This is also a good way to approach system design in the real world. Don't simply go with the first solution that looks like it might work. Also don't add on nice looking features on general principle. Instead sketch out the simplest thing which works in your head, figure out the limitations, check whether each is OK, and then improve my design if it doesn't work yet.

[donavanm]

Lately Ive been going the other way as an interviewer. I try to get the candidate to deeply explain their system design; starting point, requirements, conflicting priorities, compromises, etc. Alternatively we can pivot slightly to solving the same class of problem with my system.

I can almost always find a relevant overlap between my background and theirs, which helps. And (I think) its beneficial for them to talk about their experience and existing decision making as opposed to hypotheticals. As a bonus you can also gauge the ability to communicate complex or nuanced ideas in a succinct manner.

[nolevels]

This has been my experience as well. These interviews should be open-ended with no right answer as long as you can reasonably support your design and discuss its tradeoffs. Unfortunately, many interviewers have a set solution / structure / technology already in mind.

[jtchang]

First time I saw geohashing. Can't this result in some lopsided squares? The way it is described has a standard rectangle projection. But those are inaccurate due to the earth being spherical. So the areas on top and bottom will be much larger.

To be fair I've heard of most of these in my career but they are fairly specialized. If you are conducting a system design interview and expecting the candidate to know one of these I'd suspect there is a bit of bias there (unless that is their area of study).

[killingtime74]

The shape is considered by H3 https://www.uber.com/en-NZ/blog/h3/

[patches11]

I think in practice you might use something like https://h3geo.org/docs/

[bigbillheck]

> So the areas on top and bottom will be much larger.

Should be fine in practice, not much demand there.

[EddySchauHai]

I weirdly only found out about a few of these rate limiting algorithms yesterday when I was looking at rate limiting Elixir processes for a small load testing tool. Merkle Trees, bloom filters, and raft/paxos are prevalent in crypto so if you read those topics you'd know them. Hyperloglog is an HN favorite.

Failed an interview for a test infra engineer because I couldn't implement a trie from memory earlier in the year -.-'

[time0ut]

I was expecting to see idempotent consumer, circuit breaker, and a few others that I’ve used frequently when designing systems. Maybe not interesting enough to make the list?

[baltimore]

These are more "patterns" than "algorithms"...

[FabHK]

Several interesting algorithms, but why a picture of a table instead of a table?

[mandeepj]

> but why a picture of a table instead of a table?

I guess they drawn the whole thing in an image editing tool and exported it as one image. A Table would've required much more effort, multiples images, styling, placement and many web requests to load them.

[noughtme]

Because Substack. Same thing with Medium articles. Never used either of these platforms, but surely they allow custom HTML?

[nerdyadventurer]

Another question, does anyone know any good curated resource that mention system design use cases of each data structure and algorithm?

[eminemence]

I assume its part of the system design course on https://bytebytego.com/.

[wollsmoth]

Yeah I can look these up no problem but links to articles would have been rad.

[madelyn]

I feel that if more interviews involved this sort of algorithm instead of the ultra-niche / only situationally useful, there would be way less opposition and much more signal.

At work, I have written and then used a bunch of these in production, just for the narrow scope of things I work on. Might be indicative of me being in a bubble though.

Please, ask me to make a bloom filter or show how consistent hashing enables sharding! I'll pass on yet another "Implement String.reverse()"

[patrickthebold]

TBH reversing a string is probably harder than the others if you consider how strange unicode is.

[andrew_]

I see "systems design" tossed around a lot these days, and the phrase is taking on multiple meanings. What's the context here for this use?

[ultra_nick]

It's for interviews that test your ability to design multi- computer program systems.

[keyle]

Same. I don't know. Sounds like the devops of algo? /s

[earth2mars]

author wasted some stars, not an optimal algorithm :). He defined only 1, 3 and 5. he could simply used 3 stars

[pcthrowaway]

The difference between 1 star and 5 stars on a 5-star scale is greater than the difference between 1 and 3 on a 3-star scale

[bitL]

I want to see how many people can recite Paxos/RAFT or "Operational transformation" on a system design interview... If you meet such people, start throwing gold at them as you found unicorns!

[code007]

Thank you so much for all the suggestions. I'll update the diagram in the next few days.

We plan to go through the whole list with video explanations. So far, we have done two: Consistent hashing: https://www.youtube.com/watch?v=UF9Iqmg94tk Geohash/Quadtree: https://www.youtube.com/watch?v=M4lR_Va97cQ

[fcd12]

When I used hyperloglog, count min sketch in system design interviews, I usually ended up explaining the data-structure from scratch as the interviewer had no clue what it was

[a-dub]

system design interviews are weird. the best systems are designed by doing as much research as possible on relevant systems, techniques and tools; then using experience/skill to separate the good from the bad to come up with a solid plan, not some stupid real-time whiteboard performance.

that said, this is a collection of nice solutions to interesting technical problems that have come up in practice over the last 15 years. :)

[cosmotic]

If knowing these gets you the job and it can be crammed for, that's not an effective interview.

[bufferoverflow]

You're confusing sufficient vs necessary.

Knowing them is probably necessary, but knowing them alone is very unlikely to land you a job.

[dqpb]

If the quantity and quality of knowledge is high enough, then “cramming” just means learning. This is how things should be.

[jahewson]

It’s effective at ruling out people who haven’t even heard of any of them. Though I can’t imagine really expecting people to know more than three or four of these, certainly not in detail.

[inopinatus]

You may divide your study time into two equal parts thus:

1. Paxos,

2. The whole of the rest of the list.

[sulam]

I would add CRDTs to your list. They are a tool that, when they're applicable, are almost magical.

Overview link: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...

[sitkack]

You could include CRDTs and operational transform under the same section.

[nicwolff]

They have OTs in last place, maybe CRDTs would have been next...