Forberedelse til kodeinterviews · Lektion

Den n'te højeste værdi med DENSE_RANK

Generalisér til den n'te entydige værdi, og håndtér dubletter

Lektion 2 af 413 trin

Den n'te højeste værdi med DENSE_RANK er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.

Generalisering til den N.-højeste løn

Når du kan finde den næsthøjeste løn, spørger interviewere straks: "Giv mig nu den N.-højeste." Det reneste og mest forsvarlige svar bruger DENSE_RANK.

Mønstret er altid det samme: Rangordn forskellige lønninger i faldende rækkefølge, og filtrer derefter efter den række, hvis rang er lig med N. Fordi logikken ikke ændrer sig med N, besvarer denne ene tilgang hele denne type spørgsmål.

Vi bygger løsningen op, håndterer ens lønninger og dubletter og gennemgår, hvorfor DENSE_RANK er den rigtige rangordningsfunktion til betydningen "forskellig værdi".

Den grundlæggende skabelon

Her er den genbrugelige skabelon til den N.-højeste løn. Erstat konstanten med det N, intervieweren spørger efter.

Du beregner DENSE_RANK i en indre forespørgsel (vinduesfunktionen kan ikke stå i WHERE) og filtrerer derefter efter rnk = N udenfor. For den tredjehøjeste løn skal du sætte filteret til 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;

Sådan nummererer DENSE_RANK forskellige værdier

DENSE_RANK tildeler ens værdier samme rang og efterlader aldrig et hul bagefter. Det er præcis definitionen på den "N.-te forskellige værdi", som interviewere mener.

For lønningerne 800, 800, 600, 600, 400:

800 -> rang 1
600 -> rang 2
400 -> rang 3

Den tredjehøjeste løn er altså 400, selv om der er fem rækker. Dubletter samles automatisk i én rang.

Hvorfor RANK giver det forkerte svar

Erstat den med RANK, så bliver svaret forkert. RANK efterlader huller, der svarer til antallet af ens værdier.

For lønningerne 800, 800, 600, 600, 400:

800, 800 -> rang 1 (to af dem)
600, 600 -> rang 3 (hul, ingen rang 2)
400 -> rang 5

Filtrering efter rnk = 3 returnerer 600, og rnk = 2 returnerer ingen rækker. Medmindre intervieweren specifikt ønsker rangordning som i konkurrencer, er DENSE_RANK korrekt til betydningen "den N.-højeste forskellige løn".

Hvorfor ROW_NUMBER også er forkert her

ROW_NUMBER tildeler hver række et unikt nummer og ignorerer ens værdier fuldstændigt. For 800, 800, 600, 600, 400 giver den 1, 2, 3, 4, 5.

Så rn = 3 returnerer 600, men rn = 2 returnerer dubletten 800, ikke en anden forskellig værdi. ROW_NUMBER besvarer spørgsmålet "den N. række" og ikke "den N. forskellige værdi".

Brug kun ROW_NUMBER, når spørgsmålet reelt handler om en bestemt række, f.eks. ved deduplikering eller når du skal beholde præcis én række blandt de N bedste pr. gruppe.

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

Parameterisering af N på en sikker måde

I rigtig kode ville du ikke indkode rangen fast. Send N som en parameter, og sammenlign med den. Vinduesdefinitionen forbliver identisk; kun det ydre filter parameteriseres.

Det er også her, du kan returnere alle ens lønninger på rang N: Fordi DENSE_RANK deler en rang mellem ens værdier, kan WHERE rnk = N returnere flere rækker, hvis flere medarbejdere har den N.-højeste forskellige løn, hvilket ofte er den ønskede adfærd.

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

Generalisering med korreleret optælling

Tilgangen fra før vinduesfunktioner kan også generaliseres: En løn er den N.-højeste forskellige løn, når præcis N - 1 forskellige lønninger er strengt højere end den.

