Wie wichtig ist es für einen Programmierer, einen QuickSort / MergeSort-Algorithmus aus dem Speicher zu implementieren? [geschlossen]

58

Ich habe meine Notizen überprüft und bin über die Implementierung verschiedener Sortieralgorithmen gestolpert.

Als ich versuchte, einen Sinn für die Implementierung von QuickSort und MergeSort zu finden, kam mir der Gedanke, dass ich, obwohl ich beruflich programmiere und mich für anständig halte, weder über das fotografische Gedächtnis noch über die schiere Intelligenz verfüge, um diese Algorithmen ohne zu implementieren unter Berufung auf meine Notizen. Ich erinnerte mich nur daran, dass einige dieser Algorithmen stabil sind und andere nicht. Einige benötigen O (nlog (n)) oder O (n ^ 2), um den Vorgang abzuschließen. Einige verwenden mehr Speicher als andere ...

Ich würde das Gefühl haben, dass ich diese Art von Arbeit nicht verdiene, wenn es nicht so wäre, weil meine Position nicht erfordert, dass ich einen anderen Sortieralgorithmus verwende als die, die in Standard-APIs zu finden sind. Ich meine, wie viele von Ihnen haben eine Programmierposition, bei der es wirklich wichtig ist, dass Sie sich an solche Dinge erinnern oder sich diese selbst einfallen lassen?

algorithms John Smith
quelle
13
Sie müssen sich daran erinnern, dass eine Lösung vorhanden ist und wann Sie sie verwenden müssen. Dann gehen Sie in die Dokumentation und implementieren Sie es. Wenn Sie nicht über Quicksort oder Mergesort Bescheid gewusst hätten, würden Sie Bubblesort weiterhin verwenden und beobachten, wie Ihr Programm crawlt und subparente Lösungen findet, wenn die Datenmenge steigt.
Pieter B
1
Abgesehen von den guten Antworten, die im Folgenden genannt werden, müssen viele Unternehmen (1) die Komplexität solcher Algorithmen kennen, (2) sie fließend auf einer Tafel implementieren.
Sakisk
3
Ich bin mir sicher, dass es wichtig ist, sich diese Algen zu merken, wenn Google häufig offline ist. : o
Lee James
Sie müssen ihre Leistung, Anwendungsfälle usw. kennen. Nur in Interviews müssen Tech-Unternehmen wissen, wie sie auswendig können.
Sakisk
@ DieterB, ich bin anderer Meinung. Man muss nicht über "Mergesort" und "Quicksort" zu Google "Best Performing Sorting Algorithmus"
wissen

Antworten:

117

Lassen Sie uns Albert fragen und sehen, was er zu diesem Thema zu sagen hat:

"Ich muss nicht alles wissen, ich muss nur wissen, wo ich es finden kann, wenn ich es brauche."

- Albert Einstein , umschrieben

Amen, Bruder Albert, Amen.

Sobald Sie einen guten Überblick über die wesentlichen Algorithmen in einer bestimmten Disziplin (Sortieren, Suchen usw.) erhalten haben, können Sie die Implementierungsdetails vergessen, bis Sie das Algo tatsächlich benötigen. In diesem Fall können Sie es nachschlagen oder a verwenden bereits existierende lib. Vor 25 Jahren baute ich ein großes Suchsystem mit B * -Bäumen auf, aber heute würde ich RTFM benötigen, um sie gut zu nutzen.

