SQL Interview Prep · Lekcja

Znajdowanie luk w sekwencji

Wykrywanie brakujących wartości oraz początku i końca każdej luki

Znajdowanie luk w sekwencji to bezpłatna lekcja SQL Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej SQL Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs SQL Interview Prep zawiera 4 lekcji w sumie.

Teraz poszukajmy luk

Do tej pory grupowaliśmy wiersze w wyspy. Lustrzane pytanie rekrutacyjne brzmi: których wartości brakuje? Osoby prowadzące rozmowy formułują je na przykład jako „znajdź luki w tym ciągu identyfikatorów”, „które numery faktur pominięto” lub „w które dni nie było aktywności”.

Luki to puste przestrzenie między wyspami. Najważniejszy wniosek jest taki, że zazwyczaj nie trzeba wyświetlać każdej brakującej wartości z osobna; należy podać początek i koniec każdego zakresu luki, co jest znacznie bardziej zwięzłe i odpowiada oczekiwaniom osób prowadzących rozmowy.

Przykładowy zbiór danych z lukami

Wykorzystajmy ponownie istniejące wartości 1, 2, 3, 7, 8, 10 z tabeli seq(n). Luki, które należy zgłosić, to:

od 4 do 6 (po pierwszej wyspie, przed 7)
od 9 do 9 (między 8 a 10)

Zauważmy, że lukę opisujemy jako zakres: gap_start = ostatnia istniejąca wartość + 1, gap_end = następna istniejąca wartość - 1. Ta zwięzła postać jest celem podstawowej techniki przedstawionej poniżej.

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

Podejście LEAD do luk

Najbardziej przejrzysty detektor luk porównuje każdy wiersz z następnym wierszem za pomocą LEAD. Jeśli następna wartość jest większa od bieżącej o więcej niż 1, między nimi występuje luka.

Dla każdego takiego wiersza luka zaczyna się od n + 1 i kończy na next_n - 1. Najpierw warto przyjrzeć się surowemu wynikowi LEAD:

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

Raportowanie zakresów luk

Wynik LEAD należy umieścić w CTE i zachować tylko te wiersze, w których skok do następnej wartości przekracza 1. Wiersze te wyznaczają luki:

Zwraca to dokładnie lukę 4-6 oraz lukę 9-9. Wyrażenie next_n - n - 1 podaje również liczbę brakujących wartości w każdej luce, o co często pyta się dodatkowo.

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;

Symetryczny wariant z LAG

Te same luki można wykrywać, patrząc wstecz za pomocą LAG. Luka występuje przed bieżącym wierszem, gdy poprzednia wartość jest od niego mniejsza o więcej niż 1.

Obie metody są w pełni równoważne; należy wybrać tę, która naturalniej pasuje do pytania. Niektóre osoby prowadzące rozmowy preferują LEAD, ponieważ luka jest opisywana względem poprzedzającego ją wiersza, zgodnie z naturalnym sposobem mówienia.

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;

Wyświetlanie każdej brakującej wartości

Czasami osoba prowadząca rozmowę rzeczywiście oczekuje pełnej listy brakujących liczb, a nie tylko zakresów. Solidne rozwiązanie polega na wygenerowaniu pełnego oczekiwanego ciągu i wykonaniu anty-join względem istniejących danych. W Postgresie funkcja generate_series tworzy pełny zakres:

Każda liczba całkowita z oczekiwanego zakresu, której nie ma w seq, jest brakującą wartością. Rozwiązanie to obsługuje również luki na samych krańcach, jeśli znane są zamierzone minimum i maksimum.

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;

Generowanie ciągu w różnych dialektach

Nie każdy silnik udostępnia funkcję generate_series. Należy znać alternatywy:

Postgres: generate_series(1, 100).
SQL Server: rekurencyjne CTE lub tabela liczb/tally.
MySQL 8: rekurencyjne CTE zliczające do wartości maksymalnej.

Rekurencyjne CTE jest przenośnym rozwiązaniem awaryjnym. Tworzy ten sam oczekiwany ciąg, względem którego można wykonać anty-join.

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;

