[解決済み] 電話番号1000件を保存する最も効率的な方法

質問

これはgoogleのインタビューの質問です。

10桁の電話番号が約1000個格納されています。各電話番号の最初の5桁は、千の番号間で同じであると仮定することができます。あなたは、次の操作を実行する必要があります。 a. 与えられた番号が存在するかどうかを検索する。 b. すべての数字を表示する

これを行うための最も効率的なスペースセーブの方法は何ですか？

私はハッシュテーブルと答え、その後ハフマンコーディングと答えましたが、面接官は私が正しい方向に進んでいないと言いました。助けてください。

suffix trieを使えばいいのでしょうか？

理想的には、1000個の数字を格納するのに4バイトかかるので、全部で4000バイトかかることになります。定量的には4000バイトまで減らしたいのですが、これは面接官から説明されたことです。

どのように解決するのですか？

ここで、改善策として aix の回答 . データ構造に3つの層(quot;layer")を使うことを考えます。1つ目は最初の5桁（17ビット）の定数で、ここから先は各電話番号には残りの5桁だけが残ります。この残りの5桁を17ビットの2進整数と見なし、以下のように格納する。 k を、ある方法と17 - を使って格納します。 k = m を別の方法で求めると k を最後に決定し、必要なスペースを最小にします。

まず、電話番号(すべて10進数5桁に縮小)を並べ替えます。次に、最初の m ビットがすべて 0 である電話番号がいくつあるか、最初の m のビットは最大で 0...01 であり、いくつの電話番号に対して、最初の m のビットは最大で0...10、などなど、最初の m ビットが1...11である電話番号の数まで、この最後のカウントは1000(10進数)です。このとき、2^ m このようなカウントがあり、各カウントは最大で1000です。最後の 1 つを省略すると (どうせ 1000 と分かっているので)、これらの数をすべて連続したブロックに格納することができ、 (2^ m - 1) * 10ビットの連続したブロックに格納することができます。(10 ビットは 1024 未満の数を格納するのに十分です)。

最後の k ビットはメモリに連続的に格納されます。 k が例えば7である場合、メモリのこのブロックの最初の7ビット（ビット0から6）は最初の（縮小された）電話番号の最後の7ビットに対応し、ビット7から13は2番目の（縮小された）電話番号の最後の7ビットに対応するなど、さまざまです。これには、1000個の*. k のビットが必要で、合計17 + (2^(17 -) k ) - 1) * 10 + 1000 * k で最小の11287となります。 k = 10. したがって、すべての電話番号をceil(11287/8)=1411バイトで格納することができます。

というのは、1111111(2進数)で始まる最も小さい数字は130048であり、10進数では5桁しかないからです。これにより、メモリの最初のブロックからいくつかのエントリを削除することができます：2^の代わりに m - 1カウントの代わりに、ceil(99999/2^)だけが必要です。 k ). つまり、式は次のようになります。

17 + ceil(99999/2^) k ) * 10 + 1000 * k

の両方で最小の 10997 を達成するのは驚くべきことです。 k = 9 と k = 10、または ceil(10997/8) = 1375 bytes です。

ある電話番号が集合の中にあるかどうかを知りたい場合、まず最初の5桁の2進数が、保存してある5桁と一致するかどうかを調べます。次に、残りの 5 桁を分割して、その先頭の m =7ビット（これは、例えば m -というビット数 M ) とその下位の k =10ビット(数値 K ). ここで、数 a が1番目の電話番号となる縮小電話番号の[M-1]を求める。 m が最大で M - 1であり、その数は a が1である縮小電話番号の[M]。 m が最大で M は、両方とも最初のブロックのビットからです。ここで a [M-1]番目と a の [M] 番目のシーケンス k が見つかるかどうかを確認するために、メモリの 2 番目のブロックのビットに K 最悪の場合、このような配列は 1000 個あるので、バイナリサーチを使用すれば O(log 1000) 回で終了します。

1000個の数字をすべて表示するための疑似コードは以下の通りです。 K をアクセスします。 k -というメモリの最初のブロックのビット・エントリ。 a [K]とし M 'の m -として、2 番目のメモリブロックのビットエントリを指定します。 b [M]とします（いずれも書き出すのが面倒なビット演算が必要です）。最初の5桁は数字で c .

i := 0;
for K from 0 to ceil(99999 / 2^k) do
  while i < a[K] do
    print(c * 10^5 + K * 2^k + b[i]);
    i := i + 1;
  end do;
end do;

のバウンダリケースで何か問題が発生したのかもしれません。 K = ceil(99999/2^ k ) がありますが、これは修正するのが簡単です。

最後に、エントロピーの観点から、10^5 より小さい 10^3 の正の整数のサブセットを ceil(log[2](binomial(10^5, 10^3)) = 8073 以下で保存することは不可能です。最初の5桁に必要な17個を含めても、10997 - 8090 = 2907ビットのギャップがあるのです。それでも比較的効率的に数字にアクセスできる、より良いソリューションがあるかどうかを確認するのは、興味深い挑戦です!