Algorithms Interviews: Theory vs. Practice (2020)
danluu.com
danluu.com
I continue to insist on algorithm & data structure interviews for software engineer candidates. Not every project needs them as much, but in large enough institutions, every engineer is likely to run into at least one project that does. If they can't figure it out and can't get help from someone who can, their weak solution can easily cost the company and its other engineers far more than it would have cost to interview engineers properly and compensate the fewer qualified engineers commensurately.
There's also a difference between "don't interview for algorithms at all" and "interview for algorithms but occasionally accept an engineer weak in them". In the former case you're unlikely to get lucky enough to end up with any engineers good in algorithms, in the latter case some engineers can help others with algorithms, hopefully in exchange for other relevant skills. In other words, it's worth interviewing to make sure certain mixes of skills end up on your teams, not necessarily as a hard cutoff on one skill that means you pass on other candidates with other skills.
The most widespread failure I have seen, by far, is to write code that is so abstracted out that it isn't really clear on how to get the necessary parts inline to get at efficient code. You'll have an obvious path on how to load all data for something, but no obvious path on how to get just the relevant points for the algorithm in. This is super hilarious for code paths that try and hide network hits, such that you don't see that that loop is doing a network call per iteration.
It really depends. Abstractions can and often do to otherwise avoidable copies. It's pointless to argue about computational complexity of an algorithm if you don't even notice that an abstraction you're using is adding a performance penalty in the form of running a linear-time algorithm in the hot path, and is even preventing the runtime from optimizing away problematic code.
What you wind up with is someone designing a giant system from parts they have read about that, honestly would probably work. However, it would also require retouching pretty much every system in the company to get things aligned. Which, isn't likely to ever happen.
Put a different way, the longer a project spends in design phase, the higher the chance it will not get completed. And all too often people will spend a ton of time in design looking for ways to make sure what they are building will scale to success level loads.
On phone, so will be brief. Will try a longer response later. (Apologies to other responses, not hitting them all.)
Basic point is that many will abstract out data to different locations and ownership lifetimes. So, congrats, you kept us at a lower complexity, but failed to realize you need to first essentially reindex all of the data for that to happen.
Now, I grant that often the problem is more in the data scattered over any number of databases. If there are reasons to keep that spread, though, hard to just sweep it aside.
And then there are those that don't accept, "send it to a solver." Really annoying how often people assume they can easily beat cplex and friends.
True story: once I worked on a C++ project with a very ambitious junior developer who liked to portray himself as the local authority in performance and code quality. That junior developer once blocked a PR alleging performance problems because a function call was passing strings by value instead of moving them. Except that function call was only called once per run, and its responsibility was to make 1+n calls to a REST service.
Whenever anyone complains about performance, ask for benchmarks. Odds are, even if they are technically right they are still wrong.
Knowing the difference between arrays and linked lists is one thing, but knowing the puzzle tricks such as sliding windows, two pointers or some exotic DSs that are only used in such puzzles is another thing.
That's what recruiters do when they use leetcode-type problems as their first interview to filter out the bulk of their applicantions.
[1] https://www.oreilly.com/library/view/software-engineering-at...
Anything that supports this? Because I don't believe it at all
The only thing that I can think of that could cost company a lot is data corruption / database being destroyed
Unless it is very specific case like HFT
I've seen a lot of critical fuckups in my years, but I have yet to see someone fuck up everything by using a woefully unsuitable algorithm.
That, of course, does not mean that it doesn't happen - could very well be the case at the type of companies I haven't worked for, where performance is absolutely critical...but I have a hard time believing those places don't have safety guards at place.
In fact, the vast majority of fabled horror stories I've heard in the industry are seemingly just that...fabled.
To give a contrived example that I think should make sense no matter what kind of software people actually work on:
Imagine nobody had ever figured out video compression and the only way we could see electronic video required orders of magnitude higher costs. VOD and video conferencing may not even be viable for most people. We'd still be live streaming television over analog radio. It would have vast consequences throughout other technologies and what we can do with them.
If a service gets the kind of viral growth that their creators dearly hope they will, that will almost certainly involve a level of scale that would benefit from knowledge of algorithms (including practical mathematics as a subset) and the difference between a good or bad solution could have far-reaching consequences. Of course many problems do have well-known solutions that anybody can look up, but many projects do end up needing solutions novel to them.
When some method is being called, or some data structure is being used, trillions or quadrillions of times (all the users of facebook/tiktok/etc. clicking on something / using a feature) - even small optimizations can add up quickly, which can obviously mean more compute or storage.
But I do not believe that you will find a single point of failure for those cases. In fact, no single person should be able to create such failures. And at companies that operate at such scale, there are many, many safety measures put up - not to mention the continuous performance analysis and reviews.
If I can see these issues hit at multiple separate FAANG companies famed for their algorithm interviewing then we still don't have enough safety measures. As long as a spectrum of individual algorithm skill goes as low as X, there's always a non-zero probability you'll have a whole team around that level X. A larger institution just creates more opportunities for random teams to be low outliers just like you'd hope some would be high outliers.
Sure, these situations shouldn't last forever, sooner or later the problem will be bad enough that someone has to come in and rescue the project. I've been that person multiple times [1], so some might say maybe I've just seen the worst of it and my experience isn't universal, but ask yourself how likely it is that I've had to save multiple large projects across multiple large companies if there isn't enough of this in the industry to go around.
It's always a total disaster when you get to a project like that. There'll be one "worst" algorithm but there'll also be many other terrible algorithms. I wish I could say they were only inefficient; people who don't understand algorithms usually produce plainly incorrect algorithms, not just inefficient ones, because algorithm knowledge is required for both. Even if they bother to write tests, which is far from a given, they won't think of the algorithmic edge cases most deserving of tests.
If you're very lucky, you can find a way to regenerate production data to fix whatever errors were introduced by the incorrect algorithms. Often this is impossible because the original inputs were not saved because of the assumption that the algorithm was correct even if inefficient. We can talk all we want about how there should be safety nets for these things, but there's no denying incorrect code does sometimes end up in production even at a large scale.
[1] I'm really not even that good at algorithms. I can do every day in Advent of Code without spoilers, but nowhere near a competitive level, and not always the most efficient algorithm for a given day. It turns out that's still far more algorithm knowledge than the average senior FAANG engineer who doesn't even attempt AoC because they're too busy step-debugging their last dumpster fire.
This bears repeating. With the exception of very niche applications, such as AAA games and scientific computing, the only realistic impact of picking a sub-optimal algorithm is slightly higher CPU utilization rates and background tasks taking a bit longer to finish.
This means the outcome of all this song and dance amounts at month to a few dollars per month.
Knuth mentioned something about premature optimization.
At FAANG scale this couldn't be further from the truth. Let me give an example from my own work. With a tiny bit of rewording, it could cover at least two other examples I have worked on as well, at multiple companies, so I think it generalizes well enough.
A global control system needed to generate its control signals algorithmically because it had to optimize an objective worth billions per year. The dataset had grown to take over 8 hours to process, which was just barely tolerable in fair weather, it became a batch job. This was doubling every year, mind you.
Sometimes tactical changes were required on short notice, e.g. a datacenter outage required failing over to another datacenter and re-calculating the optimal way to meet those objectives, not just for resource costs but user experience. Here it was bad enough taking 8 hours, and nobody wanted to see it double in the following year.
In a few days I rewrote this tool to give the same optimal results in under 5 minutes. Now every time a tactical change is needed, it's no big deal at all. There's no doubt this saved millions already, and as the dataset continues to grow, taking 15 minutes would still be a lot better than taking 24 hours.
Another case was even more extreme but harder to compare. Re-generating all control plane data from management plane intent would have taken at least several days with the old algorithm, but this was so impractical that nobody ever did it and we never had a number for it. I made it take less than a second total, completely changing how the entire architecture, implementation, operations, observability, scale, availability, latency, etc. hinged around the new algorithm. It was the single biggest improvement to a large platform that impacted the entire company, and it's a big company.
I have several such cases. Sometimes they're offline tools that occasionally end up in the critical path of an operation during an incident, sometimes they're in the critical path of serving user requests or in a control system affecting the availability and user experience of other user-facing services. None of these were "slightly higher CPU utilization rates", they were a quantative improvement to performance so great that it made a qualitative improvement to what was possible.
Here's the problem with this blend of specious reasoning. Even without questioning your claims, your example is based on a scenario consisting of a niche of niches whose relevance is limited to rare corner cases which have virtually no expression on the real world.
It's like trying to extrapolate optimization details from Formula 1 as something relevant for the design of a Volkswagen hatchback.
I mean, I worked at a FAANG on flagship services that virtually the whole world used, and I can tell you as a matter of fact that the vast majority of real-world FAANG services do not qualify as your hypothetical FAANG scale.
That's where you're basing your anecdotal example.
Even in large organizations, lots of people aren't touching the massively-scaled systems and are in fact just application developers.
Testing hard algorithms is probably not going to help in figuring out if someone is a good front end engineer who is only expected to build web or mobile apps. It will however be useful to identify if someone who's expected to regularly design system components, like say a cache layer for something, to actually understand the drawbacks of different caching strategies. Algorithms should be tested, but conditionally.
On the other hand, every engineer needs to know data structures and should be tested on them.
I worked at a very large company (over 100K employees) for over a decade. I definitely encountered problems where knowing complexity and graph algorithms helped. Not knowing them would have cost the company almost nothing.
I think you're subject to survivorship bias. Many (most?) large Fortune 500 companies make the bulk of their money by simple business logic and grunt work. Not by scaling. Internet based companies (which are the minority) are outliers.
I think some people have a trick, and they desperately try to upsell their trick in order to subtly overstate the importance of their skillset. It's very hard to get anyone to be honest about the importance of their contributions when their livelihood depends on it.
I strongly disagree with this assertion. Using algorithms&data structures trivia in interviews means you will reject candidates who might happen to fail a inane trivia question in spite of otherwise being perfect fits and the ideal candidate.
Imposing trivia on algorithms&data structures as a requirement communicates the idea that you don't believe anyone, including the ideal candidate, is unable to learn and develop this skill while working at your organization. This is telling regarding the bar which is set at your organization to nurture development in this skill set.
If your org is indeed large, odds are you can find a subject matter expert within your ranks, which means it's utterly pointless to expect your engineers must be able to come up with perfectly optimal solutions on their own. They are a Slack message away from that.
The biggest blindspot you convey in your post is the ladder-pulling aspect of data structures & algorithms in today's recruitment process. Subpar engineers use it to depict themselves as competent or raising the bar within their organization by coming up with obscure puzzles that bear absolutely no relationship to the job they are hiring for. They spend days hand-picking a problem for which they have a solution to, they go over the problem as many times as they need, they proceed to grill candidates on this trivia, they make their hire/no hire decision on the 20minute performance a candidate has after being presented with a riddle, and then go back to not have to face that issue ever again in any production setting.
The worst offenders are interviewers who pull this stunt in spite of they themselves completely failing to understand their own problem.
I never said trivia. By definition, trivia is stuff that is not important. I interview for things that are important to the work we do, and I give plenty of hints along the way to give a candidate a chance to show their reasoning abilities even if they have gaps in their knowledge or memory. This is what critics of algorithm interviewing conveniently ignore to make the interview seem unfair and unreasonable.
If you had a bad interviewer I'm sorry to hear that. Formal interview training in places like Google explicitly includes how to hint and unblock people effectively, and hiring committee feedback-on-feedback can instruct interviewers how to be more fair and better reflect the candidate's potential. Maybe your interviewer did a bad job and later received that feedback, but it had already soured your perception of algorithm interviews.
It's also a total myth that candidates are completely rejected because of one bad algorithm interview. If you have a day of five interviews, your success is not an AND() of the five, but it's also not an OR(). Whoever looks at the feedback weighs the various positive and negative signals to determine if it's a fit for the role. Skills in some areas can outweigh skills in other areas. Algorithms are one of those areas for a reason but it's still only one area and probably only one or two of the five or more interviews people will do.
If you know a better way to interview for these skills before hiring someone, please tell the rest of us and change the industry for the better. Until then, this seems to be the best we can do.
If your organization has very different needs, you can interview your candidates however best meets those needs. I know my organization needs algorithms and data structure skills, not just trivia but actual fundamental skills that generalize to novel problems we encounter along the way, and I'm going to keep interviewing for those skills. It's still just one interview out of several, and we've hired people that totally flunked my interview, so I'm not even gatekeeping, I'm giving the hiring team the signal they asked me to give them and the rest is up to them.
> I can't pass algorithms interviews! When I say that, people often think I mean that I fail half my interviews or something. It's more than half.
is insane.
Dan’s day job is (or was, on the occasions that I’ve worked with him) to identify and solve the weirdest, gnarliest scaling and performance bugs in extremely large systems. If Dan isn’t passing your algorithms interview, it’s not testing what you think it is.
I think it's also much easier to see/solve problems in practice than on a theoretical whiteboard.
I've rarely had to use Leetcode level algorithms at work. But when I did, it was much easier to solve than if I'd been given the exact same problem without the context of the experience I'd accumulated working on the project.
Example: I wrote a C++ program that stored a large number of 32 bit numbers[1] in a map (both key and value were 32 bits). When I ran the program, it ran out of memory (something like 80GB of RAM). I quickly realized that the map had a high overhead - all those pointers in a red-black tree consume more RAM than my data! As I was storing only once and doing lookups many times, it was simpler to simply sort all the keys, and then store the values. When I needed to do a lookup, I'd do a binary search and find it. Algorithmically same complexity as a map.
If someone gave me this problem as a whiteboard, I'd implement the map based solution, and would really struggle if I started getting questions about memory performance, and it would be silly to ding me for not choosing a binary search. In reality, my screwup was extremely simple to solve - given that I had a good understanding of the problem domain - something lacking in a whiteboard interview.
So in general, people who do poorly in those whiteboard interviews may well solve the exact same problem with ease in an actual work situation.
Another example: I wrote a DAG and needed to check if two (arbitrary) nodes were connected. I chose a fairly inefficient algorithm - recursive backtracking with no memoization. If I've already computed that B is connected to C, and I know A is connected to B, I don't need to run the whole algorithm to know that A is connected to C.
I wrote the simple, inefficient version, knowing it was a poor algorithm. But my reasoning was that I wanted to write all my tests with corner cases working before I fixed the performance.
Once I had all the tests written, I returned to optimize the algorithm. Then I said "Heck, let's see how bad it is with real world data."
The algorithm was fast. Even when I significantly increased N. How come?
Oh, it's because due to real world limitations in the problem I was solving, the maximum distance between any 2 nodes I was comparing was 7. Yes, in the abstract, it seemed very inefficient, but when you apply real world limitations, you realize there is nothing to gain by making it more efficient. Leetcode biased folks would have made the code more complex for little gain.
[1] Maybe it was 64 bit - I forget.
That is true if you use std::map , which should only be used if you have a strong requirement in having sorted keys.
If you do not have a requirement to keep sorted keys, you should use std::unordered_map which internally implements a dictionary as a hash table, exactly as std::unordered_set.
> As I was storing only once and doing lookups many times, it was simpler to simply sort all the keys, and then store the values. When I needed to do a lookup, I'd do a binary search and find it. Algorithmically same complexity as a map.
If you used std::unordered_map instead, you would be doing the same thing with a constant-time computational complexity instead of logarithmic, while retaining linear space complexity.
A) Are deeply interested in the topic. If you dabble in competitive programming, then these interviews should be a breeze.
B) Young people out of college, with a fresh memory of data structures and algorithms classes.
C) High IQ individuals. This one might be controversial, but I've met plenty of people that were just intellectually sharp enough to deduce the solutions, without having touched the material in 10 year, nor have been "grinding" LeetCode. But even these folks might not get through, if they haven't practiced - as you also have to solve the problems quick enough.
D) Those that are willing to grind LeetCode for months and months, and dedicate all their time to such prep.
One common trait has also been the ability to work under pressure / stress. If you're a good test-taker, you have an advantage. If tests make you anxious, that could be enough to derail your performance.
I don't remember which company that did the internal study, but they found that women fared worse at whiteboard interviews due to higher rates of anxiety and lower self-confidence, compared to guys - even though they were equals as far as technical knowledge and work performance goes.
- better error handling (you don't want your batch to fail because 1 of 1 million items had an issue, usually)
- sane retry/timeouts
- fixing bad db queries
- everything becomes stream processing when you really need performance and/or your dataset gets big enough.
But that isn't the entire world. I've spent a lot of time doing hard realtime code. Often on limited-resource systems. (Oddly, its more difficult to get it right on resource-rich systems...) In the realtime world, it does require a certain amount of savvy to pick an optimal trade-off of run time, memory, and I/O. Hard realtime forces you to learn complexity analysis or die. You also have the luxury of a clear, bright benchmark for "good enough to ship", which shuts down a lot of purely philosophical arguments.
When people claim that some shocking proportion of allegedly-accomplished candidates can’t write basic code to perform even a simple task on a whiteboard—do they mean pseudocode, or something akin to that? Or are they counting off points for getting actual syntax wrong?
Because I’ve been paid to write code for more than two decades but will reliably screw up syntax details on a language I wrote 200 lines of earlier that same day. Like I’ll use the wrong “elseif” (or is it elif? elsif? else if? God I don’t remember). Basic shit like that. I might well fail a fizzbuzz even, by those standards, unless asking some really dumb questions about the language won’t raise red flags.
If you're biggest worry about leetcode is does this language need a semi-colon at the end then I doubt you have trouble interviewing.
---
Do you do much interviewing as an interviewer?
I don’t exactly have a dataset (who does? A few Bigcos but most interviewers are working with tea-leaves and guesses) but I really liked the “try to learn something” approach and would use it again. It helps that I don’t know much so it’s pretty easy for me to find something I don’t know that the candidate can teach me about, I suppose—maybe this doesn’t work so well for people who know a lot and also aren’t good at faking not-knowing things.
So I failed the technical as I had to spend like a substantial amount of a 45m session console logging out values and experimenting as I went. It turned out I missed a few characters in my code. I was pretty beside myself.
Is there a public version of the tutorial?
Call it what it is: your intellectual laziness in evaluating people and your own bias towards “winners.”
Regression to the mean is very real. I doubt an org of sufficient size can truly beat it, if only because not every employee can do well in every situation/project, regardless of their skill level.
They use bottom of the barrel practices for hiring (such as leetcode), practices for collaboration (stack ranking), for distribution of rewards (skimping on existing employees in favor of hiring more headcount), and generally incapable of creating and sharing solid visions and giving people the resources to get them to fruition (Sitting back after OKRs are decided out of thin air, never truly explaining why something is important and never really supporting their reports to achieve those goals).
The level of algorithm skills I deal with in code reviews is to correct and explain the redundance of statements like
bool variable = true...
if (variable == true) ...
So I don't dare expect a deep understanding of O notation and algorithm efficiency.
Algorithms Interviews: Theory vs. Practice - https://news.ycombinator.com/item?id=39493689 - Feb 2024 (1 comment)
Algorithms Interviews: Theory vs. Practice - https://news.ycombinator.com/item?id=28838769 - Oct 2021 (8 comments)
Algorithms Interviews: Theory vs. Practice - https://news.ycombinator.com/item?id=21961174 - Jan 2020 (76 comments)
If you really cared, it wouldn't be that hard to get good enough to deal with most of these "gotcha" algorithm questions.. (Partially giving myself a pep talk here :P)
From my experience big tech interviews are not for making sure that candidates don't write O(n^2) loops. Code reviews are for that, some of the times.
Those interviews are there because we haven't figured out a better way to interview yet and this seems somehow correlated with the job. I don't think it is correlated, but it looks like it is!
Those interviews have also the hidden characteristics (your call of it is an plus or a minus) to select for quite confident engineers that usually can talk and defend their opinion. Which is quite useful in big tech.
For the reason why this does not get fixed.
It is not because no-one looked. People in the team know. We all know.
But we are being told not to focus on them.
With scales comes cost of running the whole machinery AND opportunity cost of not having the next product launched. With the scale of big tech, the opportunity cost easily dominate the cost of 1% increase in performance.
People don't realize it, but it is working well and as designed.
It is wasteful? Absolutely.
It makes a shit tons of money? Definitely!
But most companies are cargo cults. For example Stripe copies Airbnb which in turn copies Google.
The main point (I think? Hard to extract a thesis from this one besides "algo interviews bad") doesn't even hold up: "People say algo interviews reduce costly algo issues in production, but these issues still happen in production, therefore algo interviews don't work/those people are wrong." This conclusion doesn't follow. Who's to say that there wouldn't be twice as many, or twice as severe, algo problems if companies didn't interview this way? I'm not asserting that's the case, but it's consistent with the data points provided.
Outside of official HR statements, perhaps, I don't think anybody pretends leetcode-style interviews are actually ideal for evaluating corporate software engineer candidates. Everyone knows they are deeply flawed and provided limited value. They persist because they seem to be the least worst option, all things considered.
So I think it kind of work as a filter. It is not perfect, other signals are needed, in particular, as the article says, the interview format may be a problem, but recruiters need something to test. And algorithms have the advantage of being relevant to the job (unlike logic puzzles), hard to bullshit (unlike experience), fair (unlike personal situation), and not too time consuming (unlike assignments).
During COVID, every tom dick and harry thought they could be a coder.
is that in theory, theory and reality are the same;
but in reality, they're not...
Surely there are way worse questions that companies ask.
Also, I stopped reading after his first argument which is incredibly stupid. He thinks the fact that he found inefficiencies in code at companies asking such questions proves something. The company I work for asks questions about testing yet we still have untested code. This is not strange, because outcomes depend on many things, not solely interview questions. It’s such an idiotic argument.