"Implement a recursive depth first traversal of a tree" isn't an engineering problem. It's a CS textbook problem. A fairly basic one, surely, but about as useful to a software engineering project in most cases as the ability to smelt and construct a screw is to an automobile engineer. And the software interviews GP complained about these days don't even start with something that trivial. Usually it's more absurd, and involves what are essentially little math tricks.

> but about as useful to a software engineering project in most cases as the ability to smelt and construct a screw is to an automobile engineer

I strongly disagree. Having a deeper understanding of how the data structures you use day-to-day (whether or not you implemented them or not) is vital to you picking the correct structure for any particular task. Not knowing the basics of how to implement a binary tree, a singly or doubly linked list is a massive red flag in terms of the competence of a candidate in my humble opinion.

I think absolutely there are classes of data structures that are obscure or leftfield that shouldn't be asked of a candidate, but there's a hell of a lot that a professional should know, regardless of whether they're using a library that does it for them.

> Not knowing the basics of how to implement a binary tree, a singly or doubly linked list is a massive red flag in terms of the competence of a candidate in my humble opinion.

I agree.

On the flip side-- upon successfully implementing a linked list, a clever candidate might let it slip that he/she designed the interface to be performant with a particular use case in mind, and that they weren't sure if the interview had the same expectation for that use case. If the interviewer consequently signaled agreement with the premise that linked lists have performance benefits in certain cases, it's a good indicator that the people in charge probably aren't thinking critically about the software they are producing.

Is having a deeper than big-O understanding of data structure truely necessary?

A mechanical engineer will have an understanding the characteristics of different screws (tensile strength, corrosion resistance, material compatibly etc) enabling them to pick the right one for the task at hand. Understanding the crystalline structure and the ability to smelt one yourself is likely out of scope and probably predefined by domains experts.

Why can’t software work like this?

By the time you've memorized all the cases where a binary tree does and doesn't make sense, you might as well have just learned how they work.

Exactly. I'd be very wary of any professional that hadn't had the intellectual curiosity to at least understand how they work, never mind actually try to implement one.

Where are you working that you don't have tree structures, nor can't recite the generic three lines of pseudocode to traverse it?

I have used trees in almost every moderately complicated program I've ever written, both for fun and at the office.

Sounds a bit like deriving the equations of kinematics over and over again to me. To each his or her own, but that just sounds incredibly boring to me.

I mean, it's literally a for loop:

    def visit(node):
        for child in node.children:
            visit(child)

I don't hire people in my current position, but I certainly think anyone baffled by that would be a giant red flag. It's simpler than FizzBuzz.

I mean, I keep writing for-loops even though I've written many of them before.

Found the imperative programmer.

I'm only half-joking: how often do you need an actual for loop instead of the more abstract concepts of mapping/reducing collections?

I think you made his analogy stronger, not weaker.

As a programmer I am (should be?) concerned with the actual implications of which data structures I use, not how to use them. It should be seamless.

You wouldn't judge an EE on his ability to build wires after you give them some copper and plastic. Sure, he could with tools and a bit of time. It's just a waste of everyone's time and effort.

Some languages don't have first-class functions that you would pass into a map or reduce function, which makes writing loops unavoidable.

But even if you do use map/reduce all the time instead of loops, you're just saying the same thing I did in another way - unless you're doing it for the intellectual thrill of writing a call to map/reduce for the n+1th time.

I wouldn't ask this question but I don't think it's irrelevant.

It shows you that the person understands concepts like recursion, is familiar with data structures like trees, and understands how to express and work with those concepts in code.

Completing this problem should take only a few minutes and tells you whether a candidate has a basic degree of competence. When someone breezes through a problem like this, you learn something. If someone struggles with it, you also learn something. You can use that knowledge to calibrate subsequent questions and find the limits of their knowledge.

I would be skeptical about the effectiveness of software engineer candidate who isn't comfortable with trees or recursion or algorithms like search. It's a weed-out question like FizzBuzz.

I wouldn't ask this question because I think there are better questions available that allows candidates to demonstrate mastery of concepts like these and also have depth so you can go into substantially more detail when the candidate performs well. (And questions that permit multiple solutions, etc.)

Then you want to hire people are good at interviewing; not necessarily people who are good at their job.

I have learned programming on the job, not in school. I think I have a pretty good handle on things like recursion or traversing or implementing structures. But I don't speak the lingo so I don't know what "Implement a recursive depth first traversal of a tree" means exactly. I have been doing this for 25 years now and I don't think I have ever heard anybody formulating a problem that way.

What do you mean, you don't understand "lingo"? Do you not understand english? Because that's an easily understood english sentence, and you just claimed "pretty good handle on things like recursion or traversing or implementing structures".

What's the difficulty with questions like that? But honestly you are lucky if you get asked these questions. Usually it is more about some absurd dynamic programming questions.

I suppose the debate is really between those who want to know and those who don't want to or feel that they don't need to.

That is a perfect example for why you need CS in engineering! Please do a right click view source on this page, what do you see? Look at the comment structure on this page, what do you see? Nobody could work with any of those without using recursive depth first traversal. And once someone understands recursion, the implementation of it is absolutely trivial and obvious. Why would you not use that? The same goes for all the other CS textbook problems, they are specialized screwdrivers that are useless until they aren't.

It's hazing.

I would never hire someone who would rather spend 20 minutes thumbing together a solution that may work instead of someone who would rather read available documentation and literature to find either...

    1. A trusted library that implements a complex feature
    2. A way to abstract away the need for a complex solution
    3. Feel the need to rush an implementation of a mission critical piece of code

I'd say software engineering is more about organization, abstracting, and simplification of a problem than it is about writing complex data structure implementations or complex algorithms. When you do need to implement a complex data structure or algorithm I think it's much more wise to survey available (and current) literature and implement the algorithm after thinking about the problem for a day or two then it is to attempt to implement it yourself in front of 3 people in a stressful time.

I'd expect no one I've ever worked with to be able to correctly meet any business requirement (full battery of tests, an attempt to avoid the more complex solution, documentation for the need and edge cases of an algorithm, real error messages, abstraction or library-extraction of this algorithm into a documented sub-project in our company's git server, etc) I have with a big 5 styled interview question.

It boils down to this:

    1. Your question is so simple it is stupid to ask someone who is actually qualified
    2. Your question is so complicated that anyone who would feel semi-confident in having actually solved it in 40 minutes is someone too dangerous to keep around

> It boils down to this: 1. Your question is so simple it is stupid to ask someone who is actually qualified 2. Your question is so complicated that anyone who would feel semi-confident in having actually solved it in 40 minutes is someone too dangerous to keep around

Really? You don't think there's any possibility of a middle ground here?

I don't think there is anything representative of an employee's quality of work that can be done during a short interview that would have a strong correlate to productivity and quality. I think a real-world take-home problem followed by a meeting-style presentation of your work, your solution, and a Q&A about the implementation with a representative subset of your peers would be better as this would actually be representative of the work load at hand at the company.

the basis of the question its self invalidates middle ground

bingo

> interview questions are engineering problems that either applicable to real world systems, or were inspired from them.

My experience has shown me that in all cases except for two, this is false.

Agreed, a good interview question is also a springboard to a discussion of engineering practices related to the problem.

The only work environment viable engineering answer is to get a library to solve whatever the problem at hand.

At best a top candidate should be able to turn a whitepaper into working code. Knowing trivia rarely translate in solid, productive teams.

Very, very few companies are pushing the what's known barrier.