Ottieni 100 numeri più alti da una lista infinita

Diciamo che k è il numero di numeri più alti che vuoi sapere (100 nel tuo esempio). Quindi, puoi aggiungere un nuovo numero in O(k) che è anche O(1) . Perché O(k*g) = O(g) if k is not zero and constant .

Mantieni l'elenco non ordinato. Capire se inserire o meno un nuovo numero richiederà più tempo, ma l'inserimento sarà O (1).

Questo è facile. La dimensione dell'elenco di costanti, quindi il tempo di ordinamento dell'elenco è costante. Un'operazione che viene eseguita in un tempo costante è detta O (1). Pertanto, l'ordinamento dell'elenco è O (1) per un elenco di dimensioni fisse.

Dopo aver passato 100 numeri, il costo massimo che dovrai sostenere per il numero successivo è il costo per verificare se il numero è nei 100 numeri più alti (etichettiamo CheckTime ) più il costo per inserirli in quel set ed espellere quello più basso (chiamiamolo EnterTime ), che è un tempo costante (almeno per i numeri limitati) o O (1) .

Worst = CheckTime + EnterTime

Successivamente, se la distribuzione dei numeri è casuale, il costo medio diminuisce più numeri hai. Ad esempio, la possibilità di inserire il numero 101 nel set massimo è 100/101, le possibilità per il numero 1000 saranno 1/10 e le probabilità per l'ennesimo numero saranno 100 / n. Pertanto, la nostra equazione per il costo medio sarà:

Average = CheckTime + EnterTime / n

Pertanto, poiché n si avvicina all'infinito, solo CheckTime è importante:

Average = CheckTime

Se i numeri sono vincolati, CheckTime è costante, quindi è O (1) tempo.

Se i numeri non sono vincolati, il tempo di controllo aumenterà con più numeri. In teoria, questo è perché se il numero più piccolo nel set massimo diventa abbastanza grande, il tempo di controllo sarà maggiore perché dovrai considerare più bit. Questo fa sembrare che sarà leggermente più alto del tempo costante. Tuttavia, potresti anche obiettare che la possibilità che il prossimo numero sia nel set più alto si avvicina a zero quando n si avvicina all'infinito e quindi la possibilità di considerare più bit si avvicina a 0, che sarebbe un argomento per il tempo O (1) .

Non sono positivo, ma il mio istinto dice che è O (log (log (n))) tempo. Questo perché la possibilità che il numero più basso aumenti è logaritmico e la possibilità che il numero di bit da considerare per ogni controllo sia logaritmico. Mi interessa che altri popoli se ne accorgano, perché non sono proprio sicuro ...

questo è facile se conosci Alberi heap binari . Gli heap binari supportano l'inserimento in tempo costante medio, O (1). E ti danno un facile accesso ai primi x elementi.

Se dalla domanda che l'intervistatore intendeva davvero chiedere "possiamo assicurarci che ogni numero in entrata venga elaborato in tempo costante", quindi come già indicato (vedi la risposta di @ duedl0r), la soluzione del tuo amico è già O (1 ), e sarebbe così anche se avesse usato liste non ordinate, o usato bubble sort, o qualsiasi altra cosa. In questo caso la domanda non ha molto senso, a meno che non si tratti di domande complicate o se le ricordi male.

Presumo che la domanda dell'intervistatore fosse significativa, che non stesse chiedendo come fare qualcosa per essere O (1) che è ovviamente molto evidente.

Poiché la complessità dell'algoritmo di interrogazione ha senso solo quando la dimensione dell'input cresce indefinitamente e l'unico input che può crescere qui è 100: la dimensione dell'elenco; Presumo che la vera domanda fosse "possiamo essere sicuri che riceviamo Top N spendendo O (1) tempo per numero (non O (N) come nella soluzione del tuo amico), è possibile?".

La prima cosa che mi viene in mente è contare gli ordinamenti, che compreranno la complessità del tempo O (1) per numero per il problema Top-N al prezzo dell'utilizzo dello spazio O (m), dove m è la lunghezza dell'intervallo dei numeri in arrivo. Quindi sì, è possibile.

Utilizza una coda con priorità minime implementata con un heap Fibonacci , che ha un tempo di inserimento costante:

