Algorithms you should know before you take system design 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.

Generally the entire interview is, "Let's design an X", where X is some kind of system that has a substantial software component. The goal is to see how a candidate handles an open ended design problem of undefined size when we only have 45-60 minutes to discuss it.

For example, do they expect to be handed requirements? Do they ask what the requirements and use cases are? How much detail do they go into? Can they strike the right balance of depth and breadth of the requirements? (Or better yet, can they ask the right questions for guidance on what level of depth I'm looking for?) Once they've settled on a design, can they at least write pseudo code to demonstrate how the software would work? Can they come up with reasonable test cases? Do they even think about how they're going to test the system at all? Did they design for testability or was that an afterthought?

Some of the most effective systems for X include things that feel trivial or simple on the surface, but have some layer of hidden complexity that's only apparent once you really start thinking about it how it works, where different people may have different expectations or assumptions about the desired system behavior. For example, I frequently use a Garage Door Opener. It seems simple enough until you start enumerating the different states the system can be in, what should happen in each state when the button is pressed, what happens if multiple buttons are pressed at the same time, how to integrate the safety laser sensor which is supposed to stop the door if something is under it, etc.

More senior engineers tend to ask lots of clarifying questions and probe the bounds of the design and expectations of the customer before they start. They usually end up in good shape, because they discovered the potential blind alleys early in the discussion, their questions helped them understand the right scope for the system design, etc. It usually works out well with some very minor refactoring along the way.

More junior engineers tend to assume a LOT of the requirements and use cases if the system's operation sounds simple, and jump straight into coding without establishing these things explicitly. This is almost always a mistake, because you discover important design considerations too late and end up having to do major refactors for things that could have been identified at the very beginning, if only you'd taken more initiative and asked more questions.

For example, I recently gave this interview to a junior with 3 years of experience. He didn't ask many questions up front, and only after 45 minutes did we come to realize that he assumed the garage door remote would have 2 buttons, one to explicitly make the door go up and one to make the door go down. I (the customer) had assumed there would be one button that would toggle directions based on the door state, but this never came up or was asked about before he launched into a complex design involving 7 different classes and several circular dependencies.