[hinkley]

I got screwed like that on my Google interview. You should not be blamed for assuming, when talking to Google, that the O(n!) or O(n^2) solution is not even worth talking about. So I flopped around on O(n), O(nm) and O(nlogn) solutions after trying to whiteboard a recurrence relationship and giving up on O(1).

Interviewer had already decided that somehow the crazy rules I related to him about the industry I was coming from were somehow personally my fault to he had fun letting me twist in the wind.

Personally, I think that given how small the industry is, one of the goals of the interview process should be not to make an enemy of the candidate. Candidates have friends, and sometimes candidates come back in a few years after they've gotten more experience or you're looking for different skills. None of this will matter to Google until they find themselves in a MS-style hiring crisis in another five years when they aren't cool anymore.

[blackflame7000]

I think most people will agree that Google doesn't have the best hiring strategy for minimizing false negatives during Interviews. Fortunately for them, they have the luxury of only needing to protect against false positives. Not getting hired at Google was the best thing that ever happened to my career. I ended up earning far more at a successful startup where I used the rejection as motivation.

[lalwanivikas]

> You should not be blamed for assuming, when talking to Google, that the O(n!) or O(n^2) solution is not even worth talking about. So I flopped around on O(n), O(nm) and O(nlogn) solutions after trying to whiteboard a recurrence relationship and giving up on O(1).

Did they say that they don't even want to listen to O(n^2) solution?

[badlucklottery]

I'd be super surprised if they did. Google interviewers usually encourage you to spit out an easily-verifiable O(n^2) (or even worse!) solution as fast as possible. That way, if you get stuck and honestly can't finesse a faster solution, you can code that up and provide a code sample. People still try to fake their way through the process so being able to code up something close to a compilable function is a useful metric.

[ASinclair]

Yep. This is how I conduct my interviews. I don't ask trick questions. Many of my candidates can quickly notice the simple solution but fail to write the solution in code.

[hinkley]

Yeah, this wasn't a coding question.

[sumeno]

> You should not be blamed for assuming, when talking to Google, that the O(n!) or O(n^2) solution is not even worth talking about.

If the naive solution is O(n!) then describing an O(n^2) solution is perfectly acceptable.

[zodiac]

Interesting fact: the standard DP algorithm for TSP reduces the running time from O(n!) to O(n^2 2^n)

[joeldg]

Long ago, I had applied for a software position at Google and they brought me in then said "We are going to interview you for a systems position" and I was like "umm, but I applied for a software position and am not prepared for a systems interview" then they said "roll with it, lets see". As I told them, I bombed at least partly because it threw me for a total loop and I was pretty shocked at the rudeness of that.

I didn't get further along in that process because of that stupidity and have never even considered them as a place to work since, and I am an SRE/PE these days.