Meine liebste Interviewfrage für Software Engineering: Median berechnen

 (krisshamloo.com)
1 Punkte von GN⁺ 4 시간 전 | 1 Kommentare | Auf WhatsApp teilen
  • Kleine Implementierungsaufgaben in technischen Interviews können wirkungsvoller sein als Rätsel, und die Berechnung des Medians zeigt zugleich grundlegende Coding-Fähigkeiten und Gespür für Design
  • Da das Problem eine Sortierung erfordert, führt es ganz natürlich zu API-Diskussionen wie: Soll die Funktion selbst sortieren, soll der Aufrufer sortieren, und darf das Original-Array verändert werden?
  • Die Verzweigung zwischen ungerader und gerader Länge, Indexberechnung und off-by-one-Fehler eignen sich gut, um den Debugging-Prozess von Kandidaten zu beobachten
  • Innerhalb einer kurzen Aufgabe lassen sich der Unterschied zwischen Median und Mittelwert, die Eignung zum Schreiben von Tests und sogar Kenntnisse der Python-Standardbibliothek statistics prüfen
  • Die Beispielimplementierung wirft bei einer leeren Liste einen ValueError, sortiert mit sorted() auf einer Kopie und gibt bei gerader Länge den Mittelwert der beiden mittleren Werte, bei ungerader Länge den mittleren Wert zurück

Warum sich die Median-Aufgabe gut für Interviews eignet

  • Gute Fragen für technische Interviews sollten keine verkopften Rätsel sein, sondern aus einer intuitiven Implementierung heraus tiefere Themen erschließen
  • Die Frage „Schreiben Sie eine Funktion, die ein Zahlenarray entgegennimmt und den Median zurückgibt“ eignet sich gut als Signal vom Typ Fizz Buzz, um zu prüfen, ob ein Kandidat tatsächlich programmieren kann
  • Die Reduktion von Array-Werten auf ein einzelnes Ergebnis gehört zu den Grundlagen, und das Problem ist klein genug, um Gespräch und Debugging gut gemeinsam zu beobachten

Entscheidungspunkte, die sich in der Implementierung zeigen

  • Für die Berechnung des Medians ist zunächst eine Sortierung erforderlich
    • Es muss entschieden werden, ob die Funktion selbst sortiert oder ob der Aufrufer ein sortiertes Array übergeben muss
    • Wenn das Array per Referenz übergeben wird, gehört auch zur API-Vereinbarung, ob das Original verändert werden darf
    • Solche Entscheidungen führen auch zu Performance-Diskussionen
  • Bei der Indexberechnung gibt es off-by-one-Fallstricke
    • Wichtiger als der Fehler selbst ist die Beobachtung, wie kleine Probleme debuggt werden
  • Je nach Array-Länge unterscheidet sich die Rückgabe
    • Bei gerader Länge wird der Mittelwert der beiden mittleren Werte zurückgegeben
    • Bei ungerader Länge wird der mittlere Wert zurückgegeben

Gespräche, die sich aus einer kurzen Aufgabe entwickeln

  • Daraus kann sich eine Statistik-Diskussion ergeben, etwa warum der Median im Vergleich zum Mittelwert in den meisten Fällen die bessere Wahl sein kann
  • Da Eingaben und erwartete Werte einfach sind, lässt sich die Aufgabe gut testen, und Kandidaten können ein Gespür für Tests zeigen
  • In Python bietet sich außerdem die Gelegenheit, Kenntnisse der Standardbibliothek statistics zu zeigen

Entscheidungen in der Beispielimplementierung in Python

  • Bei einer leeren Liste wird ValueError("median called with empty list") ausgelöst
  • Mit sorted(numbers) wird die Eingabeliste im Unterschied zu numbers.sort() nicht direkt sortiert
  • Die Länge wird mit len(numbers) ermittelt, der mittlere Index mit mid = length // 2 berechnet
  • Bei gerader Länge wird (numbers[mid - 1] + numbers[mid]) / 2.0 zurückgegeben, bei ungerader Länge numbers[mid]

Verwandte Beiträge

