0Pricing
Coding Interview Prep · Lezione

Riconoscere un problema di gaps-and-islands

Individuare il pattern in un problema descritto a parole e l'intuizione fondamentale sul raggruppamento

Riconoscere un problema di gaps-and-islands è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.

Lo schema che gli intervistatori vogliono verificare

Quando un intervistatore senior chiede di trovare sequenze consecutive di qualcosa, si tratta di un problema di gaps-and-islands. Il nome deriva da un'immagine mentale: le righe che appartengono allo stesso gruppo formano un'isola, mentre le interruzioni tra loro sono i vuoti.

  • Un'isola è una sequenza massimale di righe adiacenti secondo una certa regola (interi consecutivi, date consecutive oppure lo stesso stato ripetuto).
  • Un vuoto è lo spazio mancante tra due isole.

Riconoscere immediatamente questa categoria di problemi è già un segnale di seniority. Molti candidati ricorrono a un groviglio di self-join; la soluzione elegante consiste quasi sempre nelle funzioni finestra.

Problemi descrittivi che nascondono un'isola

La difficoltà sta nel fatto che gli intervistatori raramente dicono "gaps-and-islands". Lo nascondono dietro altre formulazioni. Impari a riconoscere espressioni come:

  • "Trovi ogni periodo in cui un utente è stato continuativamente abbonato."
  • "Per quanti giorni consecutivi il server è rimasto operativo?"
  • "Quali intervalli di ID mancano in questa tabella?"
  • "Raggruppi le righe adiacenti con lo stesso stato in un'unica riga."

Tutti questi casi hanno la stessa struttura: raggruppare le righe adiacenti e poi restituire l'inizio, la fine o l'assenza di tali gruppi. Una volta associate le parole al concetto di isole, la query SQL si scrive quasi da sola.

L'idea fondamentale: creare una chiave di gruppo

Ecco il trucco in una sola frase: se assegna a ogni riga della stessa isola una chiave di gruppo identica, un semplice GROUP BY riduce ogni isola a una riga riepilogativa.

Il vero lavoro, quindi, in ogni problema di gaps-and-islands consiste nel calcolare questa chiave di gruppo. Le diverse varianti la calcolano in modi differenti, ma condividono tutte questo obiettivo. Una volta ottenuta la chiave, il passaggio finale è banale:

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;

Un insieme di dati concreto

Partiamo dai dati. Immagini una tabella logins che registra i numeri dei giorni in cui un utente ha effettuato l'accesso:

  • Giorni presenti: 1, 2, 3, 7, 8, 10

A colpo d'occhio, le isole sono {1,2,3}, {7,8} e {10}. I vuoti sono i giorni 4-6 e il giorno 9. In un colloquio, il compito consiste nel fare in modo che sia il database a individuare queste tre isole, senza indicarle manualmente. Tenga a mente questo piccolo insieme di dati mentre esaminiamo ogni tecnica.

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

Perché gli approcci ingenui falliscono

Un'idea iniziale comune consiste nel confrontare ogni riga con la successiva tramite un self-join e segnalare le interruzioni. Funziona per trovare un singolo vuoto, ma diventa rapidamente difficile da gestire:

  • È necessario rilevare sia l'inizio sia la fine di ogni isola, il che richiede due passaggi o due join.
  • Le righe ai margini, cioè la prima e l'ultima, richiedono una gestione speciale.
  • Non si generalizza alla richiesta di "restituire la lunghezza di ogni sequenza" senza aggiungere ulteriore complessità.

Gli intervistatori osservano se si ricorre a una guerra di self-join oppure si riconosce che un unico passaggio con una funzione finestra è più semplice.

Il modello mentale per rilevare i vuoti

Un modo affidabile di impostare il problema è il seguente: una nuova isola inizia ogni volta che la riga corrente non è adiacente a quella precedente. Usi LAG per risalire di una riga e confrontare i valori.

Se day_no - LAG(day_no) è maggiore di 1 (oppure NULL per la prima riga), questa riga dà inizio a una nuova isola. Lo si indica con un flag pari a 1; negli altri casi il flag è 0. Osservi l'aspetto di questi flag per i nostri dati.

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;

Trasformare i flag in una chiave di gruppo

I flag del passaggio precedente sono 1, 0, 0, 1, 0, 1 per i giorni 1,2,3,7,8,10. Noti che la somma progressiva di questi flag produce un numero che rimane costante all'interno di un'isola e aumenta a ogni nuova isola: 1,1,1,2,2,3.