1. Insert first 100 elements into PQ
2. loop forever
       n = getNextNumber();
       if n > PQ.findMin() then
           PQ.deleteMin()
           PQ.insert(n)

L'attività è chiaramente quella di trovare un algoritmo che sia O (1) nella lunghezza N dell'elenco di numeri richiesto. Quindi non importa se hai bisogno del numero 100 o 10000 più alto, il tempo di inserimento dovrebbe essere O (1).

Il trucco qui è che sebbene il requisito O (1) sia menzionato per la lista inserita, la domanda non ha detto nulla sull'ordine del tempo di ricerca nell'intero spazio numerico, ma risulta che questo può essere fatto O (1) pure. La soluzione è quindi la seguente:

1. Organizzare una tabella hash con i numeri per le chiavi e le coppie di puntatori di elenchi collegati per i valori. Ogni coppia di puntatori è l'inizio e la fine di una sequenza di elenchi collegati. Normalmente questo sarà solo un elemento di quello successivo. Ogni elemento nell'elenco collegato si posiziona accanto all'elemento con il successivo numero più alto. L'elenco collegato contiene quindi la sequenza ordinata dei numeri richiesti. Conserva un record del numero più basso.

2. Prendi un nuovo numero x dal flusso casuale.

3. È superiore all'ultimo numero più basso registrato? Sì = > Passaggio 4, No = > Passaggio 2

4. Premi la tabella hash con il numero appena preso. C'è una voce? Sì = > Passaggio 5. No = > Prendi un nuovo numero x-1 e ripeti questo passaggio (questa è una semplice ricerca lineare verso il basso, portami solo qui, questo può essere migliorato e ti spiegherò come)

