But I kind of miss the old Google where you DID need to be a genius. I interviewed with Google probably around the year 2000, and there was a genuinely hard ball packing problem. I'm kind of curious what happened. Anyone who could answer that question would find this one trivial -- and not just the dynamic programming solution, but the O(log n) one which apparently no one at Google (or even applying to Google) noticed.
What I hate about Google is that everyone there still thinks they're a genius. In 2000, it felt okay, since for the most part, they actually were. Today, it's kind of obnoxious.