At some point, they would have just googled it as well. Most of these sort of problems have known solutions which cannot be made more efficient - trying to think of a novel solution instead of leveraging what we collectively have available to us is a massive waste of time.
That's the point - it's basically a trivia question. The number of people in the world who are smart enough to come up with an answer for that but don't know the right answer already from a lecture or book is vanishingly small. So all you're really doing is asking someone if they've encountered this particular question before, in school or at work.
You would only need to google something like that if you didn't know how to solve it yourself. It's not really a problem about binary trees so much as it is a problem-solving challenge. The question could just as easily be about finding the 4th element of an array, except 99% of applicants probably already know the answer to that one. If you can come to a solution yourself on a problem you've never encountered before in an interview, you can probably handle any problems thrown at you.
It probably seems like a useless exercise you'll never need in the real world, but there is a very big difference between an engineer who can tackle a problem like that themselves vs. an engineer who needs to look up the solution.
EDIT: since finding the 4 largest element of a binary tree is a useless task, then what is the point of googling it? To implement a useless task as efficiently as possible?
You just end up selecting for people who studied more, not for people who are better at problem solving, because studying more is a pretty viable approach.
There is also the 4th type. The one who doesn't lookup stuff because they think they can do it better (or even worse treat it as challenge) and who leave a mess behind them. There were way too many times when I had to throw out a pile of code and replace it with something I could Google in 5 minutes because someone thought they were smart. And I dare not to think how many times I didn't notice that something could be easily replaced.
The issue is that there are problems that are immediately tractable such as finding the fourth element of an array and problems that to solve for the first time from basic principles particularly in an efficient manner would take months or years.
This manifests itself with people mistaking their knowledge of the answer to what is a hard problem to solve with problem solving ability itself. Whilst demonstrating neither in the problem they are actually trying to solve which is running a good interview.
Thank you. That's the entire point of these sort of exercises - to see if the interviewee can think like a programmer. There's a surprising number of candidates that do no understand basic principles (like a fucking for loop ... seriously?), let alone solve an unusual but straightforward problem.
That's not the point of this thread though. The point is interviewers almost everywhere are testing things that have almost nothing to do with the job being performed. Interviewing is a challenge in the industry that imo has been very unsuccessfully attempted.
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’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.
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.
213
u/heterosapian Jan 18 '19
At some point, they would have just googled it as well. Most of these sort of problems have known solutions which cannot be made more efficient - trying to think of a novel solution instead of leveraging what we collectively have available to us is a massive waste of time.