インタビュー：挿入、欠失及びランダム値発生

Question

を最適化するデータ構造を提案する操作の下にあるすべての3を最適化することができるデータ構造を提案する：

1. 挿入
2. 削除
3. 戻りセットからランダムな値既存の値の

あなたは、整数/数字を入れていると仮定します。

Answer 1

ダイナミックアレイ+ハッシュマップ=すべての3つの操作のためにO（1）

• 挿入アレイO（1）の尾部に

追加、およびハッシュマップする値インデックスのペアを追加しますO（1）。

• 削除

O（1）は、アレイ内のインデックスによって削除スロットO（1）に最後の要素を交換ハッシュマップ内の値によってインデックスを検索し、付加価値を更新します（使用されるべき）最後の要素O（1）のためのインデックス対。

• 戻りランダム

アレイO（1）ランダムインデックスを生成。

Answer 2

O（1）Pythonで：

from collections import defaultdict 
from random import choice 

class DataStructure(list): 
    def __init__(self): 
     self.values = [] 
     self.locations = defaultdict(list) 

    def add(self, val): 
     i = len(self.values) 
     self.locations[val].append(i) 
     self.values.append(val) 
     assert self.values[i] == val 

    def delete(self, val): 
     locations = self.locations[val] 
     if locations: 
      i = locations.pop() 
      self.values[i] = self.values[-1] 
      self.values.pop() 

    def random(self): 
     return choice(self.values) 

ds = DataStructure() 

ds.add(3) 
ds.add(5) 
print ds.random() 
print ds.random() 
print ds.random() 
print ds.random() 
ds.delete(5) 
print ds.random() 
ds.delete(3) 

""" 
5 
3 
3 
5 
3 
""" 

See Time Complexities of List and Dict operations to Confirm

（ポップに注意してくださいO（1）私たちは、リストの末尾からポップされているので）

Answer 3

とハッシュテーブルを使用しますopen addressing。必要なときに焼き直しでαとβ間の負荷率を保管してください。振動を避けるために、αとβの間にいくつかの値に焼き直し。ほとんどのオープンハッシュスキームの実装では、2の累乗や素数のようなテーブルが便利なサイズである必要があります。 αとβの典型的な値は、目標負荷率が0.5であると、0.25と0.75であるかもしれません。

オープン負荷率が1に近づき、そして指数リサイズがO（1）償却されるので、インサートはO（1）償却されていない限り、ハッシュテーブルはO（1）ルックアップである対処しました。削除処理するための最も簡単な方法があるレイジー削除：削除された要素が削除済みとしてマークされなく削除ので、彼らは挿入時に上書きすることができます。ここでも指数関数的なサイズ変更はO（1）で償却され、削除操作自体はルックアップにのみ依存します。

ランダム選択は、ハッシュメカニズムを完全にバイパスし、削除されていないレコードが見つかるまでランダムなスタブを基本配列にとります。負荷率が少なくともαであるため、予想されるスタブ数は最大で1/αであり、再びO（1）です。