0Pricing
Coding Interview Prep · Lekcja

Rozpoznawanie problemu luk i wysp

Rozpoznawanie wzorca w zadaniu opisowym oraz kluczowej idei grupowania

Rozpoznawanie problemu luk i wysp to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Wzorzec sprawdzany podczas rozmowy technicznej

Gdy podczas rozmowy technicznej na poziomie senior pojawia się prośba o znalezienie kolejnych ciągów pewnych elementów, mamy do czynienia z problemem luk i wysp. Nazwa pochodzi z obrazu mentalnego: wiersze należące do siebie tworzą wyspę, a przerwy między nimi to luki.

  • Wyspa to maksymalny ciąg wierszy sąsiadujących według określonej reguły (kolejne liczby całkowite, kolejne daty albo wielokrotnie powtarzający się ten sam status).
  • Luka to brakująca przestrzeń między dwiema wyspami.

Samo rozpoznanie tej klasy problemów jest już sygnałem kompetencji na poziomie senior. Wielu kandydatów sięga po skomplikowaną sieć self-joinów, podczas gdy elegancką odpowiedzią są niemal zawsze funkcje okna.

Zadania opisowe, w których kryje się wyspa

Trudność polega na tym, że osoby prowadzące rozmowę rzadko mówią wprost o „lukach i wyspach”. Zamiast tego ukrywają ten wzorzec w treści zadania. Warto wyczulić się na sformułowania takie jak:

  • „Znajdź każdy okres, w którym użytkownik miał nieprzerwaną subskrypcję”.
  • „Przez ile kolejnych dni serwer pozostawał dostępny?”
  • „Których zakresów identyfikatorów brakuje w tej tabeli?”
  • „Połącz sąsiednie wiersze o tym samym statusie w jeden wiersz”.

Każde z tych zadań ma ten sam schemat: pogrupować sąsiadujące wiersze, a następnie zwrócić początek, koniec lub brak tych grup. Gdy słowa zostaną rozpoznane jako wyspy, zapisanie SQL staje się niemal oczywiste.

Najważniejsza intuicja: utworzenie klucza grupy

Cały trik można ująć w jednym zdaniu: jeśli każdemu wierszowi z tej samej wyspy można przypisać identyczny klucz grupy, zwykłe GROUP BY zredukuje każdą wyspę do jednego wiersza podsumowania.

Dlatego w każdym problemie luk i wysp najważniejsze jest obliczenie tego klucza grupy. Różne warianty obliczają go w różny sposób, ale cel zawsze pozostaje ten sam. Gdy klucz jest już gotowy, ostatni krok jest prosty:

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;

Konkretny zbiór danych

Oprzyjmy się na danych. Wyobraźmy sobie tabelę logins rejestrującą numery dni, w których użytkownik się logował:

  • Obecne dni: 1, 2, 3, 7, 8, 10

Na pierwszy rzut oka wyspy to {1,2,3}, {7,8} oraz {10}. Lukami są dni 4–6 i dzień 9. Zadaniem podczas rozmowy jest sprawić, aby baza danych sama rozpoznała te trzy wyspy, bez ręcznego wskazywania ich. Warto pamiętać o tym niewielkim zbiorze danych podczas omawiania każdej techniki.

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

Dlaczego naiwne podejścia zawodzą

Częstym pierwszym odruchem jest porównanie każdego wiersza z następnym za pomocą self-join i oznaczenie przerw. To działa przy znajdowaniu pojedynczej luki, ale szybko staje się nieporęczne:

  • Należy wykryć zarówno początek, jak i koniec każdej wyspy, co oznacza dwa przebiegi lub dwa złączenia.
  • Wiersze brzegowe (pierwszy i ostatni) wymagają specjalnej obsługi.
  • Bez dodatkowych mechanizmów takie podejście nie uogólnia się na pytanie „podaj długość każdego ciągu”.

Osoby prowadzące rozmowę zwracają uwagę na to, czy kandydat eskaluje do wojny z self-joinami, czy rozpoznaje, że jedno przejście z funkcją okna jest prostsze.

Model mentalny wykrywania luk

Jedno z niezawodnych ujęć problemu brzmi: nowa wyspa zaczyna się, gdy bieżący wiersz nie jest bezpośrednio sąsiadujący z poprzednim wierszem. Do spojrzenia o jeden wiersz wstecz służy LAG, za pomocą którego można wykonać porównanie.

Jeśli day_no - LAG(day_no) jest większe niż 1 (albo ma wartość NULL dla pierwszego wiersza), ten wiersz rozpoczyna nową wyspę. Oznaczamy to flagą o wartości 1, a w przeciwnym razie wartością 0. Warto przyjrzeć się, jak te flagi wyglądają dla naszych danych.

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;

Przekształcanie flag w klucz grupy

Flagi z poprzedniego kroku mają wartości 1, 0, 0, 1, 0, 1 dla dni 1,2,3,7,8,10. Zauważmy, że suma narastająca tych flag tworzy liczbę, która pozostaje stała wewnątrz wyspy i zwiększa się przy każdej nowej wyspie: 1,1,1,2,2,3.

