Ranking der Interviewfragen FizzBuzz (1), Implementierung von malloc (10) [geschlossen]

Ich hätte gerne Ihre Meinung zur Schwierigkeit der folgenden Interviewfrage:

Suchen Sie das zusammenhängende Subarray mit der maximalen Summe in einem Array von Ganzzahlen in O (n) -Zeit.

Dieses trivial klingende Problem wurde von Jon Bentley in seinen Programming Pearls bekannt gemacht, wo er es verwendet, um Algorithmus-Design-Techniken zu demonstrieren.

Wie würden Sie auf einer Skala von 1 bis 10, wobei 1 der FizzBuzz- (oder HoppityHop- ) Test und 10 die C stdlib-Funktion malloc () ist, das obige Problem bewerten?

Ich denke, die Leute, die diese Frage am besten beantworten können, sind diejenigen, die Programmierperlen gelesen und versucht haben, dieses Problem selbst zu lösen. Um diejenigen zu motivieren, die dies nicht getan haben, wird 'Programming Pearls' mehrmals in der Liste der 'Top 10 Programmierbücher' aufgeführt.

Ein paar Kommentare könnten helfen, eine bessere Bewertung zu erhalten:

• Die Implementierung von malloc () ist nicht so beeindruckend, wie es scheint. Siehe zum Beispiel die Programmiersprache C von K & R. Es wird manchmal bei Microsoft gefragt .

• CLRS- Beobachtung zur Problemlösung: Es ist oft schwieriger, ein Problem von Grund auf zu lösen, als eine klar dargestellte Lösung zu überprüfen, insbesondere wenn unter Zeitbeschränkungen gearbeitet wird .

Das hängt wirklich vom Entwickler ab.

Wenn malloc 10 wäre, würde ich dieses Problem mit 20 bewerten. Aber andererseits habe ich malloc schon einmal gemacht und könnte es wahrscheinlich wieder tun.

Jemand, der dieses Problem gelöst hat oder den entsprechenden Algorithmus auf der Oberseite seines Kopfes kennt, macht es zu einer 5 und malloc () zu einer 10.

Das Problem bei dieser Art von Frage ist, dass, wenn Sie sie zuvor erledigt haben, sie einfach sind und dies wirklich ein Test dafür ist, ob Sie diesen Algorithmus schon einmal gesehen haben. Daher mag ich sie nicht für Interviews.

Für Tests, bei denen Sie dem Entwickler ein paar Tage Zeit geben, ist dies ein perfekter Test, denn wenn er den Algorithmus nicht kennt, geben Sie ihm die Möglichkeit, Nachforschungen anzustellen und sich auf den neuesten Stand zu bringen. Dies ist nicht nur ein Test Ihr Wissen, aber Ihre Fähigkeit, neues Wissen zu erlangen.

Ich denke, die Bewertung sollte zumindest zweidimensional sein. FizzBuzz- mallocbeschreibt den Bereich auf einer Achse, ich würde es "technologische Komplexität" nennen. Aber diese einzige Dimension reicht sicherlich nicht aus, um das Problem zu beschreiben. Um das fragliche Problem zu lösen, sollte der Entwickler mehr als nur Code denken , während die Implementierung mallocmehr Codierungsdisziplin erfordert als die Erstellung komplexer Algorithmen.

So würde ich diese Probleme arrangieren:

Um meinen Standpunkt zu verdeutlichen, habe ich die parallele Zusammenführungssortierung zum Plot hinzugefügt , da dies ein gutes Beispiel für eine technologisch und algorithmisch anspruchsvolle Aufgabe ist.

Ich denke, es ist erheblich schwieriger als FizzBuzz oder HoppityHop - diese beiden sind nichts weiter als ein einfaches If-else oder Switch-Case in einer Schleife.

Das maximale Subarray erfordert eine eingehendere Analyse des zugrunde liegenden Problems - dies ist in einer Programmierklasse für Anfänger nicht zu erwarten, da es höhere mathematische Fähigkeiten erfordert als ein Problem vom Typ FizzBuzz. Dieses Problem hat ein ähnliches Gefühl wie das Problem des kürzesten Pfades, das durch den Dijkstra-Algorithmus gelöst wird - vielleicht ist es eine Spezialisierung des Problems des längsten Pfades .

Auf Ihrer Skala von 1 bis 10 würde ich es wahrscheinlich zwischen 3 und 5 bewerten.

* Während der Server ausfiel , stellte ich fest, dass das maximale Subarray-Problem eine eigene Seite auf Wikipedia hat.

Ich gebe ihm eine 3. Über die meisten Programmierer hinaus, die ich interviewt habe, aber ein leichtes Problem für diejenigen, die ich zum Mieten empfohlen habe.