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(1)。

友人:友人いわく、これはEfficientではない。Bitを使うらしいよ。1,000,000のintegerをパースして、1が見つかったら、2Mbytesのメモリーの1つ目のBitをたてる、99が見つかったら2Mbytesのメモリーの99番目の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より大きい値が含まれている場合は対応できない。

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s