Interview Question for Senior Software Engineer at Google:

It's a standard bipartite matching problem, aka assignment problem. Solutions are standard as well, but none of them are easy. They cannot be figured out during the interview, you just have to know them. These types of questions just make me wonder about those who ask those questions. What exactly do they test? How long have you been from college where you studied Ford-Fulkerson maximum flow algorithm, or Hungarian algorithm (both applicable to the problem)? Show me an interviewer who can answer this question, unless he or she specially prepared it for an interview, thus wasting his productive time at work?

And, by the way, trying to use textbook algorithms for real life assignment problems would lead to the results that are mediocre at best. Commercial-strength packages have lots of optimizations for special cases of input data. For instance, the Linux qsort command uses 3 different sorting algorithms depending on the size of input data.