I'm as critical of how we interview in this industry as anybody, but I've never found this particular criticism compelling or charitable. It's implicit that you know the correct first answer is to seek prior art. Making that explicit is fine but a bit pedantic. The follow-up question is: "ok great, now say that you can't find any satisfying prior art for this on Google, how would you reason through your own solution?".

They aren't looking for people who don't know to start by doing some research, they're looking for people who won't be completely stuck when that research doesn't turn up the answer.

Maybe but I once had an interview in which I was asked how to find how similar two text strings were (for search). I answered that I would use one of the algorithms from Apache commons text or within Lucerne which implement one or several of the appropriate distance algorithms. He told me he had written his own. I asked why he would do that when these algorithms were written by people who did intense research and the implementations in these libraries have been tested by more eyes than his could ever be. He said “what if I want it to run in Ruby?”...I was interviewing but this is a guy I would not hire. He was wasting time for his own amusement. Never assume people know to do the research on existing solutions. Many developers would rather work on their own toy solutions while avoiding the actual unsolved problems in their domain

Sure, your mileage may vary and there are definitely bad apples, but my claim is that the vast majority of interviewers aren't looking for people who like reinventing wheels, but are rather trying to suss out the extent to which you can reason through a problem. So I think that's the charitable assumption to make.

Are you serious? For any algorithmic question, if googling does not turn up a great answer, you would need to be a genius if you could come up with one on the spot.

We had a CS class at UNH, a state university, where we learned how to express the complexity of an algorithm and then how to refactor algorithms to be less complex, when possible. Although we do not do this type of work for most of our jobs, it is not a stretch to think that half of people with a CS degree might have at one point known how to do this on the spot.

Yes, that’s exactly the kind of thing companies like Google are looking for.

Sure, but I would seriously question someone's Google fu, if it came to this.

My job often entails reasoning through a solution to a specific problem which is dissimilar enough from the general formulation of some problem that there isn't an obvious way to Google for an exact answer. It may take a genius to devise the best algorithm to solve some general problem, but it does not take a genius to reason through a decent solution to a specific problem using general knowledge and experience.

Except they don't just want a solution, they want a solution with certain performance characteristics. And they want it to be the solution with the best performance.

Which means what they're really saying is not "we want problem solvers". What they're really saying is "the bare minimum for entry level work here is being able to, in 30 minutes and on the spot, out-perform top-tier theoretical CS researchers".

Which in turn really boils down to "be a recent CS graduate who memorized this algorithm in advance so as to 'derive' it later on command".

That's reasonable, but at the same time, unless it's a top-secret clearance job, don't threaten me with doing web development on an air-gapped machine. We both know it's absurd, just don't do it.

> ok great, now say that you can't find any satisfying prior art for this on Google, how would you reason through your own solution?

So then I try and give them a O(n^3) solution (or something).

Of course this isn't accepted as there's a better O(n^2) solution, which can always be found by googling, and I fail the interview.

The "turtle and the hare" problem of finding a loop in a single linked list in O(n) time and O(1) memory is the perfect example. It's easy if you know the answer (or can google) but basically impossible if you don't.

What did the interviewer do when I said I couldn't do better than a hashmap? He laughed and said "not many can".

I’m not familiar with this one but have been thinking about it for a few minutes and think I have an answer (granted I think it will depend on language and OS whether it would work)

The gist of it is: walk the list and after each step, multiply the previous node’s pointer by negative one.

If the current node’s pointer is negative you’ve found a loop (because you colored it by inverting the pointer in a previous step).

Clean up by starting at the beginning and multiplying all pointers by negative one until you reach the last one you inverted. Then return your answer (true).

If you reach a null pointer there is no loop because you’ve gotten to the end of the list. Clean up by going through again and multiplying all the nodes by negative one. Then return your answer (false).

Your worst case running time is 2n (if there is no loop) which reduces to O(n) and you use O(1) memory because you’re coloring the list by using the already existing pointers in the list.