0Pricing
Coding Interview Prep · Lektion

Lücken in einer Sequenz finden

Fehlende Werte sowie Anfang und Ende jeder Lücke erkennen

Lücken in einer Sequenz finden ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 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.

Jetzt die Lücken finden

Bisher haben wir Zeilen zu Inseln gruppiert. Die spiegelbildliche Interviewfrage lautet: Welche Werte fehlen? Interviewer formulieren sie beispielsweise als „Finden Sie die Lücken in dieser ID-Sequenz“, „Welche Rechnungsnummern wurden übersprungen?“ oder „An welchen Tagen gab es keine Aktivität?“

Lücken sind die leeren Zwischenräume zwischen Inseln. Die entscheidende Erkenntnis ist, dass Sie normalerweise nicht jeden einzelnen fehlenden Wert auflisten müssen. Sie sollen den Anfang und das Ende jedes Lückenbereichs ausgeben. Das ist deutlich kompakter und entspricht dem, was Interviewer erwarten.

Der Beispieldatensatz für Lücken

Verwenden Sie erneut die vorhandenen Werte 1, 2, 3, 7, 8, 10 aus der Tabelle seq(n). Die auszugebenden Lücken sind:

  • Von 4 bis 6 (nach der ersten Insel, vor 7)
  • Von 9 bis 9 (zwischen 8 und 10)

Beachten Sie, dass wir eine Lücke als Bereich beschreiben: gap_start = letzter vorhandener Wert + 1, gap_end = nächster vorhandener Wert - 1. Diese kompakte Form ist das Ziel der folgenden Kerntechnik.

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

Lücken mit LEAD finden

Der sauberste Lückendetektor vergleicht jede Zeile mithilfe von LEAD mit der nächsten Zeile. Ist der nächste Wert um mehr als 1 größer als der aktuelle, liegt dazwischen eine Lücke.

Für jede solche Zeile beginnt die Lücke bei n + 1 und endet bei next_n - 1. Sehen Sie sich zunächst die unverarbeitete LEAD-Ausgabe an:

SELECT
  n,
  LEAD(n) OVER (ORDER BY n) AS next_n
FROM seq
ORDER BY n;

Lückenbereiche ausgeben

Verpacken Sie das LEAD-Ergebnis in einer CTE und behalten Sie nur die Zeilen, bei denen der Sprung zum nächsten Wert größer als 1 ist. Diese Zeilen markieren Lücken:

Dies ergibt genau die Lücken 4-6 und 9-9. Der Ausdruck next_n - n - 1 liefert außerdem die Anzahl der fehlenden Werte in jeder Lücke, eine häufige Anschlussfrage.

WITH stepped AS (
  SELECT n, LEAD(n) OVER (ORDER BY n) AS next_n
  FROM seq
)
SELECT
  n + 1            AS gap_start,
  next_n - 1       AS gap_end,
  next_n - n - 1   AS missing_count
FROM stepped
WHERE next_n - n > 1
ORDER BY gap_start;

Die symmetrische LAG-Variante

Sie können dieselben Lücken stattdessen auch mit LAG in Blickrichtung zurück erkennen. Vor der aktuellen Zeile existiert eine Lücke, wenn der vorherige Wert um mehr als 1 kleiner ist als der aktuelle.

Beide Verfahren sind vollständig gleichwertig. Wählen Sie dasjenige, das sich für die jeweilige Frage natürlicher liest. Manche Interviewer bevorzugen LEAD, weil die Lücke relativ zu der Zeile beschrieben wird, die ihr vorausgeht, und dies der üblichen Ausdrucksweise entspricht.

WITH stepped AS (
  SELECT n, LAG(n) OVER (ORDER BY n) AS prev_n
  FROM seq
)
SELECT prev_n + 1 AS gap_start,
       n - 1       AS gap_end
FROM stepped
WHERE n - prev_n > 1
ORDER BY gap_start;

Jeden fehlenden Wert auflisten

Manchmal möchte der Interviewer tatsächlich die vollständige Liste der fehlenden Zahlen und nicht nur Bereiche. Der robuste Ansatz besteht darin, die vollständige erwartete Sequenz zu erzeugen und sie per Anti-Join mit den vorhandenen Werten abzugleichen. In Postgres erstellt generate_series den vollständigen Bereich:

Jede Ganzzahl im erwarteten Bereich, die in seq nicht vorhanden ist, ist ein fehlender Wert. Wenn Sie das vorgesehene Minimum und Maximum kennen, werden damit auch Lücken an den äußersten Rändern erkannt.

SELECT g.n AS missing_value
FROM generate_series(
       (SELECT MIN(n) FROM seq),
       (SELECT MAX(n) FROM seq)
     ) AS g(n)
LEFT JOIN seq s ON s.n = g.n
WHERE s.n IS NULL
ORDER BY g.n;

Sequenzgenerierung in verschiedenen SQL-Dialekten

Nicht jede Engine verfügt über generate_series. Sie sollten die Alternativen kennen:

  • Postgres: generate_series(1, 100).
  • SQL Server: eine rekursive CTE oder eine Zahlen-/Tally-Tabelle.
  • MySQL 8: eine rekursive CTE, die bis zum Maximum hochzählt.

