[pathseeker]

>then implement any kind of sort for an array, then implement depth-first-search.

How have you not grokked how useless those questions actually are when it comes to knowledge about writing software? Those are both trivia in the same category as "implement the TCP acking mechanism".

[vidarh]

Not my experience, as long as you're prepared to accept that people may need some prompting, and won't necessarily find the optimal solutions.

Someone who knows the 'trivia' may remember how to implement quicksort without actually being any good.

But someone with even a little bit of understanding and some prodding to not worry about efficiency will be able to come up with some sort of solution, even if bubblesort. If people appear truly petrified, it's easy to give them a chance by breaking down the problem and see if they can reason about it. E.g.whay if you start with a two element array? Then how about 3? How do you generalise that?

Someone with both the trivia and the smarts will give you a good solution and be able to muse about tradeoffs of different implementation methods, pivot selection and the like.

It's usually fairly simple to find out if people understand the solution they offer up and can reason about it, and that's often a lot more important than whether they come up with a great solution.

[aetherson]

Re-implementing bubble-sort is, I think, a pretty reasonable fizzbuzz-style question. Can people think in loops.

Depth first search I would now be a little less eager to do (I was asking these questions ten years ago), but there were a few things that I felt came out well from it: if someone wrote something like:

if (DFS(node.left) || DFS(node.right)) return true else return false

That seems to me like it demonstrates at the very least some immaturity of how to write professional code. If the person doesn't know how to do recursion, that stands out. If they fundamentally don't know how to deal with a stack, that stands out.

If someone has never encountered DFS and just gets fundamentally stock on what the algorithm is at all, then that's, I agree, not wildly meaningful. But that was not, in general, a reason why people didn't get the DFS question.

EDIT: I will also note that I've had a couple of people on HN react with horror at the notion that someone might be asked to impelement DFS or BFS. While I agree that these aren't perfect questions, I think they're pretty radically different than some of the puzzle-y or impossible-to-re-derive questions that you sometimes hear about. The algorithm for DFS is:

1. Check to see if the input is null. If it is, return false. 2. Check to see if the input's value is the searched operand. If it is, return true. 3. Return DFS(left) || DFS(right)

Breadth-first is a tiny bit harder, but it's still a while loop on a queue and just test equality and push the children onto the queue. It's about ten lines of code and it's far from rocket science. If nobody ever taught you about binary trees at all, you might still be a great programmer. But if you're a good programmer, and you ever got taught about binary trees (which most people who have traditional backgrounds have), then you should be able to recreate those algorithms from first principles in, I don't know, 15-30 minutes.