3 ms·

How snarky do people get on these interviews? If anyone asked me to find the kth-greatest element in a tree I'd write down a loop that increments std:set::crbe

How snarky do people get on these interviews? If anyone asked me to find the kth-greatest element in a tree I'd write down a loop that increments std:set::crbegin k-many times and then dereferences and returns it. This is literally how anybody at Giant Search and Advertising Company would do it, and almost nobody at that company has ever written a tree, they just use the one in libc++, from Jeff Dean on down.

ajross 7y ago
Sigh. They aren't asking you the question because they expect you to write an in-memory data structure library. They are asking you this question because they want to know that you can reason about systems with subtle behavior, and a binary tree is one such system that most programmers learn about in school. So if you refuse to engage, they'll have no evidence from you about your ability to write subtle code of any kind. And they'll go with someone less snarky who they know does.
- thedance 7y ago
  Isn’t it up to the interviewer to ask a useful question? This is exactly how I would find the kth item of a search tree. I don’t feel like that is refusal to engage. Is the question is more like “describe various approaches to the designs of search trees and their iterators, and discuss the time/space complexity of a few examples” then that’s a different question.
  - ajross 7y ago
    But... demonstrating the ability to write subtle code is a useful question. "Describing" or "discussing" algorithms isn't the same thing at all. I mean, I can't speak to the thinking of the original interviewer, but this is what I'm looking for with that sort of question. And I don't see how a binary tree is a bad choice. Again, it's something that everyone sees in school, so it doesn't require a ton of description in the interview. I guess I put the question back to you: if you won't write a binary tree traversal in an interview, what subtle code would you be willing to demonstrate? And why is that better than a binary tree?
    - thedance 7y ago
      I really can’t more strenuously disagree. At Giant Search writing “subtle” code is very strongly discouraged. The very last thing I want is candidates with a penchant toward subtlety.
      - ajross 7y ago
        The point is to demonstrate capability, not "penchant". I mean, look, subtle code happens. Maybe it shouldn't. But it does, and it has to be fixed. There was a story here just a few days ago about some Project Zero work to find a bug in Chrome that involved a state machine with something like 50+ states! And realistically finding people who can do that requires that they be able to also do things like traversing a binary tree, right? So I'm going to ask the question one more time: if you won't traverse a tree in an interview, how else do you propose to select for people able to reason about that kind of problem in practical code?
throwaway22527 7y ago
Snarky or not, you missed that the question was about a binary tree, not a binary search tree.

ajross 7y ago

Sigh. They aren't asking you the question because they expect you to write an in-memory data structure library. They are asking you this question because they want to know that you can reason about systems with subtle behavior, and a binary tree is one such system that most programmers learn about in school. So if you refuse to engage, they'll have no evidence from you about your ability to write subtle code of any kind. And they'll go with someone less snarky who they know does.

thedance 7y ago
Isn’t it up to the interviewer to ask a useful question? This is exactly how I would find the kth item of a search tree. I don’t feel like that is refusal to engage. Is the question is more like “describe various approaches to the designs of search trees and their iterators, and discuss the time/space complexity of a few examples” then that’s a different question.
- ajross 7y ago
  But... demonstrating the ability to write subtle code is a useful question. "Describing" or "discussing" algorithms isn't the same thing at all. I mean, I can't speak to the thinking of the original interviewer, but this is what I'm looking for with that sort of question. And I don't see how a binary tree is a bad choice. Again, it's something that everyone sees in school, so it doesn't require a ton of description in the interview. I guess I put the question back to you: if you won't write a binary tree traversal in an interview, what subtle code would you be willing to demonstrate? And why is that better than a binary tree?
  - thedance 7y ago
    I really can’t more strenuously disagree. At Giant Search writing “subtle” code is very strongly discouraged. The very last thing I want is candidates with a penchant toward subtlety.
    - ajross 7y ago
      The point is to demonstrate capability, not "penchant". I mean, look, subtle code happens. Maybe it shouldn't. But it does, and it has to be fixed. There was a story here just a few days ago about some Project Zero work to find a bug in Chrome that involved a state machine with something like 50+ states! And realistically finding people who can do that requires that they be able to also do things like traversing a binary tree, right? So I'm going to ask the question one more time: if you won't traverse a tree in an interview, how else do you propose to select for people able to reason about that kind of problem in practical code?

throwaway22527 7y ago

Snarky or not, you missed that the question was about a binary tree, not a binary search tree.