Forberedelse til kodeinterviews · Lektion

Tricket med forskellen på rækkenumre

Træk ROW_NUMBER fra en sekvens for at gruppere fortløbende værdier i islands

Lektion 2 af 413 trin

Tricket med forskellen på rækkenumre 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.

Den mest elegante ø-nøgle

Tricket med forskellen mellem rækkenumre er den teknik, interviewere helst vil se til øer med sammenhængende heltal eller datoer. Det beregner gruppenøglen med én subtraktion, uden LAG og uden løbende sum.

Hele idéen er: Træk et ROW_NUMBER fra selve værdien. I ethvert forløb med sammenhængende værdier øges både værdien og rækkenummeret præcis med 1 for hvert trin, så deres forskel er konstant gennem hele forløbet. Denne konstant er din ø-nøgle.

Hvorfor forskellen forbliver konstant

Tænk på to tilstødende rækker i et sammenhængende forløb. Når du går fra den ene til den næste, øges værdien med 1, og rækkenummeret øges med 1. Træk dem fra hinanden, så går +1'erne ud, og value - row_number ændrer sig ikke.

Men så snart der er et hul, springer værdien mere end 1, mens rækkenummeret stadig kun stiger med 1. Forskellen skifter til en ny konstant værdi. Det skift adskiller præcis den ene ø fra den næste.

Se det på vores data

Husk login-dagene 1, 2, 3, 7, 8, 10. Lad os stille rækkenummeret og forskellen op side om side:

dag 1, rn 1, forskel 0
dag 2, rn 2, forskel 0
dag 3, rn 3, forskel 0
dag 7, rn 4, forskel 3
dag 8, rn 5, forskel 3
dag 10, rn 6, forskel 4

Forskellene (0,0,0,3,3,4) opdeler perfekt rækkerne i de tre øer. Samme forskel betyder samme ø.

SELECT
  day_no,
  ROW_NUMBER() OVER (ORDER BY day_no) AS rn,
  day_no - ROW_NUMBER() OVER (ORDER BY day_no) AS grp
FROM logins
ORDER BY day_no;

Saml rækkerne til øer

Med forskellen som gruppenøgle er den sidste forespørgsel den sædvanlige samling. Omslut forskellen i en CTE, og brug GROUP BY på den:

Dette giver de samme tre øer som før, men SQL'en er kortere og tydeligere end versionen med LAG og løbende sum. For heltalssekvenser eller sekvenser med jævnt trin er dette det svar, du bør vælge først.

WITH keyed AS (
  SELECT
    day_no,
    day_no - ROW_NUMBER() OVER (ORDER BY day_no) AS grp
  FROM logins
)
SELECT
  MIN(day_no) AS start_day,
  MAX(day_no) AS end_day,
  COUNT(*)    AS length
FROM keyed
GROUP BY grp
ORDER BY start_day;

Faldgruben: Værdier skal stige med én ad gangen

Det enkle forskelstrick forudsætter, at sekvensen øges med præcis 1 for hvert trin. Det gælder for sammenhængende heltal og fortløbende kalenderdage, men det fungerer ikke, hvis dine værdier øges med en anden fast værdi, eller hvis der findes dubletter.

Selv de lige værdier 2, 4, 6, 8 vil fremstå som huller, hvis du trækker rækkenummeret fra værdien.
Dubletter forskyder justeringen, fordi rækkenummeret fortsætter med at stige, mens værdien ikke gør.

At kende denne begrænsning og vide, hvordan du retter den, er det, der adskiller et indlært trick fra reel forståelse.

Sekvenser med fast trinlængde

Hvis værdierne øges med en kendt konstant k i stedet for 1, skal du først normalisere dem: dividér værdien med k (eller brug value / k for heltal), så hvert trin igen bliver 1, og træk derefter rækkenummeret fra.

For lige tal med trin på 2 kan du for eksempel bruge day_no / 2 - ROW_NUMBER(). Den normaliserede værdi stiger nu med 1 for hvert efterfølgende element, så egenskaben med den konstante forskel genskabes.

SELECT
  val,
  (val / 2) - ROW_NUMBER() OVER (ORDER BY val) AS grp
FROM even_series
ORDER BY val;

Anvendelse på datoer

Datoer er det mest almindelige eksempel fra virkeligheden. Kalenderdatoer kan ikke trækkes direkte fra et rækkenummer, så du skal først konvertere datoen til et dagetal. I Postgres trækker du en fast forankringsdato fra datoen for at få et heltal, der angiver antal dage, og anvender derefter det samme trick.

Fordi fortløbende kalenderdage adskiller sig med 1, er forskellen mellem dagtallet og rækkenummeret igen konstant inden for en ø.

