I agree with you on the unnecessary puzzle solving. I don't even solve Sudoku. How can I even come up with a reasonable solution in 45 minute? The only puzzle I ever solved with C++ and Java was minesweeper and it took me a month in each language. I do think algorithm design problems like fitting 1 million 8 digits into 1 M ram is an OKAY question. Google's scale is big, and they want to test you how quickly you can arrive an OKAY solution in 45 minutes, even if it's wrong.
NP-complete problems aren't impossible, they just get very computationally expensive the bigger they get.
OP would only be rich & famous if they had developed an algorithm that solved minesweeper in polynomial or better time. (i.e., a time complexity on the order of O(n^k), where k is some constant)
Many NP-Complete problems are trivially solvable, just not trivially solvable in an efficient manner. - like the Travelling Salesman Problem. You can just try every possible combination. It's not fast, but it works.
Exactly what Yen said. People generally say "solve" to some sizes of the problem,. Obviously it isn't hard to solve a 4x4 minsweeper... maybe I need to rephrase: "I wrote a minesweeper game..."
The article refers to Google developer relations (where I previously worked). Google developer relations does expect people to come from a deep technical background as there's generally a much greater emphasis on support and high-touch collaboration than the traditional developer evangelism role. (Hence, the job titles are "developer advocate" and "developer programs engineer" instead of "developer evangelist".) So programming questions are fair game, if not the only game.
That's fine for a programming position, but they apparently (from the article, not personal experience) ask these type of questions to more than just programmers.
