Coding Interview Prep · Lektion

Der n-höchste Wert mit DENSE_RANK

Auf den n-höchsten unterschiedlichen Wert verallgemeinern und Duplikate behandeln

Der n-höchste Wert mit DENSE_RANK ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Verallgemeinerung auf das N.-höchste Gehalt

Sobald Sie das zweithöchste Gehalt finden können, fragen Interviewer sofort nach: „Und jetzt geben Sie mir das N.-höchste Gehalt.“ Die sauberste und am besten begründbare Antwort verwendet DENSE_RANK.

Das Muster ist immer gleich: Rängen Sie unterschiedliche Gehälter absteigend und filtern Sie anschließend nach der Zeile, deren Rang N entspricht. Da sich die Logik mit N nicht ändert, beantwortet dieser eine Ansatz die gesamte Familie solcher Fragen.

Wir bauen die Lösung schrittweise auf, behandeln Gleichstände und Duplikate und besprechen, warum DENSE_RANK für die Semantik „unterschiedlicher Wert“ die richtige Rankingfunktion ist.

Die grundlegende Vorlage

Hier ist die wiederverwendbare Vorlage für das N.-höchste Gehalt. Ersetzen Sie die Konstante durch den Wert für N, nach dem der Interviewer fragt.

Sie berechnen DENSE_RANK in einer inneren Abfrage, da die Fensterfunktion nicht in WHERE verwendet werden kann, und filtern außerhalb nach rnk = N. Für das dritthöchste Gehalt setzen Sie den Filter auf rnk = 3.

SELECT salary AS nth_highest
FROM (
  SELECT salary,
         DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
  FROM employee
) ranked
WHERE rnk = 3;

Wie DENSE_RANK unterschiedliche Werte nummeriert

DENSE_RANK weist gleichen Werten denselben Rang zu und lässt danach niemals eine Rangnummer aus. Genau das ist die Definition des „N.-höchsten unterschiedlichen Werts“, die Interviewer meinen.

Für die Gehälter 800, 800, 600, 600, 400 gilt:

800 → Rang 1
600 → Rang 2
400 → Rang 3

Das dritthöchste Gehalt ist also 400, obwohl es fünf Zeilen gibt. Duplikate werden automatisch zu einem einzigen Rang zusammengefasst.

Warum RANK das falsche Ergebnis liefert

Ersetzen Sie DENSE_RANK durch RANK, und das Ergebnis ist falsch. RANK lässt entsprechend der Anzahl der Gleichstände Rangnummern aus.

Für die Gehälter 800, 800, 600, 600, 400 gilt:

800, 800 → Rang 1 (zweimal)
600, 600 → Rang 3 (Lücke, kein Rang 2)
400 → Rang 5

Ein Filter auf rnk = 3 liefert 600, während rnk = 2 nichts liefert. Wenn der Interviewer nicht ausdrücklich eine Rangfolge im Wettbewerbsstil verlangt, ist DENSE_RANK für das „N.-höchste unterschiedliche Gehalt“ die richtige Wahl.

Warum ROW_NUMBER hier ebenfalls falsch ist

ROW_NUMBER weist jeder Zeile eine eindeutige Nummer zu und ignoriert Gleichstände vollständig. Für 800, 800, 600, 600, 400 entstehen die Nummern 1, 2, 3, 4, 5.

rn = 3 liefert daher 600, aber rn = 2 liefert das doppelte Gehalt 800 statt eines unterschiedlichen zweithöchsten Werts. ROW_NUMBER beantwortet die Frage „die N.-te Zeile“, nicht „der N.-te unterschiedliche Wert“.

Verwenden Sie ROW_NUMBER nur, wenn die Frage tatsächlich eine bestimmte Zeile verlangt, etwa zur Entfernung von Duplikaten oder für Top-N-pro-Gruppe-Abfragen, bei denen genau eine Zeile behalten werden soll.

SELECT salary, ROW_NUMBER() OVER (ORDER BY salary DESC) AS rn
FROM employee;

N sicher parametrisieren

In echtem Code würden Sie den Rang nicht fest codieren. Übergeben Sie N als Parameter und vergleichen Sie damit. Die Fensterdefinition bleibt identisch; nur der äußere Filter wird parametrisiert.

Hier können Sie auch alle Gehälter mit Rang N zurückgeben: Da DENSE_RANK bei Gleichständen denselben Rang verwendet, kann WHERE rnk = N mehrere Zeilen liefern, wenn mehrere Mitarbeiter dasselbe N.-höchste unterschiedliche Gehalt haben. Das ist oft das gewünschte Verhalten.

SELECT id, salary
FROM (
  SELECT id, salary,
         DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
  FROM employee
) ranked
WHERE rnk = :n;

Die Verallgemeinerung der korrelierten Zählung

Auch der Ansatz ohne Fensterfunktion lässt sich verallgemeinern: Ein Gehalt ist das N.-höchste unterschiedliche Gehalt, wenn genau N - 1 unterschiedliche Gehälter strikt höher sind.

