Gaps-and-Islands-ongelman tunnistaminen
Tunnista sanallisesta ongelmasta sen rakenne ja keskeinen ryhmittelyidea
Gaps-and-Islands-ongelman tunnistaminen on ilmainen SQL-työhaastatteluun valmistautuminen-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu SQL-työhaastatteluun valmistautuminen-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. SQL-työhaastatteluun valmistautuminen-kurssilla on yhteensä 4 oppituntia.
Haastattelijoiden testaama toimintamalli
Kun senioritason haastattelija pyytää etsimään jonkin asian peräkkäisiä jaksoja, kyseessä on gaps-and-islands-ongelma. Nimi perustuu mielikuvaan: yhteen kuuluvat rivit muodostavat saarekkeen, ja niiden väliset katkokset ovat aukkoja.
- Saareke on sääntöjen mukaan vierekkäisten rivien pisin mahdollinen yhtenäinen jakso (peräkkäiset kokonaisluvut, peräkkäiset päivämäärät tai toistuva sama tila).
- Aukko on kahden saarekkeen väliin jäävä puuttuva alue.
Tämän ongelmaluokan tunnistaminen heti on jo itsessään merkki senioritason osaamisesta. Monet ehdokkaat turvautuvat monimutkaisiin self-join-rakenteisiin, vaikka tyylikäs ratkaisu on lähes aina ikkunafunktioiden käyttö.
Sanalliset tehtävät, joissa saareke on piilossa
Haasteena on, että haastattelijat harvoin sanovat suoraan ”gaps and islands”. Harjoitelkaa tunnistamaan esimerkiksi tällaiset muotoilut:
- ”Etsikää kaikki jaksot, jolloin käyttäjä oli yhtäjaksoisesti tilaajana.”
- ”Kuinka monta peräkkäistä päivää palvelin pysyi toiminnassa?”
- ”Mitkä tunnusalueet puuttuvat tästä taulusta?”
- ”Yhdistäkää vierekkäiset rivit, joiden tila on sama, yhdeksi riviksi.”
Kaikissa on sama rakenne: ryhmitellään vierekkäiset rivit ja ilmoitetaan näiden ryhmien alku, loppu tai puuttuminen. Kun sanat yhdistää saarekkeisiin, SQL rakentuu lähes itsestään.
Ydinajatus: ryhmittelyavaimen muodostaminen
Tässä koko temppu yhdellä lauseella: jos jokaiselle saman saarekkeen riville voidaan antaa sama ryhmittelyavain, yksinkertainen GROUP BY kokoaa saarekkeen yhdeksi yhteenvetoriviksi.
Gaps-and-islands-ongelman varsinainen työ on siis ryhmittelyavaimen laskeminen. Eri muunnelmissa se lasketaan eri tavoin, mutta tavoite on aina sama. Kun avain on käytettävissä, viimeinen vaihe on yksinkertainen:
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;Konkreettinen aineisto
Otetaan lähtökohdaksi data. Kuvitellaan logins-taulu, joka seuraa, minä päivinä käyttäjä kirjautui:
- Paikalla olevat päivät: 1, 2, 3, 7, 8, 10
Silmävaraisesti tarkasteltuna saarekkeet ovat {1,2,3}, {7,8} ja {10}. Aukot ovat päivät 4–6 ja päivä 9. Tehtävänä haastattelussa on saada tietokanta tunnistamaan nämä kolme saareketta ilman, että osoitatte niitä sille manuaalisesti. Pitäkää tämä pieni aineisto mielessä, kun tutustumme kuhunkin tekniikkaan.
CREATE TABLE logins (day_no INT);
INSERT INTO logins VALUES (1),(2),(3),(7),(8),(10);Miksi naiivit lähestymistavat epäonnistuvat
Yleinen ensireaktio on verrata jokaista riviä seuraavaan self-joinilla ja merkitä katkokset. Yhden aukon etsimiseen se toimii, mutta muuttuu nopeasti hankalaksi:
- Jokaisen saarekkeen sekä alku että loppu on tunnistettava, mikä edellyttää kahta käsittelykierrosta tai kahta liitosta.
- Reunarivit eli aivan ensimmäinen ja viimeinen rivi vaativat erikoiskäsittelyä.
- Ratkaisu ei yleisty muotoon ”anna jokaisen jakson pituus” ilman lisärakenteita.
Haastattelijat tarkkailevat, ajaudutteko self-joinien taisteluun vai tunnistatteko, että yksi ikkunafunktiota käyttävä käsittelykierros on selkeämpi.
Aukkojen tunnistamisen ajatusmalli
Yksi toimiva tapa jäsentää asia on seuraava: uusi saareke alkaa aina, kun nykyinen rivi ei ole vierekkäinen edellisen rivin kanssa. Katsokaa yhtä edellistä riviä taaksepäin LAG-funktiolla ja tehkää vertailu.
Jos day_no - LAG(day_no) on suurempi kuin 1 (tai ensimmäisellä rivillä NULL), tämä rivi aloittaa uuden saarekkeen. Merkitkää se lipulla 1 ja muut rivit lipulla 0. Katsotaan, miltä liput näyttävät aineistossamme.
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;Lippujen muuntaminen ryhmittelyavaimeksi
Edellisen vaiheen liput ovat päiville 1,2,3,7,8,10 muodossa 1, 0, 0, 1, 0, 1. Huomatkaa, että lippujen kumulatiivinen summa tuottaa luvun, joka pysyy vakiona saarekkeen sisällä ja kasvaa jokaisen uuden saarekkeen kohdalla: 1,1,1,2,2,3.
Tuo kumulatiivinen summa on muodostamamme ryhmittelyavain. Käärimme lippukyselyn CTE:hen ja laskemme summan toisella ikkunafunktiolla:
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;Esimerkin viimeistely
Lisätään nyt ryhmittelyavaimen päälle lopullinen GROUP BY. Jokainen erillinen grp-arvo vastaa yhtä saareketta, jonka rajat ja koko ilmoitetaan:
Tulos on täsmälleen samat kolme saareketta, jotka havaitsimme silmävaraisesti: 1–3 (pituus 3), 7–8 (pituus 2) ja 10–10 (pituus 1). Tämä kolmivaiheinen resepti (lippu, kumulatiivinen summa, ryhmittely) on lähes jokaisen kirjoittamanne gaps-and-islands-ratkaisun perusta.
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;Vierekkäisyys riippuu sovellusalueesta
Ainoa ongelmasta toiseen muuttuva asia on vierekkäisyyden määritelmä. Oikean vierekkäisyyssäännön tunnistaminen on puolet ongelman tunnistamisesta:
- Kokonaisluvut: vierekkäisiä, kun erotus on täsmälleen 1.
- Kalenteripäivät: vierekkäisiä, kun toinen päivämäärä on seuraava päivä (
date = prev + INTERVAL '1 day'). - Tilajaksot: vierekkäisiä, kun tila-arvo ei muutu edelliseen riviin verrattuna.
Runko on sama, mutta CASE-lausekkeen sisäinen vertailu muuttuu. Sen tunnistaminen, mitä vierekkäisyyssääntöä käytetään, on tarkentava kysymys, joka kannattaa esittää haastattelussa ääneen.
Tarkentavat kysymykset
Ennen ensimmäistä SQL-riviä osoittakaa osaamisenne tarkentamalla tehtävän laajuutta. Hyviä gaps-and-islands-ongelman tarkentavia kysymyksiä ovat:
- ”Pitäisikö tiedot käsitellä käyttäjäkohtaisesti vai globaalisti?” (Tämä ratkaisee, lisätäänkö
PARTITION BY user_id.) - ”Voiko samalle päivälle tulla duplikaatteja, ja katkaisevatko vai pidentävätkö ne jaksoa?”
- ”Haluatteko saarekkeet, aukot vai molemmat?”
- ”Onko sarja varmasti valmiiksi järjestetty, vai pitäisikö minun järjestää se itse?”
Näiden kysymysten esittäminen osoittaa, että olette ratkaisseet tämän ongelmaluokan aiemmin ja ymmärrätte sen reunatapaukset.
Ryhmän sisäiset saarekkeet PARTITION BY -lauseella
Haastattelujen aineisto on lähes aina ryhmiteltyä, esimerkiksi käyttäjäkohtaisia kirjautumisia. Korjaus on mekaaninen: lisätkää PARTITION BY user_id jokaiseen ikkunafunktioon, jotta saarekkeet eivät koskaan ulotu käyttäjältä toiselle.
Runko pysyy samana; lisäätte vain osioinnin. Siksi yhden tietovirran tapauksen hallitseminen ensin kannattaa: ryhmäkohtaiseksi laajentaminen vaatii vain yhden lausekkeen lisäämisen.
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;Pikatarkistus
Testatkaa kykynne tunnistaa tämä malli.
Kertaus: rakenteen tunnistaminen
Osaatte nyt tunnistaa gaps-and-islands-ongelman sen naamioidusta muodosta ja nimetä ratkaisustrategian:
- Tunnussanat: peräkkäinen, yhtäjaksoinen, katkeamaton, putki, puuttuvat alueet, vierekkäisten rivien yhdistäminen.
- Ydinajatus: annetaan jokaiselle saman jakson riville sama ryhmittelyavain ja tehdään sitten siitä
GROUP BY. - Resepti: merkitään uudet saarekkeet
LAG-funktiolla, muunnetaan liput kumulatiivisella summalla avaimeksi ja kootaan tulokset. - Vierekkäisyys riippuu sovellusalueesta (kokonaisluvut, päivämäärät tai muuttumaton tila).
- Lisätään
PARTITION BYryhmäkohtaiseen analyysiin ja tarkennetaan laajuus ennen koodaamista.
Seuraavaksi tarkennamme tyylikkäintä avaimen muodostustapaa: rivinumeroiden erotustekniikkaa.
Opi SQL tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Gaps-and-Islands-ongelman tunnistaminen” ilmainen?
Kyllä – oppitunnin ”Gaps-and-Islands-ongelman tunnistaminen” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko SQL-työhaastatteluun valmistautuminen-kurssin, päivitä CoddyKit PROhon. SQL-työhaastatteluun valmistautuminen-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Gaps-and-Islands-ongelman tunnistaminen”?
Tunnista sanallisesta ongelmasta sen rakenne ja keskeinen ryhmittelyidea Harjoittelet SQL-työhaastatteluun valmistautuminen-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni SQL-työhaastatteluun valmistautuminen-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin SQL-työhaastatteluun valmistautuminen-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Gaps-and-Islands-ongelman tunnistaminen”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä SQL-työhaastatteluun valmistautuminen-oppitunnilla?
Kyllä. Jokainen SQL-työhaastatteluun valmistautuminen-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Gaps-and-Islands-ongelman tunnistaminen
- Rivinumeron erotustemppu
- Sarjan aukkojen etsiminen
- Jaksot päivämäärä- ja tilamuutosten avulla