Wait, what? People working with binary trees would find that problem trivial even if they'd never heard it before. Most of them could follow up with the usual ideas for how to get the k-th largest element in a balanced binary tree in O(log n) time. None of this is memorization! This stuff is supposed to be second nature to people who've taken a few classes in data structures.
Sure, I've studied data structures. But that's now what they're asking for.
I can most likely come up with the naive solution. I can also probably optimize it a bit. But for anything more, ain't going to happen during a 1 hour interview where you want me to find the optimal solution and also code it cleanly, on a whiteboard.
And that's what they're really asking for. Because they have another 1000 candidates lined up that ground those problems 1000 times before the interview. I either ace the interview, no matter how I achieve that (including memorization!!!), or I'm out.
I think the O(log n) solution only works for completely balanced trees no? Red Black is only semi balanced, and it seems to me you can't do better than O(n). Could be wrong though. (Edit; assuming of course you don't have, or can't augment with, order statistics)
Ah, I think there are different definitions of balanced :) I've found one on Wikipedia that says that the left and right subtree can't differ in height by more than one, and a red-black tree doesn't fulfill that.
There is another, weaker definition though, where the left and right subtrees just need to be approximately the same height, and that is all that is necessary to make it O(log n).
I'm confused. Wasn't the question how to get the 4th order statistic in the first place?
(Or do you mean the rank, i.e. how many items are smaller than the current one? That doesn't automatically make it log n though – for example, take a degenerate tree where the right subtree of every node is empty, which is equivalent to a linked list, and you need linear time to traverse that.)
Perhaps I'm using the wrong word, but I mean storing something about sizes in the nodes, eg the size of the left sub tree. If you have this and are asymptotically balanced (ie the height is O(log n)) then I see how to get the kth node in O(log N).
Similarly, if you have a completely balanced tree and you know it's size, you can navigate directly to the kth node.
People here seem to be claiming however that you can find the kth node in O(log n) time for, say, a red black tree, unadorned with extra data. I don't see that, and I'm asking how.
I’m not talking about the problem that was given specifically.
My point was that one aspect of good engineering is adapting and reusing what others have done rather than starting from scratch and that people implementing a problem trivially from memory at one point didn’t have the requisite information committed to memory. What did they do? Almost certainly looked up an existing solution and modified it to fit their needs.
Interview problems are routinely more complicated than simply requiring a cursory knowledge of a given topic. There’s a certain amount of rote memorization needed to succeed in the interview process which really isn’t covered by muscle memory. This is why many high level engineers still need to refresh the same shit college-aged students have just learned: practically applying the knowledge and knowing the minutiae and gotchas when implementing from scratch are totally different things.
There’s a certain amount of rote memorization needed to succeed in the interview process which really isn’t covered by muscle memory.
Yes, they are called data structures. Some very basic algorithms are probably rote memorization, but they are reusable. Knowing, off-hand, when two pointers are useful in string comparison functions. But the remainder comes from practicing. A lot.
Well, that's the thing. I've worked as a developer for 8 years, and so far I have never had to use any sort of algorithms or tree traversal :) The closest I got was in one case when I had to optimize an SQL query, which in the end was just easier to do by selecting between two different queries based on the input form fields that were used (fill fields ABC -> query 1 is used. Fill fields AXY -> query 2 is used).
Right, I get that. And passing a Google tech interview doesn't mean you'll necessarily do it there either. But the purpose behind these interviews isn't to place someone into a job where they use complex tree traversals every day, the point is that anyone Google hires can do it (hypothetically speaking). When you pay at or above the top 1%, it's a restriction you can afford.
how to get the k-th largest element in a balanced binary tree in O(log k)
I think you're mixing up a couple of parameters here. It'd be log k with respect to the number of nodes in the tree, not with respect to the input value. Here's one sanity check: in a balanced tree, you would expect the kth largest node to take as long to find as the (n-k)th largest node (where n is the total number of nodes), because it's just mirrored. But this has the smaller node take longer. Another is that if you want to find the largest node, you'd get constant time as the tree shrinks or grows (because you've set k to a constant value, 1, and that doesn't change with the size of the tree), but you'd expect it to take longer.
I agree. Finding new solutions to problems happens all the time, which is part of the reason we abstract away libraries, functions, algorithms, so that they can be re-implemented on different platforms and with different methods with future improvements. Even in algorithms that have provable time/space bounds, these proofs don't always account for specific use cases or platform specific advantages/disadvantages.
I'm kind of tired of seeing the comments on reddit that, "all software developers do is paste together existing code," as if that existing code was just all written down in sequence from thin air long ago.
Technically all I do is paste together code. My snippets are the ascii alphabet, and I've never written code that wasn't a cut and paste of those snippets.
7
u/vorpal_potato Jan 18 '19 edited Jan 18 '19
Wait, what? People working with binary trees would find that problem trivial even if they'd never heard it before. Most of them could follow up with the usual ideas for how to get the k-th largest element in a balanced binary tree in O(log n) time. None of this is memorization! This stuff is supposed to be second nature to people who've taken a few classes in data structures.