Questa somma progressiva è la chiave di gruppo che abbiamo creato. Racchiudiamo la query dei flag in una CTE e calcoliamo la somma con un'altra funzione finestra:

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;

Completare l'esempio guidato

Ora aggiungiamo il GROUP BY finale sopra la chiave di gruppo. Ogni valore distinto di grp rappresenta un'isola, di cui restituiamo i limiti e la dimensione:

Il risultato corrisponde esattamente alle tre isole individuate a colpo d'occhio: 1-3 (lunghezza 3), 7-8 (lunghezza 2) e 10-10 (lunghezza 1). Questa procedura in tre livelli (flag, somma progressiva, raggruppamento) è la struttura portante di quasi ogni soluzione di gaps-and-islands che si scriverà.

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;

L'adiacenza dipende dal dominio

L'unico elemento che cambia da un problema all'altro è la definizione di adiacenza. Riconoscere la regola corretta di adiacenza è metà del lavoro di riconoscimento del problema:

  • Interi: sono adiacenti quando la differenza è esattamente 1.
  • Giorni di calendario: sono adiacenti quando una data è il giorno successivo (date = prev + INTERVAL '1 day').
  • Periodi di stato: sono adiacenti quando il valore dello stato non cambia rispetto alla riga precedente.

La struttura è la stessa, ma cambia il confronto all'interno del CASE. Individuare quale regola di adiacenza si applica è la domanda di chiarimento da porre ad alta voce durante il colloquio.

Domande di chiarimento da porre

Prima di scrivere una riga di SQL, faccia una buona impressione chiarendo l'ambito del problema. Ecco alcune domande utili sui problemi di gaps-and-islands:

  • "Devo considerare i dati per utente o globalmente?" (Questo determina se aggiungere PARTITION BY user_id.)
  • "Possono esserci valori duplicati nello stesso giorno e, in tal caso, interrompono o estendono una sequenza?"
  • "Desidera le isole, i vuoti o entrambi?"
  • "La sequenza è sicuramente ordinata oppure devo ordinarla io?"

Porre queste domande dimostra di aver già risolto questa categoria di problemi e di comprenderne i casi limite.

Isole per gruppo con PARTITION BY

I dati dei colloqui sono quasi sempre raggruppati, per esempio gli accessi per utente. La correzione è meccanica: aggiunga PARTITION BY user_id a ogni funzione finestra, così le isole non si estenderanno mai da un utente all'altro.

La struttura è identica: basta creare le partizioni. Ecco perché padroneggiare prima il caso a flusso singolo è utile: per passare all'analisi per gruppo basta modificare una sola clausola.

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;

Verifica rapida

Metta alla prova il Suo intuito nel riconoscere lo schema.

Riepilogo: riconoscere la struttura

Ora è in grado di identificare un problema di gaps-and-islands anche quando viene presentato in forma diversa e di indicare la strategia:

  • Parole chiave: consecutivo, continuo, ininterrotto, sequenza, intervalli mancanti, raggruppare gli elementi adiacenti.
  • Idea fondamentale: assegni a ogni riga della stessa sequenza una chiave di gruppo identica, quindi applichi GROUP BY a tale chiave.
  • Procedura: segnali le nuove isole con LAG, trasformi i flag in una chiave tramite una somma progressiva, quindi aggreghi.
  • L'adiacenza dipende dal dominio (interi, date o stato invariato).
  • Aggiunga PARTITION BY per l'analisi per gruppo e chiarisca l'ambito prima di scrivere il codice.

Ora perfezioneremo il metodo più elegante per creare la chiave: il trucco della differenza tra numeri di riga.

Domande Frequenti

La lezione «Riconoscere un problema di gaps-and-islands» è gratuita?

Sì — il testo completo di «Riconoscere un problema di gaps-and-islands» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.

Cosa imparerò in «Riconoscere un problema di gaps-and-islands»?

Individuare il pattern in un problema descritto a parole e l'intuizione fondamentale sul raggruppamento Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Coding Interview Prep?

Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.

Quanto tempo richiede la lezione «Riconoscere un problema di gaps-and-islands»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?

Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Riconoscere un problema di gaps-and-islands
  2. Il trucco della differenza tra numeri di riga
  3. Trovare le lacune in una sequenza
  4. Isole con cambi di data e stato
← Torna a Coding Interview Prep