Peter Rowell
quelle
5
Dieses Zitat ist zweifelhaft: Ich kann "keine substanziellen Beweise finden, die das Sprichwort mit Einstein verbinden" .
Wok
9
Wie beantwortet das die Frage? Er sagte "Ich muss nicht alles wissen", er sagte nicht "Ich muss nichts wissen". Einige Fähigkeiten sind grundlegend, und die ganze Frage war, ob eine bestimmte Information zur Kategorie der grundlegenden Fähigkeiten gehört oder nicht.
Konrad Rudolph
1
Zu denken, dass das Ziel darin besteht, Quicksort auswendig zu lernen, bedeutet, den Punkt der Frage zu verfehlen. Wenn Sie in der Praxis eine allgemeine Kurzübersicht benötigen, können Sie natürlich die Bibliotheksroutine verwenden oder den Code nachschlagen und kopieren. Der Test besteht darin, festzustellen, ob Sie Rekursion, Schleifeninvarianten usw. verstehen. Die Aufforderung, schnell einen Sortieralgorithmus aufzuschreiben, ist nur eine einfache Demonstration dieses Wissens. Wenn Sie nicht in der Lage sind, eine 20-Zeilen-Quicksortierung vor Ort erneut abzuleiten, wie viele Dinge tun Sie routinemäßig wirklich ineffizient oder falsch, ohne es überhaupt zu wissen?
Larry Gritz
3
@ Larry: Ich glaube, ich habe mehr vergessen, als viele Programmierer über Details von Algorithmen Bescheid wissen - und Quick Sort from Scratch ist einer von ihnen - aus gutem Grund - ich habe mich dafür entschieden, über High-Level-Dinge zu lesen und lieber High-Level-Sprachen zu verwenden als unten in Schalen mit niedrigen Implementierungsdetails zu bleiben. Ehrlich gesagt - es ist mir egal, welche Art von Bibliotheksroutine ich verwende - es kann Pixy Dust und Feen verwenden, soweit es mich betrifft. Die Docs teilen dem O () die Größe mit - das ist alles, was ich wissen muss.
Mattnz
2
@mattnz: Eine etwas verspätete Fortsetzung Ihrer "O () Größe". Eine Sache, die ich auf die harte Tour gelernt habe, war, dass eine schlechte Referenzstelle bei einem großen Datensatz das O () völlig überwältigen kann. Sie haben vielleicht eine Algo , aber wenn Sie viele Cache-Ausfälle bekommen oder (Gott bewahre) auf die Festplatte treffen, dann ist das nur eine schöne Erinnerung. O(n log n)n log n
Peter Rowell
49

  1. Es geht nicht wirklich um Auswendiglernen. Es geht darum, allgemeine Klassen von Algorithmen wie Teilen und Erobern zu verstehen. Wenn Sie das Teilen und Erobern wirklich verstehen, brauchen Sie sich Quicksort nicht zu merken. Sie können es bei Bedarf vor Ort erneut abrufen. Außerdem lohnt es sich nicht einmal, Quicksorting selbst abzuleiten, sondern zu erkennen, wann ein neues Problem einer Lösung zum Teilen und Erobern zugänglich ist.

  2. Nicht alle Programmieraufträge sind gleich. Einige Jobs erfordern fundierte Kenntnisse über Algorithmen, andere brauchen Leute, die sich mit Typentheorie auskennen, und andere brauchen Leute, die Daten aus einem Webformular entfernen und in eine Datenbank verschieben können. Einige Jobs erfordern sogar all diese Fähigkeiten auf einmal. Bei welcher Art von Job möchten Sie arbeiten?

Charles E. Grant
quelle
5
Ich denke nicht, dass es möglich ist, QuickSort zu verstehen, ohne sich an QuickSort zu erinnern. Es ist keine komplizierte und arkane Sache, es sind nur zwei generische Ideen, die kombiniert werden. Das Gleiche gilt für das Zusammenführen, aber da haben Sie nur eine Idee: P
drxzcl
Ich bin mit Punkt 2 nicht einverstanden. Alle Jobs sind gleich, nur der Interviewer wechselt. Dieser kennt sich sehr gut mit Sortieren aus und glaubt, dass jeder gute Programmierer das Sortieren kennen muss, denn das ist alles, was er weiß und was ihn interessiert.
IAdapter
2
@IAdapter, du scherzt doch! Ich weiß aus eigener Erfahrung, dass die Kenntnisse und Fähigkeiten, die ich für meine erste Stelle beim Schreiben von TROFF-Makros für ein Shrink-Wrap-Software-Unternehmen benötigte, sich sehr von denen unterscheiden, die ich für meine derzeitige Tätigkeit in einem biologischen Computerlabor benötige.
Charles E. Grant
@ CharlesE.Grant Die meiste Zeit überprüft der Interviewer nicht, ob Sie die Fähigkeiten haben, die Sie für Ihre Arbeit benötigen.
IAdapter
10

Ich denke, Sie müssen sich nur an alles erinnern, wenn Sie sich für eine Stelle bewerben, wenn Sie vor Ort Antworten finden müssen und keine externen Ressourcen haben.

Ich habe Kollegen QuickSort und so weiter umschreiben lassen, aber ich fordere sie immer wieder auf, wieder die in der Sprache integrierten Sortierfunktionen zu verwenden. Ich weiß, dass wir uns abhängig von der Art der Projekte, an denen wir arbeiten, an andere Algorithmen erinnern müssen, da diese normalerweise nicht in Standardbibliotheken enthalten sind, die Sortierung jedoch nicht erfolgt, da sie normalerweise in die Sprache integriert ist.

Wenn wir uns diese Algorithmen merken müssen, wenden wir uns in der Regel Google oder einem Buch zu, und in der Regel wird nicht nach einer bestimmten Implementierung gesucht, sondern nach der besten Implementierung für unser Problem.

scaryrawr
quelle
6

