Gパズル

ランチタイムにパズルの話題をする事がたまにある。今日まで知らなかったが、Googleでは下記のパズルを聞くらしい。有名すぎてもう使われていないと思うが。

“How do you determine good ways of sorting one million 32-bit integers in two megabytes of RAM?”

CEOのEric Schmidtは大統領候補にこのパズルを聞いたらしい。参照。

ランチ中の僕の答え：ソートの問題には反射的にQuickSortと答えてしまう。ComplexityはO(n log n)だし、Memory UsageはO(１)。

友人：友人いわく、これはEfficientではない。Bitを使うらしいよ。1,000,000のintegerをパースして、１が見つかったら、2Mbytesのメモリーの１つ目のBitをたてる、９９が見つかったら2Mbytesのメモリーの９９番目のBitをたてる、それをone million times繰り返えせば、O(n)でソートできると言っていた。

家に帰って考えてみた(確かめてみた)：32-bitのIntegerだから、単純化して整数のみを考えるとIntegerの値は0から2の32乗の値(4,294,967,296) 、使えるメモリーは 2Mbytesだからビットで考えると2*1024*1024*8 = 16,777,216 bits。よって友人が言っていた方法では16,777,216より大きい値が含まれている場合は対応できない。

現状：多分何かトリックがあるのだと思う。考案中。