Mi è stata posta questa domanda durante una selezione tecnica telefonica di recente e non ho funzionato bene. La domanda è inclusa testualmente sotto.
Generate
{2^i * 5^j | i,j >= 0}sorted collection. Continuously print the next smallest value.Example:
{ 1, 2, 4, 5, 8, 10...}
"Next smallest" mi fa pensare che sia coinvolto un min-heap, ma non sapevo davvero da dove andare e l'intervistatore non ha fornito assistenza.
Qualcuno ha consigli su come risolvere un simile problema?
Risolviamo il problema: Emetti ogni numero da 1 a infinito in modo che il numero non contenga fattori tranne 2 e 5.
Di seguito è riportato un semplice snippet C #:
for (int i = 1;;++i)
{
int num = i;
while(num%2 == 0) num/=2;
while(num%5 == 0) num/=5;
if(num == 1) Console.WriteLine(i);
}
Kilian's / QuestionC è molto più performante. Snippet C # con questo approccio:
var itms = new SortedSet<int>();
itms.Add(1);
while(true)
{
int cur = itms.Min;
itms.Remove(itms.Min);
itms.Add(cur*2);
itms.Add(cur*5);
Console.WriteLine(cur);
}
SortedSet impedisce gli inserimenti duplicati.
Fondamentalmente, funziona assicurandosi che il prossimo numero nella sequenza sia in itms .
Prova che questo approccio è valido:
L'algoritmo descritto assicura che dopo per qualsiasi numero di output nella forma 2^i*5^j , l'insieme ora contenga 2^(i+1)*5^j e 2^i*5^(j+1) . Supponiamo che il prossimo numero nella sequenza sia 2^p*5^q . Deve esistere un numero di output precedente della forma 2^(p-1)*5^(q) o 2^p*5^(q-1) (o entrambi, se né p né q sono uguali a 0). In caso contrario, 2^p*5^q non è il numero successivo, poiché 2^(p-1)*5^(q) e 2^p*5^(q-1) sono entrambi minori.
Il secondo frammento utilizza O(n) memoria (dove n è il numero di numeri che sono stati generati), poiché O(i+j) = O(n) (perché i e j sono entrambi minori di n), e troverà n numeri in O(n log n) tempo. Il primo snippet trova i numeri in tempo esponenziale.
Questa è una domanda di intervista abbastanza comune che è utile conoscere la risposta. Ecco la voce pertinente nel mio foglio personale per il presepe:
- to generate the numbers of the form 3a5b7cin order, start with 1, stuff all three possible successors (3, 5, 7) into an auxiliary structure, then add the smallest number from it to your list.
In altre parole, è necessario un approccio in due fasi con un buffer di ordinamento aggiuntivo per risolvere questo problema in modo efficiente. (Una descrizione più lunga è in Cracking the Coding Interview di Gayle McDowell.
Ecco una risposta che funziona con memoria costante, a scapito della CPU. Questa non è una buona risposta nel contesto della domanda originale (ad esempio risposta durante un'intervista). Ma se l'intervista dura 24 ore, allora non è così male. ;)
L'idea è che se ho n che è una risposta valida, allora la prossima nella sequenza sarà n volte una potenza di due, divisa per una potenza di 5. Oppure n volte una potenza di 5, diviso per un potere di due. Purché si divida in modo uniforme. (... o il divisore può essere 1;) nel qual caso stai solo moltiplicando per 2 o 5)
Ad esempio, per passare da 625 a 640, moltiplicare per 5 ** 4/2 ** 7. Oppure, più in generale, moltiplicare per un valore di 2 ** m * 5 ** n per alcuni m, n dove uno è positivo e uno è negativo o zero e il moltiplicatore divide il numero in modo uniforme.
Ora, la parte difficile è trovare il moltiplicatore. Ma sappiamo a) il divisore deve dividere il numero in modo uniforme, b) il moltiplicatore deve essere maggiore di uno (i numeri continuano ad aumentare) e c) se selezioniamo il più basso moltiplicatore maggiore di 1 (cioè 1 < f < tutte le altre f's), quindi è garantito che sarà il nostro prossimo passo. Il passo successivo sarà il passo più basso.
La parte cattiva è trovare il valore di m, n. Ci sono solo possibilità log (n), perché ci sono solo così tanti 2 o 5 da rinunciare, ma ho dovuto aggiungere un fattore da -1 a +1 come modo sciatto per affrontare il roundoff. Quindi dobbiamo solo ripetere su O (log (n)) ogni passo. Quindi è O (n log (n)) nel complesso.
La buona notizia è che, poiché accetta un valore e trova il valore successivo, puoi iniziare in qualsiasi punto della sequenza. Quindi se vuoi il successivo dopo 1 miliardo, puoi trovarlo semplicemente iterando attraverso i 2/5 o 5/2 e selezionando il moltiplicatore più piccolo maggiore di 1.
(python)
MAX = 30
F = - math.log(2) / math.log(5)
def val(i, j):
return 2 ** i * 5 ** j
def best(i, j):
f = 100
m = 0
n = 0
max_i = (int)(math.log(val(i, j)) / math.log(2) + 1) if i + j else 1
#print((val(i, j), max_i, x))
for mm in range(-i, max_i + 1):
for rr in {-1, 0, 1}:
nn = (int)(mm * F + rr)
if nn < -j: continue
ff = val(mm, nn)
#print(' ' + str((ff, mm, nn, rr)))
if ff > 1 and ff < f:
f = ff
m = mm
n = nn
return m, n
def detSeq():
i = 0
j = 0
got = [val(i, j)]
while len(got) < MAX:
m, n = best(i, j)
i += m
j += n
got.append(val(i, j))
#print('* ' + str((val(i, j), m, n)))
#print('- ' + str((v, i, j)))
return got
Ho convalidato i primi 10.000 numeri che questo genera contro i primi 10.000 generati dalla soluzione elenco ordinato, e funziona almeno fino a quel punto.
BTW il prossimo dopo un trilione sembra essere 1.024.000.000.000.
...
Hm. Posso ottenere prestazioni O (n) - O (1) per valore (!) - e O (log n) utilizzo della memoria trattando best() come tabella di ricerca che estendo in modo incrementale. In questo momento salva la memoria iterando ogni volta, ma sta facendo molti calcoli ridondanti. Tenendo quei valori intermedi - e una lista di valori minimi - posso evitare il lavoro duplicato & accelerare molto. Tuttavia, l'elenco dei valori intermedi crescerà con n, quindi la memoria O (log n).
Brian aveva assolutamente ragione - la mia altra risposta era troppo complicata. Ecco un modo più semplice e veloce per farlo.
Immagina il quadrante I del piano euclideo, limitato agli interi. Chiama un asse l'asse i e l'altro asse l'asse j.
Ovviamente, i punti vicini all'origine verranno selezionati prima di punti lontani dall'origine. Inoltre, l'area attiva si sposterà dall'asse i prima che si allontani dall'asse j.
Una volta che un punto è stato usato, non sarà mai più usato. E un punto può essere usato solo se il punto immediatamente sottostante o a sinistra di esso è già stato utilizzato.
Mettendoli insieme, puoi immaginare una "frontiera" o "leading edge" che inizia intorno all'origine e si estende su e destra, diffondendosi lungo l'asse i più lontano che sull'asse j.
In effetti, possiamo capire qualcosa di più: ci sarà al massimo un punto sulla frontiera / limite per ogni dato valore. (Devi incrementare i più di 2 volte per eguagliare un incremento di j.) Quindi, possiamo rappresentare la frontiera come una lista contenente un elemento per ogni coordinata i, variando solo con la coordinata j e il valore della funzione.
Ogni passaggio, selezioniamo l'elemento minimo sul bordo principale e poi lo spostiamo nella direzione-j una volta. Se capita di sollevare l'ultimo elemento, aggiungiamo un nuovo ultimo elemento con un valore i incrementato e un valore j di 0.
using System;
using System.Collections.Generic;
using System.Text;
namespace TwosFives
{
class LatticePoint : IComparable<LatticePoint>
{
public int i;
public int j;
public double value;
public LatticePoint(int ii, int jj, double vvalue)
{
i = ii;
j = jj;
value = vvalue;
}
public int CompareTo(LatticePoint rhs)
{
return value.CompareTo(rhs.value);
}
}
class Program
{
static void Main(string[] args)
{
LatticePoint startPoint = new LatticePoint(0, 0, 1);
var leadingEdge = new List<LatticePoint> { startPoint } ;
while (true)
{
LatticePoint min = leadingEdge.Min();
Console.WriteLine(min.value);
if (min.j + 1 == leadingEdge.Count)
{
leadingEdge.Add(new LatticePoint(0, min.j + 1, min.value * 2));
}
min.i++;
min.value *= 5;
}
}
}
}
Spazio: O (n) nel numero di elementi stampati finora.
Velocità: inserimenti O (1), ma quelli non vengono eseguiti ogni volta. (Occasionalmente più lungo quando List<> deve crescere, ma ancora O (1) ammortizzato). Il grande time sink è la ricerca del minimo, O (n) nel numero di elementi stampati finora.
La soluzione basata su set era probabilmente ciò che il tuo intervistatore stava cercando, tuttavia ha la sfortunata conseguenza di avere O(n) di memoria e O(n lg n) di tempo totale per il sequencing di n elementi.
Un po 'di matematica ci aiuta a trovare una soluzione O(1) di spazio e O(n sqrt(n)) di tempo. Si noti che 2^i * 5^j = 2^(i + j lg 5) . La ricerca dei primi n elementi di {i,j > 0 | 2^(i + j lg 5)} si riduce alla ricerca del primo n elementi di {i,j > 0 | i + j lg 5} perché la funzione (x -> 2^x) è strettamente monotona in aumento, quindi l'unico modo per alcuni a,b che 2^a < 2^b è se a < b .
Ora, abbiamo solo bisogno di un algoritmo per trovare la sequenza di i + j lg 5 , dove i,j sono numeri naturali. In altre parole, dato il nostro valore attuale di i, j , ciò che minimizza la prossima mossa (cioè, ci dà il prossimo numero nella sequenza), è un certo aumento di uno dei valori (diciamo j += 1 ) insieme ad una diminuzione l'altro ( i -= 2 ). L'unica cosa che ci limita è che i,j > 0 .
Ci sono solo due casi da prendere in considerazione - aumenta i o aumenta j . Uno di questi deve aumentare poiché la nostra sequenza è in aumento, e non aumentano entrambi perché altrimenti saltiamo il termine in cui abbiamo solo uno di incremento di i,j . Così uno aumenta e l'altro rimane uguale o diminuisce. Espresso in C ++ 11, l'intero algoritmo e il suo confronto con la soluzione impostata sono disponibili qui .
Ciò consente di ottenere memoria costante in quanto vi è solo una quantità costante di oggetti allocati nel metodo, a parte la matrice di output (vedi link). Il metodo raggiunge il tempo logaritmico ogni iterazione poiché per ogni dato (i,j) , attraversa per la migliore coppia (a, b) tale che (i + a, j + b) è il più piccolo aumento del valore di i + j lg 5 . Questo traversamento è O(i + j) :
Attempt to increase i:
++i
current difference in value CD = 1
while (j > 0)
--j
mark difference in value for
current (i,j) as CD -= lg 5
while (CD < 0) // Have to increase the sequence
++i // This while will end in three loops at most.
CD += 1
find minimum among each marked difference ((i,j) -> CD)
Attempt to increase j:
++j
current difference in value CD = lg 5
while (j > 0)
--i
mark difference in value for
current (i,j) as CD -= 1
while (CD < 0) // have to increase the sequence
++j // This while will end in one loop at most.
CD += lg 5
find minimum among each marked difference ((i,j) -> CD)
Ogni iterazione tenta di aggiornare i , poi j , e va con l'aggiornamento più piccolo dei due.
Poiché i e j sono al massimo O(sqrt(n)) , abbiamo tempo O(n sqrt(n)) totale. i e j crescono alla velocità del quadrato di n poiché per qualsiasi valore massimo di imax e jmax esiste O(i j) coppie uniche da cui fare la nostra sequenza se la nostra sequenza è n termini, e i e j crescono all'interno di un fattore costante l'uno dell'altro (perché l'esponente è composto da una combinazione lineare dei due), sappiamo che i e j sono O(sqrt(n)) .
Non c'è molto di cui preoccuparsi per quanto riguarda l'errore in virgola mobile - dal momento che i termini crescono in modo esponenziale, dovremmo affrontare l'overflow prima che l'errore del flop raggiunga, con diverse grandezze. Aggiungerò ulteriori discussioni a questo se avrò tempo.
Leggi altre domande sui tag algorithms