WITH keyed AS (
  SELECT
    login_date,
    (login_date - DATE '2000-01-01')
      - ROW_NUMBER() OVER (ORDER BY login_date) AS grp
  FROM daily_logins
)
SELECT MIN(login_date) AS start_date,
       MAX(login_date) AS end_date,
       COUNT(*)        AS days_in_run
FROM keyed GROUP BY grp ORDER BY start_date;

Datoforskelle på tværs af SQL-dialekter

Trinnet fra dato til heltal varierer fra databasesystem til databasesystem, og interviewere sætter pris på, at du kender forskellene på tværs af dialekter:

Postgres: træk en datoliteral fra: login_date - DATE '2000-01-01' giver et heltal.
MySQL: brug DATEDIFF(login_date, '2000-01-01').
SQL Server: brug DATEDIFF(day, '2000-01-01', login_date).

På nogle databasesystemer findes der en endnu smartere løsning: træk direkte ROW_NUMBER dage fra datoen ved hjælp af intervalregning, og lav derefter GROUP BY efter den resulterende forankringsdato.

SELECT
  login_date,
  login_date - (ROW_NUMBER() OVER (ORDER BY login_date)
               * INTERVAL '1 day') AS grp_date
FROM daily_logins;

Tilføjelse af partitioner pr. gruppe

Hvis du vil finde øer pr. bruger, skal du partitionere rækkenummeret efter gruppekollonnen. Det er afgørende, at gruppenøglen derefter også indeholder partitionskolonnen, fordi to forskellige brugere tilfældigvis kan få den samme forskelsværdi.

Lav derfor GROUP BY efter både user_id og den beregnede forskel. Hvis du glemmer user_id i den endelige GROUP BY, opstår der en subtil fejl, som interviewere elsker at opdage.

WITH keyed AS (
  SELECT user_id, day_no,
    day_no - ROW_NUMBER()
      OVER (PARTITION BY user_id ORDER BY day_no) AS grp
  FROM logins
)
SELECT user_id, MIN(day_no) AS start_day,
       MAX(day_no) AS end_day, COUNT(*) AS len
FROM keyed
GROUP BY user_id, grp
ORDER BY user_id, start_day;

Trick eller LAG: Hvad skal du bruge?

Du har nu to solide teknikker i værktøjskassen. Vælg bevidst:

Forskel mellem rækkenummer og værdi: kortest og enklest til serier med ensartede trin (sammenhængende heltal og fortløbende datoer). Det første valg, når naboskab betyder, at værdierne adskiller sig med en konstant.
LAG plus løbende sum: mere fleksibelt, når naboskab ikke er et fast numerisk trin, for eksempel når den aktuelle status skal være den samme som i den forrige række, eller når du har uregelmæssige specialregler.

Forklar dit valg og hvorfor i interviewet; din begrundelse imponerer mere end syntaksen.

Håndtering af dubletter med omtanke

Hvis en værdi kan gentage sig, og du stadig vil have én ø pr. sammenhængende serie, skal du først fjerne dubletter med DISTINCT eller et grupperings trin, så rækkenummeret passer én til én med værdierne. Alternativt kan du bruge DENSE_RANK i stedet for ROW_NUMBER, så ens værdier deler en rangering.

Spørg altid intervieweren, om der kan forekomme dubletter; den rigtige løsning afhænger af, om dubletter skal forlænge serien eller ignoreres i den.

WITH d AS (SELECT DISTINCT day_no FROM logins)
SELECT day_no,
  day_no - ROW_NUMBER() OVER (ORDER BY day_no) AS grp
FROM d;

Hurtigt tjek

Sørg for, at du forstår, hvorfor tricket virker.

Besvar den i den interaktive lektion

Opsummering: Forskels-tricket

Du har nu den reneste nøgle til en ø:

Nøgleformel: value - ROW_NUMBER() OVER (ORDER BY value) er konstant i hver sammenhængende serie.
Gruppér efter forskellen med GROUP BY for at få start, slut og længde.
For sekvenser med fast trinlængde skal du først normalisere dem (dividere med trinnet).
For datoer skal du konvertere til et heltal, der angiver antal dage, via dialektens differensfunktion.
Pr. gruppe: partitionér rækkenummeret med PARTITION BY, og medtag gruppekollonnen i den endelige GROUP BY.
Beskyt dig mod dubletter med DISTINCT eller DENSE_RANK.

Nu skifter vi fokus fra øer til de tomme mellemrum: at finde huller.

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 “Tricket med forskellen på rækkenumre” gratis?

Ja — hele teksten til “Tricket med forskellen på rækkenumre” 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 “Tricket med forskellen på rækkenumre”?

Træk ROW_NUMBER fra en sekvens for at gruppere fortløbende værdier i islands 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 “Tricket med forskellen på rækkenumre”?

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

Genkendelse af et Gaps-and-Islands-problem
Tricket med forskellen på rækkenumre
Find huller i en sekvens
Islands med ændringer i dato og status

← Tilbage til Forberedelse til kodeinterviews