Forberedelse til kodeintervjuer · leksjon

Gjenkjenne et Gaps-and-Islands-problem

Identifiser mønsteret i en tekstoppgave og den grunnleggende grupperingsinnsikten.

Leksjon 1 av 413 trinn

Gjenkjenne et Gaps-and-Islands-problem er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Mønsteret intervjuere tester

Når en seniorintervjuer ber deg finne sammenhengende sekvenser av noe, ser du på et gaps-and-islands-problem. Navnet kommer fra et mentalt bilde: Rader som hører sammen, danner en island, og bruddene mellom dem er gaps.

En island er en lengst mulig sammenhengende sekvens av rader som er tilstøtende etter en bestemt regel (sammenhengende heltall, sammenhengende datoer eller samme status gjentatt).
Et gap er mellomrommet som mangler mellom to islands.

Å gjenkjenne denne oppgavetypen umiddelbart er i seg selv et tegn på seniornivå. Mange kandidater tyr til et virvar av self-joiner, mens det elegante svaret nesten alltid er vindusfunksjoner.

Oppgaver som skjuler en island

Utfordringen er at intervjuere sjelden sier «gaps and islands». De kamuflerer problemet. Tren deg på å lytte etter formuleringer som:

«Finn hver periode en bruker var sammenhengende abonnert.»
«Hvor mange sammenhengende dager var serveren oppe?»
«Hvilke ID-intervaller mangler i denne tabellen?»
«Slå sammen tilstøtende rader med samme status til én rad.»

Alle disse har samme struktur: grupper rader som ligger ved siden av hverandre, og rapporter deretter start, slutt eller fravær for gruppene. Når du kobler formuleringene til islands, blir SQL-en nesten selvsagt.

Hovedinnsikten: Lag en gruppenøkkel

Her er hele trikset i én setning: Hvis du kan gi alle radene i samme island en identisk gruppenøkkel, kan en enkel GROUP BY slå sammen hver island til én oppsummeringsrad.

Det egentlige arbeidet i alle gaps-and-islands-problemer er derfor å beregne denne gruppenøkkelen. Ulike varianter beregner den på ulike måter, men målet er alltid det samme. Når du har nøkkelen, er det siste trinnet trivielt:

SELECT
  grp,
  MIN(value) AS island_start,
  MAX(value) AS island_end,
  COUNT(*)   AS island_length
FROM rows_with_group_key
GROUP BY grp
ORDER BY island_start;

Et konkret datasett

La oss ta utgangspunkt i data. Forestill deg en logins-tabell som registrerer hvilke dagnumre en bruker logget inn på:

Dager som finnes: 1, 2, 3, 7, 8, 10

Ved å se på dataene er islands {1,2,3}, {7,8} og {10}. Gapene er dag 4–6 og dag 9. Oppgaven din i et intervju er å få databasen til å finne disse tre islands uten at du peker på dem manuelt. Ha dette lille datasettet i tankene mens vi utforsker hver teknikk.

CREATE TABLE logins (day_no INT);
INSERT INTO logins VALUES (1),(2),(3),(7),(8),(10);

Hvorfor naive tilnærminger mislykkes

En vanlig første tanke er å sammenligne hver rad med den neste ved hjelp av en self-join og markere brudd. Det fungerer for å finne ett gap, men blir raskt uhåndterlig:

Du må finne både starten og slutten på hver island, noe som krever to gjennomganger eller to joiner.
Kanterader, altså den aller første og den aller siste, krever særskilt behandling.
Tilnærmingen kan ikke uten videre generaliseres til «gi meg lengden på hver sekvens» uten mer arbeid.

Intervjuere ser etter om du tyr til et virvar av self-joiner, eller om du innser at én gjennomgang med en vindusfunksjon er ryddigere.

Den mentale modellen for å finne gap

En robust måte å formulere det på er: En ny island begynner når den gjeldende raden ikke ligger rett etter den forrige raden. Bruk LAG til å hente forrige rad og sammenligne.

Hvis day_no - LAG(day_no) er større enn 1 (eller NULL for den første raden), begynner denne raden en ny island. Vi markerer dette med et flagg på 1, og ellers 0. Se hvordan disse flaggene ser ut for dataene våre.

SELECT
  day_no,
  CASE
    WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1 THEN 0
    ELSE 1
  END AS is_new_island
FROM logins
ORDER BY day_no;

Gjør flagg om til en gruppenøkkel

Flaggene fra forrige trinn er 1, 0, 0, 1, 0, 1 for dagene 1,2,3,7,8,10. Legg merke til at en løpende sum av disse flaggene gir et tall som forblir konstant innenfor en island og øker ved hver nye island: 1,1,1,2,2,3.

