undefined | Better HN

0 pointsXyik9y ago0 comments

No offense, but not knowing BFS is kind of a red flag, even if its for a front-end position. It's the most basic graph / tree traversal algorithm there is. And you when you work with the DOM on a daily basis and use libraries that traverse for you its a good idea to have a basic understanding of whats going on under the hood. It's like saying you're a good programmer but not understanding basic concepts about memory management and whether things are stored on the stack or on the heap.

0 comments

tptacek9y ago

If I took an interview with a random developer at your firm, drawn at random, not including you, and I spontaneously asked them to implement Djikstra's shortest path algorithm from memory, what percentage of them would be able to do that? Djikstra is not only basic and extremely simple, but it's also an algorithm that everyone who takes graph theory --- or really, computer science at all --- learns.

I'm guessing 10%.

SamReidHughes9y ago

Ask somebody to implement Dijkstra's algorithm and they might not remember specifically which algorithm that was. Questions shouldn't say "BFS" or "Dijkstra" in them -- if you're going to ask whiteboard questions, the way to do it is to pose a problem where that's a solution. Ask an actual shortest path problem or a weighted shortest path problem, or an "any path in non-infinite time" problem, or what-have-you.

BFS and Dijkstra's aren't really the sort of thing you implement from memory, you figure it out fresh each time, unconsciously plagiarizing from your past experiences.

XyikOP9y ago

They all got through the interview process so I'm pretty confident about 80% of them would be able to do it and 100% of them would be able to implement BFS.

Also yes it's a basic graph algorithm everyone learns, but its inherently much more complicated than BFS which is a simple traversal. It's like bubble sort vs radix sort ... which makes this kind of a loaded question.

tptacek9y ago

Now, I didn't say BFS, did I? :)

I expect they can all do BFS, because your interview process apparently requires that.

1 more reply

jmathai9y ago

It's really not a red flag. Not knowing or having BFS memorized does not indicate that one can't implement it relatively quickly by refreshing oneself on the algorithms.

Unless, of course, you mean if all academic papers and material that describe BFS suddenly vanished and you had to come up with a solution yourself in 30 minutes with someone looking over your back. In that case, I agree, it's a red flag for whatever position you're interviewing for.

XyikOP9y ago

Where do you draw the line then? You can google and stack-overflow answers to pretty much any technical interview question that has a non-subjective answer.

BFS is not much more than a loop, a queue and a set to keep track of state (which nodes to visit next and which nodes have been visited). I can't think of many algorithms simpler than that to ask outside of things like fizz-buzz.

If you are arguing for whether algorithms are an effective way to gauge a candidate's skill then you should state that.

j / k navigate · click thread line to collapse

0 comments

tptacek9y ago

I'm guessing 10%.

SamReidHughes9y ago

BFS and Dijkstra's aren't really the sort of thing you implement from memory, you figure it out fresh each time, unconsciously plagiarizing from your past experiences.

XyikOP9y ago

They all got through the interview process so I'm pretty confident about 80% of them would be able to do it and 100% of them would be able to implement BFS.

tptacek9y ago

Now, I didn't say BFS, did I? :)

I expect they can all do BFS, because your interview process apparently requires that.

1 more reply

jmathai9y ago

It's really not a red flag. Not knowing or having BFS memorized does not indicate that one can't implement it relatively quickly by refreshing oneself on the algorithms.

XyikOP9y ago

Where do you draw the line then? You can google and stack-overflow answers to pretty much any technical interview question that has a non-subjective answer.

If you are arguing for whether algorithms are an effective way to gauge a candidate's skill then you should state that.

j / k navigate · click thread line to collapse