Luki w datach kalendarzowych

W przypadku brakujących dat należy wygenerować pełny kalendarz z krokiem jednego dnia i wykonać anty-join. Jest to standardowe zapytanie typu „w które dni nie było zamówień”:

Można połączyć tę metodę z techniką zakresów, stosując LEAD do rzeczywistych dat, aby raportować zakresy brakujących dat zamiast poszczególnych dni, oraz używając + INTERVAL '1 day' do wyznaczenia granic.

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;

Luki poza zakresem danych

Subtelna pułapka polega na tym, że LEAD/LAG znajduje tylko luki pomiędzy istniejącymi wartościami. Jeśli brakuje liczby przed najmniejszą lub za największą istniejącą wartością, podejście okienkowe jej nie wykryje, ponieważ nie ma sąsiedniego wiersza.

Jeśli osoba prowadząca rozmowę określi pełny oczekiwany zakres (na przykład identyfikatory od 1 do 100), a dane zaczynają się od 5, należy użyć generate-series anti-join ograniczonego zadeklarowanym zakresem, a nie minimum i maksimum wynikającymi z danych. Zawsze należy ustalić, czy granice oczekiwanego zakresu są stałe.

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;

Wykrywanie luk według grup

W przypadku luk dla poszczególnych użytkowników należy partycjonować LEAD/LAG według kolumny grupującej, aby luka nigdy nie była zgłaszana między strumieniami dwóch różnych użytkowników:

Brakujące zakresy dla każdego użytkownika są obliczane niezależnie. Podobnie jak w przypadku wysp, pominięcie partycjonowania po cichu scala użytkowników i tworzy pozorne luki rozciągające się między niepowiązanymi wierszami.

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;

Wybór właściwej metody wykrywania luk

Wskazówki dotyczące wyboru podczas rozmowy kwalifikacyjnej:

Potrzebne są zwięzłe zakresy i tylko luki wewnętrzne? Należy użyć LEAD/LAG i odfiltrować wiersze, w których krok przekracza 1.
Potrzebna jest każda pojedyncza brakująca wartość lub luki poza granicami danych? Należy użyć generate-series anti-join względem zadeklarowanego pełnego zakresu.

Wspomnienie o obu możliwościach i wyjaśnienie, kiedy należy stosować każdą z nich, sygnalizuje dogłębną znajomość tematu. Metoda LEAD jest tańsza, natomiast metoda z generowaniem serii jest pełniejsza.

Szybkie sprawdzenie

Należy dokładnie zrozumieć pułapkę związaną z granicami zakresu.

Podsumowanie: znajdowanie luk

Najważniejsze informacje o wykrywaniu luk:

Luki należy raportować jako zakresy: gap_start = value + 1, gap_end = next_value - 1.
LEAD (lub symetryczne LAG) z filtrowaniem kroków większych niż 1 tanio wykrywa luki wewnętrzne.
generate-series anti-join wyświetla każdą brakującą wartość i wykrywa luki na krańcach względem zadeklarowanego zakresu.
Rekurencyjne CTE generują serię tam, gdzie nie ma generate_series.
W przypadku luk dla poszczególnych użytkowników należy partycjonować dane według kolumny grupującej.
Zawsze należy ustalić oczekiwane granice zakresu.

Na koniec zajmiemy się najbardziej rozbudowanym wariantem: wyspami wyznaczanymi przez datę i zmiany statusu.

Często zadawane pytania

Czy lekcja „Znajdowanie luk w sekwencji” jest bezpłatna?

Tak — pełny tekst „Znajdowanie luk w sekwencji” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu SQL Interview Prep, przejdź na CoddyKit PRO. Kurs SQL Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Znajdowanie luk w sekwencji”?

Wykrywanie brakujących wartości oraz początku i końca każdej luki Ćwiczysz SQL Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć SQL Interview Prep?

Nie wymagamy żadnego doświadczenia. SQL Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Znajdowanie luk w sekwencji”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji SQL Interview Prep?

Tak. Każda lekcja SQL Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do SQL Interview Prep