Denne løpende summen er den produserte gruppenøkkelen vår. Vi pakker flaggspørringen inn i en CTE og summerer den med en annen vindusfunksjon:

WITH flagged AS (
  SELECT
    day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new_island
  FROM logins
)
SELECT
  day_no,
  SUM(is_new_island) OVER (ORDER BY day_no) AS grp
FROM flagged;

Fullfør det gjennomgåtte eksempelet

Legg nå den avsluttende GROUP BY-en oppå gruppenøkkelen. Hver distinkte grp-verdi er én island, og vi rapporterer grensene og størrelsen:

Resultatet er nøyaktig de tre islands vi fant ved å se på dataene: 1–3 (lengde 3), 7–8 (lengde 2) og 10–10 (lengde 1). Denne oppskriften med tre lag (flagg, løpende sum, gruppering) er grunnstrukturen i nesten alle gaps-and-islands-svar du kommer til å skrive.

WITH flagged AS (
  SELECT day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new
  FROM logins
),
keyed AS (
  SELECT day_no,
    SUM(is_new) OVER (ORDER BY day_no) AS grp
  FROM flagged
)
SELECT grp, MIN(day_no) AS start_day,
       MAX(day_no) AS end_day, COUNT(*) AS len
FROM keyed GROUP BY grp ORDER BY start_day;

Tilstøting avhenger av domenet

Det eneste som endres mellom problemene, er definisjonen av tilstøting. Å finne riktig regel for tilstøting er halvparten av å gjenkjenne problemet:

Heltall: tilstøtende når differansen er nøyaktig 1.
Kalenderdager: tilstøtende når den ene datoen er dagen etter den andre (date = prev + INTERVAL '1 day').
Statusperioder: tilstøtende når statusverdien er uendret fra forrige rad.

Samme skjelett, men en annen sammenligning inne i CASE. Å finne ut hvilken regel for tilstøting som gjelder, er avklaringsspørsmålet du bør stille høyt i intervjuet.

Avklarende spørsmål du bør stille

Før du skriver en eneste SQL-linje, får du poeng ved å avklare omfanget. Gode avklaringer for gaps-and-islands-problemer er:

«Skal jeg behandle dataene per bruker eller globalt?» (Det avgjør om du legger til PARTITION BY user_id.)
«Kan det finnes duplikater på samme dag, og skal de bryte eller forlenge en sekvens?»
«Ønsker du islands, gaps eller begge deler?»
«Er sekvensen garantert sortert, eller skal jeg sortere den selv?»

Ved å stille disse spørsmålene viser du at du har løst denne typen problemer før, og at du forstår randtilfellene.

Islands per gruppe med PARTITION BY

Data i reelle intervjuer er nesten alltid gruppert, for eksempel innlogginger per bruker. Løsningen er mekanisk: Legg til PARTITION BY user_id i hver vindusfunksjon, slik at islands aldri går på tvers av brukere.

Skjelettet er identisk; du partisjonerer bare dataene. Derfor lønner det seg å mestre tilfellet med én datastrøm først: Skalering til grupper per bruker krever bare en endring av én klausul.

SELECT
  user_id, day_no,
  CASE WHEN day_no - LAG(day_no)
         OVER (PARTITION BY user_id ORDER BY day_no) = 1
       THEN 0 ELSE 1 END AS is_new
FROM logins;

Hurtigsjekk

Test instinktet ditt for mønstergjenkjenning.

Besvar den i den interaktive leksjonen

Oppsummering: Gjenkjenn strukturen

Du kan nå identifisere et gaps-and-islands-problem ut fra forkledningen og navngi strategien:

Utløsende ord: sammenhengende, kontinuerlig, ubrutt, rekke, manglende intervaller, slå sammen tilstøtende.
Kjerneidé: Gi alle radene i samme sekvens én identisk gruppenøkkel, og bruk deretter GROUP BY på den.
Oppskrift: Marker nye islands med LAG, summer flaggene løpende til en nøkkel, og aggreger deretter.
Regelen for tilstøting er domenespesifikk (heltall, datoer eller uendret status).
Legg til PARTITION BY for analyse per gruppe, og avklar omfanget før du koder.

Deretter skjerper vi den mest elegante metoden for å bygge en nøkkel: trikset med differansen mellom radnumre.

Gratis å komme i gang

Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 90
Leksjoner: 360

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Gjenkjenne et Gaps-and-Islands-problem» gratis?

Ja – hele teksten i «Gjenkjenne et Gaps-and-Islands-problem» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Hva lærer jeg i «Gjenkjenne et Gaps-and-Islands-problem»?

Identifiser mønsteret i en tekstoppgave og den grunnleggende grupperingsinnsikten. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?

Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.

Hvor lang tid tar leksjonen «Gjenkjenne et Gaps-and-Islands-problem»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?

Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til Forberedelse til kodeintervjuer