Sich nur daran zu erinnern, welcher Algorithmus in welchen Szenarien nützlich ist, ist mehr als genug , um Ihnen bei Ihrer Arbeit zu helfen. Tatsächlich erfordern die meisten Programmieraufträge kein Auswendiglernen des Ansatzes. Sie interessieren sich vielmehr für Ihre Art , algorithmische Muster zu erkennen, wenn Sie mit dem Problem konfrontiert sind .

Tatsächlich gibt es in den meisten Programmierblogs / -artikeln zu Algorithmus-Themen eine Fülle von Informationen. Das Auswendiglernen der genauen Umsetzung spielt daher keine Rolle. Die wertvollste Information wäre, sich einen Überblick darüber zu verschaffen, welche Arten von Algorithmen zur Verfügung stehen und welche spezifischen Probleme sie lösen können . Die Suche nach einer genauen Implementierung, sobald Sie wissen, wonach Sie suchen, ist ziemlich schnell.

Zusammenfassend ist es immer besser zu wissen, wonach Sie suchen und wo sich die Referenzen befinden - was Sie zur Quelle führt.

EL Yusubov
quelle
5

Die genaue Implementierung ist nicht sehr wichtig. Das Prinzip von Mergesort / Quicksort - Rekursion, Partitionierung usw. ist jedoch sehr einfach und sollte von jedem Programmierer verstanden werden. Diese Algorithmen sind tatsächlich sehr einfach in Worten zu beschreiben, sobald Sie sie verstanden haben.

Es ist nicht wirklich ein Problem, ob Sie es nachschlagen oder googeln können, sondern ob Programmierer diese Problemlösungstechniken verstehen und sie auf andere Situationen anwenden können.

hgh
quelle
3

Ich bin bei diesem Thema zweideutig. Ich kenne viele Programmierer, die nicht wissen, was ein Sortieralgorithmus ist, aber ihre Arbeit ziemlich gut machen. Ich glaube auch daran, Prinzipien zu verstehen, um die Domäne wirklich zu verstehen.

Es fällt mir schwer, eine unvoreingenommene Antwort zu diesem Thema zu finden, da ich so lange programmiert habe, dass ich wahrscheinlich mehr Algorithmen vergessen habe, die ich derzeit kenne - aber die in dieser Frage erwähnten Sortierungen kenne ich immer noch. Ich denke, die Vordenker in Agile (z. B. Ron Jeffries, Alistair Cockburn) haben einige gute Ideen in der Nähe dieser Idee (z. B. Shu-Ha-Ri).

Zusammenfassend zu dieser verwirrenden Antwort: Verwenden Sie auf jeden Fall die API (NIH ist ein Zeichen für die Unreife des Entwicklers), aber verstehen Sie immer die zugrunde liegenden Prinzipien. Ich hoffe das hilft.

Mike Polen
quelle
2

Sortieren und Suchen sind unglaublich wichtig, egal ob Sie Donald Knuth-Fan sind oder die nächste Larry Page sein möchten. Abhängig von Ihrem Unternehmen und dem Grad des Wettbewerbs, den Sie unter Ihren Bewerbern ausüben können, würde ich Ihnen empfehlen, einige der folgenden Konzepte in das Interview aufzunehmen.

Sortierung

  • Skizze eines Sortieralgorithmus.
  • Nennen Sie einige Beispiele für Sortieralgorithmen.
  • Vergleichen Sie zwei Sorten mit unterschiedlichen Leistungsmerkmalen.
  • Wenn sie die Speichernutzung nicht erwähnen, fragen Sie danach.

Suchen

  • Nennen Sie so viele Suchalgorithmen wie möglich.
  • Vergleichen Sie zwei Suchalgorithmen.
  • Skizzieren Sie eine andere Suche als die lineare Suche.

Einige könnten sagen, dass das Erfordern des Codes für diese Algorithmen übertrieben ist, es sei denn, der Job befindet sich auf einer verlassenen Insel ohne Internetverbindung. Eine weitere Überlegung ist, dass die Implementierung dieser Art für viele Kandidaten einen großen Teil Ihrer Zeit in Anspruch nehmen kann, wenn Sie 30 Minuten Zeit haben und nach etwas anderem fragen möchten.

DeveloperDon
quelle
Früher hielt ich es für albern, Leute zu bitten, auf Interviews zu programmieren, aber man würde es einfach nicht glauben, dass es so viele Leute gibt, die scheinbar fantastische Lebensläufe haben und die "soziale" Fragen mit Bravour beantworten, die es aber für ihr Leben nicht können Schreiben Sie eine korrekte Implementierung von 'strcat' oder einer anderen einfachen Funktion auf. Dies hat mich mehrmals davon abgehalten, jemanden einzustellen, der, wenn nicht die alberne Codierungsfrage gewesen wäre, endlosen Kummer verursacht und das Team mit Inkompetenz runtergezogen hätte.
Larry Gritz