> I had the same question you mention. "This is a problem a paper was written on, are you expecting me to derive a whole paper from first principles in half an hour, or are you expecting me to have seen it before? If it's the latter, why not let me Google, as I normally would?"
> I feel that saying "I would solve this problem with <algorithm>" should be good enough, and if I'm asked to implement it, I should be able to copy paste the Wikipedia pseudocode and start converting.
Long ago, milo.com posted a challenge to codeeval.com (both websites now dead) which turned out to be an example of the "assignment problem". That is, given a set X, another set Y, and a payoff function f(x,y), assign each element y in Y to exactly one element x in X such that the total payoff from all assignments is maximized.
I tried to solve it, realized I didn't know how, and was eventually able to look up the solution in a couple of papers. There is an algorithm called "the Hungarian algorithm" which will do it.
So I wrote up the Hungarian algorithm and sent it in. This was good enough to get a phone interview with the company.
I tried to prepare for the screen by going over the Hungarian algorithm to the point that I could myself give the proof that it correctly solved the problem. This was fun. But in the phone interview, it was barely mentioned at all. According to the interviewer, I passed that step by just mentioning the name "Hungarian algorithm".