3 ms·

> “Yes. Can you write an algorithm to find the Kth highest value in a binary tree?” I got this exact question on a phone screen with "Giant Search and Advertis

> “Yes. Can you write an algorithm to find the Kth highest value in a binary tree?” I got this exact question on a phone screen with "Giant Search and Advertising Company." I got stuck on a stupid detail and botched the implementation. Once I hung up the phone I took a deep breath and fixed the algorithm in about 15 minutes. That still isn't very good since I was only given 15 minutes total at the end of the interview to implement it in the first place so I assume that is the time-span they expect to get an answer from a senior engineer. Fair enough, I didn't study for the interview, I don't have a lot of binary tree experience. I realized that if I couldn't get through that phone screen cleanly/easily then I probably wouldn't make it passed 4 or 5 whiteboard problems either (which are likely to be significantly more difficult). Fair play to any company that wants to screen candidates using that approach because I am not the kind of guy they are looking for and that is just fine. Everyone I spoke to was polite, professional and sounded competent. I do wish they would stop calling me and letting me know that I did well enough to be eligible to retry. I have no doubt that I would contribute at an above-average level within any of those FAANG orgs but I appreciate their process and the reasons behind it. I have had no problem finding high-paying employment and distinguishing myself within any team I have worked on for my entire career. I generally get promoted quickly and asked to lead teams. As far as I can tell there is no dystopia, just people looking for different things.

chillacy 7y ago
If it makes you feel better I’ve failed google’s interview several times before passing, after just grinding questions. It’s in some ways silly but not so silly that I’m willing to forgo a job which pays so much out of principle if I can help it.
thedance 7y ago
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.
        7y ago
throwaway307349 7y ago
It’s an easy question if you just do an inorder traversal and stop at the kth element, but of course that’s not optimal. To get log(n) efficiency you need to augment the tree with subtree counts.

chillacy 7y ago

If it makes you feel better I’ve failed google’s interview several times before passing, after just grinding questions. It’s in some ways silly but not so silly that I’m willing to forgo a job which pays so much out of principle if I can help it.

thedance 7y ago

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.
      - 7y ago

throwaway307349 7y ago

It’s an easy question if you just do an inorder traversal and stop at the kth element, but of course that’s not optimal. To get log(n) efficiency you need to augment the tree with subtree counts.