ソフトウェアのインタビューを受けました。質問の1つは、高度に最適化された方法で、insert、delete、getRandomの3つのメソッドを使用してデータ構造を設計することでした。インタビュアーは、新しいものを設計するためにデータ構造の組み合わせを考えるように私に頼みました。挿入はとにかく設計できますが、ランダムおよび削除の場合、特定の要素の位置を取得する必要があります。彼は私に、ソートに最小限の時間を要するデータ構造について考えるためのヒントをくれました。
どんな答えや議論も歓迎します....
データ構造に格納する要素tのタイプとします。elementsすべての要素を特定の順序で含まない拡張可能な配列を用意します。indicesタイプの要素をのt位置にマップするハッシュテーブルを用意しますelements。
e手段
eの最後に追加し、その位置を取得しますelementsi(e,i)を`インデックスに挿入しますeとは
iを見つけるeelementsindiceseの最後の要素fで上書きしますelementsindices：マッピングを削除して(f,indices.size())挿入します(f,i)peek、ではなくpop）は、単に整数iを描画して[0,elements.size()[を返すことelements[i]です。ハッシュテーブルがタイプの要素に適していると仮定すると、t3つの操作はすべてO（1）です。
データ構造に0または1つの要素がある場合に注意してください。
ここでは木がうまく機能するかもしれません。log（n）の挿入と削除を注文し、ランダムに選択することもlog（n）になります。ルートノードから開始し、各ジャンクションで子をランダムに選択します（子あたりのリーフノードの総数で重み付け）。葉。
並べ替えにかかる時間が最も短いデータ構造は、並べ替えられた配列です。
get_random（）は二分探索であるため、O（log n）です。
insert（）とdelete（）は、問題の要素を追加/削除してから、O（n log n）である、たとえば恐ろしいものに頼ることを含みます。
彼のヒントは貧弱だったと思います。あなたは悪い面接を受けていたのかもしれません。
私が感じているのは、赤黒木のようなバランスの取れたバージョンのツリーを使用できるということです。これにより、O（log n）の挿入と削除の時間が与えられます。ランダムな要素を取得するために、ツリー構造にある要素を追跡するための追加のハッシュテーブルを作成できる場合があります。
ヒープ（データ構造）の可能性があります