In my experience, people start complaining that an interview is "theory-heavy" at about the point that you expect them to know when and how to use a binary tree. Binary trees are not hard-core CS theory, they are freshman Intro to Data Structures. They are a very basic tool (almost) every programmer should be familiar with.
Moreover, when I ask candidates questions about data structures and algorithms, while it's nice if they can ace it all without hesitation, what I'm really looking for is what happens when their first answer is wrong. When they pick an incorrect data structure for the problem and I probe to say, "so, using that data structure, how do you this task?", I want to see if they will realize that the task I'm asking for is hard to implement or has very poor performance using the data structure they have chosen, and whether they will step back and realize they made a mistake. The point is less what do you know, but do you know what you don't know and do you recognize when what you're trying isn't working.
> In my experience, people start complaining that an interview is "theory-heavy" at about the point that you expect them to know when and how to use a binary tree. Binary trees are not hard-core CS theory, they are freshman Intro to Data Structures.
The other part about binary trees is by their very nature they involve pointers and recursion. Understanding pointers and recursion is the difference between being able to write code and being a programmer. The former is a fundamental skill any knowledge worker should have (scientists and financiers using Matlab or Python, statisticians using R); the latter takes passion, effort and talent.
The other extreme I've seen is asking questions from computational geometry, combinatorics and complexity theory (for generalist software engineering positions). These are all relevant skills and for the former two a good cursory knowledge is important for a generalist: however, unlike pointers or recursion they're not as fundamental to programming.
I don't understand how someone can not understand pointers and recursion. There are very intuitive, you have to probably have to study bits of math which is more unintuitive to get on computer science in the first place.
Binary trees are also something you will never need to know about in 99.9999% of real world programming situations, especially if you're using a sufficiently high-level language. In the real world, there are thousands of other factors, tasks and considerations on your plate other than having to figure out exactly how to manually create a binary tree or even think about it. It's one tiny thing in a sea of issues. Speaking from 25 years of programming experience here, about half that in industry.
Useful? Yes. Necessary? No. And in the real world, you could just look it up, give yourself a refresher, etc. as needed.
I don't generally ask people to implement a binary tree. I ask about what data structure is appropriate to use in certain situations. I.e., do you understand the performance characteristics of basic data structures and enough about how they are implemented to realize why certain tasks are very inefficient if you use the wrong one.
Moreover, when I ask candidates questions about data structures and algorithms, while it's nice if they can ace it all without hesitation, what I'm really looking for is what happens when their first answer is wrong. When they pick an incorrect data structure for the problem and I probe to say, "so, using that data structure, how do you this task?", I want to see if they will realize that the task I'm asking for is hard to implement or has very poor performance using the data structure they have chosen, and whether they will step back and realize they made a mistake. The point is less what do you know, but do you know what you don't know and do you recognize when what you're trying isn't working.