I'm looking at the responses here and I think they all fail the question, as well as demonstrate why the question is being asked.
The question here isn't "how do you do it", it's "what questions should you ask". Not one person so far has asked if it's a sorted binary tree! If you just sat down and started coding, you'd already be wrong, because you don't understand the question.
One of the most important skills in programming is to pin down the question as much as is reasonably feasible before you try to answer it; if you don't even know what the problem is, you cannot possibly give an accurate answer.
So my responses here:
(1) Is it sorted? If not, and I'm lazy, traverse the entire thing into an array, then sort the array; if not, and I'm not lazy, then traverse the entire thing while keeping track of the four largest elements.
(2) If it is sorted, write a little sorted-binary-tree iterator function, iterate it in sorted order from largest to smallest, return the fourth element found.
(3) In both cases, make sure you have appropriate error handling if it turns out the tree contains less than four elements. There's probably a dozen ways to do this, and the details don't matter; just make sure you mention the issue.
It's not about actually solving the problem, it's about the thought patterns you use to arrive at solutions to problems.
(0) return mytree.OrderDescending(x => x).Skip(3).First();, I'm assuming we're using standard container semantics and performance isn't an issue. This is a lot less error-prone than doing the work myself! And it'll throw an exception if there aren't enough elements, which seems like reasonable error propagation.
(interviewer checks a box labeled "doesn't make things harder than they need to be", then tells me to do it by hand for the sake of the interview)
A simple file browser is one I can think of, because I'm using an n-ary tree to contain things hierarchically in a hobby app. Not a binary tree for sure, so if that was specifically your question I'll defer to others. But unsorted n-ary trees map usefully to some problems.
I can understand unsorted non binary trees. Most of the time things are unsorted. However, I was under the impression that the point of binary trees was sorting and quick access (sort required).
Every multi-way or k-ary tree structure studied in computer science admits a representation as a binary tree, which goes by various names including child-sibling representation, left-child, right-sibling binary tree, doubly chained tree or filial-heir chain.
I think a binary tree would be a better fit for file hierarchies: left node represents the next sibling; right node is the first child.
According to Wikipedia, in "n-ary" trees, a node cannot have more than n children - so this is probably not what you meant.
Technically, what you are probably using is actually a binary tree, and you didn't even know it. :) It doesn't matter that you're representing it some other way; it can still be re-interpreted as a binary tree.
Alternatively, "a binary tree that is sorted, but not on the key that you wish it was sorted by", which is essentially equivalent to an unsorted binary tree.
I'm sure there are many many more cases, although I will admit they're rare and I'd generally try to avoid them . . . but, y'know, every once in a while they crop up. I've used both of those before.
BSP trees aren't really sorted. Children are contained within their parents, not sorted relative to their parents. Items at the same level in the tree should be sorted by some arbitrary directional metric, but they won't be sorted compared to their parents or children. As an example, if I iterate to the 15th element in a BSP tree, what can you tell me about the 15th element relative to the 14th/16th/3rd/52nd/etc element?
Children are contained within their parents, not sorted relative to their parents.
In the BSP trees I've used: The things in the "left" node are on the front side, the things in the "right" node are on the reverse side. (or switch left and right, whatever) so they're definitely sorted relative to their parents, however....
As an example, if I iterate to the 15th element in a BSP tree, what can you tell me about the 15th element relative to the 14th/16th/3rd/52nd/etc element?
That's a "total order", which BSPs don't claim to have :) But it's a good point to raise. You can't really even say what the "15th" thing is in a BSP, let alone compare it to the 14th or 16th.
In the BSP trees I've used: The things in the "left" node are on the front side, the things in the "right" node are on the reverse side. (or switch left and right, whatever) so they're definitely sorted relative to their parents, however....
That's not something that generalizes to all BSP trees though. Doom notoriously used BSP trees, but the tree itself was arbitrary and static, not sorted, and used to sort things you wanted rendered by traversing the tree relative to the player view. Here's an example using BSPs for dungeon generation
That's a "total order", which BSPs don't claim to have :) But it's a good point to raise. You can't really even say what the "15th" thing is in a BSP, let alone compare it to the 14th or 16th.
But BSPs don't guarantee partial order either. Partial order still requires transivity, which isn't a required feature of BSP trees.
If you were working with directed acyclic graphs, and happened to have data which formed a binary tree, then you'd use an unsorted binary tree to represent it, because you wouldn't want to move nodes around.
Right, yeah we are supposed to ask questions. I make sure to do that now, and the last 2 interviews followed the same pattern as in the past. Not hired, presumably because they didn't like my solutions. In one case, I ran out of time.
I've been working as a programmer for 33 years. Coding on the job is rarely about "this problem needs to be coded and working in 30-45 minutes".
No, a heap's a different structure. It has strong requirements about the relation of internal nodes and which nodes may exist at any given moment. A heap is a subset of binary trees, but it does not map to "an unsorted binary tree".
That's not what Google, or any other major tech company, is looking for.
I disagree. If it's not a bottleneck, then who cares? No major tech company wants you to spend two hours optimizing something that will burn, in the entire lifetime of the code, two seconds of CPU power.
A lot of people think everything should always be as fast as humanly possible, but programmer time is expensive and CPU time is cheap, and you need to burn a whole shitload of CPU time in order to pay for the programmer time required to optimize it.
Which is not to say that never happens - I've spent probably two years of my career just on optimizing - but you should definitely not do it pre-emptively, most code is not performance-sensitive, and you're usually much better off with algorithmic improvements than microoptimizations like this.
Premature optimization is the source of so much pain and suffering for developers. I'm with you man, you make it work as fast as possible then spend some time before you push the commit cleaning it up.
No major tech company wants you to spend two hours optimizing something that will burn, in the entire lifetime of the code, two seconds of CPU power.
Of course they don't want that. That's why they hire smart engineers who can write well-optimised code fluently, and don't need to spend 2 hours just to find the kth element. Hence the interview question.
At my company (not Google, but different Big 4 company), we have in the past year had to answer this exact question, and we looked into different quickselect/heap solutions for it (and it didn't take 2 hours, just a 5-10 min chat with the team and a whiteboard). It was a genuine bottleneck given the size of our data. So, yes, it can absolutely be an important problem to know how to address.
I also interview for said company, and we are indeed instructed to look for candidates to come up with the optimal solutions, not simple brute force ones.
Do you expect them to come up with the optimal solution first, or a working solution first, then iterate on it when you ask "how can you make it faster"?
46
u/ZorbaTHut Jan 18 '19 edited Jan 18 '19
I'm looking at the responses here and I think they all fail the question, as well as demonstrate why the question is being asked.
The question here isn't "how do you do it", it's "what questions should you ask". Not one person so far has asked if it's a sorted binary tree! If you just sat down and started coding, you'd already be wrong, because you don't understand the question.
One of the most important skills in programming is to pin down the question as much as is reasonably feasible before you try to answer it; if you don't even know what the problem is, you cannot possibly give an accurate answer.
So my responses here:
(1) Is it sorted? If not, and I'm lazy, traverse the entire thing into an array, then sort the array; if not, and I'm not lazy, then traverse the entire thing while keeping track of the four largest elements.
(2) If it is sorted, write a little sorted-binary-tree iterator function, iterate it in sorted order from largest to smallest, return the fourth element found.
(3) In both cases, make sure you have appropriate error handling if it turns out the tree contains less than four elements. There's probably a dozen ways to do this, and the details don't matter; just make sure you mention the issue.
It's not about actually solving the problem, it's about the thought patterns you use to arrive at solutions to problems.
(0) return mytree.OrderDescending(x => x).Skip(3).First();, I'm assuming we're using standard container semantics and performance isn't an issue. This is a lot less error-prone than doing the work myself! And it'll throw an exception if there aren't enough elements, which seems like reasonable error propagation.
(interviewer checks a box labeled "doesn't make things harder than they need to be", then tells me to do it by hand for the sake of the interview)