1 Kommentare

 
GN⁺ 4 시간 전
Lobste.rs-Kommentare

  • Ich verstehe diesen Beitrag nicht so recht. Der Autor scheint nicht zu wissen, dass sich der Median in O(n) berechnen lässt. Siehe: https://rcoh.me/posts/linear-time-median-finding/
    Deshalb ist die Aussage „Die Zahlen müssen von Anfang an sortiert sein“ falsch. Darum halte ich das auch nicht für eine gute Interviewfrage. Die optimale Lösung ist ein komplexer Algorithmus; wenn man ihn nicht auswendig kennt, ist es schwer, ihn spontan zu erwarten, und selbst wenn jemand ihn auswendig kennt, hilft das bei der Bewertung von Kandidaten nicht besonders.
    Eher könnte man den Kandidaten bitten, die naive Lösung zu nennen: das Array mit einer Bibliotheksfunktion zu sortieren und dann den mittleren Wert zurückzugeben

    • Ich war fast wütend, weil ich mich erinnere, mit einer n*log(n)-Lösung in einem Telefoninterview ausgesiebt worden zu sein
      Später habe ich im Algorithmik-Kurs quickselect gelernt und gedacht: „Die können doch unmöglich erwartet haben, dass man darauf spontan kommt.“ Nun ja, vielleicht passte ich einfach nicht zu der Stelle
    • Ich bin der Autor. Wenn ein Kandidat quickselect erwähnt, fände ich das ziemlich beeindruckend. Trotzdem halte ich das nicht für eine schlechte Frage. Auch mit rein intuitiven Algorithmen gibt es viel Gesprächsstoff
      Zu der Aussage, man könne „die naive Lösung erwarten, das Array mit einer Bibliotheksfunktion zu sortieren und den mittleren Wert zurückzugeben“: Ich würde vom Kandidaten keinen besseren Code erwarten als in der python standard library

  • Als Bonus sieht man sofort, ob jemand Algorithmen gelernt oder sich zumindest auf Interviews vorbereitet hat. Er wird vorschlagen, quickselect zu verwenden: https://en.wikipedia.org/wiki/Quickselect

    • Ich war überrascht, dass das nicht erwähnt wurde. Wenn ich diese Frage bekäme und C++ benutzen würde, würde ich wohl nth_element verwenden
      Und wenn ich quickselect komplett selbst schreiben müsste, ginge das auch. Im Grunde ist es fast Partitionierung + binäre Suche
    • Ich glaube eigentlich nicht, dass es darum geht. Diese Frage wirkt eher wie eine grundlegende Prüfung: „Kann die Person tatsächlich programmieren?“ bzw. „Hat der Screener seine Arbeit richtig gemacht?“ Selbst wenn ich quickselect aus dem Stegreif herunterbeten könnte, würde ich es vermutlich nicht perfekt hinbekommen und aus Rücksicht auf die Zeit des Interviewers die naive Lösung wählen
    • Interessant wird es bei Arrays mit gerader Länge. Man kann den normalen quickselect zweimal für die beiden mittleren Indizes laufen lassen oder quickselect für diese Aufgabe anpassen. Im Grunde könnte das auf dasselbe hinauslaufen
    • Mich hat die Anforderung verwirrt, dass die Liste unbedingt sortiert sein müsse. Intuitiv ist das auch gar nicht nötig
    • Das war die Antwort, die ich von einem LLM bekommen habe, inklusive einer immutablen Variante, die man bei Bedarf wählen könnte

  • Der int-Typ in Python hat keinen Overflow, aber wenn man C, C++ oder Go verwendet, müsste man sich im Zweig für Arrays gerader Länge nicht auch um Additions-Overflow sorgen?

    • Diese Addition passiert nicht bei int, sondern bei float. Trotzdem kann es durch Overflow zu inf kommen. Wenn beide Elemente im Array sys.float_info.max sind, sollte die Antwort ebenfalls sys.float_info.max sein, aber das Ergebnis der Addition wird inf, und auch nach der Division durch 2 bleibt es inf
      Man könnte versuchen, das zu beheben, indem man die Division durch 2 auf die Addition verteilt, aber dann bekommt man bei denormalisierten Zahlen ein falsches Ergebnis. Die meisten scheinen einfach anzunehmen, dass in Programmen keine Zahlen vorkommen, die groß genug sind, um dieses Problem auszulösen. Auch numpy gibt hier mit einer Warnung inf zurück: 
      >>> import sys  
>>> import numpy  
>>> numpy.median([sys.float_info.max, sys.float_info.max])  
.../venv/lib64/python3.11/site-packages/numpy/_core/_methods.py:132: RuntimeWarning: overflow encountered in reduce  
  ret = umr_sum(arr, axis, dtype, out, keepdims, where=where)  
np.float64(inf)

  • Tatsächlich gibt es auch mehrere Möglichkeiten, den Median selbst festzulegen. Man kann sich etwa für lineare Interpolation, die obere Grenze oder die untere Grenze entscheiden
    Und wenn man zu Quantilen übergeht, kann man stundenlang darüber reden. Ob man nur eines auswählt oder mehrere auf einmal, erfordert unterschiedliche Ansätze

  • Interviewfragen wie im Originalbeitrag verwende ich nicht. Ich verlange Sanftheit, also dass die Schwierigkeit der Aufgabe sich je nach Fähigkeit und Erfahrung des Kandidaten glatt verändert. Wenn insbesondere das Wissen um Bibliotheksfunktionen oder Algorithmen wie quickselect oder Radixsort das Ergebnis abrupt verändert, ist das keine gute Messaufgabe
    Dann misst man nicht Erfahrung und Fähigkeit des Kandidaten, sondern prüft nur, ob er ein bestimmtes magisches Artefakt kennt. Man kann das mit Anschlussfragen abfedern, aber besser ist es, von Anfang an eine sanftere Aufgabe zu stellen

    • Falls du ein Beispiel teilen kannst, wäre ich sehr neugierig auf ein konkretes Beispiel für so eine sanfte Aufgabe