インタビューの質問:
100万台の車を収容できる駐車場で、空いている駐車場を見つける必要があります。スロットがどこにあるかについての条件はありません。つまり、駐車場には複数の入り口がある可能性があり、入り口の近くにスロットを見つけることは重要ではありません。問題は、どのようなデータ構造を使用する必要があり、さまざまな操作の複雑さがどの程度かということでした。
私は、100 万ビットのビット配列を使用することを提案しました。0/1 は使用済み/空きスロットであり、空きスポットを見つけるために、質問は最初のセット ビットを見つけることに変換されます。何台の車があるかなどについて何も仮定しないでください。つまり、ビット配列は疎または密の可能性があります。
巨大なビットマップでセットビットを見つける最速の方法は何ですか? スキームとして、バイナリ検索+単語ごとの効率的なffs()を提案しました。
100 万の 32 ビット整数には、約 4MB のメモリが必要です。だから私はあなたが空きスロットのリストを保持していると思います. 車が入るたびに、リストからアイテムを取り出して割り当てます。車が出発するたびに、解放されたスロット番号をリストに入れます。
リストの最後を操作するだけなので (したがって、これは実際にはスタックまたはLIFO構造として使用されます)、これにより、空きスロットの検索と空きスロットへの返却の両方で最適な O(1) パフォーマンスが得られます。州。未加工のメモリ チャンクを使用して低レベルでこれを行う場合は、リストの現在の末尾を示すポインタが必要になります。スロットを見つけると、そのポインターがデクリメントされ、その値が返されます。スロットを返すと、ポインターに割り当てられ、後でインクリメントされます。
後で追加の要件を追加することにした場合は、データを操作して、たとえばheapに変換することができます。0/1 ビットの大きなマップでは、このような拡張は不可能です。
あなたはこのように行くことができます：
最後の空きスロットのインデックスを変数に格納し、次の空きスロットを探すには、最初からビットマップをスキャンするのではなく、この値からスキャンします。
スロットを解放する必要がある場合は、それを最後のインデックスに割り当てます。
std::vector<bool>ビット配列にすることができるので、自分でビットを処理する必要はありません (bool は内部で int にパックされます)。
構造を導入できますmip-mapped：
``std::vector<bool>`` Bitmap;
``std::vector<bool>`` Bitmap2; // half-sized
``std::vector<bool>`` Bitmap4; // 1/4
``std::vector<bool>`` Bitmap8; // 1/8
// etc
上位レベルの配列のfree値は、下位レベルの配列に空きスロットがある状況に対応しています。二分探索を使用して、この構造をたどることができます。