2 ms·
That's really unprofessional. I've never talked to anybody at Google who administered a "I don't know the algorithm" interview like that. They would have been
by dekhn 5y ago
That's really unprofessional. I've never talked to anybody at Google who administered a "I don't know the algorithm" interview like that. They would have been spanked badly by the interview committee, if repeating this behavior.
If I may ask, why in that interview did you just sit there and not ask any questions? I've passed code interviews where I learned an entire new algorithm on the fly (funny how knowing there is an nlogn solution to an n**2 problem can produce workable solutions).
- cperciva 5y agoI should have been clearer. After thinking for a bit I did start asking questions, but the interviewer didn't give me any useful information. IIRC I asked if I could assume the problem was small enough that I could just do a brute force search of possible solutions and the answer came back that no, they needed a solution which would work for any size; I know I asked other questions but I can't remember what they were. I wasn't silent for half an hour, just for the first couple minutes; but I didn't write any code (which is what the interviewer was pressing me to do). (Speaking of entirely new algorithms though, there was an interview question which was a thinly disguised 3SUM, and they expected the very obvious N^2 solution; my interviewers were shocked when I pointed out that the way they had structured the problem, the density was high enough to use a convolution and solve it in N log N time.)
- qumpis 5y agoWhat structure should there be for nlogn solution to be applicable?
- cperciva 5y agoThe issue isn't structure but rather density. If you have N values ranging from -M to M, the "obvious" solution is O(N^2) and the convolution us O(M log M). So if you have lots of values within a narrow range the convolution wins.