intervista: Aggiungere una struttura di dati che ottimizza inserimento, cancellazione e la generazione valore casuale

Question

Suggerisci una struttura di dati che può ottimizzare tutte 3 sotto operazioni:

1. inserimento
2. eliminazione
3. restituire un valore casuale dal set di valori esistenti

Si supponga di inserire numeri interi/numeri.

Answer 1

dinamico Array + hashmap = O (1) per tutte le tre operazioni

• inserimento

accodamento alla coda di Array O (1), e aggiungere una coppia di valori-indice HashMap O (1).

• eliminazione

Trova l'indice per il valore HashMap O (1), cancellare dall'indice di matrice e scambiare l'ultimo elemento nell'alloggiamento O (1), e aggiornare il valore- coppia di indici per il (ultimo) (ultimo) O (1).

• ritorno casuale

generare un indice casuale per la matrice O (1).

Answer 2

O (1) in 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

(nota pop è O (1) da abbiamo pop dalla fine della lista)

Answer 3

Utilizzare una tabella hash con open addressing. Mantenere il fattore di carico tra α e β rimodellando se necessario. Per evitare oscillazioni, eseguire nuovamente il cambio su un valore compreso tra α e β. La maggior parte delle implementazioni di schemi di hash aperti richiedono che la tabella sia di dimensioni convenienti, come una potenza di due o un numero primo. I valori tipici di α e β potrebbero essere 0,25 e 0,75, con il fattore di carico di destinazione pari a 0,5.

Le tabelle di hash aperte sono le ricerche O (1) a meno che il fattore di carico non si avvicini a 1 e il ridimensionamento esponenziale sia ammortizzato O (1), quindi inserire è ammortizzato O (1). Il modo più semplice per gestire l'eliminazione è lazy-delete: gli elementi eliminati sono contrassegnati come eliminati ma non rimossi, quindi possono essere sovrascritti durante un inserimento. Di nuovo, il ridimensionamento esponenziale viene ammortizzato O (1) e l'operazione di eliminazione stessa dipende solo da una ricerca.

La selezione casuale ignora del tutto il meccanismo di hashing e prende solo pugnalate casuali nell'array sottostante fino a quando non trova un record non cancellato. Poiché il fattore di carico è almeno α, il numero previsto di punti di stabilizzazione è al massimo 1/α, nuovamente O (1).