Ta suma narastająca jest naszym utworzonym kluczem grupy. Zapytanie z flagą umieszczamy w CTE, a następnie sumujemy ją za pomocą kolejnej funkcji okna:

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;

Dokończenie przykładu

Teraz należy nałożyć końcowe GROUP BY na klucz grupy. Każda odrębna wartość grp odpowiada jednej wyspie, dlatego zwracamy jej granice i rozmiar:

Wynik dokładnie odpowiada trzem wyspom rozpoznanym wcześniej wzrokowo: 1–3 (długość 3), 7–8 (długość 2) oraz 10–10 (długość 1). Ten trzywarstwowy przepis (flaga, suma narastająca, grupowanie) stanowi podstawę niemal każdej odpowiedzi dotyczącej luk i wysp.

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;

Sąsiedztwo zależy od dziedziny

Jedynym elementem, który zmienia się między zadaniami, jest definicja sąsiedztwa. Rozpoznanie właściwej reguły sąsiedztwa stanowi połowę sukcesu w rozpoznaniu problemu:

  • Liczby całkowite: sąsiadują, gdy różnica wynosi dokładnie 1.
  • Dni kalendarzowe: sąsiadują, gdy jedna data przypada następnego dnia (date = prev + INTERVAL '1 day').
  • Okresy statusu: sąsiadują, gdy wartość statusu nie zmieniła się względem poprzedniego wiersza.

Szkielet pozostaje taki sam, zmienia się tylko porównanie wewnątrz CASE. Rozpoznanie właściwej reguły sąsiedztwa to pytanie doprecyzowujące, które należy zadać na głos podczas rozmowy.

Pytania doprecyzowujące

Przed napisaniem choćby jednej linii SQL warto doprecyzować zakres problemu. Dobre pytania dotyczące luk i wysp to:

  • „Czy dane należy traktować osobno dla każdego użytkownika, czy globalnie?” (Od tego zależy, czy trzeba dodać PARTITION BY user_id).
  • „Czy tego samego dnia mogą wystąpić duplikaty i czy przerywają one ciąg, czy go wydłużają?”
  • „Czy potrzebne są wyspy, luki, czy oba te elementy?”
  • „Czy kolejność jest gwarantowana, czy należy ustawić ją samodzielnie?”

Zadanie takich pytań pokazuje, że ten typ problemu został już wcześniej rozwiązany i że znane są jego przypadki brzegowe.

Wyspy w grupach z PARTITION BY

Rzeczywiste dane podczas rozmów technicznych niemal zawsze są pogrupowane, na przykład logowania osobno dla każdego użytkownika. Rozwiązanie jest mechaniczne: należy dodać PARTITION BY user_id do każdej funkcji okna, aby wyspy nigdy nie obejmowały wielu użytkowników.

Szkielet pozostaje identyczny — zmienia się tylko partycjonowanie. Dlatego warto najpierw opanować przypadek pojedynczego strumienia, ponieważ przejście do analizy w grupach wymaga zmiany tylko jednej klauzuli.

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;

Szybki test

Sprawdźmy intuicję dotyczącą rozpoznawania wzorców.

Podsumowanie: rozpoznawanie schematu

Można już rozpoznać problem luk i wysp niezależnie od sposobu, w jaki został opisany, oraz wskazać właściwą strategię:

  • Słowa sygnałowe: kolejny, ciągły, nieprzerwany, seria, brakujące zakresy, łączenie sąsiednich wierszy.
  • Najważniejsza idea: każdemu wierszowi z tego samego ciągu przypisać identyczny klucz grupy, a następnie wykonać GROUP BY po tym kluczu.
  • Przepis: oznaczyć nowe wyspy za pomocą LAG, utworzyć klucz przez sumę narastającą flag, a następnie wykonać agregację.
  • Sąsiedztwo zależy od dziedziny (liczby całkowite, daty lub niezmieniony status).
  • Dodać PARTITION BY do analizy w grupach i doprecyzować zakres przed rozpoczęciem kodowania.

W następnym kroku zostanie omówiona najbardziej elegancka metoda budowania klucza: trik z różnicą numerów wierszy.

Często zadawane pytania

Czy lekcja „Rozpoznawanie problemu luk i wysp” jest bezpłatna?

Tak — pełny tekst „Rozpoznawanie problemu luk i wysp” 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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Rozpoznawanie problemu luk i wysp”?

Rozpoznawanie wzorca w zadaniu opisowym oraz kluczowej idei grupowania Ćwiczysz Coding 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ąć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding 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 1 z 4.

Ile czasu zajmuje lekcja „Rozpoznawanie problemu luk i wysp”?

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 Coding Interview Prep?

Tak. Każda lekcja Coding 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

  1. Rozpoznawanie problemu luk i wysp
  2. Sztuczka z różnicą numerów wierszy
  3. Znajdowanie luk w sekwencji
  4. Wyspy przy zmianach dat i statusów
← Powrót do Coding Interview Prep