0Pricing
Coding Interview Prep · Lektion

Ein Gaps-and-Islands-Problem erkennen

Das Muster in einer Textaufgabe und die zentrale Erkenntnis zur Gruppierung identifizieren

Ein Gaps-and-Islands-Problem erkennen ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 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.

Das Muster, das Interviewer prüfen

Wenn Sie ein Senior-Interviewer auffordert, aufeinanderfolgende Folgen zu finden, handelt es sich um ein Gaps-and-Islands-Problem. Der Name geht auf ein gedankliches Bild zurück: Zusammengehörige Zeilen bilden eine Insel, und die Unterbrechungen dazwischen sind Lücken.

  • Eine Insel ist eine maximal lange Folge von Zeilen, die nach einer bestimmten Regel benachbart sind (aufeinanderfolgende Ganzzahlen, aufeinanderfolgende Daten oder wiederholt derselbe Status).
  • Eine Lücke ist der fehlende Bereich zwischen zwei Inseln.

Diese Problemklasse sofort zu erkennen, ist bereits ein klares Signal für Senior-Niveau. Viele Kandidaten greifen zu einem Wirrwarr aus Self-Joins; die elegante Lösung besteht fast immer in Window-Funktionen.

Textaufgaben, die eine Insel verbergen

Die Herausforderung besteht darin, dass Interviewer nur selten „Gaps and Islands“ sagen. Sie verbergen das Muster. Achten Sie auf Formulierungen wie:

  • „Finden Sie jeden Zeitraum, in dem ein Benutzer durchgehend abonniert war.“
  • „Wie viele aufeinanderfolgende Tage blieb der Server verfügbar?“
  • „Welche ID-Bereiche fehlen in dieser Tabelle?“
  • „Fassen Sie benachbarte Zeilen mit demselben Status zu einer Zeile zusammen.“

Alle diese Aufgaben haben dieselbe Struktur: Gruppieren Sie benachbarte Zeilen und geben Sie anschließend den Anfang, das Ende oder das Fehlen dieser Gruppen aus. Sobald Sie die Formulierungen den Inseln zuordnen, ergibt sich das SQL fast von selbst.

Die zentrale Idee: Einen Gruppenschlüssel erzeugen

Hier ist der gesamte Trick in einem Satz: Wenn Sie jeder Zeile derselben Insel einen identischen Gruppenschlüssel zuweisen können, fasst ein einfaches GROUP BY jede Insel zu einer Zusammenfassungszeile zusammen.

Die eigentliche Arbeit bei jedem Gaps-and-Islands-Problem besteht also darin, diesen Gruppenschlüssel zu berechnen. Die verschiedenen Varianten berechnen ihn unterschiedlich, verfolgen aber alle dasselbe Ziel. Sobald der Schlüssel vorliegt, ist der letzte Schritt trivial:

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;

Ein konkreter Datensatz

Schauen wir uns konkrete Daten an. Stellen Sie sich eine Tabelle logins vor, die erfasst, an welchen Tagesnummern sich ein Benutzer angemeldet hat:

  • Vorhandene Tage: 1, 2, 3, 7, 8, 10

Auf den ersten Blick sind die Inseln {1,2,3}, {7,8} und {10}. Die Lücken sind die Tage 4–6 und der Tag 9. Ihre Aufgabe im Interview besteht darin, die Datenbank diese drei Inseln erkennen zu lassen, ohne sie manuell vorzugeben. Behalten Sie diesen kleinen Datensatz im Hinterkopf, während wir die einzelnen Techniken betrachten.

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

Warum naive Ansätze scheitern

Ein häufiger erster Ansatz besteht darin, jede Zeile per Self-Join mit der nächsten zu vergleichen und Unterbrechungen zu markieren. Das funktioniert, um eine einzelne Lücke zu finden, wird aber schnell unhandlich:

  • Sie müssen sowohl den Anfang als auch das Ende jeder Insel erkennen, was zwei Durchläufe oder zwei Joins erfordert.
  • Randzeilen (die allererste und die allerletzte) benötigen eine Sonderbehandlung.
  • Der Ansatz lässt sich nicht ohne zusätzliche Logik auf „Geben Sie mir die Länge jeder Folge“ verallgemeinern.

Interviewer achten darauf, ob Sie in einen Self-Join-Krieg eskalieren oder erkennen, dass ein einziger Durchlauf mit einer Window-Funktion übersichtlicher ist.

Das mentale Modell zur Lückenerkennung

Eine robuste Betrachtungsweise lautet: Eine neue Insel beginnt immer dann, wenn die aktuelle Zeile nicht an die vorherige Zeile angrenzt. Verwenden Sie LAG, um eine Zeile zurückzublicken und den Vergleich durchzuführen.

Wenn day_no - LAG(day_no) größer als 1 ist (oder für die erste Zeile NULL), beginnt diese Zeile eine neue Insel. Wir markieren das mit einem Flag von 1, andernfalls mit 0. Sehen Sie sich an, wie diese Flags für unsere Daten aussehen.

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;

Flags in einen Gruppenschlüssel umwandeln

