[aavz]

I'm sorry, but breadth-first-search is a simple and fundamental algorithm and straightforward to write if you understand the concept and have decent coding skills. You're just visiting a level of the tree at a time: stick each level in a list, iterate over it, and append the next level's nodes to the next list. There's no trick to it.

Not being able to do write a basic BFS algorithm suggests a) you didn't do any interview prep and b) whatever you've been working on hasn't involved any non-trivial algorithms.

It doesn't mean you're a bad programmer but if you can't answer a basic BFS algorithms question I wouldn't trust you to touch code with any non-trivial algorithms in it.

[fencepost]

Simple, fundamental, and for a surprisingly large percentage of folks completely non-relevant to anything they've done in the past 5-10 years (or more).

My immediate thought is that if I have to implement a breadth-first search from scratch it probably means that I or someone has made a terrible mistake someplace.

Also, I'd want more information. Am I just getting some values then doing some recursion? How large is the maze? The stack? Are these spherical frictionless chickens or do I need to worry about real-world constraints?

Or for someone else's mention of the Nth from last item in a linked list, my first questions would be "Do I know the length?", "Is this going to need to be repeated?" and possibly "Do I have enough RAM available to create a ring buffer of N addresses?"

[geebee]

That's reasonable, but I'd like to share an experience I had interviewing a long time back.

I'd been writing lots of mathematically intensive code for building and solving large scale linear programs for about a year, and I interviewed at a job that was doing lots of math-ish business analysis. Code would certainly be written.

I was incredibly busy, and mainly spent my interview prep on math I thought would be relevant, though I really didn't adequately prep for the interview.

One of my interview questions involved some simple (really, I must be honest there, it was simple) recursive tree traversal. I blew it, and I'm pretty sure this is why they didn't hire me.

Six months later, I had to use quite a bit of tree traversal to model a series of conditions that had to occur in several possible patterns for a manufacturing system. Because there were various combinations of events that would "pass", I used trees to model the system, and I needed to recursively determine, in the event that the system didn't pass, what possible paths (including the least cost path) existed to bring the system into compliance.

I picked up my old reference books, reviewed for a couple days, and started writing code. As I did this, I started to feeling kind of embarrassed about the questions I had failed, since I was now reminded of how basic they actually were. I was chatting with a coworker about it and mentioned the interview, and told him that I could see why they didn't want to hire me.

He's my buddy, so he tends to say nice things, but he said (paraphrasing from memory): "but wait, doesn't that prove the opposite? The moment you needed to do tree traversal, you knew exactly where to go look. You know about these algorithms, you've done them and taken exams on them in the past, you just don't walk around ready to implement these algorithms on the spot."

So ok, BFS is so basic that I'll probably never forget how to to it again. But right now, this moment? I'd have to reason back through it. To get really sharp (especially since I won't know the questions in advance), yeah, I'd have to hit the books for a while.

Just how many times do I need to re-take my Data Structures and Algorithms midterm?

[pklausler]

How the question is posed really matters. What if the question had been "hey, you have a starting node in a linked structure, and you want to visit / collect / search all of the nodes that it can reach, without duplicates", you'd probably come up with DFS or BFS on the spot because the problem is not that hard and those are really the only two ways to attack it, and having found one of the two you'd probably also realize that the other approach could have been used. Whereas, if just asked to implement DFS or BFS, the question becomes less about problem solving aptitude and more about memorization.

[geebee]

All that is true, but I went through some interviews last year at Google, and honestly, you really can't afford to be thinking about things like this. Nobody is going to ask you to just implement DFS, but you may get a problem that essentially reduces to DFS, if you can see it. In my experience, you really will be expected to solve this problem at a whiteboard in 45 minutes. Syntax and so forth won't be an issue, but you can't do too much handwaving, you really are expected to write code that solves the problem.

If you have to stop and reason your way back through DFS, I'd say there's no way you'll get this done in 45 minutes. You need to know this stuff cold.

Rote memorization is useless, of course, because you won't be able to adapt or modify these algorithms. But there's a kind of memorization in the level of sharpness and mental prep you need to have when you walk into those interviews.

[pklausler]

I've conducted hundreds of programming interviews for Google, and I'd expect any good candidate to need way less than 45 minutes to code up a graph traversal in arbitrary order, even if I believed that they didn't already know an algorithm for doing so.