Coppie di stringhe in ordine inverso in un elenco di oltre un milione di stringhe?

Question

chiesto di recente durante alcune intervista che "Come trovare retro di tutte le stringhe, se esiste in un elenco di più di milioni di stringhe?

Per esempio str [1] = 'abc', ho bisogno di verificare la presenza di 'CBA' esattamente, non anagrammi.

Metodo 1. Conservare tutte le stringhe in un hashset, iniziano l'attraversamento dalla prima stringa e controllare per la forma invertita esiste in HashSet. se sì, allora accoppiano altro passaggio al successivo elemento.

Puoi suggerire qualche metodo se la memoria è il vincolo?

Answer 1

È possibile utilizzare uno Bloom Filter che ti dirà se una stringa esiste già all'interno di una tabella hash come struttura, ma ogni bucket è solo 0 o 1, quindi viene utilizzato uno spazio molto piccolo.

Esattamente 1 000 000 bit == 125 KB

Answer 2

Se consentito, si potrebbe sul posto di ordinamento le corde in modo che quando si guarda il rovescio di una stringa si può fare una ricerca binaria.

Answer 3

Per prima cosa avrei cancellato le stringhe utilizzando un hash indipendente dalla direzione. Potrebbe trattarsi di una semplice somma di caratteri, sebbene esistano sicuramente schemi migliori che eliminerebbero l'hash da entrambe le estremità. E per "addolcire l'affare" si può aggiungere la lunghezza della stringa al valore hash, o altrimenti incorporarla nell'hash.

Quindi, quando le stringhe sono suddivise in gruppi di hash identici, confrontare la "mano lunga".

Si noti che, utilizzando questo schema o quello in cui si utilizza semplicemente un hash dipendente dalla direzione in avanti o all'indietro, la cosa da fare è non inserire immediatamente la stringa nel set di hash, ma piuttosto controllarla (con l'inverso hash, se necessario) prima, e se ottieni una corrispondenza (e il confronto lungo successivo è vero) rimuovi la stringa già cancellata e abbina i due. La seconda stringa non entra mai nel set e, se tutte le stringhe hanno al massimo corrispondenze, avresti sempre e solo 500.000 voci nel set di hash e, se le stringhe fossero casuali, probabilmente più vicino a 250.000 (non mi sono seduto giù per capire le probabilità).

Quindi è necessario un solo passaggio attraverso il set di stringhe per fare tutto.

Answer 4

Con " memoria come un vincolo", allora non avrei nemmeno andare a fare una HashSet (che, per quanto ne so anche rimuovere le corde duplicati nella lista originale) perché sarete utilizzando la struttura aggiuntiva di un HashSet che prende un po 'di memoria.

L'ordinamento, non migliorerebbe l'utilizzo della memoria.

Vorrei utilizzare l'elenco originale (che è già presente, quindi non verrà utilizzata memoria aggiuntiva) + una variabile intera di 3 byte per iterare l'elenco. 3 byte possono iterare su una lista di 2^24 = 16777216 stringhe

Con "memoria come un vincolo" Vorrei andare per 2 cicli for. Penso che uno pseudocodice C-Like sarà più facile da capire che il mio semplice inglese.

Note:

1. Dall'esempio fornito in questione, non è in realtà un elenco ma una matrice, quindi opererà sulla struttura come se fosse un array
2. La questione non è chiaro se abbinare questo "abc", "def", "cba", "abc". Accoppierò il primo "abc" con "cba" e anche quel "cba" con "il secondo" abc "(l'intenzione non è chiara nella domanda)
3. Suppongo che non possiamo modificare l'elenco originale

Qui è il minimo codice memoria consumo posso pensare:

// "list" holds the original list (array) 
for (int i = 0; i < length(list) - 1; i++) { 
    for (int j = i + 1; j < length(list); j++) { 
     if (list[i] == reverse(list[j])) { 
      print(list[i] + " reversed is " list[j]) 
     } 
    } 
} 

quanto riguarda l'utilizzo della memoria, questa soluzione avrà 2 variabili intere (solitamente 4 byte ciascuno) + lista originale, che presumo noi non può sbarazzarsi di.

Per quanto riguarda la CPU usag e (in realtà, non rilevante in base alla domanda), la quantità di volte in cui le stringhe verranno invertite sarà: (N * (N + 1))/2 dove N è la lunghezza della lista

Answer 5

Puoi scegliere HashTable e usa i bucket per ridurre il conflitto di hash. Quello che ora dobbiamo fare per una specifica stringa di query è semplicemente invertirlo, cancellarlo e trovarlo nella HashTable anziché attraversare dall'inizio alla fine.

Answer 6

Questo è jus mio parere:

vorrei creare un hash con

key = carattere

value = Elenco di stringa che inizia con quel carattere

• Ora avvia un ciclo all'interno del quale è necessario iniziare dalla prima stringa.
• invertire
• Prendere il primo carattere e la ricerca di quella chiave nella hash
• quindi nel valore di ciò, esso contiene l'elenco delle stringhe e trovare la stringa in tale elenco