> write a depth first search and explain its time complexity.
Part of our test goes "here's a function, in plain English what does it do?", and then "there's a few bugs in this implementation, what are they and how can they be fixed?"
I think there's a lot of alternatives to traditional algorithmic questions that just don't usually get considered. This one I liked because it involves things you'd actually do day-to-day: Reading other people's code, figuring out intent, and finding/fixing bugs.
My experience with former BigCo engineers I've had to work with is that 1% of interviewees can actually confidently design a relational data model from scratch for a weekend MVP of reasonably any major web service you could think of. If they can't even do that (which is basically among the first things you do as an engineer standing up a service from scratch), how do you trust that they have the skills to design and implement even more complicated systems?
See, I just took what you said and replaced it with a couple of key phrases. But the truth is, when it comes to designing and implementing even more complicated systems, my passage (while reductive and still arguably wrong) makes a lot more sense than yours. I'm not saying this to pick on you, just to say that you probably want to revise what you say at the very end. Instead of "how do you trust they that they have the skills to design and implement even more complicated systems?" you should really be phrasing what you're looking for as "How do you trust that they have the skills to maintain and build efficient modules at Google scale?" because there are plenty of "even more complicated systems" The truth is that the architectures that consist of the grunt work of what you do scaling a company from $0B to $100M or $100M to $1B or $1B to $10B that are by and far more important than a depth first search. The fact that you leapt to do that rather than something more widely applicable shows exactly what's wrong with this mentality. It's not that you're incorrect; you're not even wrong. You never got to the point of knowing what the right question is.
I'm pretty sure that didn't come up until at least my 2nd or 3rd year - which was 25+ years ago (and I've never had to implement it by hand since.) You seem to be biasing your selection criteria towards "new/very recent graduates"?