Hacker News Reader

Comment by tptacek | Hacker News Reader

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%.

View on HN

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.

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.

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

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

The parent was talking about BFS, it's not exactly clear to me why you're asking about Dijkstra's. The two things are entirely different and, as the parent said, it's akin to asking bubblesort vs radix sort.

My point is that they are not entirely different; both are academic, simple, basic applications of the kind of graph theory freshmen learn. Described in terms of a heap, Djikstra is barely more complicated than BFS.

BFS is far from academic though, it's a very common tree/graph traversal algorithm when you want to traverse in-order, like propagation of events in a UI, or printing contents of a nested data structure for debugging purposes, or searching for the top-most element in a tree that meets your criteria so you can insert a new child subtree (very common operation in nested GUI). Hell, it's not even such an alien concept for a web/frontend developer...

I mean "academic" in the sense of "basic". SPF is one of the most fundamental problems in applied graph theory.

Reply on news.ycombinator.com