Die Flags aus dem vorherigen Schritt lauten für die Tage 1,2,3,7,8,10: 1, 0, 0, 1, 0, 1. Beachten Sie, dass eine laufende Summe dieser Flags eine Zahl erzeugt, die innerhalb einer Insel konstant bleibt und bei jeder neuen Insel erhöht wird: 1,1,1,2,2,3.

Diese laufende Summe ist unser erzeugter Gruppenschlüssel. Wir kapseln die Abfrage für die Flags in einer CTE und bilden die Summe mit einer weiteren Window-Funktion:

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;

Das ausgearbeitete Beispiel vervollständigen

Setzen Sie nun das abschließende GROUP BY auf den Gruppenschlüssel. Jeder unterschiedliche Wert von grp entspricht einer Insel, deren Grenzen und Größe wir ausgeben:

Das Ergebnis sind genau die drei Inseln, die wir auf den ersten Blick erkannt haben: 1–3 (Länge 3), 7–8 (Länge 2) und 10–10 (Länge 1). Dieses Rezept mit drei Ebenen (Markierung, laufende Summe, Gruppierung) bildet das Grundgerüst fast jeder Lösung für ein Gaps-and-Islands-Problem.

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;

Nachbarschaft ist domänenspezifisch

Der einzige Teil, der sich zwischen den Problemen ändert, ist die Definition von benachbart. Die richtige Regel für Nachbarschaft zu erkennen, ist bereits die halbe Lösung:

  • Ganzzahlen: benachbart, wenn die Differenz genau 1 beträgt.
  • Kalendertage: benachbart, wenn ein Datum auf den nächsten Tag folgt (date = prev + INTERVAL '1 day').
  • Statuszeiträume: benachbart, wenn der Statuswert gegenüber der vorherigen Zeile unverändert ist.

Dasselbe Grundgerüst, aber ein anderer Vergleich innerhalb von CASE. Welche Regel für Nachbarschaft gilt, ist die klärende Frage, die Sie im Interview laut stellen sollten.

Rückfragen, die Sie stellen sollten

Bevor Sie eine Zeile SQL schreiben, können Sie durch die Klärung des Umfangs punkten. Gute Rückfragen zu Gaps-and-Islands-Problemen sind:

  • „Soll ich die Daten pro Benutzer oder global betrachten?“ (Das entscheidet, ob Sie PARTITION BY user_id ergänzen.)
  • „Kann es am selben Tag Duplikate geben, und unterbrechen oder verlängern sie eine Folge?“
  • „Möchten Sie die Inseln, die Lücken oder beides?“
  • „Ist die Sequenz garantiert sortiert, oder soll ich sie selbst sortieren?“

Wenn Sie diese Fragen stellen, zeigen Sie, dass Sie diese Problemklasse bereits gelöst haben und ihre Randfälle verstehen.

Inseln pro Gruppe mit PARTITION BY

Reale Interviewdaten sind fast immer gruppiert, zum Beispiel Anmeldungen pro Benutzer. Die Lösung ist mechanisch: Fügen Sie jeder Window-Funktion PARTITION BY user_id hinzu, damit sich Inseln niemals über mehrere Benutzer erstrecken.

Das Grundgerüst bleibt identisch; Sie partitionieren lediglich. Deshalb lohnt es sich, zunächst den Fall eines einzelnen Datenstroms zu beherrschen: Die Erweiterung auf einzelne Gruppen erfordert nur eine Klausel.

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;

Schnelltest

Testen Sie Ihren Instinkt zur Mustererkennung.

Zusammenfassung: Das Muster erkennen

Sie können nun ein Gaps-and-Islands-Problem an seiner Tarnung erkennen und die passende Strategie benennen:

  • Schlüsselwörter: aufeinanderfolgend, durchgehend, ununterbrochen, Serie, fehlende Bereiche, benachbarte Zeilen zusammenfassen.
  • Zentrale Idee: Weisen Sie jeder Zeile derselben Folge einen identischen Gruppenschlüssel zu und wenden Sie anschließend GROUP BY darauf an.
  • Rezept: Markieren Sie neue Inseln mit LAG, bilden Sie aus den Flags per laufender Summe einen Schlüssel und aggregieren Sie anschließend.
  • Nachbarschaft ist domänenspezifisch (Ganzzahlen, Daten oder ein unveränderter Status).
  • Fügen Sie für Analysen pro Gruppe PARTITION BY hinzu und klären Sie den Umfang vor dem Programmieren.

Als Nächstes schärfen wir die eleganteste Methode zur Schlüsselerzeugung: den Trick mit der Differenz aus Zeilennummern.

Häufig gestellte Fragen

Ist die Lektion „Ein Gaps-and-Islands-Problem erkennen“ kostenlos?

Ja — der vollständige Text von „Ein Gaps-and-Islands-Problem erkennen“ 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 „Ein Gaps-and-Islands-Problem erkennen“?

Das Muster in einer Textaufgabe und die zentrale Erkenntnis zur Gruppierung identifizieren 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 1 von 4.

Wie lange dauert die Lektion „Ein Gaps-and-Islands-Problem erkennen“?

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

  1. Ein Gaps-and-Islands-Problem erkennen
  2. Der Trick mit der Differenz von Zeilennummern
  3. Lücken in einer Sequenz finden
  4. Inseln mit Datums- und Statusänderungen
← Zurück zu Coding Interview Prep