[2bitencryption]

I recently had a programming interview where, at the whiteboard question, I said "this may be a dynamic programming question, let me see--"

and the interviewer said "STOP! Stop, every time someone says that, they end up flopping and never getting anywhere. Don't go down that path, I'm telling you."

I think it had more to do with the interviewer being a poor interviewer, however.

[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.

[fizixer]

For me it was a bit the other way around. I solved the problem in a brute force way and on interviewer's asking, was flopping to come up with a better algorithm. Then he mentioned that I should consider DP.

Unfortunately my DP was really bad so I knew right then I'm going to flop. And flop I did.

For me the two weakest points are DP, and coming up with the right O() estimate for an algorithm that I just created on the whiteboard, and am looking at it for the first time in my life. Would love advice on how to get good at both.

[moufestaphio]

For DP? Practice a couple on like HackerRank, CodeFights etc. It starts to make sense after you do a few.

For Big O notation? Just think about how many times you're iterating through things (in the worst possible case).

e.g. Got two nested for loops each going to N.. we're going to loop N on the outer loop, so and each iteration of the inner loop we go through N times? that's N x N so O(N^2).. (easy example obviously).

[lalwanivikas]

Woah! What was the problem? Maybe then we can say if he was right or not.