Een probleem met hiaten en eilanden herkennen

Wanneer een senior-interviewer je vraagt om opeenvolgende reeksen van iets te vinden, gaat het om een probleem met gaten en eilanden. De naam komt van een beeldspraak: rijen die bij elkaar horen vormen een eiland, en de onderbrekingen ertussen zijn gaten.

• Een eiland is een maximale reeks rijen die volgens een bepaalde regel aangrenzend zijn (opeenvolgende gehele getallen, opeenvolgende datums of herhaaldelijk dezelfde status).
• Een gat is de ontbrekende ruimte tussen twee eilanden.

Dat je dit soort probleem meteen herkent, is op zichzelf al een signaal van senioriteit. Veel kandidaten grijpen naar een wirwar van self-joins; het elegante antwoord bestaat vrijwel altijd uit windowfuncties.

De uitdaging is dat interviewers zelden letterlijk zeggen: "gaten en eilanden". Ze verhullen het probleem. Let op formuleringen zoals:

• "Zoek elke periode waarin een gebruiker ononderbroken geabonneerd was."
• "Hoeveel opeenvolgende dagen bleef de server actief?"
• "Welke ID-bereiken ontbreken in deze tabel?"
• "Voeg aangrenzende rijen met dezelfde status samen tot één rij."

Elk van deze vragen heeft dezelfde vorm: groepeer rijen die naast elkaar staan en rapporteer vervolgens het begin, het einde of het ontbreken van die groepen. Zodra je de woorden aan eilanden koppelt, schrijft de SQL zichzelf.

Hier is de hele truc in één zin: als je elke rij in hetzelfde eiland dezelfde groepssleutel kunt geven, laat een eenvoudige GROUP BY elk eiland samenvallen tot één samenvattingsrij.

Het echte werk in elk probleem met gaten en eilanden is dus het berekenen van die groepssleutel. Verschillende varianten berekenen die sleutel op verschillende manieren, maar ze streven allemaal hetzelfde doel na. Zodra je de sleutel hebt, is de laatste stap eenvoudig:

Laten we dit aan gegevens vastmaken. Stel je een tabel logins voor die bijhoudt op welke dagnummers een gebruiker heeft ingelogd:

• Dagen die voorkomen: 1, 2, 3, 7, 8, 10

Op het eerste gezicht zijn de eilanden {1,2,3}, {7,8} en {10}. De gaten zijn dagen 4-6 en dag 9. Jouw taak in een sollicitatiegesprek is om de database deze drie eilanden te laten herkennen zonder ze handmatig aan te wijzen. Houd deze kleine gegevensset in gedachten terwijl we elke techniek bekijken.

Een veelvoorkomende eerste ingeving is om elke rij met de volgende te vergelijken via een self-join en onderbrekingen te markeren. Dat werkt om één gat te vinden, maar wordt al snel onhandelbaar:

• Je moet zowel het begin als het einde van elk eiland detecteren, wat twee doorgangen of twee joins betekent.
• Rijen aan de randen, dus de allereerste en allerlaatste rij, vereisen speciale behandeling.
• Deze aanpak kan niet zonder extra hulpmiddelen worden uitgebreid naar "geef me de lengte van elke reeks".

Interviewers letten erop of je belandt in een oorlog met self-joins, of inziet dat één doorgang met een windowfunctie overzichtelijker is.

Een robuuste manier om ernaar te kijken is: een nieuw eiland begint zodra de huidige rij niet aan de vorige grenst. Gebruik LAG om één rij terug te kijken en de rijen te vergelijken.

Als day_no - LAG(day_no) groter is dan 1 (of NULL is voor de eerste rij), begint deze rij een nieuw eiland. We markeren dat met een vlag 1 en anders met 0. Bekijk hoe die vlaggen eruitzien voor onze gegevens.

De vlaggen uit de vorige stap zijn 1, 0, 0, 1, 0, 1 voor de dagen 1,2,3,7,8,10. Let op: een cumulatieve som van die vlaggen levert een getal op dat binnen een eiland constant blijft en bij elk nieuw eiland met één toeneemt: 1,1,1,2,2,3.

Die cumulatieve som is onze geconstrueerde groepssleutel. We stoppen de query met de vlaggen in een CTE en tellen die op met een andere windowfunctie:

Voeg nu de laatste GROUP BY boven op de groepssleutel toe. Elke unieke waarde van grp is één eiland; we rapporteren de grenzen en de grootte ervan:

Het resultaat bestaat precies uit de drie eilanden die we op het eerste gezicht zagen: 1-3 (lengte 3), 7-8 (lengte 2) en 10-10 (lengte 1). Dit recept in drie lagen (vlag, cumulatieve som, groepering) vormt de basis van vrijwel elk antwoord over gaten en eilanden dat je zult schrijven.

Het enige dat tussen problemen verandert, is de definitie van aangrenzend. De juiste regel voor aangrenzendheid herkennen is de helft van het herkennen van het probleem:

• Gehele getallen: aangrenzend als het verschil precies 1 is.
• Kalenderdagen: aangrenzend als de ene datum de volgende dag is (date = prev + INTERVAL '1 day').
• Statusperioden: aangrenzend als de statuswaarde ongewijzigd is ten opzichte van de vorige rij.

De basisstructuur blijft hetzelfde; alleen de vergelijking binnen CASE verandert. Bepalen welke regel voor aangrenzendheid van toepassing is, is de verduidelijkende vraag die je tijdens het sollicitatiegesprek hardop moet stellen.

Voordat je een regel SQL schrijft, scoor je punten door eerst de reikwijdte te verduidelijken. Goede verduidelijkingen bij problemen met gaten en eilanden zijn:

• "Moet ik de gegevens per gebruiker behandelen, of globaal?" (Dat bepaalt of je PARTITION BY user_id toevoegt.)
• "Kunnen er op dezelfde dag dubbele waarden voorkomen, en verbreken of verlengen die een reeks?"
• "Wil je de eilanden, de gaten of beide?"
• "Is de reeks gegarandeerd gesorteerd, of moet ik die zelf ordenen?"

Door deze vragen hardop te stellen laat je zien dat je dit soort probleem al eerder hebt opgelost en de randgevallen begrijpt.

Echte gegevens uit sollicitatiegesprekken zijn bijna altijd gegroepeerd, bijvoorbeeld logins per gebruiker. De oplossing is mechanisch: voeg aan elke windowfunctie PARTITION BY user_id toe, zodat eilanden nooit over gebruikers heen lopen.

De basisstructuur is identiek; je deelt de gegevens alleen op in partities. Daarom loont het om eerst de situatie met één gegevensstroom goed te beheersen: uitbreiden naar groepen per gebruiker is slechts een wijziging van één clausule.

Je kunt nu een probleem met gaten en eilanden herkennen aan de verhulling ervan en de strategie benoemen:

• Signaalwoorden: opeenvolgend, doorlopend, ononderbroken, reeks, ontbrekende bereiken, aangrenzende rijen samenvoegen.
• Kernidee: geef elke rij in dezelfde reeks één identieke groepssleutel en gebruik daar vervolgens GROUP BY op.
• Recept: markeer nieuwe eilanden met LAG, maak met een cumulatieve som van de vlaggen een sleutel en aggregeer daarna.
• Aangrenzendheid is domeinspecifiek (gehele getallen, datums of een ongewijzigde status).
• Voeg PARTITION BY toe voor analyse per groep en verduidelijk de reikwijdte voordat je code schrijft.

Vervolgens scherpen we de elegantste methode om een sleutel te maken aan: de truc met het verschil tussen rijnummers.