I've used a version of it before, to traverse a cached client-side hierarchy of domain objects.
The inevitable response to that is "well that's an exception, it's only occasionally needed." True, as far as it goes. But if you exempt all of these "rare special cases," you've suddenly exempted 10% of the work. That 10% is among the trickier bits (though the hardest is always organizational and product).
I also hate to say this, because it's snotty, but as far as obscure algorithms or tricky, complicated algorithms go... BFS and DFS don't really fall into those categories.
>But if you exempt all of these "rare special cases," you've suddenly exempted 10% of the work.
I don't think that's the issue though.
The issue, as I see it, is not that you had to figure out how to implement BFS. I think many of us are confident we could do that under professional working conditions. If I had a day and some data structures to poke around with, I'd write a killer BFS supported by tests if I needed to (I've had to do similar things in the past).
The issue is that interviews expect us to recall this kind of specialized and rare problem solving like it's a day-to-day thing. We as candidates are being judged on how well we can come up with a novel solution on the spot to something that many of us will need to do once or twice in a career, and will be able to solve under completely different conditions.
In short, for most candidates, these kinds of questions don't test anything realistic, and a lot of people have issue with that. It's like judging whether you want to go to a chef's restaurant based on how well they did on Chopped! They might do well under pressure because they have practice with it because they're always in the weeds because their restaurant is poorly run. A terrible dining experience might translate to a win on a cooking competition show, because the show isn't testing the chef on the experience they provide you. Just as these kinds of interview questions don't test you on how you'll actually be interacting with code and solving problems day to day.
I don't want to hold up whiteboard interviews focus on algorithms as the be all, end all. They're a poor proxy for day-to-day skills: the hard stuff is organizational, knowing all the things that can go wrong, and technical design that's both flexible to changing conditions and easy to work with. None of those are really amendable to probing in a 45 minute interview, or even several hours of pair programming.
But it's about friction: I want my coworkers to be focused on the genuinely hard problems, not spending a day writing a BFS. The current interview process does manage to probe that.
Going a bit deeper, the whiteboard interview process is a good proxy for ability to prepare over the medium term (a month or three of consistent studying should give you as good a chance as anyone to get into a generalist position at a prestige company) and of IQ. The latter is controversial and most organizations can't test for it directly (owing to legal concerns), but a relatively high IQ is a core requirement of technical roles, and whiteboards provide a solid proxy for that when coupled with the opportunity to prepare for them beforehand.
That said, I'd always go for someone who has the ability to deliver on complicated, large projects over someone great at whiteboards or who has a high paper IQ. It's just that it's pretty much impossible to evaluate for that in a way that works on a general application pool.
This is a very acute answer. I actually do think well-structured algorithm questions that are variants of common ones might be strongly g-loaded. E.g. They test knowledge + IQ.
I would say big companies that hire new people or generalist programmers benefit greatly from them. These types of questions test for intelligence at scale without outright being an IQ test. In fact, I think I read somewhere that Google engineers' performance is strongly correlated with how well they do on their interviews.
Sure, these questions might not test for conscientiousness, curiosity and general agreeableness, but that's why you have the other portions of the interview.
All this being said, I don't necessarily think these questions work at most companies where the engineering teams are significantly smaller and you can really spend a lot of 1-1 time probing knowledge and experience and reviewing coding exercises. However, I would still say basic DFS/BFS and using a hash to solve a problem is still a must. I use them on occasion, even as a generalist.
I think the goal of hiring is always: "We have a particular business problem, and need to determine: if we pay this person will they be able to help us solve it?"
As much as I think certain companies shoot themselves in the foot by spending their interviews asking trivia questions about e.g. Rails (because that's what they use), it's not unreasonable that they might just more highly value having someone who can be productive in their Rails world immediately against someone who, while excellent, nevertheless needs a week or several to onboard the ecosystem. Or in other words, they think the goal question is answered in the affirmative more strongly for someone already in the ecosystem. A dangerous assumption, but possibly valid. There are always tradeoffs to be made in the specificity and category of your questioning, but interviewers need to keep in mind how they contribute to the overall goal's question.
For larger companies, it's more likely that there are more problems to solve, and more likely a need to get people working on them sooner rather than later, so the incentives start pushing for addressing the goal of hiring (if not for all positions, at least for many positions) by answering a simpler goal question of "is this person smart and gets things done?" (which is just high IQ + conscientiousness) and hiring en masse. If you put such people to work on any of the problems you can rightly expect they will advance them some amount, even if they have to ramp up on a programming language / framework / whatever feature of the problem's environment first, and as time goes they can shift around the company to where they're even more effective. In addition to being fast it's also very fair with respect to people's backgrounds, suddenly it doesn't really matter if you have a thousand widely used github repos or not, have a 10 year experience headstart or just graduated a bootcamp, if you have a degree or not, if you know the framework already or not; people from the "wrong background" can still be hired if they can demonstrate they are sufficiently smart and conscientious to start working on one of the various problems you need work on yesterday. The fact we have to proxy this with whiteboard hazing sucks, it's expensive for everyone involved compared to just asking for ACT/SAT scores or the results of a previously taken IQ test when available and giving an IQ test when not. In my own interviewing I try to proxy for "smart & gets things done" (because that's all my teams at my current company have needed) in a less asymmetric/aggressive way while answering other questions since we can't hire everyone. But even the aggressive whiteboarding is better than every job interview screening for highly specific backgrounds and/or trivia knowledge...
And I agree that BFS/DFS is appropriate, though needlessly so (i.e. there are even simpler questions that take less time), as a first step in answering the business goal which is simply verifying: can this person who says they can program, actually program? Unless you're willing to train people to program, you have to start the cutoff somewhere. It's modestly appropriate to answer the question of: does this person know their craft's basic tools?
> Going a bit deeper, the whiteboard interview process is a good proxy for ability to prepare over the medium term (a month or three of consistent studying should give you as good a chance as anyone to get into a generalist position at a prestige company) and of IQ.
This is where I have a problem. Why are we the only industry that has this expectation of months of preparation? Engineers don't do it. Doctors don't it. Professors don't do it. Why?
I did use BFS/DFS or things like find/union in my job. But I'd say it's mostly about how quickly you can wrap your head around abstract concepts.
An analogy from finance: if you take a pen and a paper, and think about it for a few minutes it'll be clear that buying a stock and a put option is equivalent to buying a call option (and a bond, since you're also locking in some capital). This is fine, and most people can do that. But the brilliance happens only when such things are immediately obvious to you, in the same manner as you don't need to consciously decode English while reading this sentence. It's another question whether this or that particular company really needs brilliance.
How do you know that implementing a feature very close to how BFS works won't be necessary in the job? You can't. At this point asking if a candidate can make BFS is akin to asking if they can count. Same thing for inverting a binary tree or doing fizzbuzz. They're general and easy enough that anyone with a programming background should be able to figure them out.
Given that the hiring process has time constraints (however you do hiring, you can’t use infinite time, so you need to pick what you’ll include in the process), why use time testing the candidate’s ability of something that might be necessary in the job. Wouldn’t that time be better served testing something you know will be necessary?
You ask about things you know will be necessary as well. In an interview the time shouldn't be spent entirely on academic programming questions. They're there only to gauge problem solving skills in real time in a stressful environment, which work sometimes is. Who says you can't fit any of the above mentioned programming problems in 10 to 15 minutes?
Wouldn’t asking real-world questions that the person will definitely run into during the job also gauge problem solving skills? Unless problem-solving isn’t part of the real job, in which case it’s not worth testing for.
If your point is that you do a mix of questions that are definitely relevant and some that are academic and might be relevant, why not just do 100% known-relevant questions? What’s the value add of asking questions that are less than 100% relevant?
Here's a simple way to quantify the argument: go find the most popular Node or React front-end projects on Github, and then find out how many of them --- in their own source code, not in the vast, unending dependency tree NPM generates --- contain a breadth-first search.
I’ve had to write tree searching algorithms at multiple companies, although I usually find myself reaching for depth-first search instead. It comes up often when dealing with hierarchies (think things like company org charts for HR software, for example).
The inevitable response to that is "well that's an exception, it's only occasionally needed." True, as far as it goes. But if you exempt all of these "rare special cases," you've suddenly exempted 10% of the work. That 10% is among the trickier bits (though the hardest is always organizational and product).
I also hate to say this, because it's snotty, but as far as obscure algorithms or tricky, complicated algorithms go... BFS and DFS don't really fall into those categories.