See also: Ron Paul as Vice President For Barack Obama http://ronpaulnewsblg.blogspot.com/2007/11/ron-paul-as-vice-president-for-barack.html |
> "What is the most efficient way to sort a million 32-bit integers"
Haha, great idea to ask him this question, eric! |
[Moved from "Obama visits Google" at http://blogoscoped.com/forum/115118.html]
http://www.sfgate.com/cgi-bin/article.cgi?f=/c/a/2007/11/15/MN5BTCBP4.DTL&tsp=1
Obama Pays Visit To Google
The Democratic presidential candidate pitches youth, technology during town hall in Mountain View.
Chronicle Breaking News 8:05 PM |
At what time is the funny question asked, anyone? |
Look at from 22:30/-41:20 when he finishes the question, the camera guy pops up and films the audience, and half way through jumps as if he saw something that shouldn't be on camera! Classic! |
Sorry for post again, but just after what I posted above, the quoted question is on. |
A couple of my friends went to one of his speech about a month ago. One of them (a girl) screamed out "I want to have a baby with you!" and then everyone was silent. :) |
I find it kind of interesting that nobody is posting a better answer to the sorting question. Come on guys, 80% Google should at least have users with an 80% answer :-)). Who can top Obama? |
WOOOOOOOOOOOOOOOOOW!!! If I was American, I would vote for... CHUCK NORRIS!
*** TRUE ad on US TV! *** http://www.youtube.com/watch?v=EjYv2YW6azE
Have fun! |
"What is the most efficient way to sort a million integers?"
"With a computer!"
http://betathoughts.blogspot.com/2007/02/google-does-impossible.html
Seriously, I think with this question Google wants to see how you approach the answer, which would probably ideally include a lot of computer history and discussion of pros and cons of different sorting algos, showing you learned your basic computer science. Perhaps they even want to test if you resort to arrogance, which might get you minus points for bad team play (e.g. blurting out "that is too easy, are you serious?"). Personally, with the programming languages I use (e.g. writing a web-based game, not a mobile screensaver in assembler!) I expect the programming language itself to dynamically figure out how many numbers are in the set and what size they are to then pick the best sorting algo for me completely automated, with the additional pro that when processor technology changes or an optimized software is released or the numbers in my software change from a million integers to a thousand floats it can all adjust to my program dynamically, increasing its speed over time, without me having to maintain it a bit – because I as programmer didn't provide specifics of how I wanted it to perform, but rather, what I wanted it to achieve. Not to say you don't need both kinds of programmers (e.g. those caring about the hardware), you definitely do :) |
Yes, but Philipp, you aren't going to work for Google. ;-) At Google, it would be terribly inefficient to invent a whole language just for the things Google uses it for. It's much better to optimize on the spot (of course, once you've done profiling and see that you really _do_ have to optimize).
As for the question, since they say it's integers and specify the number of bits, probably they want to hear the radix sort as the best answer (with bonus points if you realize that by 32-bit integers they probably mean _signed_ ones, and you first filter through sign bit, then sort nonnegatives and negatives separately, without resorting to two's complementation). Or maybe even a pigeonhole sort, since the number of possible items (about 4 billion) is not _that_ much bigger than a million, the number of actual items you have. ;-)
(Disclaimer: I was once offered a job at Google, though that probably wasn't serious.;) |