For den tredjehøjeste løn kræves præcis to forskellige højere lønninger. Det fungerer i ældre databasemotorer uden vinduesfunktioner, men skalerer dårligt, fordi den indre optælling køres igen for hver række i den ydre forespørgsel.

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

MySQL-funktionsformen, interviewere spørger efter

Det LeetCode-lignende problem om "den N.-højeste løn" beder ofte om en lagret funktion, der returnerer en enkelt værdi. Funktionens krop er blot DENSE_RANK-skabelonen pakket ind, så den returnerer én løn.

Du behøver ikke at kunne huske den præcise funktionssyntaks til et interview, men det er værd at vide, at LIMIT N-1, 1 over forskellige lønninger er det korte MySQL-udtryk.

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

Gennemarbejdet eksempel: den fjerdehøjeste løn

Lønninger: 1000, 900, 900, 700, 500, 500, 300.

Forskellige lønninger i faldende rækkefølge med DENSE_RANK:

1000 -> 1
900 -> 2
700 -> 3
500 -> 4
300 -> 5

Den fjerdehøjeste løn er 500. Bemærk, at begge rækker med 500 har rang 4, så filtrering efter rnk = 4 returnerer begge medarbejdere, der tjener 500, hvis du også vælger deres id'er.

Bemærkninger om ydeevne

Hvordan klarer metoderne sig på store datamængder?

DENSE_RANK: Én sortering af dataene og derefter et filter. Effektivt, og forespørgselsplanlæggeren kan bruge et indeks på salary til sorteringen.
Korreleret optælling: Potentielt O(n i anden), fordi det indre aggregat køres for hver række. Undgå den på store tabeller.
LIMIT/OFFSET: Hurtig ved små N, men dataene skal stadig sorteres, og store forskydninger scanner og kasserer mange rækker.

Læg ud med DENSE_RANK, så går du sjældent galt i byen.

Kanttilfælde, du bør nævne

Stærke kandidater nævner kanttilfældene, før de bliver spurgt:

N større end antallet af forskellige lønninger: Filteret matcher ingen rækker, og resultatet bliver tomt. Lektion 4 gennemgår, hvordan du tvinger en enkelt NULL frem.
Ens lønninger på rang N: DENSE_RANK returnerer alle medarbejdere med samme rang; afgør, om det er det ønskede resultat.
N = 1: Skabelonen fungerer stadig og returnerer maksimum.

Hurtigt tjek

Anvend skabelonen til den N.-højeste løn.

Besvar den i den interaktive lektion

Opsummering

Den N.-højeste løn har ét oplagt standardsvar: Rangordn forskellige lønninger med DENSE_RANK() OVER (ORDER BY salary DESC) i en underforespørgsel, og filtrer derefter med WHERE rnk = N.

DENSE_RANK betyder "den N.-te forskellige værdi", hvor ens værdier deler rang uden huller.
RANK indsætter huller, mens ROW_NUMBER tæller rækker og ikke værdier.
Tricket med korreleret optælling = N-1 generaliserer den samme idé uden vinduesfunktioner, men skalerer dårligt.

Gør altid opmærksom på kanttilfældet, hvor N overstiger antallet af tilgængelige værdier. Det løser vi nu.

Gratis at komme i gang

Lær Forberedelse til kodeinterviews med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 90
Lektioner: 360

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Den n'te højeste værdi med DENSE_RANK” gratis?

Ja — hele teksten til “Den n'te højeste værdi med DENSE_RANK” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Den n'te højeste værdi med DENSE_RANK”?

Generalisér til den n'te entydige værdi, og håndtér dubletter Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?

Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.

Hvor lang tid tager lektionen “Den n'te højeste værdi med DENSE_RANK”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?

Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

Næsthøjeste løn på fem måder
Den n'te højeste værdi med DENSE_RANK
Den bedst lønnede pr. afdeling
Returnér NULL, når den n'te værdi ikke findes

← Tilbage til Forberedelse til kodeinterviews