> “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.
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.
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.
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.
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?
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.
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?
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.
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.
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.