Hashing 100 verschiedene Werte der Bereich 1 Milliarde

Question

Ich wurde vor kurzem diese Frage in einem Interview gestellt. Ich habe eine Reihe von n Elementen. Das Array hat nur 100 verschiedene Werte. Ich muss die Anzahl der Vorkommen jeder Zahl ausdrucken.

1<=n<=10^6 
1<=A[i]<=10^12 

Erwartete Speicherkomplexität war O (k), wo k die Anzahl der verschiedenen Werte in dem Array ist.

Zum Beispiel 1 2 3 2 1 4 3 2 4 2 3 1 2; hier k ist 4. Zuerst schlug ich vor, Karten in stl zu verwenden, aber er wollte meine eigene Datenstruktur implementieren. Dann schlug ich vor, sortierte Insert für jedes Element wie in einem binären Suchbaum zu verwenden, aber das würde eine Zeitkomplexität von O (nlogn) ergeben. Er wollte eine O (n) -Lösung. Ich habe versucht, an irgendeine Hash-Funktion zu denken, aber ich konnte mir keine solche Funktion einfallen lassen. Ich habe auch versucht, an die Datenstruktur zu denken, aber wieder muss ich jede Ziffer jeder Zahl abtasten, was wiederum eine O (nlogn) -Komplexität ergibt. Was könnte ein möglicher Ansatz sein, um dies zu lösen?

Answer 1

Die Hash-Tabelle garantiert nicht die theoretische Komplexität von O (n * k). Aber es ist ziemlich einfach, einen solchen zu machen.

Zuerst müssen wir einige Annahmen über Werte Wahrscheinlichkeitsverteilung machen - lassen Sie es einheitlich sein (oder wir brauchen einige spezialisierte Hash-Funktion).

Als nächstes wählen wir Hash-Tabelle Größe, sagen wir 201 Einträge (so wird es weniger als 50% voll sein).

Als nächstes lass die Hash-Funktion nur hash(A[i]) = A[i] mod 201 sein.

Und dann verwenden Sie Open-Adressierung Hash-Tabelle H [] mit 201 Einträgen Paare: A [i] oder NULL; Häufigkeitswert

Answer 2

Ich denke, dass eine Hash-Tabelle eine gute Lösung dafür ist, aber ich stelle mir vor, der Interviewer hat erwartet, dass Sie Ihre eigene Hash-Tabelle erstellen.

Hier ist eine Lösung, die ich in Python entwickelt habe. Ich verwende mod 100 als meine Hash-Funktion und Separate chaining verwenden, um mit Kollisionen umzugehen.

import random 

N = random.randint(1, 10**6) 
K = 100 
HASH_TABLE_SIZE = 100 

distinct = [random.randint(1, 10**12) for _ in range(K)] 
numbers = [random.choice(distinct) for _ in range(N)] 

hash_table = [[] for _ in range(HASH_TABLE_SIZE)] 

def hash(n): 
    hash_key = n % HASH_TABLE_SIZE 
    bucket = hash_table[hash_key] 
    for value in bucket: 
     if value[0] == n: 
      value[1] += 1 
      return 
    bucket.append([n, 1]) 

for number in numbers: 
    hash(number) 

for bucket in hash_table: 
    for value in bucket: 
     print('{}: {}'.format(*value)) 

EDIT

den Code ein Bit Erklären:

My Hash-Tabelle ist eine 100-Element-Array. Jeder Eintrag im Array ist eine Liste von (number, count) Einträgen. Um eine Zahl zu hashen, nehme ich den Wert modulo 100, um einen Index in das Array zu finden. Ich scanne die Zahlen, die sich bereits in diesem Bucket befinden, und wenn einer von ihnen mit der aktuellen Nummer übereinstimmt, inkrementiere ich seine Anzahl. Wenn ich die Nummer nicht finden, ich habe einen neuen Eintrag in die Liste mit der Anzahl und einem Anfangszahl von 1.

Optisch anhängen, sieht das Array Art wie folgt aus:

[ 
    [ [0, 3], [34500, 1] ] 
    [ [101, 1] ], 
    [], 
    [ [1502, 1] ], 
    ... 
] 

Beachten Sie, dass Bei Index n entspricht jeder im Bucket gespeicherte Wert n (mod 100). Im Durchschnitt gibt es nur einen Wert pro Bucket, da es bis zu 100 verschiedene Werte und 100 Elemente im Array gibt.

Um die endgültigen Zählungen auszudrucken, müssen Sie nur durch das Array und jeden Eintrag in jedem Bucket gehen und sie ausdrucken.

EDIT 2

Hier ist eine etwas andere Implementierung, die anstelle Open addressing mit linearer Sondierung verwendet. Ich glaube, ich bevorzuge diesen Ansatz.

hash_table = [None] * HASH_TABLE_SIZE 

def hash(n): 
    hash_key = n % HASH_TABLE_SIZE 

    while hash_table[hash_key] is not None and hash_table[hash_key][0] != n: 
     hash_key = (hash_key + 1) % HASH_TABLE_SIZE 

    if hash_table[hash_key] is None: 
     hash_table[hash_key] = [n, 1] 
    else: 
     hash_table[hash_key][1] += 1 

for number in numbers: 
    hash(number) 

for entry in hash_table: 
    print('{}: {}'.format(*entry)) 

HINWEIS: Dieser Code wird scheitern wenn es tatsächlich mehr als 100 verschiedene Zahlen sind. (Es wird für immer hängenbleiben und versuchen, einen offenen Punkt im Array zu finden.) Es wäre schön, diesen Zustand zu erkennen (z. B. wenn Sie eine ganze Runde im Array gelaufen sind) und eine Ausnahme auslösen.

Answer 3

Eigentlich irren Sie sich, der Trie würde Ihnen O(N) Komplexität geben.

Eine Operation zum Einfügen/Suchen/Löschen eines Trie erfordert O(L) Zeit, wobei L die Länge der in diesen Trie geschobenen Strings ist. Glücklicherweise fügen Sie nur Zahlen ein, die nicht größer als 1 Billion sind, was bedeutet, dass L nicht größer ist als log(10^12) (Logarithmusbasis hängt vom Zählsystem ab, das Sie in diesem Trie verwenden. Ich persönlich würde 256 oder 65536 auswählen, je nachdem welcher Teil eines ganzen Systems spielt diese Struktur).

Zusammenfassend benötigen Sie O(N) * O(log(10^12)), was O(N) durch die Definition von O() entspricht.