Für das dritthöchste Gehalt müssen genau zwei unterschiedliche höhere Gehälter vorhanden sein. Das funktioniert in älteren Datenbanksystemen ohne Fensterfunktionen, skaliert aber schlecht, weil die innere Zählung für jede äußere Zeile erneut ausgeführt wird.

SELECT DISTINCT salary AS nth_highest
FROM employee e
WHERE (
  SELECT COUNT(DISTINCT e2.salary)
  FROM employee e2
  WHERE e2.salary > e.salary
) = 2;

Die MySQL-Funktionsform, nach der Interviewer fragen

Bei der LeetCode-ähnlichen Aufgabe „Nth highest salary“ wird häufig eine gespeicherte Funktion verlangt, die einen einzelnen Wert zurückgibt. Der Funktionskörper besteht einfach aus der DENSE_RANK-Vorlage, angepasst für die Rückgabe eines Gehalts.

Sie müssen sich im Bewerbungsgespräch nicht die exakte Syntax der Funktion merken. Es ist aber hilfreich zu wissen, dass LIMIT N-1, 1 über unterschiedlichen Gehältern die kompakte MySQL-Schreibweise dafür ist.

SELECT DISTINCT salary
FROM employee
ORDER BY salary DESC
LIMIT 1 OFFSET 2;  -- N = 3, so OFFSET N-1

Beispiel: das vierthöchste Gehalt

Gehälter: 1000, 900, 900, 700, 500, 500, 300.

Absteigend sortierte unterschiedliche Gehälter mit DENSE_RANK:

1000 → 1
900 → 2
700 → 3
500 → 4
300 → 5

Das vierthöchste Gehalt ist 500. Beachten Sie, dass beide Zeilen mit 500 Rang 4 erhalten. Wenn Sie zusätzlich ihre IDs auswählen, liefert ein Filter auf rnk = 4 daher beide Mitarbeiter mit einem Gehalt von 500.

Hinweise zur Performance

Wie schneiden die Ansätze bei großen Datenmengen ab?

DENSE_RANK: eine Sortierung der Daten und anschließend ein Filter. Der Ansatz ist effizient, und der Abfrageplaner kann für die Sortierung einen Index auf salary verwenden.
Korrelierte Zählung: potenziell O(n²), weil das innere Aggregat für jede Zeile ausgeführt wird. Vermeiden Sie diesen Ansatz bei großen Tabellen.
LIMIT/OFFSET: bei kleinem N schnell, muss aber ebenfalls sortieren; große Offsets durchsuchen viele Zeilen und verwerfen sie anschließend.

Beginnen Sie mit DENSE_RANK, dann liegen Sie nur selten falsch.

Sonderfälle, die Sie erwähnen sollten

Starke Kandidaten nennen die Sonderfälle, bevor sie danach gefragt werden:

N größer als die Anzahl der unterschiedlichen Gehälter: Der Filter trifft keine Zeilen und liefert ein leeres Ergebnis. In Lektion 4 erfahren Sie, wie Sie stattdessen genau ein NULL erzwingen.
Gleichstände bei Rang N: DENSE_RANK liefert jeden Mitarbeiter mit diesem Rang zurück. Entscheiden Sie, ob das gewünscht ist.
N = 1: Die Vorlage funktioniert weiterhin und liefert das Maximum.

Kurzer Test

Wenden Sie die Vorlage für das N.-höchste Gehalt an.

Zusammenfassung

Für das N.-höchste Gehalt gibt es eine Standardlösung: Rängen Sie unterschiedliche Gehälter mit DENSE_RANK() OVER (ORDER BY salary DESC) in einer Unterabfrage und filtern Sie anschließend mit WHERE rnk = N.

DENSE_RANK bedeutet „N.-ter unterschiedlicher Wert“: Bei Gleichständen teilen sich die Werte einen Rang, und es gibt keine Lücken.
RANK führt Lücken ein; ROW_NUMBER zählt Zeilen statt Werte.
Der Trick korrelierte Zählung = N-1 verallgemeinert dieselbe Idee ohne Fensterfunktionen, skaliert aber schlecht.

Weisen Sie immer auf den Sonderfall hin, dass N die verfügbaren Werte übersteigt. Diesen Fall lösen wir als Nächstes.

Häufig gestellte Fragen

Ist die Lektion „Der n-höchste Wert mit DENSE_RANK“ kostenlos?

Ja — der vollständige Text von „Der n-höchste Wert mit DENSE_RANK“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Der n-höchste Wert mit DENSE_RANK“?

Auf den n-höchsten unterschiedlichen Wert verallgemeinern und Duplikate behandeln Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um Coding Interview Prep zu starten?

Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.

Wie lange dauert die Lektion „Der n-höchste Wert mit DENSE_RANK“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?

Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

Das zweithöchste Gehalt auf fünf Arten
Der n-höchste Wert mit DENSE_RANK
Der Spitzenverdiener je Abteilung
NULL zurückgeben, wenn kein n-ter Wert existiert

← Zurück zu Coding Interview Prep