7 ms·

I will still never understand why I was asked to code an implementation of a binary tree for an interview once, something that is usually left to those who impl

by jb1991 5y ago

I will still never understand why I was asked to code an implementation of a binary tree for an interview once, something that is usually left to those who implement standard libraries or similar low-level needs, for a job that was basically writing user interfaces.

nostrebored 5y ago
Because an implementation of a binary tree is dead simple.
- jhgb 5y ago
  You mean a naive one, that is, a useless one...or a practical one? Such as, at least something like LLRB?
  - ascar 5y ago
    A binary tree is just a tree data structure where each node has at most two children. And that's dead simple and every programmer should be able to implement that when aksed. Note that it doesn't even have the search (i.e. sorted) requirement and much less the self-balancing one. You can work your way towards that with the right questions and that would be an acceptable way to structure an interview. Start with something simple everyone should be able to do and then work your way up the requirements and discuss potential problems/pitfalls and their solutions. Nobody talked about implementing a specific variant of a red-black tree when the general topic of self-balancing binary search tree hasn't even be mentioned.
    - jhgb 5y ago
      It is dead simple. What you're describing (two children, no constraints) is basically a cons cell. Yet I suspect that most people don't use cons cells as binary trees. Which is probably why I didn't understand that apparently rather nebulous topic as being this generic.
    - sureglymop 5y ago
      To add to that, a binary tree is often not really "implemented" but simply encoded in an array. That is, the children of any given node i are 2i and 2i+1 in the array. So depending on the actual exercise/interview question you might able to just show that, especially of you have to use pseudo code.
      - jhgb 5y ago
        Correct me if I'm wrong, but isn't this exactly the case where you don't want an unbalanced tree? A degenerate tree is bad enough; a degenerate tree implemented as an array in this way is catastrophic. So it seems to me that if you're refining the topic further in some sort of talk, the topic of balancing should precede the topic of physically representing the tree as an array.
        ascar 5y ago
        It all depends on the specific topic. If I just want to store my data in binary tree structure without the possibility of deletes and just with an insertion-order requirement, then the tree is automatically balanced and using an array like that is totally fine. The use-cases are probably rare (I can't think of a situation from the top of my head), but binary tree doesn't have to mean search tree. The self-balancing part is usually added after the search part as balance is trivial/unimportant when the order/position of the elements has no constraints.
        jhgb 5y ago
        > The use-cases are probably rare (I can't think of a situation from the top of my head) I imagine there's quite a lot of them. Things like VP-trees and such get often built statically and could be implemented in a similar way. Not sure if the simple (2i, 2i+1) schema is optimal for this but perhaps it could be adapted.
        sureglymop 5y ago
        Yes, you are of course correct. I was thinking of a heap, which is a complete binary tree.
  - magicalhippo 5y ago
    This is another point in which this can be a good interviewing question. For certain jobs you don't want someone who just forges ahead with an unclear specification. That said, for most dev jobs implementing a binary tree isn't necessary knowledge. But if I need a dev who can get their hands dirty I would be weary of hiring someone who can't take a decent stab at it during an interview.
- Koshkin 5y ago
  Not to those who struggle with the notion of a pointer (or other such “fundamentals”), it’s not.
- jb1991 5y ago
  This is an arrogant comment. You are right that the general algorithm of a binary tree is not complicated. But coding it under pressure, for anyone who is not writing that kind of code on a daily basis, which is most people, and especially for a job where you’re not required to write that kind of code, is ridiculous. If you audition for the New York City ballet, they don’t expect you to ice skate.
- kayodelycaon 5y ago
  I have a computer science degree from 10 years ago and I couldn't tell you how to implement one. I vaguely know the general principles but I'd have to sit down and start from scratch on how to implement one. Why? The only time I knowingly used them is with database indices. For everything else I do, they are an unnecessary implementation detail. It doesn't matter what Ruby's Set uses.
  - gameswithgo 5y ago
    People who make this comment, I generally don't believe you, or don't believe you have done any programming. If I put a gun to your head and give you an hour, you can't make a node that points to two other nodes of the same type? If you really can't, you should get familiar with how data can point to other data, it is fundamental and done all the time.
    - jb1991 5y ago
      There’s more than making a node the points to other nodes. That’s not what makes a binary tree a binary tree.
      - nostrebored 5y ago
        I mean… it literally is all there is to it
        jb1991 5y ago
        Well, the requirements I faced were to implement the tree such that nodes were inserted with the standard ordering you would expect. Walking the tree to find the best place to insert them, etc.
        maximus-decimus 5y ago
        Again, that's stupidly easy. Right is bigger, left is smaller. If the current node is a leaf, insert left if smaller and right if bigger. If not a leaf nods, run the method recursively on the left it it's smaller, on the right if it's bigger. If they asked you to write a self-balancing binary tree it's one thing, but there's nothing tricky about writing a normal ordered binary tree.
- ClumsyPilot 5y ago
  There are loads of simple tasks, there should be a bit more reasonaing as to why this is a good filter relevant to the job's day to day. For example I think writing some logic to filter datapoints or timespans is much better and more practical. But it takes more effort than just opening and pocking binary tree.
- marcosdumay 5y ago
  The fact that you didn't even think about asking if it's balanced or not, and just went into declaring stupid everyone that considers the problem hard is annoying. I wouldn't want to have an interview with you, or you selecting people for a team I'm on.
  - CheezeIt 5y ago
    Why would it be balanced. Nobody said it was a search tree.
    - marcosdumay 5y ago
      Just the fact that somebody is talking about "implementing" it implies there's further complication than defining a recursive type. People in general do not communicate on the cleanest ambiguosity-free way;
  - nostrebored 5y ago
    If you can’t remember the details or understand what makes the problem hard I doubt it would’ve been fine even given a whole day. I’ve interviewed a _lot_ of people. The people who gripe the loudest about algorithms haven’t had a chance just from answers to situational questions.
smallerfish 5y ago
Because sometimes the requirement is that the engineer being hired is able to come up with efficient algorithms. You don't have to be able to create the textbook binary tree algorithms, but you should be able to derive a reasonably performant algorithm with simple data structures if it matters to the position you're being hired for.
- p2t2p 5y ago
  > requirement is that the engineer being hired is able to come up with efficient algorithms. Coding binary tree is not the way to discover that. Presenting a task and observing people solving it and explaining computation complexity behind their solution and the thinking behind their solution is how you do that.
  - gameswithgo 5y ago
    If I give a candidate a truly real world difficult problem with an hour or even a day to solve it, some people who are not so smart will get the correct answer by luck, some people who are brilliant will start off with a bad approach and not get there. If I ask if you can do something basic binary tree things, I will also not know if you are brilliant, but I can at least rule out if you are totally clueless or not.
  - smallerfish 5y ago
    It's a fine way of doing it, although certainly it shouldn't be the only algorithms question. It's a simple data structures / algorithms question. Can you think in terms of how data is stored in memory? Do you understand the tradeoffs of storing data in one form or another? Can you work with recursive algorithms? Given a challenge of having to think about data in a form you haven't recently, can you wrap your mind around the characteristics of that data structure? If you're getting asked all this for a ReactJS UI building job, then the interviewer is probably off-base. But otherwise, make sure you're applying for jobs you're suited for. If you don't want a job where coming up with efficient algorithms is important, that's fine - there's plenty of others out there.
    - 5y ago
thingsgoup 5y ago
I asked this once as a take home for an interview. First, I copied the first hit for “implement binary tree in C” from google. I made sure it compiled and then deleted the implementation of the insert method. That was the take home. I wanted to know that the applicant could reimplement this one missing function and compile the project and not get immediately stuck.
gameswithgo 5y ago
Because it is the 2nd easiest possible data structure to implement, if you can't do that it means you don't grasp how data can point to other data and how you can leverage recursion to make hard problems easy to solve. Perhaps they were hiring for someone that they needed to be capable of more than just trivial CRUD wiring. Even when you aren't writing core libraries these things come up constantly, sometimes at higher levels when designing systems and how they interact even. I implore you get to a state where this isn't hard for you, it will make you capable of more.
rmah 5y ago
That was probably a question to determine basic competency in coding, simple data structures and simple algorithms. I.e. if he can do this, that means he's at least minimally competent. if he can't, then we don't have to waste any more time.

by jb1991 5y ago

nostrebored 5y ago

Because an implementation of a binary tree is dead simple.

jhgb 5y ago
You mean a naive one, that is, a useless one...or a practical one? Such as, at least something like LLRB?
- ascar 5y ago
  A binary tree is just a tree data structure where each node has at most two children. And that's dead simple and every programmer should be able to implement that when aksed. Note that it doesn't even have the search (i.e. sorted) requirement and much less the self-balancing one. You can work your way towards that with the right questions and that would be an acceptable way to structure an interview. Start with something simple everyone should be able to do and then work your way up the requirements and discuss potential problems/pitfalls and their solutions. Nobody talked about implementing a specific variant of a red-black tree when the general topic of self-balancing binary search tree hasn't even be mentioned.
  - jhgb 5y ago
    It is dead simple. What you're describing (two children, no constraints) is basically a cons cell. Yet I suspect that most people don't use cons cells as binary trees. Which is probably why I didn't understand that apparently rather nebulous topic as being this generic.
  - sureglymop 5y ago
    To add to that, a binary tree is often not really "implemented" but simply encoded in an array. That is, the children of any given node i are 2i and 2i+1 in the array. So depending on the actual exercise/interview question you might able to just show that, especially of you have to use pseudo code.
    - jhgb 5y ago
      Correct me if I'm wrong, but isn't this exactly the case where you don't want an unbalanced tree? A degenerate tree is bad enough; a degenerate tree implemented as an array in this way is catastrophic. So it seems to me that if you're refining the topic further in some sort of talk, the topic of balancing should precede the topic of physically representing the tree as an array.
      - ascar 5y ago
        It all depends on the specific topic. If I just want to store my data in binary tree structure without the possibility of deletes and just with an insertion-order requirement, then the tree is automatically balanced and using an array like that is totally fine. The use-cases are probably rare (I can't think of a situation from the top of my head), but binary tree doesn't have to mean search tree. The self-balancing part is usually added after the search part as balance is trivial/unimportant when the order/position of the elements has no constraints.
        jhgb 5y ago
        > The use-cases are probably rare (I can't think of a situation from the top of my head) I imagine there's quite a lot of them. Things like VP-trees and such get often built statically and could be implemented in a similar way. Not sure if the simple (2i, 2i+1) schema is optimal for this but perhaps it could be adapted.
      - sureglymop 5y ago
        Yes, you are of course correct. I was thinking of a heap, which is a complete binary tree.
- magicalhippo 5y ago
  This is another point in which this can be a good interviewing question. For certain jobs you don't want someone who just forges ahead with an unclear specification. That said, for most dev jobs implementing a binary tree isn't necessary knowledge. But if I need a dev who can get their hands dirty I would be weary of hiring someone who can't take a decent stab at it during an interview.
Koshkin 5y ago
Not to those who struggle with the notion of a pointer (or other such “fundamentals”), it’s not.
jb1991 5y ago
This is an arrogant comment. You are right that the general algorithm of a binary tree is not complicated. But coding it under pressure, for anyone who is not writing that kind of code on a daily basis, which is most people, and especially for a job where you’re not required to write that kind of code, is ridiculous. If you audition for the New York City ballet, they don’t expect you to ice skate.
kayodelycaon 5y ago
I have a computer science degree from 10 years ago and I couldn't tell you how to implement one. I vaguely know the general principles but I'd have to sit down and start from scratch on how to implement one. Why? The only time I knowingly used them is with database indices. For everything else I do, they are an unnecessary implementation detail. It doesn't matter what Ruby's Set uses.
- gameswithgo 5y ago
  People who make this comment, I generally don't believe you, or don't believe you have done any programming. If I put a gun to your head and give you an hour, you can't make a node that points to two other nodes of the same type? If you really can't, you should get familiar with how data can point to other data, it is fundamental and done all the time.
  - jb1991 5y ago
    There’s more than making a node the points to other nodes. That’s not what makes a binary tree a binary tree.
    - nostrebored 5y ago
      I mean… it literally is all there is to it
      - jb1991 5y ago
        Well, the requirements I faced were to implement the tree such that nodes were inserted with the standard ordering you would expect. Walking the tree to find the best place to insert them, etc.
        maximus-decimus 5y ago
        Again, that's stupidly easy. Right is bigger, left is smaller. If the current node is a leaf, insert left if smaller and right if bigger. If not a leaf nods, run the method recursively on the left it it's smaller, on the right if it's bigger. If they asked you to write a self-balancing binary tree it's one thing, but there's nothing tricky about writing a normal ordered binary tree.
ClumsyPilot 5y ago
There are loads of simple tasks, there should be a bit more reasonaing as to why this is a good filter relevant to the job's day to day. For example I think writing some logic to filter datapoints or timespans is much better and more practical. But it takes more effort than just opening and pocking binary tree.
marcosdumay 5y ago
The fact that you didn't even think about asking if it's balanced or not, and just went into declaring stupid everyone that considers the problem hard is annoying. I wouldn't want to have an interview with you, or you selecting people for a team I'm on.
- CheezeIt 5y ago
  Why would it be balanced. Nobody said it was a search tree.
  - marcosdumay 5y ago
    Just the fact that somebody is talking about "implementing" it implies there's further complication than defining a recursive type. People in general do not communicate on the cleanest ambiguosity-free way;
- nostrebored 5y ago
  If you can’t remember the details or understand what makes the problem hard I doubt it would’ve been fine even given a whole day. I’ve interviewed a _lot_ of people. The people who gripe the loudest about algorithms haven’t had a chance just from answers to situational questions.

smallerfish 5y ago

Because sometimes the requirement is that the engineer being hired is able to come up with efficient algorithms. You don't have to be able to create the textbook binary tree algorithms, but you should be able to derive a reasonably performant algorithm with simple data structures if it matters to the position you're being hired for.

p2t2p 5y ago
> requirement is that the engineer being hired is able to come up with efficient algorithms. Coding binary tree is not the way to discover that. Presenting a task and observing people solving it and explaining computation complexity behind their solution and the thinking behind their solution is how you do that.
- gameswithgo 5y ago
  If I give a candidate a truly real world difficult problem with an hour or even a day to solve it, some people who are not so smart will get the correct answer by luck, some people who are brilliant will start off with a bad approach and not get there. If I ask if you can do something basic binary tree things, I will also not know if you are brilliant, but I can at least rule out if you are totally clueless or not.
- smallerfish 5y ago
  It's a fine way of doing it, although certainly it shouldn't be the only algorithms question. It's a simple data structures / algorithms question. Can you think in terms of how data is stored in memory? Do you understand the tradeoffs of storing data in one form or another? Can you work with recursive algorithms? Given a challenge of having to think about data in a form you haven't recently, can you wrap your mind around the characteristics of that data structure? If you're getting asked all this for a ReactJS UI building job, then the interviewer is probably off-base. But otherwise, make sure you're applying for jobs you're suited for. If you don't want a job where coming up with efficient algorithms is important, that's fine - there's plenty of others out there.
  - 5y ago

thingsgoup 5y ago

I asked this once as a take home for an interview. First, I copied the first hit for “implement binary tree in C” from google. I made sure it compiled and then deleted the implementation of the insert method. That was the take home. I wanted to know that the applicant could reimplement this one missing function and compile the project and not get immediately stuck.

gameswithgo 5y ago

Because it is the 2nd easiest possible data structure to implement, if you can't do that it means you don't grasp how data can point to other data and how you can leverage recursion to make hard problems easy to solve. Perhaps they were hiring for someone that they needed to be capable of more than just trivial CRUD wiring. Even when you aren't writing core libraries these things come up constantly, sometimes at higher levels when designing systems and how they interact even. I implore you get to a state where this isn't hard for you, it will make you capable of more.

rmah 5y ago

That was probably a question to determine basic competency in coding, simple data structures and simple algorithms. I.e. if he can do this, that means he's at least minimally competent. if he can't, then we don't have to waste any more time.