Interviewfrage: Entferne Duplikate aus einer unsortierten Verkettungsliste

Wenn Sie einer Person einen Fisch geben, essen sie einen Tag lang. Wenn Sie einer Person beibringen zu fischen ...

Meine Maßnahmen für die Qualität einer Implementierung sind:

• Korrektheit : Wenn Sie nicht in allen Fällen die richtige Antwort erhalten, ist sie nicht bereit
• Lesbarkeit / Wartbarkeit : Betrachten Sie Codewiederholung, verständliche Namen, die Anzahl der Codezeilen pro Block / Methode (und die Anzahl der Dinge, die jeder Block tut) und wie schwierig es ist, den Fluss von dein Code. Schauen Sie sich eine beliebige Anzahl von Büchern an, die sich auf Refactoring, Programmierung von Best Practices, Codierungsstandards usw. konzentrieren, wenn Sie mehr Informationen dazu wünschen.
• Theoretische Leistung (Worst-Case und ammortalisiert): Big-O ist eine Metrik, die Sie verwenden können . CPU- und Speicherverbrauch sollten beide gemessen werden
• Komplexität : Schätzen Sie, wie ein durchschnittlicher professioneller Programmierer zu implementieren wäre (wenn er den Algorithmus bereits kennt). Sehen Sie, ob das mit dem Schwierigkeitsgrad des Problems übereinstimmt.

Wie für Ihre Implementierung:

• Korrektheit : Ich schlage vor, Komponententests zu schreiben, um diese für sich selbst zu bestimmen und / oder sie (auf Papier) von Anfang bis Ende mit interessanten Beispiel- / Randfällen zu debuggen. Null, ein Element, zwei Elemente, verschiedene Anzahl von Duplikaten usw.
• Lesbarkeit / Wartbarkeit : Es sieht meistens gut aus, obwohl Ihre letzten beiden Kommentare nichts hinzufügen. Es ist etwas offensichtlicher, was Ihr Code tut als der Code im Buch
• Leistung : Ich glaube beide sind N-Quadrat. Ob die fortgeführten Anschaffungskosten niedriger sind, lasse ich Sie herausfinden:)
• Zeit zu implementieren : Ein durchschnittlicher Profi sollte in der Lage sein, diesen Algorithmus im Schlaf zu programmieren, also gut aussehen

Es gibt keinen großen Unterschied. Wenn ich meine Mathematik richtig gemacht habe, ist Ihr Durchschnitt durchschnittlich N / 16 langsamer als die Autoren, aber es gibt Fälle, wo Ihre Implementierung schneller sein wird.

Bearbeiten:

Ich rufe Ihre Implementierung Y und das A des Autors

Beide vorgeschlagenen Lösungen haben O (N ^ 2) als schlechtesten Fall und beide haben den besten Fall von O (N), wenn alle Elemente den gleichen Wert haben.

BEARBEITEN: Dies ist eine vollständige Neuschreibung. Inspiriert durch das Debat in den Kommentaren versuchte ich den durchschnittlichen Fall für zufällige N Zufallszahlen zu finden. Das ist eine Sequenz mit zufälliger Größe und zufälliger Verteilung. Was wäre der durchschnittliche Fall?

Y wird immer U-mal laufen, wobei U die Anzahl der eindeutigen Zahlen ist. Für jede Iteration werden N-X-Vergleiche durchgeführt, wobei X die Anzahl der Elemente ist, die vor der Iteration (+1) entfernt wurden. Das erste Mal, dass kein Element entfernt wurde und im Durchschnitt bei der zweiten Iteration wurde N / U entfernt.

Das heißt, im Durchschnitt wird ½N iteriert. Wir können die durchschnittlichen Kosten als ausdrücken U * ½N. Der Durchschnittswert U kann basierend auf N und 0 ausgedrückt werden

Das Ausdrücken von A wird schwieriger. Nehmen wir an, wir verwenden I Iterationen, bevor wir alle eindeutigen Werte gefunden haben. Danach wird zwischen 1 und U Vergleichen laufen (im Durchschnitt ist das U / ") und das wird N-I mal machen.

I * c + U / 2 (N-I)

aber was ist die durchschnittliche Anzahl der Vergleiche (c) wir für die ersten I Iterationen laufen. Im Durchschnitt müssen wir die Hälfte der bereits besuchten Elemente vergleichen, und im Durchschnitt haben wir I / 2-Elemente besucht, dh. c = I / 4

I / 4 + U / 2 (N-I).

Ich kann ausgedrückt werden als N. Im Durchschnitt müssen wir die Hälfte von N aufsuchen, um die eindeutigen Werte zu finden, so dass I = N / 2 ergibt einen Durchschnitt von

(I ^ 2) / 4 + U / 2 (N-I), die auf (3 * N ^ 2) / 16 reduziert werden kann.

Das ist natürlich, wenn meine Schätzung der Durchschnittswerte richtig ist. Das ist im Durchschnitt für jede mögliche Sequenz A hat N / 16 weniger Vergleiche als Y, aber es gibt Fälle, in denen Y schneller als A ist. Ich würde also sagen, dass sie im Vergleich zur Anzahl der Vergleiche gleich sind

Ihre Lösung ist genauso gut wie die des Autors, nur hat sie einen Fehler in der Implementierung :) Versuchen Sie, sie auf einer Liste von zwei Knoten mit gleichen Daten zu verfolgen.

Ihr Ansatz ist einfach nur ein Spiegelbild des Buches! Du gehst vorwärts, das Buch geht rückwärts. Es gibt keinen Unterschied, da Sie beide alle Elemente scannen. Und, ja, da kein Puffer zulässig ist, gibt es Leistungsprobleme. In der Regel müssen Sie sich nicht mit solchen überlasteten Fragen auseinandersetzen, wenn diese Fragen nicht berücksichtigt werden.

Interviewfragen werden gemacht, um deine offene Mentalität zu testen. Ich habe Zweifel an Marks Antwort: Es ist definitiv die beste Lösung in realen Beispielen, aber selbst wenn diese Algorithmen konstanten Speicherplatz verwenden, muss die Einschränkung, dass kein temporärer Puffer erlaubt ist, respektiert werden.

Ansonsten würde ich annehmen, dass das Buch einen solchen Ansatz angenommen hätte. Mark, bitte vergib mir, dass ich gegen dich kritisiert habe.

Wie auch immer, nur um tiefer in die Sache einzusteigen, benötigen Ihre und der Ansatz des Buches Theta(n^2) time, während Marks Ansatz Theta(n logn) + Theta(n) time benötigt, was in Theta(n logn) resultiert. Warum Theta ? Da compare-swap-Algorithmen auch Omega(n logn) sind, denken Sie daran!

Code in Java:

Erprobt das gleiche in cpp. Bitte lassen Sie mich Ihre Kommentare dazu wissen.

// ConsoleApplication2.cpp: Definiert den Einstiegspunkt für die Konsolenanwendung.     //

Code in C:

Hier ist die Antwort in C