Data structures and algorithms I actually used while working at tech companies

I did many SWE interviews at Google. I came up with my own question that obviously required using data structures and algorithms, but probably not something the candidate had ever thought about. Most people had a good thought process which was 90% of the question; some people arrived at the answer I thought was correct. Sadly, nobody ever came up with a better answer than what I decided was best. I was kind of hoping they would ;)

The problem with Google's interview system is that everyone gets to come up with their own questions. Some are bad! Some interviewers are bad! It takes the Hiring Committee a few candidates to recognize this and give the interviewer feedback about what's bad. But, that's why the HC exists and that's why you have 4 or more in-person interviews. The uncalibrated first-time interviewer does not have full veto power over hiring you. It can make for an uncomfortable experience (when is meeting new people and writing code on a whiteboard ever comfortable?), but overall the process does find good engineers.

The end result of the process, which I really liked, was that people on the team you're joining assume competency and don't explain simple things to you that you already know. I remember a few discussions in my first weeks at Google that blew my mind; we were talking about idempotency, and nobody needed to explain what it was. Every time I've ever used that word it derailed the meeting completely, requiring a remedial CS 101 course to bring everyone else on the team up to speed about that concept. Everyone at Google knows what that is, so you don't have explain it. It was nice. (This came up again when there was a discussion about state machines. Again, everyone knew what a state machine was, and used them somewhat regularly, so what was in my past life a discussion-derailing tangent was just a thing everyone knew.)

Software engineers aren't mathematicians. We don't invent algorithms or data-structures. That's not our trade-skill. And even actual mathematicians don't sit down to solve a real-world problem that no maths they're aware of directly solve—and then produce novel maths, and then use them to solve the problem—the very same year, let alone the same hour.

What I can do, as a software engineer, is to take algorithms that exist, and repurpose them or glue them together in novel ways that the designers of those algorithms never thought of, to do something new. Bitcoin, for one example, is a feat of pure software-engineering: it takes four or five existing well-known algorithms, and puts them together in a novel combination to solve a problem. I could maybe invent Bitcoin. But I can't invent Floyd-Warshall, if I don't know about it.

Google doesn't employ computer scientists (i.e. mathematicians who invent algorithms.) Alphabet does, under DeepMind and Waymo; but Google itself only employs—and only needs—software engineers.

Asking a software engineer, under pressure, to derive a novel algorithm, is a bit like asking a chemist, under pressure, to derive a novel class of chemical reaction; or a materials scientist, under pressure, to derive a novel material.

That's not the type of pressure that a real-world person in these jobs will ever be under. And moreover, it's precisely the type of pressure that people with experience in these positions have learned to mentally associate with "going in the wrong direction, toward wasted effort", flinch away from, and to turn around and study the literature instead.

It's ironic that Google expects its employees to all have university degrees. If there's one skill people who've gone to university are guaranteed to know (and to have built up a reliance on), it's consulting the literature.

Why not just summarizes the traits of the technical skills you expect from the candidate, lay it out, and come up appropriate questions for each interview?

General software engineering interview does not work. But there can be more specific measures to improve the experience.

This attitude will keep you from hiring someone who will just "do the right thing," which is to look up stuff that can be looked up, and also persevere when an off-the-shelf solution won't be sufficient. Plenty of engineers will spend time trying to reinvent the wheel when it is totally unncesssary.