Questa è una domanda di intervista che ho incontrato diverse volte e non sono sicuro di come risolverlo, dato che mancano quattro numeri. Ho familiarità con gli algoritmi per trovare uno o due numeri mancanti, ma non vedo un modo per generalizzare uno di loro a quattro.
Che si tratti di un'intervista o di un lavoro effettivo, la tua priorità principale deve essere una soluzione di lavoro che abbia senso per te . Che di solito significa che dovresti offrire la prima soluzione che ti viene in mente che è semplice e facile per tu spiegare.
Per me, ciò significa che ordina i numeri e scansiona gli spazi vuoti. Tuttavia, lavoro su sistemi aziendali e app web. Non mi diverto con i bit, e non voglio che la mia squadra!
Se stai intervistando per un lavoro di basso livello, più vicino al metallo, "l'ordinamento" verrà probabilmente raggiunto con gli sguardi vuoti. Vogliono che tu sia a tuo agio nei pensieri sui bit e così via. La tua prima risposta dovrebbe essere: "Oh, userei una bitmap". (O array di bit o bit impostato.)
E poi, in entrambi i casi - anche se dai la soluzione "sbagliata", se il tuo intervistatore (o il tuo capo!) lo preme , puoi suggerire alcuni miglioramenti o alternative, concentrandoti sul gestore specifica area di interesse.
O(n*log(n)) . (O O (n) per un ordinamento con bucket intero!) BitSet / BitMap / BitArray ) BitArray per contrassegnare i "numeri trovati". E poi cerca 0 . BitArray / BitSet (per trovare 0 ). Questo è O(n) , penso! O qualsiasi altra cosa.
Affronta le preoccupazioni che hai effettivamente. Per prima cosa risolvi il problema, usando soluzioni ingenue, se necessario. Non sprecare il tempo di tutti a risolvere problemi che ancora non esistono.
Poiché si tratta di un file, presumo che sia consentito effettuare più passaggi. Prima creare una matrice di 256 contatori, scorrere il file e per ogni numero incrementare il contatore indicizzato come il primo byte del numero. Quando hai finito, la maggior parte dei contatori dovrebbe essere a 2 ^ 24, ma da 1 a 4 contatori dovrebbe avere valori più bassi. Ognuno di questi indici rappresenta un primo byte di uno dei numeri mancanti (se ci sono meno di 4 è perché più numeri mancanti condividono lo stesso primo byte).
Per ciascuno di questi indici, crea un altro array di 256 contatori e fai un secondo passaggio sul file. Questa volta, se il primo byte è uno dei valori precedenti, incrementa un contatore nel suo array in base al byte secondo . Quando hai finito, cerca di nuovo i contatori inferiori a 2 ^ 16, e avrai il secondo byte dei numeri mancanti, ciascuno corrispondente al primo byte.
Ripeti per il terzo byte (nota che hai bisogno di un massimo di 4 matrici per ogni passaggio, anche se ogni byte può essere seguito da un massimo di 4 byte diversi) e per il quarto byte, e hai trovato tutte le numeri mancanti.
Complessità temporale - O(n * log n)
Complessità dello spazio - costante !
In realtà, ho considerato n=2^32 il parametro, ma anche il numero di numeri mancanti k=4 è un parametro. Assumendo k<<n questo significa che la complessità dello spazio è O(k) .
Solo per divertimento (e perché attualmente sto cercando di imparare Rust) l'ho implementato in Rust: link . Ho scelto di avere una rappresentazione testuale, dal momento che su uno lo eseguirà con ~ 2 ^ 32 numeri ...
Se questo fosse Java, potresti usare un BitSet. Bene, due di loro, perché non riescono a contenere tutti i numeri a 32 bit. Codice scheletrico, forse buggy:
BitSet bitsetForPositives = new Bitset(2^31); // obviously not 2^31 but you get the idea
BitSet bitsetForNegatives = new Bitset(2^31);
for (int value: valuesTheyPassInSomehow) {
if ((value & 0x80000000) == 0)
bitsetForPositives.set(value );
else
bitsetForNegatives.set(value & ~0x80000000);
}
Quindi usa BitSet.nextClearBit() per trovare chi manca.
Nota aggiunta molto dopo:
Si noti che con questo algoritmo, è abbastanza facile eseguire la parte che richiede tempo in parallelo . Supponiamo che il file originale sia stato suddiviso in quattro parti approssimativamente uguali. Assegna 4 coppie di BitSet (2 GB, ancora gestibili).
Mi aspetto che I / O sia ancora il passo limitatore di velocità, ma se magicamente tutti i numeri fossero in memoria potresti davvero accelerare le cose.
Questa domanda può essere risolta usando una serie di bit (vero / falso). Questa dovrebbe essere la struttura più efficiente per contenere le risposte per tutti i numeri usando l'indice dell'array per stabilire se quel particolare numero è stato trovato.
C #
var bArray = new BitArray(Int32.MaxValue);
//Assume the file has 1 number per line
using (StreamReader sr = File.OpenText(fileName))
{
string s = String.Empty;
while ((s = sr.ReadLine()) != null)
{
var n = int32.Parse(s);
bArray[n] = true;
}
}
Quindi basta scorrere l'array e per quei valori che sono ancora falsi non sono nel file.
Potresti suddividere il file in blocchi più piccoli, ma sono stato in grado di allocare un array di dimensione massima int32 (2147483647) sul mio laptop 16.0 con Windows 7 (64 bit).
Anche se non ero in esecuzione a 64 bit, potevo allocare array di bit più piccoli. Avrei pre-elaborato il file creando un insieme di file più piccoli ciascuno con un intervallo di [0-64000] [64001-128000], numeri ecc. Che sarebbero adatti per le risorse ambientali disponibili. Passare attraverso il file grande e scrivere ogni numero nel file set corrispondente. Quindi elaborare ciascun file più piccolo. Ci sarebbe voluto un po 'di più a causa della fase di pre-elaborazione, ma questo avrebbe aggirato i limiti delle risorse se ci fossero risorse limitate.
Poiché questa è una domanda dell'intervista, mostrerei all'intervistatore una certa comprensione dei vincoli. Quindi, cosa significa "tutti i numeri possibili"? È davvero 0 ... 2 < (32-1) come tutti indovinano? Le solite architetture a 32 bit possono funzionare con molti più di soli numeri a 32 bit. È solo una questione di rappresentazione, ovviamente.
È da risolvere su un sistema a 32 bit, o è piuttosto una parte della restrizione sui numeri? Ad esempio, un tipico sistema a 32 bit non sarà in grado di caricare il file nella RAM in una sola volta. Vorrei anche ricordare che un sistema a 32 bit spesso non è in grado di avere un file contenente tutti i numeri a causa della limitazione delle dimensioni del file. Bene, a meno che non abbia una codifica intelligente, come "Tutti i numeri tranne quei quattro", nel qual caso il problema è risolto banalmente.
Ma se vuoi veramente capire la domanda come "Dato un file con tutti i numeri da 0 ... 2 ^ (32-1) tranne alcuni, dammi quelli mancanti" (e questo è un grande if !), quindi ci sono molti modi per risolverlo.
Insignificante ma non fattibile: per ogni numero possibile, scansiona il file e verifica se è presente.
Con 512 MB di RAM e file pass-through: contrassegna ogni numero (= bit impostato in quell'indice) letto dal file, quindi passa la RAM una volta e visualizza quelli mancanti.
Un approccio facile da ricordare e facile da articolare in un'intervista sarebbe utilizzare il fatto che se si guardano tutti i numeri in N bit, ogni bit verrà impostato esattamente a metà di tali valori e non impostato in l'altra metà.
Se si itera su tutti i valori nel file e si mantengono 32 conteggi dei valori alla fine, si otterranno 32 valori che sono esattamente (2 ^ 32/2) o leggermente inferiori a quel valore. La differenza che il massimo (2 ^ 32/2) e il totale ti danno i bit totali impostati in ciascuna posizione dei valori mancanti.
Una volta ottenuto ciò, è possibile determinare tutti i possibili set di 4 valori che potrebbero dare quei totali. Detto questo, puoi quindi controllare nuovamente i valori nel file controllando eventuali valori che fanno parte di tali combinazioni. Quando ne trovi uno, le combinazioni contenenti quel valore vengono eliminate come possibilità. Una volta rimasta una sola combinazione possibile, hai una risposta.
Ad esempio usando un nibble, hai i seguenti valori:
1010
0110
1111
0111
1101
1001
0100
0101
0001
1011
1100
1110
I bit totali impostati in ogni posizione sono:
7867
Sottraendo quelli da 8 (4 ^ 2/2) otteniamo:
1021
Il che significa che ci sono questi seguenti possibili set di 4 valori:
1000
0000
0011
0010
1010
0001
0010
0000
(perdonami se ne ho perso qualcuno, lo faccio solo di vista)
E poi guardando nuovamente i numeri originali, troviamo subito 1010, il che significa che il primo set era la risposta.
Supponendo che il file sia ordinato aumentando i numeri:
Assicurati che contenga effettivamente i numeri (2³²-4).
Ora se il file fosse completo (o se i 4 numeri mancanti fossero gli ultimi 4), leggendo qualsiasi parola nel file in posizione N si restituirebbe il valore corrispondente N.
Utilizzare una ricerca di dicotomia sulle posizioni [0..2³²-4-1) per cercare il primo numero non previsto X1.
Una volta trovato il primo numero mancante, eseguire nuovamente la dictotomia nelle posizioni [X1 .. (2³²-4-1)] per trovare il secondo mancante, X2: questa volta, la lettura di una parola nella posizione N dovrebbe restituire il valore corrispondente N-1 se non ci fossero più numeri mancanti (dato che hai passato un numero mancante).
Effettuare la stessa procedura per i due numeri rimanenti. Nella terza iterazione, la lettura della parola nella posizione N dovrebbe restituire N-2 e nel quarto dovrebbe restituire N-3.
Caveat: non l'ho provato. Ma penso che dovrebbe funzionare. :)
Ora, nella vita reale, sono d'accordo con altre risposte: le prime domande riguarderanno l'ambiente. Disponiamo di RAM (quanto), è il file su un dispositivo di archiviazione ad accesso diretto, è un'operazione one-shot (nessuna ottimizzazione richiesta) o critica (ogni numero di cicli), disponiamo di un'utilità di ordinamento esterna disponibile , ecc Quindi trova un compromesso accettabile per il contesto. Questo almeno mostra che si inizia ad analizzare il problema prima di cercare un algoritmo.
Come per tutte le domande standard, la soluzione è quella di google prima dell'intervista.
Questa domanda e le varianti hanno una risposta 'corretta' molto precisa che coinvolge XOR tutti i numeri. Dovrebbe mostrarti capire gli indici nei database o qualcosa del genere. Quindi zero punti per ogni 'potrebbe funzionare ma non quello che dice sul foglio' answer im afriad.
Sul lato positivo c'è un insieme finito di queste domande, alcune ore di revisione ti faranno sembrare un genio. Ricordati solo di fingere che ti stia lavorando nella testa.
Modifica. Ahh sembra per 4 c'è un approccio diverso da XOR
Modifica. Downvoters: questa è una soluzione O (n) da manuale pubblicata per il problema esatto indicato nell'OP.
Leggi altre domande sui tag algorithms