Eine rekursive CTE ist die portable Ausweichlösung. Mit ihr erzeugen Sie dieselbe erwartete Sequenz, die Sie per Anti-Join abgleichen können.

WITH RECURSIVE nums AS (
  SELECT (SELECT MIN(n) FROM seq) AS n
  UNION ALL
  SELECT n + 1 FROM nums
  WHERE n + 1 <= (SELECT MAX(n) FROM seq)
)
SELECT nums.n AS missing_value
FROM nums
LEFT JOIN seq s ON s.n = nums.n
WHERE s.n IS NULL;

Lücken in Kalenderdaten

Für fehlende Datumswerte erzeugen Sie einen vollständigen Kalender mit einer täglichen Schrittweite und gleichen ihn per Anti-Join ab. Dies ist die Standardabfrage für „An welchen Tagen gab es keine Bestellungen?“:

Kombinieren Sie dies mit der Bereichstechnik, indem Sie LEAD auf die tatsächlichen Datumswerte anwenden. So geben Sie fehlende Datumsbereiche statt einzelner Tage aus und verwenden + INTERVAL '1 day' für die Grenzen.

SELECT d::date AS missing_day
FROM generate_series(
       DATE '2026-01-01', DATE '2026-01-31',
       INTERVAL '1 day') AS d
LEFT JOIN daily_logins l ON l.login_date = d::date
WHERE l.login_date IS NULL
ORDER BY missing_day;

Randlücken außerhalb der Daten

Eine tückische Feinheit: LEAD/LAG findet nur Lücken zwischen vorhandenen Werten. Fehlt eine Zahl vor dem kleinsten oder nach dem größten vorhandenen Wert, kann der Fensteransatz sie nicht erkennen, weil es keine benachbarte Zeile gibt.

Wenn der Interviewer einen vollständigen erwarteten Bereich festlegt, etwa die IDs 1 bis 100, und Ihre Daten bei 5 beginnen, müssen Sie den generate-series-Anti-Join verwenden, der durch den angegebenen Bereich begrenzt ist, und nicht durch das eigene Minimum und Maximum der Daten. Klären Sie immer, ob die erwarteten Grenzen fest vorgegeben sind.

SELECT g.n AS missing_value
FROM generate_series(1, 100) AS g(n)
LEFT JOIN seq s ON s.n = g.n
WHERE s.n IS NULL;

Lücken pro Gruppe erkennen

Für benutzerspezifische Lücken partitionieren Sie LEAD/LAG nach der Gruppenspalte, damit niemals eine Lücke zwischen den Datenströmen zweier verschiedener Benutzer ausgegeben wird:

Die fehlenden Bereiche jedes Benutzers werden unabhängig berechnet. Wie bei Inseln führt das Vergessen der Partitionierung dazu, dass Benutzer unbemerkt zusammengeführt werden und scheinbare Lücken zwischen unabhängigen Zeilen entstehen.

WITH stepped AS (
  SELECT user_id, n,
    LEAD(n) OVER (PARTITION BY user_id ORDER BY n) AS next_n
  FROM seq_per_user
)
SELECT user_id, n + 1 AS gap_start, next_n - 1 AS gap_end
FROM stepped
WHERE next_n - n > 1
ORDER BY user_id, gap_start;

Die richtige Methode für Lücken wählen

Entscheidungshilfe für das Interview:

  • Kompakte Bereiche und nur interne Lücken gewünscht? Verwenden Sie LEAD/LAG und filtern Sie, wenn die Schrittweite größer als 1 ist.
  • Jeder einzelne fehlende Wert oder Lücken außerhalb der Datenränder gewünscht? Verwenden Sie den generate-series-Anti-Join für den angegebenen vollständigen Bereich.

Wenn Sie beide Möglichkeiten und ihre jeweiligen Einsatzgebiete nennen, zeigen Sie ein tiefes Verständnis. Die LEAD-Methode ist kostengünstiger, die Sequenzmethode vollständiger.

Kurze Überprüfung

Verstehen Sie die Falle bei den Randfällen genau.

Zusammenfassung: Lücken finden

Lückenerkennung, auf den Punkt gebracht:

  • Geben Sie Lücken als Bereiche aus: gap_start = value + 1, gap_end = next_value - 1.
  • LEAD (oder das symmetrische LAG), gefiltert auf eine Schrittweite größer als 1, findet interne Lücken kostengünstig.
  • Der generate-series-Anti-Join listet jeden fehlenden Wert auf und erkennt Lücken an den Rändern eines angegebenen Bereichs.
  • Rekursive CTEs erzeugen die Sequenz, wenn generate_series nicht verfügbar ist.
  • Partitionieren Sie nach der Gruppenspalte, um benutzerspezifische Lücken zu finden.
  • Klären Sie immer die erwarteten Grenzen.

Zum Abschluss behandeln wir die anspruchsvollste Variante: Inseln, die durch Datums- und Statusänderungen definiert sind.

Häufig gestellte Fragen

Ist die Lektion „Lücken in einer Sequenz finden“ kostenlos?

Ja — der vollständige Text von „Lücken in einer Sequenz finden“ 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 „Lücken in einer Sequenz finden“?

Fehlende Werte sowie Anfang und Ende jeder Lücke erkennen 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 3 von 4.

Wie lange dauert die Lektion „Lücken in einer Sequenz finden“?

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