I recently interviewed a master's student for a job at our company. I asked him a very traditional question, and then was going to follow up on it with increasingly more difficult questions to see how deep his knowledge was. I wasn't out to "get" him at all, I hate interviewers that ask super-hard questions, I'm more interested in having a good conversation with the person to try to get a feel for what they really know, not just what they've memorized.
My question was easy: how would you iterate through a binary search tree.
He immediately asked me "should I do it recursively, or iteratively? Can I use a stack if I do it iteratively?" It was obvious he had studied for this question, and he banged out a solution in 2 mins. Iterating through a binary tree is a bit tricky if you've never done it before, and I wasn't even going to ask him this, but since he brought it up, I knew he knew the answer. The fact he could come to an answer immediately only indicated to me that he had memorized the answer and was essentially gaming the system.
So I asked him an even simpler question: Given a binary search tree, write code to find a particular value. If you can't find the value, then return me the next smallest value. For example, if the tree contains 1, 2, 3, and 5, and I ask for 4, then return 3.
He couldn't answer this, even though it's easier than the previous question. He had no clue how to solve it, and even worse, he couldn't recognize the simple bugs in the code, and the fact that he was dereferencing NULL pointers, etc. So I passed on him.
Personally, I think the best way to advertise for a job is to have a portfolio of code, as dpritchett says. I'm tired of testing people on whiteboards, and seeing if they can memorize solutions to every single program on glassdoor.com. I'd rather just have them point to a github repository, so that I can see their coding style, and see if they can produce quality code. Having an indepth conversation about their project, and quizzing them on their code, to me, is a more real-world determination of whether or not they're a good programmer.
Then, the onsite interview would be limited to determining if their personality is a good fit for the team, instead of trying to come up with 10 different variations on "iterate through a binary tree".
So I asked him an even simpler question: Given a binary search tree, write code to find a particular value. If you can't find the value, then return me the next smallest value. For example, if the tree contains 1, 2, 3, and 5, and I ask for 4, then return 3.
Out of curiosity, what is the solution?
I would imagine something like keeping a variable of the highest found value under 4 and if you don't find 4 then you use this variable.
- If the node value matches, return it
- If the node value is too low:
- If possible, step right and repeat
- Otherwise, return this node value
- If the node value is too high:
- If possible, step left and repeat
- Otherwise, return the value of this node's predecessor:
- Walk up until you traverse a right link
- Return the node's value
- If you hit the root, the requested value is less than any value in the tree
My question was easy: how would you iterate through a binary search tree.
He immediately asked me "should I do it recursively, or iteratively? Can I use a stack if I do it iteratively?" It was obvious he had studied for this question, and he banged out a solution in 2 mins. Iterating through a binary tree is a bit tricky if you've never done it before, and I wasn't even going to ask him this, but since he brought it up, I knew he knew the answer. The fact he could come to an answer immediately only indicated to me that he had memorized the answer and was essentially gaming the system.
So I asked him an even simpler question: Given a binary search tree, write code to find a particular value. If you can't find the value, then return me the next smallest value. For example, if the tree contains 1, 2, 3, and 5, and I ask for 4, then return 3.
He couldn't answer this, even though it's easier than the previous question. He had no clue how to solve it, and even worse, he couldn't recognize the simple bugs in the code, and the fact that he was dereferencing NULL pointers, etc. So I passed on him.
Personally, I think the best way to advertise for a job is to have a portfolio of code, as dpritchett says. I'm tired of testing people on whiteboards, and seeing if they can memorize solutions to every single program on glassdoor.com. I'd rather just have them point to a github repository, so that I can see their coding style, and see if they can produce quality code. Having an indepth conversation about their project, and quizzing them on their code, to me, is a more real-world determination of whether or not they're a good programmer.
Then, the onsite interview would be limited to determining if their personality is a good fit for the team, instead of trying to come up with 10 different variations on "iterate through a binary tree".