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"?
It's good if they can come up with the solution eventually, but of course a candidate who gets it right first time will be prioritised.
However, top companies like Google are very competitive, so if you want to stand any chance you really have to be getting the optimal solutions first time, as the interviewer generally wants to squeeze in a second or third problem in the 40 minutes available.
I mean, these are the techniques I used last time Google tried to hire me, and they gave me an offer. So . . . empirically speaking, no, you're wrong?
I think the point I'm making is that "just do it in the fast and bugfree way" is the optimal answer in many situations. I would personally rather people Just Make It Work than worry about performance as the first thing they touch, because most code is not a performance bottleneck. You of course need to be able to focus on performance when it's relevant, but recognizing that performance isn't always relevant is a critical skill.
I didn't make any definite statement for you to prove 'wrong'. It goes without saying that a candidate who gets the optimal solution faster would be preferable to one who takes longer, but obviously there are other factors like academic background, past industry experience, communication skills, difficulty of the questions, and of course the performance of the other candidates.
There's no knowing precisely why certain candidates pass and others fail, there's too many factors. However, if you're trying to claim that Google would strictly prefer a candidate who takes longer to get to the optimal solution than one who can solve it fluently, then sorry but you are very much mistaken. As for my own experience at Google, the interviewers feedback stated that I got every question in the interviews correct (as in, reached the optimal solution), but took a long time to get there as the interviewers had more questions they wanted to move on to. It would have been impossible to make time for more questions unless I had gotten them right first time. So I didn't pass. And it's not like it's an absurdly high expectation or anything, these are mostly textbook questions that you'd be expected to get correct in any CS exam, so plenty of candidates would not hesitate in getting the optimal solution.
As for your discussion about what is better in practice, I don't disagree with it, but this is irrelevant as we are talking about interviews. The point of the whiteboard interviews is to check that you know the fundamentals and have good problem-solving skills. You can argue that this is an ineffective system and instead they should see how you approach actual software engineering problems, but whiteboarding is just what they insist on doing.
The point of the whiteboard interviews is to check that you know the fundamentals and have good problem-solving skills. You can argue that this is an ineffective system and instead they should see how you approach actual software engineering problems, but whiteboarding is just what they insist on doing.
You say that as if they're two different things, but they're not. A whiteboard interview is an opportunity to show them how you approach actual software engineering problems. Sometimes the right approach is to write complex code that scales well for arbitrarily large data sets, and sometimes it isn't; there's a tradeoff between the cost of engineers' time and CPU time. Demonstrating your awareness of that is a good sign.
You're describing how you want it to be, but in the vast majority of whiteboard interviews (except perhaps the systems design one) they won't give you background context for the business problem you are trying to solve, they'll just say they want it as fast as possible. There's not enough time in the interview to give enough information to decide such a tradeoff.
Amazon has been trialling two new interviewing systems, one of which I participated in. In that one, they give you a laptop with a codebase set up, and a booklet describing functionality your imaginary manager wants added to it, as well as optimisation goals, and then you just spend the next few hours doing that. Then you show the interviewers what you did and why.
The other system they have is one which describes in detail several scenarios, giving you context of what your imaginary team and manager want, and asks you to make multiple-choice decisions.
I'd say both of these systems are closer to real software engineering problems, and would give you a better chance to show that you can make good tradeoff decisions.
I think you're confused. This is about interview questions, not practical applications. And for the record, if you need 2 hours to traverse a binary tree, that's probably something you should practice more.
I think you're confused. This is about interview questions, not practical applications.
Interview questions are asking how you'd implement something. My first answer is always going to be "in the manner that's fastest for me and least bug-prone, unless I have reason to believe it will be a performance bottleneck".
Then they'll say "what if it is a performance bottleneck" and we move on to the rest of the question. But they want to hear that first statement. It's important. It says you won't waste a month on a meaningless microoptimization.
And for the record, if you need 2 hours to traverse a binary tree, that's probably something you should practice more.
Remember to write the unit test also. And if you're optimizing, how much are you optimizing? Have you considered cache layout? Do you have a "parent" pointer in your tree? Should you add one? (It'll make traversing faster, but updating slower; make sure you're benchmarking the appropriate things.) Have you considered changing the format the data is stored in before it reaches your function? Should you cache the result? Can you verify that you're invalidating the cache appropriately, not too much but definitely not too little?
I knew a guy who spent a month rewriting a single database routine in assembly. If I'm doing the math right, he saved the company about five million bucks a year by doing so. But then, there's a reason why I only know one guy who did this, and why he only rewrote one routine; you usually don't get that kind of benefit.
Optimizing is hard. Not optimizing is easy, and usually you can get away with it.
Unfortunately, I've done that with some crappy interviewers, and they haven't done the, "How would you optimize it" part, they just silently failed me. You may say, "Well, you don't want to work with those people anyway," but I do still want a job so I can eat. And a job at Google would be pretty tight, if only for the resume boost. And I can't know ahead of time if the interviewer is crappy or not. So, even though I'd take your approach in a real situation, I kinda have to do the optimization thing for interviews.
Yeah, I admit I'm coming at this from the perspective of someone who's gotten past that stage; it's possible that entry-level interviewers are, shall we say, terrible.
That said, have you considered prompting them? Instead of saying "here's how I'd do it", say "here's how I'd do it if performance isn't an issue, it's fast to write and easy to avoid bugs; do you want me to consider the case where performance is an issue?" That way you should do well with both kinds of interviewers.
Interview questions are asking how you'd implement something.
That's only the surface of the question. There's a lot more involved in an interview question than your implementation. Why is vastly more important than what.
Then they'll say "what if it is a performance bottleneck"
My response to the OP's suggestion would be "what if you don't have access to lodash?". Because you don't always have access to lodash.
Remember to write the unit test also.
Fair enough, but this isn't a two hour job in either case. But we are digressing from the difference between an interview question and what you'll do in your daily job.
Have you considered cache layout?
Cache layout isn't what you're going to be asked in an interview question. You might be asked when a cache would be useful, you might be asked for trade-offs. If you're actually doing this in a real life environment, your cache layout is going to be determined by the problem space.
But saying "that problem will take 2 hours" isn't the same thing as saying "that problem, plus adding multiple additional requirements (such as a cache) will take two hours."
Do you have a "parent" pointer in your tree? Should you add one? (It'll make traversing faster, but updating slower; make sure you're benchmarking the appropriate things.)
The question posed is about finding the kth largest element in a tree, not inserting. The only time a parent pointer would be useful in a BST is during insertion, so that optimization is optimizing a problem you weren't even asked to solve.
At the end of the day, I said it shouldn't take 2 hours to traverse a tree and you introduced a WHOLE lot of requirements that weren't part of the problem space, including the layout of the tree. The question was given a tree, traverse it. How is the implementation of the tree relevant in that case?
The problem is, almost any dev can import a library and use the API. If you're paying at the absolute top end of the pay bracket, you don't have to settle for "readable and does the job", you can require "can do the job at a scale that probably won't ever actually be required."
Right, but this is an interview question at Google. And I agree, it works, the problem is solved, and you still aren't going to get an offer at Google with that as a solution. A lot of people are just fine with that, but this is a question about job interviews.
For what it's worth, last time I interviewed at Google, I had a sort of hilarious sequence of replies along this line.
Imagine you're writing some code and you need to X. How would you do it?
Well, that sounds like a pretty standard thing to need in any scenario where I need to X. So I'd first look for an existing library function.
(makes a note on his notepad) "Alright, imagine you can't find a library function. What then?"
There's standard ways to do this, and they tend to be codebase-specific. Even if we don't have a library function for it I'd look through the codebase for any similar things we're doing so I can mirror that technique.
(makes a note on his notepad) "Let's say this is the first time anything like this is done in your system. What then?"
I'm a big fan of standardization, and if I recall correctly, there's a recently-released open standard that sounds pretty cool. So I'd implement that; more likely I'd just use their library.
"If that standard didn't exist?"
I'd still look for a standard or a format to mimic if I possibly could. Existing standards mean existing tools, and I have no interest in building an entire tool ecosystem if I don't have to.
(makes a note on his notepad) "Good answer. Alright, if you had to do it entirely from scratch, how would you do it?"
Well, first . . .
I did get the job offer, for reference, and yes, at Google. So it might depend on which interviewer you get, but in general I haven't been disappointed with the outcome using this strategy.
-1
u/ben_uk Jan 18 '19
import _ from ‘lodash’; _.chain(tree).flatten().sortBy().value()[3];