5. Con l'elemento della lista appena ottenuto dalla tabella hash, inserisci il nuovo numero subito dopo l'elemento nella lista collegata (e aggiorna l'hash)

6. Prendi il numero più basso l registrato (e rimuovilo dall'elenco hash /).

7. Premi la tabella hash con il numero appena preso. C'è una voce? Sì = > Passaggio 8. No = > Prendi un nuovo numero l + 1 e ripeti questo passaggio (questa è una semplice ricerca lineare ascendente)

8. Con un colpo positivo il numero diventa il nuovo numero più basso. Vai al passaggio 2

Per consentire valori duplicati, l'hash deve effettivamente mantenere l'inizio e la fine della sequenza di elenchi collegati di elementi duplicati. L'aggiunta o la rimozione di un elemento in una determinata chiave aumenta o riduce l'intervallo puntato a.

L'inserto qui è O (1). Le ricerche menzionate sono, immagino qualcosa di simile, O (differenza media tra i numeri). La differenza media aumenta con la dimensione dello spazio numerico, ma diminuisce con la lunghezza richiesta dell'elenco di numeri.

Quindi la strategia di ricerca lineare è piuttosto scarsa, se lo spazio numerico è grande (ad esempio per un tipo int da 4 byte, da 0 a 2 ^ 32-1) e N = 100. Per ovviare a questo problema di prestazioni è possibile mantenere serie parallele di hashtables, in cui i numeri sono arrotondati a magnitudini più elevate (ad esempio 1s, 10s, 100s, 1000s) per rendere le chiavi idonee. In questo modo è possibile aumentare o diminuire le marce per eseguire più rapidamente le ricerche richieste. La performance diventa quindi un O (log numberrange), penso, che è costante, cioè O (1) anche.

Per renderlo più chiaro, immagina di avere a portata di mano il numero 197. Hai colpito la tabella hash 10s, con '190', è arrotondato al dieci più vicino. Nulla? No. Quindi scendi tra 10 secondi finché non premi 120. Quindi puoi iniziare a 129 nella tabella hash, quindi provare 128, 127 fino a quando non colpisci qualcosa. Ora hai trovato dove inserire nell'elenco il numero 197. Mentre lo inserisci, devi anche aggiornare l'hash di 1s con la voce 197, l'hashtable 10s con il numero 190, 100s con 100, ecc. La maggior parte dei passaggi devi fare qui 10 volte il registro dell'intervallo numerico.

Potrei aver sbagliato alcuni dettagli, ma poiché questo è lo scambio di programmatori e il contesto è stato interviste, spero che quanto sopra sia una risposta abbastanza convincente per quella situazione.

EDIT ho aggiunto ulteriori dettagli qui per spiegare lo schema di hashtable parallelo e come significa che le ricerche lineari povere che ho menzionato possono essere sostituite con una ricerca O (1). Ho anche realizzato che ovviamente non è necessario cercare il numero più basso successivo, perché puoi passare direttamente ad esso esaminando la tabella hash con il numero più basso e passando all'elemento successivo.

Possiamo supporre che i numeri siano di un tipo di dati fisso, come Integer? Se è così, quindi mantenere un conteggio di ogni singolo numero che viene aggiunto. Questa è un'operazione O (1).

1. Dichiara un array con tutti gli elementi quanti sono i possibili numeri:
2. Leggi ogni numero mentre viene trasmesso in streaming.
3. Calcola il numero. Ignoralo se quel numero è già stato calcolato 100 volte, poiché non ne avrai mai bisogno. Ciò impedisce agli overflow di raggrupparli un numero infinito di volte.
4. Ripeti dal passaggio 2.

Codice VB.Net:

Const Capacity As Integer = 100

Dim Tally(Integer.MaxValue) As Integer ' Assume all elements = 0
Do
    Value = ReadValue()
    If Tally(Value) < Capacity Then Tally(Value) += 1
Loop

Quando restituisci l'elenco, puoi impiegare tutto il tempo che vuoi. Basta scorrere fino alla fine dell'elenco e creare un nuovo elenco dei 100 valori più alti registrati. Questa è un'operazione O (n), ma è irrilevante.

Dim List(Capacity) As Integer
Dim ListCount As Integer = 0
Dim Value As Integer = Tally.Length - 1
Dim ValueCount As Integer = 0
Do Until ListCount = List.Length OrElse Value < 0
    If Tally(Value) > ValueCount Then
        List(ListCount) = Value
        ValueCount += 1
        ListCount += 1
    Else
        Value -= 1
        ValueCount = 0
    End If
Loop
Return List

Modifica: in realtà non importa se si tratta di un tipo di dati fisso. Dato che non ci sono limiti imposti al consumo di memoria (o disco rigido), puoi farlo funzionare per qualsiasi intervallo di numeri interi positivi.

Un centinaio di numeri sono facilmente memorizzati in un array, misura 100. Qualsiasi albero, elenco o set è eccessivo, dato il compito da svolgere.

Se il numero in entrata è più alto del più basso (= ultimo) dell'array, esegui tutte le voci. Una volta trovato il primo che è più piccolo del tuo nuovo numero (puoi usare le ricerche di fantasia per farlo), esegui il resto dell'array, spingendo ogni voce "in basso" di uno.

Poiché mantieni la lista ordinata dall'inizio, non è necessario eseguire alcun algoritmo di ordinamento. Questo è O (1).

Potresti usare un Max-Heap binario. Dovresti tenere traccia di un puntatore al nodo minimo (che potrebbe essere sconosciuto / null).

Si inizia inserendo i primi 100 numeri nell'heap. Il massimo sarà nella parte superiore. Al termine, manterrai sempre 100 numeri.

Quindi quando ottieni un nuovo numero:

if(minimumNode == null)
{
    minimumNode = findMinimumNode();
}
if(newNumber > minimumNode.Value)
{
    heap.Remove(minimumNode);
    minimumNode = null;
    heap.Insert(newNumber);
}

Sfortunatamente findMinimumNode è O (n), e si incorre in tale costo una volta per inserto (ma non durante l'inserimento :). La rimozione del nodo minimo e l'inserimento del nuovo nodo sono, in media, O (1) perché tenderanno verso il fondo dell'heap.

Andando dall'altra parte con un Min-Heap binario, il min è in alto, il che è ottimo per trovare il minimo per il confronto, ma fa schifo quando devi sostituire il minimo con un nuovo numero che è > min. Questo perché devi rimuovere il nodo min (sempre O (logN)) e quindi inserire il nuovo nodo (media O (1)). Quindi, hai ancora O (logN) che è migliore di Max-Heap, ma non O (1).

Naturalmente, se N è costante, hai sempre O (1). :)