次のような面接の質問を受けました:

40 億個の整数を含む入力ファイルが与えられた場合、ファイルに含まれていない整数を生成するアルゴリズムを提供します。メモリが 1 GB であると仮定します。メモリが 10 MB しかない場合に何を行うかを考えてみましょう。

私の分析：

ファイルのサイズは 4×10 ⁹ ×4 バイト = 16 GB です。

外部ソートを実行することで、整数の範囲を知ることができます。

私の質問は、ソートされた大きな整数セットで欠落している整数を検出する最良の方法は何かということです。

私の理解（すべての回答を読んだ後）：

32 ビットの整数について話していると仮定すると、2 ³² = 4*10 ^{9 個}の異なる整数が存在します。

^{ケース 1: 1 GB = 1 * 10 9} * 8 ビット = 80 億ビットのメモリがあります。

解決：

1 つの異なる整数を表す 1 ビットを使用すれば十分です。ソートは必要ありません。

実装：

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}