Ein Freund von mir interviewt für einen Job. Eine der Interviewfragen brachte mich zum Nachdenken, ich wollte nur ein Feedback.
Es gibt 2 nicht negative ganze Zahlen: i und j. Finden Sie anhand der folgenden Gleichung eine (optimale) Lösung, um i und j so zu durchlaufen, dass die Ausgabe sortiert wird.
2^i * 5^j
Die ersten Runden würden also so aussehen:
2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25
Versuchen Sie, wie ich könnte, ich kann kein Muster sehen. Ihre Gedanken?
algorithm
optimization
hamming-numbers
smooth-numbers
Chris Eberle
quelle
quelle
2^2 < 5
aber2^3 > 5
an diesem Punkt erhöhen Sie j. Ich denke, Sie können die Ausgabe in O (n) anstatt in O (nlgn) erzeugen. @ tom-zynch zwei verschachtelte Schleifen sind O (n ^ 2). Diese Frage ist sehr gültigAntworten:
Dijkstra leitet eine beredte Lösung in "A Discipline of Programming" ab. Er schreibt das Problem Hamming zu. Hier ist meine Implementierung der Dijkstra-Lösung.
quelle
Hier ist eine verfeinerte Methode (verfeinert als meine vorherige Antwort):
Stellen Sie sich vor, die Zahlen werden in einer Matrix platziert:
Was Sie tun müssen, ist diese Matrix zu durchlaufen, beginnend mit
(0,0)
. Sie müssen auch verfolgen, was Ihre möglichen nächsten Schritte sind. Wenn Sie bei beginnen, haben(0,0)
Sie nur zwei Möglichkeiten: entweder(0,1)
oder(1,0)
: Da der Wert von(0,1)
kleiner ist, wählen Sie diese. dann machen Sie dasselbe für Ihre nächste Wahl(0,2)
oder(1,0)
. Bisher haben Sie folgende Liste:1, 2, 4
. Ihr nächster Schritt ist,(1,0)
da der Wert dort kleiner als ist(0,3)
. Sie haben jetzt jedoch drei Möglichkeiten für Ihren nächsten Schritt: entweder(0,3)
oder(1,1)
oder(2,0)
.Sie benötigen die Matrix nicht, um die Liste zu erhalten, aber Sie müssen alle Ihre Auswahlmöglichkeiten im Auge behalten (dh wenn Sie 125+ erreichen, haben Sie 4 Auswahlmöglichkeiten).
quelle
j
j ~ n^0.5
für den n-ten Wert in einer Sequenz, dan
Werte einen Bereich in deri x j
Ebene ausfüllen . Dieses Algo ist alsoO(n^1.5)
Zeit mitO(n^0.5)
Raum. Es gibt jedoch ein lineares Zeitalgo mit derselben Raumkomplikationn^0.5
, und das Mini-Heap-Algo aus der folgenden Antwort istO(n*log(n))
Zeit mit demselbenn^0.5
Raum.Verwenden Sie einen Min-Haufen.
Setzen Sie 1.
Extrakt-min. Angenommen, Sie erhalten x.
Schieben Sie 2x und 5x in den Haufen.
Wiederholen.
Anstatt x = 2 ^ i * 5 ^ j zu speichern, können Sie (i, j) speichern und eine benutzerdefinierte Vergleichsfunktion verwenden.
quelle
Eine FIFO-basierte Lösung benötigt weniger Speicherkapazität. Python-Code.
Ausgabe:
quelle
Dies ist
O(n)
in funktionalen Sprachen sehr einfach . Die Listel
der2^i*5^j
Nummern kann einfach als1
und dann definiert2*l
und5*l
zusammengeführt werden. So sieht es in Haskell aus:Die
merge
Funktion gibt Ihnen in konstanter Zeit einen neuen Wert. Somap
und so auchl
.quelle
union
stattdessen einfach diese "Zusammenführungs" -Funktion , da sie die Duplikate entfernt.merge
Als Teil vonmergesort
müssen Duplikate aus beiden Eingabesequenzen beibehalten werden. SieheData.List.Ordered
Paket für verwandte Sachen.Data.List.Ordered.union
. Das macht es eine Zeile:xs = 1 : union (map (2*) xs) (map (5*) xs)
[1, 2, 4, 5,...]
also enthält es5*4
.Data.List.Ordered.union
Funktion. Nicht zu verwechselnData.List.union
.Sie müssen die einzelnen Exponenten von ihnen und ihre Summen im Auge behalten
Sie beginnen also mit
f(0,0) --> 1
einem von ihnen:Wir wissen also, dass 2 der nächste ist - wir wissen auch, dass wir den Exponenten von i erhöhen können, bis die Summe 5 überschreitet.
Sie gehen so hin und her, bis Sie die gewünschte Anzahl von Runden erreicht haben.
quelle
f(*,2)
nur weil Sie das gefunden habenf(a1,b+1)>f(a2,b)
. Ein inkrementeller Ansatz generiert schließlich eine unbegrenzte Anzahl von Paaren neben der Region, die Sie bereits ausgegeben haben.Mit dynamischer Programmierung können Sie dies in O (n) tun. Grundwahrheit ist, dass keine Werte von i und j uns 0 geben können, und um 1 zu erhalten, müssen beide Werte 0 sein;
Wenn Sie diese Funktion aufrufen, überprüfen Sie, ob i und j gesetzt sind. Wenn sie nicht null sind, füllen Sie
TwoCount
und ausFiveCount
C ++ Antwort. Entschuldigung für den schlechten Codierungsstil, aber ich habe es eilig :(
Natürlich können Sie andere Datenstrukturen als das Array verwenden, um Ihren Speicher usw. dynamisch zu vergrößern. Dies ist nur eine Skizze, um zu beweisen, dass es funktioniert.
quelle
O(exp(sqrt(n)))
,n
Zahlen der Sequenz zu erzeugen . Es gibt einen linearen Algorithmus, z. B. wie von ThomasAhle angegeben.O(n)
bedeutete diesn
, der letzte Wert zu sein, nicht die Anzahl der gedruckten Elemente, was nicht korrekt ist. Ich weiß nicht, wie funktionale Sprachen funktionieren oder wie das Zusammenführen in konstanter Zeit funktioniert, aber seine Antwort erhielt meine positive BewertungWarum nicht versuchen, dies aus der anderen Richtung zu betrachten? Verwenden Sie einen Zähler, um die möglichen Antworten anhand der Originalformel zu testen. Entschuldigung für den Pseudocode.
quelle
O(4^sqrt(n))
weil dienth
Nummer der Sequenz ungefähr so groß ist.Dies ist der relevante Eintrag bei OEIS.
Es scheint möglich zu sein, die geordnete Sequenz zu erhalten, indem beispielsweise die ersten Terme erzeugt werden
und dann ab dem zweiten Term mit 4 und 5 multiplizieren, um die nächsten beiden zu erhalten
und so weiter...
Intuitiv scheint dies richtig zu sein, aber natürlich fehlt ein Beweis.
quelle
Sie wissen, dass log_2 (5) = 2.32. Daraus ergibt sich, dass 2 ^ 2 <5 und 2 ^ 3> 5.
Schauen Sie sich nun eine Matrix möglicher Antworten an:
Wählen Sie nun für dieses Beispiel die Zahlen der Reihe nach aus. Dort wäre die Bestellung:
Beachten Sie, dass jede Zeile 2 Spalten hinter der Zeile beginnt, in der sie beginnt. Zum Beispiel kommt i = 0 j = 1 direkt nach i = 2 j = 0.
Ein Algorithmus, den wir aus diesem Muster ableiten können, ist daher (angenommen j> i):
HINWEIS: Der Code hier begrenzt die Werte der Exponenten von i und j auf weniger als 10. Sie können diesen Algorithmus leicht erweitern, um ihn in andere beliebige Grenzen einzufügen.
HINWEIS: Die Laufzeit für diesen Algorithmus beträgt O (n) für die ersten n Antworten.
HINWEIS: Die Raumkomplexität für diesen Algorithmus beträgt O (1).
quelle
Meine Implementierung basiert auf folgenden Ideen:
Beispiel:
Code in Java:
quelle
Berechnen Sie die Ergebnisse und fügen Sie sie zusammen mit den Werten für
i
und in eine sortierte Liste einj
quelle
2^n*5^n
aber nicht2^(n+1)*5^(n-1)
was kleiner ist.i
und deinej
haben, nicht wahr ? Andernfalls gelangen Sie nie in den Sortierstatus und geben daher niemals einen einzelnen Wert zurück. Aber für jedes Limit, dasn
Sie wählen, wird Ihre Liste fehlerhaft sein.i
und findenj
.2^i*5^j
Werte und sortieren sie dann. Wenn Sie keine begrenzte Anzahl von "Ergebnissen" haben, wie kommen Sie jemals zum Sortierschritt?Der von user515430 von Edsger Dijkstra (http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF) implementierte Algorithmus ist wahrscheinlich so schnell wie möglich. Ich rufe jede Nummer an, die eine Form
2^i * 5^j
einer "speziellen Nummer" ist. Jetzt würde vlads Antwort sein,O(i*j)
aber mit einem doppelten Algorithmus, einer, um die speziellen Zahlen zu generierenO(i*j)
und einer, um sie zu sortieren (gemäß dem verlinkten Artikel auchO(i*j)
.Aber lassen Sie uns den Dijkstra-Algorithmus überprüfen (siehe unten). In diesem Fall
n
ist die Anzahl der von uns generierten Sonderzahlen gleichi*j
. Wir schleifen einmal1 -> n
und führen in jeder Schleife eine konstante Aktion aus. So ist dieser Algorithmus auchO(i*j)
. Und mit einer ziemlich blitzschnellen Konstante auch.Meine Implementierung in C ++ mit GMP (C ++ - Wrapper) und Abhängigkeit davon
boost::lexical_cast
, obwohl das leicht entfernt werden kann (ich bin faul und wer verwendet Boost nicht?). Zusammengestellt mitg++ -O3 test.cpp -lgmpxx -o test
. Auf Q6600time ./test 1000000
gibt Ubuntu 10.101145ms
.quelle
Wenn Sie eine Matrix mit i als Zeile und j als Spalte zeichnen, können Sie das Muster sehen. Beginnen Sie mit i = 0 und durchlaufen Sie dann einfach die Matrix, indem Sie 2 Zeilen und 1 Spalte nach rechts gehen, bis Sie den oberen Rand der Matrix erreichen (j> = 0). Dann gehe ich + 1, etc ...
Für i = 7 reisen Sie also wie folgt:
Und für i = 8:
Hier ist es in Java bis zu i = 9. Es gibt die Matrixposition (i, j) und den Wert aus.
quelle
Meine Intuition :
Wenn ich den Anfangswert als 1 nehme, wobei i = 0, j = 0 ist, kann ich die nächsten Zahlen als (2 ^ 1) (5 ^ 0), (2 ^ 2) (5 ^ 0), (2 ^ 0) erstellen. * (5 ^ 1), ... dh 2,4,5 ..
Nehmen wir an, meine Nummer ist zu jedem Zeitpunkt x. dann kann ich die nächsten Zahlen auf folgende Weise erstellen:
Erklärung :
Testlauf
Beginnen wir mit x = 1.
Die nächsten drei Zahlen sind 1 * 2, 1 * 4, 1 * 5 [2,4,5]; Arr [1,2,4,5]
Jetzt ist x = 2
Die nächsten drei Zahlen sind [4,8,10] {Da 4 bereits aufgetreten sind, werden wir sie ignorieren} [8,10]; Arr [1,2,4,5,8,10]
Jetzt ist x = 4
Die nächsten drei Zahlen [8,16,20] {8 sind bereits aufgetreten, ignorieren Sie es} [16,20] Arr [1,2,4,5,8,10,16,20]
x = 5
Die nächsten drei Zahlen [10,20,25] {10,20} bereits [25] werden hinzugefügt Arr [1,2,4,5,8,10,16,20,25]
Kündigungsbedingung
Analyse
quelle
War nur neugierig was mich nächste Woche erwartet und habe diese Frage gefunden.
Ich denke, die Idee ist 2 ^ i steigt nicht in diesen großen Schritten als 5 ^ j. Erhöhen Sie also i, solange der nächste J-Schritt nicht größer ist.
Das Beispiel in C ++ (Qt ist optional):
Die Ausgabe:
quelle
Hier ist meine Lösung
Ergebnis:
quelle
Ich weiß, dass ich wahrscheinlich falsch liege, aber hier gibt es eine sehr einfache Heuristik, da sie nicht viele Zahlen wie 2,3,5 enthält. Wir wissen, dass für jedes i, j 2 ^ i * 5 ^ j die nächste Sequenz 2 ^ (i-2) * 5 ^ (j + 1) wäre. Als Google Q muss es eine einfache Lösung geben.
Dies erzeugt eine Ausgabe als:
quelle
Wenn Sie sich an das halten, was wirklich passiert, wenn wir i oder j im Ausdruck erhöhen
2^i * 5^j
erhöhen, multiplizieren Sie entweder mit einer anderen 2 oder einer anderen 5. Wenn wir das Problem als - bei einem bestimmten Wert von i und j wiederholen, wie würden Sie den nächsten finden? Bei größerem Wert wird die Lösung offensichtlich.Hier sind die Regeln, die wir intuitiv aufzählen können:
i > 1
der Ausdruck ein Paar von 2s ( ) enthält, sollten wir sie durch eine 5 ersetzen, um die nächstgrößere Zahl zu erhalten. Alsoi -= 2
undj += 1
.j > 0
müssen wir eine 5 ( ) durch drei 2s ersetzen. Alsoj -= 1
undi += 3
.i += 1
.Hier ist das Programm in Ruby:
quelle
Wenn wir Java Collection verwenden dürfen, können wir diese Nummer in O (n ^ 2) haben.
Hier muss powerLimit sehr sorgfältig initialisiert werden !! Abhängig davon, wie viele Nummern Sie möchten.
quelle
Hier ist mein Versuch mit Scala:
Ausgabe:
quelle