You need the pocket Dijkstra, Kruskals, Union-find, Bellman-Ford, KMP, Kadanes (sliding window), LCS, DP (1-n dimensional), Topological Sorting, NP-hard heuristics (usually DP), BFS, DFS, Backtracking, Memoization (basically DP, but usually used in DFS), Prefix sums (DP as well), that weird palindrome-specific algorithm I can't remember, binary search, bisection (numerical anaylsis ftw!)
You also need tries, heaps, red-black trees, B-trees, DAGs, priority queues (heaps)
But wait.. there's more!
Euclidean algorithm, Josephus Problem, Sieve of Erastosthenes and all the number theory bullshit I can't remember and refuse to, because it has fuck all to do with daily engineering.
I have a masters degree from CMU, certainly a very top school in CS. I probably could've passed this style of interview fresh out of school. I did enjoy algorithm classes, it was fun.
It was also well over 20+ years ago and having had a successful career in silicon valley as an individual contributor, I have used that knowledge... never. Not once. It has no relevance to software engineering. I've forgotten nearly all of it. Want to hire someone to design and implement solid, performant, maintainable, secure production code? That's me. Want to test me by regurgitating memorized algorithms? Nope, I'm not participating in your game. The loss is yours.
I've never ever even heard of an interview problem where a b-tree or RB tree was required to solve it.
But my point stands that there are a ton of great little questions that involve very very basic data structures and tree traversal algorithms that you can use to glean quite a lot about a candidate.
You're absolutely right that asking a candidate if they can solve a 2D DP problem isn't telling you anything other than if they'd either seen this problem or they are good at this algorithm. I'm stating that you can learn a lot and eliminate some bad folks by asking some basic coding LC questions.
I think most candidates could give a solution, just not while they are being treated like sardines and prodded with a stick.
It has made me ask myself: do I really want a job at FAANG, or any high level company? I mean if it's pumping out leetcode while simultaneously dealing with office politics and sadistic managers, I think I'll just go back to selling cocaine.
I've done 700+ LC and I still regularly get stuck on Meds/Hards, but I imagine if you know all these concepts and can explain tradeoffs during an interview, you have a better chance of passing than someone who immediately spits out a memorized solution but can't explain why they chose that specific approach over another.
But yes, that kind of puzzles can be fun sometimes! (Back when I had no family and free time for such things).
But worst part is that the interview experience is entirely different from doing puzzles for fun at home. In an interview you need to present a carefully choreographed act where you:
- pretend to be quickly discovering the solution out of the blue (even though the original algorithm took some PhD multiple years to figure out)
- never solving any part too quickly, or they'll fail you for having seen it before (of course you've seen it before if you've done the requisite months of practice)
- never solving any part too slowly, or you'll be labeled "yet another who can't even write an if statement" (comment seen often on HN)
- maintain a running commentary to "show how you think", make it credible
- while doing all this, be writing syntax perfect code on a whiteboard
- while the interviewer makes derogatory comments about how much help you appear to need, alternates between browsing social media on their phone