3

この質問はインタビューで尋ねられました：

整数の最終範囲および連続範囲からの整数データを処理するデータ構造を提案および実装します。O(1)データ構造は、挿入操作と削除操作もサポートする必要がありますfindOldest(データ構造に挿入された最も古い値)。

重複は許可されていません (つまり、何らかの値がすでに内部にある場合、もう一度追加しないでください)。

また、必要に応じて、いくつかの init を初期化に使用できます。

値が内部にあることを示す 1/0 の配列 (範囲サイズとしてのサイズ) を使用するソリューションを提案しました。挿入/削除を解決し、O(range size)初期化が必要です。

findOldestしかし、与えられた制約で実装する方法がわかりません。

何か案は？

PS 動的割り当ては許可されていません。

4

1 に答える 1

3

あなたの質問を誤解していたら申し訳ありませんが、私が得た感覚は

  • 検討している値の固定範囲があります ([0, N) など)。
  • 重複のない挿入と削除をサポートする必要があります。
  • findOldest をサポートする必要があります。

1 つのオプションは、長さ N の配列を作成することです。各エントリには、ブール値の「アクティブ」フラグとポインターが格納されます。さらに、各エントリには二重にリンクされたリスト セルがあります。直感的に、挿入順序を格納するリンク リストをスレッド化したビットベクターを構築しています。

最初は、すべてのビットが false に設定され、ポインターはすべて NULL です。挿入を行うときは、適切なセルのビットを true に設定し (既に設定されている場合はすぐに戻ります)、この新しいセルを追加して要素の二重リンク リストを更新します。これには O(1) の時間がかかります。ステップを実行するfindOldestには、最も古い要素へのポインターを照会するだけです。最後に、削除手順を実行するには、問題の要素のビットをクリアして、二重リンク リストから削除し、必要に応じてヘッド ポインターとテール ポインターを更新します。

全体として、すべての操作には O(1) の時間がかかり、動的割り当ては実行されません。これは、リンク リスト セルが配列の一部として事前に割り当てられているためです。

お役に立てれば！

于 2013-11-05T21:44:35.013 に答える