Articles of Algorithmus

Was ist eine gute Hash-function?

Was ist eine gute Hash-function? Ich habe eine Menge Hash-functionen und Anwendungen in meinen Datenstruktur-Kursen in der Universität gesehen, aber ich habe meistens festgestellt, dass es ziemlich schwer ist, eine gute Hash-function zu erstellen. Als Faustregel, um Kollisionen zu vermeiden, sagte mein Professor: function Hash(key) return key mod PrimeNumber end (mod ist der% Operator in […]

Was ist der schnellste Algorithmus zum Sortieren einer verknüpften Liste?

Ich bin gespannt, ob O (n log n) das Beste ist, was eine verknüpfte Liste tun kann.

Mögliche Interview Frage: Wie Sie alle überlappenden Intervalle finden

Es ist keine Interviewfrage per se , da ich in meinem Projekt darauf gestoßen bin, aber ich dachte, es könnte eine anständige Frage sein. Sie haben N Intervalle, sagen ganze Zahlen. Sie müssen alle Intervalle, die sich in O (N) -Zeit überschneiden, identifizieren. Zum Beispiel, wenn Sie haben {1, 3} {12, 14} {2, 4} {13, […]

Rekursion gegen Iteration

Ist es korrekt zu sagen, dass überall, wo recursion wird, eine For-Schleife verwendet werden könnte? Und wenn die Rekursion normalerweise langsamer ist, was ist der technische Grund dafür, sie jemals für die Iteration zu verwenden? Und wenn es immer möglich ist, eine Rekursion in eine for-Schleife umzuwandeln, gibt es eine Faustregel dafür?

Duplikate in O (n) Zeit und O (1) Raum finden

Eingabe: Gegeben sei ein Array von n Elementen, die Elemente von 0 bis n-1 enthalten, wobei jede dieser Zahlen beliebig oft vorkommen kann. Ziel: Um diese sich wiederholenden Zahlen in O (n) zu finden und nur konstanten Speicherplatz zu verwenden. Zum Beispiel sei n 7 und array be {1, 2, 3, 1, 3, 0, 6}, […]

Algorithmus zum Erzeugen eines Kreuzworträtsels

Wie würden Sie eine gegebene Wörterliste in ein Kreuzworträtselgitter einordnen? Es muss nicht wie ein “richtiges” Kreuzworträtsel sein, das symmetrisch oder ähnlich ist: Im Grunde geben Sie nur eine Ausgangsposition und eine Richtung für jedes Wort aus. Gibt es Java-Beispiele?

Generiere alle eindeutigen Teilstrings für eine gegebene Zeichenkette

Gibt es eine Zeichenfolge s , was ist die schnellste Methode, um eine Menge aller eindeutigen Teilzeichenfolgen zu generieren? Beispiel: für str = “aba” würden wir substrs={“a”, “b”, “ab”, “ba”, “aba”} . Der naive Algorithmus würde die gesamte Zeichenfolge, die Teilstrings erzeugt, in der Länge 1..n in jeder Iteration 1..n , was eine O(n^2) obere […]

Erzeugen der Partitionen einer Nummer

Ich brauchte einen Algorithmus, um alle möglichen Partitionen einer positiven Zahl zu generieren, und ich kam mit einem (als Antwort), aber es ist exponentielle Zeit. Der Algorithmus sollte alle möglichen Möglichkeiten zurückgeben, wie eine Zahl als die Summe positiver Zahlen ausgedrückt werden kann, die kleiner oder gleich sind. Also zum Beispiel für die Nummer 5 […]

Warum wird die Konstante immer aus der großen O-Analyse entfernt?

Ich versuche, einen bestimmten Aspekt der Big O–Analyse im Zusammenhang mit dem Ausführen von Programmen auf einem PC zu verstehen. Angenommen, ich habe einen Algorithmus mit einer performance von O (n + 2). Wenn n wirklich groß wird, wird die 2 unbedeutend. In diesem Fall ist es vollkommen klar, dass die wirkliche performance O (n) […]

Nächste Nachbarn in hochdimensionalen Daten?

Ich habe vor ein paar Tagen eine Frage gestellt, wie man die nächsten Nachbarn für einen gegebenen Vektor findet. Mein Vektor ist jetzt 21 Dimensionen und bevor ich weiter gehe, weil ich nicht aus dem Bereich des maschinellen Lernens oder Mathematik komme, fange ich an, mir einige grundsätzliche Fragen zu stellen: Ist die euklidische Distanz […]