Problémafelbontás

A problémafelbontás annak a készsége, hogy egy homályos feladatot kisebb, ellenőrizhető részekre bonts: constraints, inputmodell, edge case-ek, invariánsok és egy lépésről lépésre felépülő megoldási forma.

1. Definíció

Mi a problémafelbontás?

A problémafelbontás azt jelenti, hogy a teljes algoritmus megírása előtt kisebb döntésekre bontod a feladatot.

Interjús jellegű feladatoknál ez jellemzően ilyen kérdéseket jelent:

• mi pontosan az input,
• mit kell tartalmaznia az outputnak,
• mely constraint-ek számítanak,
• milyen edge case-ek törhetik el a logikát,
• és milyen invariánsnak kell igaznak maradnia futás közben.

Miért létezik?

A legtöbb rossz megoldás nem azért rossz, mert a jelölt nem tud kódolni.

Hanem azért rossz, mert túl korán kezdett el kódolni.

Ha a promptot előbb felbontod, a megoldási tér kisebb és kezelhetőbb lesz.

Hová illeszkedik?

A problémafelbontás a feladat elolvasása és az algoritmus kiválasztása közé esik.

Az egészséges sorrend általában ez:

1. értelmezed a promptot,
2. modellezed az inputot és az outputot,
3. azonosítod a constraint-eket,
4. felsorolod az edge case-eket,
5. definiálod az állapotot vagy invariánst,
6. és csak ezután implementálsz.

Mi NEM a problémafelbontás?

A problémafelbontás nem:

• azonnali pszeudokódírás,
• a prompt más szavakkal való ismétlése,
• a minta kitalálása csak a cím alapján,
• vagy a feladat túltervezése még a megértés előtt.

Ez egy gondolkodási fegyelem.

Miért fontos ez LeetCode és interjú közben?

A LeetCode-stílusú feladatok azt jutalmazzák, aki meglátja a feladat szerkezetét.

Egy erős jelölt nem csak azt kérdezi, hogy „melyik pattern ez?”.

Hanem ezt is:

• mi az adat alakja,
• milyen információt kell megőrizni,
• mi dolgozható fel lokálisan,
• és mit lehet későbbre hagyni vagy előre kiszámolni.

Pontosan ezt adja meg a problémafelbontás.

2. Alapfogalmak

A kulcskérdések

Megoldás előtt öt dolgot tisztázz:

1. Inputmodell — méret, értéktartomány, rendezettség, duplikátumok és minden szerkezeti feltételezés.
2. Outputmodell — egy válasz vagy több, index vagy érték, sorrendtartás kell-e, és mi történik, ha nincs megoldás.
3. Constraint-ek — ezek mutatják meg, hogy brute force, lineáris scan, rendezés vagy extra memória reális-e.
4. Edge case-ek — üres input, egy elem, ismétlődő értékek, lehetetlen válasz és határértékek.
5. Fő állapot — a legkisebb információhalmaz, amelynek fenn kell maradnia két lépés között.

Állapot, invariáns, tranzíció

A legtöbb tiszta megoldás három elemből áll:

• Állapot: index, futó összeg, minimum eddig, ablakhatár, frequency map vagy eddigi legjobb válasz.
• Invariáns: az az állítás, amely minden lépés után igaz marad, például hogy a best az eddig látott legjobb válasz vagy hogy az aktuális ablak érvényes.
• Tranzíció: az a frissítési szabály, amely a következő elem érkezésekor módosítja az állapotot.

Ha ezt a hármat tisztán ki tudod mondani, a végső kód sokkal könnyebben védhető.

Újrafogalmazás és részproblémák

Sok feladat akkor nyílik ki, amikor kisebb, operatív kérdéssé írod át:

• „találj duplikátumot” → „láttam már ezt az értéket?”,
• „maximalizáld a profitot” → „mi az eddigi legolcsóbb ár?”,
• „leghosszabb érvényes szegmens” → „hogyan tartok fenn egy érvényes ablakot?”,
• „számold meg a lehetőségeket” → „hány út vezet ebbe az állapotba?”.

Ez gyakran megmutatja, hogy prefix összefoglaló, lokális állapot, komplement-lookup vagy DP-részprobléma kell-e.

Információmegőrzés és töréspontok

Általában nem kell a teljes előzmény. Kérdezd meg, minek kell túlélnie:

• a legutóbbi indexnek,
• a legkisebb eddigi értéknek,
• egy seen-count mapnek,
• vagy annak, hogy egy határt már átléptél-e.

Nevezd meg azt is, mitől bukna el a megközelítés:

• ha a greedy döntéshez jövőbeli információ kell,
• ha a rendezett input feltételezés nem igaz,
• ha egy-pass logikával nem elérhető a szükséges jövőbeli kontextus,
• vagy ha az in-place módosítás miatt elvesznek még szükséges eredeti értékek.

Praktikus checklist

1. Azonosítsd az input és output alakját.
2. Olvasd ki a constraint-ekből a skálát.
3. Sorolj fel legalább három edge case-t.
4. Definiáld a legkisebb hasznos állapotot.
5. Mondd ki az invariánst.
6. Válassz baseline-t.
7. Csak akkor optimalizálj, ha a constraint megköveteli.

3. Gyakorlati használat

Mikor támaszkodj rá erősen?

Akkor használd expliciten, ha a prompt hosszú, több feltétel keveredik benne, rejtett feltételezései vannak, vagy nem világos, melyik pattern illik rá. Különösen hasznos akkor, ha visszatérő gond az off-by-one hiba vagy az output félreértése.

Mikor tartsd könnyűnek?

Ne csinálj belőle ceremóniát. Kicsi és egyértelmű feladatnál az input alakja, egy fontos edge case és az invariáns már elég lehet. A cél a tisztaság, nem a papírmunka.

Erős interjús workflow

Egy jó interjús narráció általában ezt tudja:

1. újrafogalmazza az inputot és outputot,
2. kiemeli a fontos constraint-et,
3. felsorolja a fő edge case-eket,
4. definiálja az állapotot és invariánst,
5. ad egy baseline-t,
6. és csak utána optimalizál.

Ez a gondolkodás már önmagában erős jel.

Baseline, elágazás, review

A baseline correctness-ankert és látható optimalizációs célt ad. A constraint ezután eldönti, hogy maradhatsz-e egyszerű scanen, lineáris megoldás felé kell-e mozdulni, vagy szükség van plusz memóriára, például mapre vagy counting arrayre. Pair-programming és review közben mondd ki, mit modellezel, mit jelent az állapot, melyik edge case a veszélyes, és mely feltételezés nincs dokumentálva.

Egy gyakorlati szabály

Ha egy feladat maszatosnak érződik, a válasz többnyire nem egy trükkösebb ciklus, hanem egy tisztább problémafelbontás.

4. Kódpéldák

Alap példa — nemcsökkenő tömb ellenőrzése

Ez egyszerű példa, de jól mutatja a problémafelbontást.

A feladat átírható így:

• input: egész szám tömb,
• output: boolean,
• edge case-ek: üres és egyelemű tömb,
• invariáns: minden eddig látott szomszédos párra igaz, hogy nums[i - 1] <= nums[i].

public class NonDecreasingCheck {
    public static boolean isNonDecreasing(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return true;
        }

        for (int index = 1; index < nums.length; index++) {
            if (nums[index - 1] > nums[index]) {
                return false;
            }
        }

        return true;
    }
}

Miért működik ez a felbontás?

• az output egyszerű boolean,
• csak a szomszédos reláció számít,
• és az invariáns kicsi, könnyen ellenőrizhető.

Haladó példa — legjobb profit egy vételből és egy eladásból

Ez klasszikus problémafelbontási feladat, mert könnyű rosszul olvasni.

A hasznos újrafogalmazás ez:

• az aktuális naphoz képest mi volt eddig a legolcsóbb ár,
• és mennyi lenne a legjobb profit, ha ma adnék el.

Az állapot így:

• minPriceSoFar,
• bestProfit.

Az invariáns pedig:

• a minPriceSoFar az eddig látott minimum,
• a bestProfit az eddig látott legjobb profit.

public class BestProfit {
    public static int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int minPriceSoFar = prices[0];
        int bestProfit = 0;

        for (int index = 1; index < prices.length; index++) {
            int currentPrice = prices[index];
            int candidateProfit = currentPrice - minPriceSoFar;

            if (candidateProfit > bestProfit) {
                bestProfit = candidateProfit;
            }

            if (currentPrice < minPriceSoFar) {
                minPriceSoFar = currentPrice;
            }
        }

        return bestProfit;
    }
}

Mit spórolt meg nekünk ez a felbontás?

• nem kell minden párt összehasonlítani,
• nem kevered össze a vétel és eladás sorrendjét,
• és nem felejted el, hogy veszteséges piacon is 0 a helyes válasz.

Haladó példa — azonos karakterek leghosszabb futama

Ez a példa az állapotot és a tranzíciót emeli ki.

Hasznos felbontás:

• input: string,
• output: a leghosszabb egymást követő futam hossza,
• edge case-ek: üres string és egykarakteres string,
• állapot: currentRunLength, bestRunLength, previousChar.

public class LongestRun {
    public static int longestRun(String text) {
        if (text == null || text.isEmpty()) {
            return 0;
        }

        int currentRunLength = 1;
        int bestRunLength = 1;
        char previousChar = text.charAt(0);

        for (int index = 1; index < text.length(); index++) {
            char currentChar = text.charAt(index);

            if (currentChar == previousChar) {
                currentRunLength++;
            } else {
                currentRunLength = 1;
                previousChar = currentChar;
            }

            if (currentRunLength > bestRunLength) {
                bestRunLength = currentRunLength;
            }
        }

        return bestRunLength;
    }
}

Ez nem szintaxisról szól.

Hanem arról, hogy pontosan felismerd, mely információnak kell fennmaradnia két lépés között.

Gyakori hiba — kódolás az output szabályainak tisztázása előtt

Gyakori hiba, hogy valaki egy másik problémát old meg, mint amit kértek.

public class PairSumPitfall {
    public static int[] findPair(int[] nums, int target) {
        for (int left = 0; left < nums.length; left++) {
            for (int right = left + 1; right < nums.length; right++) {
                if (nums[left] + nums[right] == target) {
                    return new int[] {nums[left], nums[right]};
                }
            }
        }

        return new int[] {-1, -1};
    }
}

Ez rossz lehet, ha a prompt valójában ezt kérte:

• indexeket értékek helyett,
• one-based indexinget,
• eredeti sorrend megtartását,
• vagy hibát dobni akkor, ha nincs megoldás.

A problémafelbontás-alapú javítás először a szerződést tisztázza.

public class PairSumFixed {
    public static int[] findPairIndices(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return new int[] {-1, -1};
        }

        for (int left = 0; left < nums.length; left++) {
            for (int right = left + 1; right < nums.length; right++) {
                if (nums[left] + nums[right] == target) {
                    return new int[] {left, right};
                }
            }
        }

        return new int[] {-1, -1};
    }
}

A kód még mindig egyszerű.

A különbség az, hogy most már a helyes feladatot oldja meg.

5. Trade-offok

Szempont	Részletek
⚡ Performance	A jó problémafelbontás korán megmutatja a valódi szűk keresztmetszetet, így nem a rossz dolgot optimalizálod.
💾 Memory	A jobb modellezés gyakran felfedi, hogy valóban kell-e map, prefix tömb vagy extra buffer.
🔧 Maintainability	A felbontott megoldás könnyebben magyarázható, review-zható és debugolható, mert az állapot és az invariáns explicit.
🔄 Flexibility	A tiszta felbontás miatt könnyebb ugyanazt a logikát promptvariánsokra adaptálni, ha kicsit változik az output vagy a constraint.

Performance trade-off: Egy perc problémafelbontás általában sokkal több mint egy perc debugolást spórol meg.

Memory trade-off: Ha pontosan tudod, milyen információnak kell fennmaradnia, sokszor felesleges történetet sem kell eltárolni.

Maintainability trade-off: A leggyorsabban leírt ciklus nem mindig a legkönnyebben review-zható megoldás.

Flexibility trade-off: A tiszta contractra épített megoldás jobban túléli a prompt kismértékű változásait, mint a túl korán kitalált pattern.

6. Gyakori hibák

1. Túl korai patternválasztás
   Csak azért, mert tömb van a feladatban, még nem biztos, hogy two pointers vagy hash map kell. Előbb tisztázd az inputot, constraint-et és output contractot.

2. Az output contract figyelmen kívül hagyása
   Értékek visszaadása indexek helyett, vagy egyetlen válasz visszaadása akkor is, amikor az összes kellene, könnyen érvényteleníti az algoritmust.

3. Edge case-ek átugrása
   Az üres input, az egyetlen elem, a duplikátumok és a lehetetlen válaszok nagyon gyorsan előhozzák a rejtett hibákat.

4. Túl sok állapot használata
   Sok kezdő több információt cipel, mint amennyi kell. A jó felbontás a legkisebb elégséges állapotot keresi.

5. Az invariáns ki nem mondása
   Ha nem tudod elmagyarázni, mi marad végig igaz a ciklusban, nagyobb eséllyel fogod véletlenül megsérteni.

6. A constraint dekorációnak tekintése
   A constraint tervezési input. Ha n nagy, a kvadratikus megoldást külön meg kell indokolni.

7. Optimalizálás helyes baseline nélkül
   Egy korrekt brute-force vagy scan baseline gyakran a legjobb módja annak, hogy megértsd, mit kell valójában javítani.

7. Mélyebb összefüggések

Hogyan bontják fel a problémát a tapasztalt fejlesztők?

A tapasztalt fejlesztők jellemzően több rétegben gondolkodnak.

Azt kérdezik:

• mi a formális contract,
• mi a legkisebb hasznos állapot,
• milyen feltételezésre épül a megoldás,
• mi törik el, ha kicsit változik a prompt,
• és mi lenne az egyszerű baseline.

Ezért maradnak nyugodtak kaotikusnak tűnő promptoknál.

A constraint valójában kockázatjelző

A constraint nem csak azt mondja meg, mi megengedett.

Azt is, mi kockázatos.

Például:

• n = 10^5 mellett a nested loop gyanús,
• nagy értéktartomány mellett a direct counting array gyanús,
• online vagy streaming input mellett pedig a „sort first” megközelítés eleve kieshet.

A jó problémafelbontás nem csak pattern-aware, hanem risk-aware is.

Az invariáns tervezési horgony

Sok interjús megoldás addig tűnik varázslatnak, amíg ki nem mondod az invariánst.

Ha az invariáns látszik, a ciklus is sokkal kevésbé misztikus.

Például:

• running minimum scanben a minimum tényleg az eddig látott minimum,
• sliding window esetén az aktuális ablak definíció szerint érvényes,
• prefix-sum logikában az összeg helyesen foglalja össze az eddigi prefixet.

Ezért senior szokás hangosan kimondani az invariánst.

Az edge case miniatűr ellenfél

Az edge case nem csak unalmas checklist pont.

Hanem egy apró ellenfél.

Ha a megoldás túléli:

• az üres inputot,
• az egyetlen elemet,
• az ismétlődő határértékeket,
• és a lehetetlen célokat,

akkor a modell általában már megbízhatóbbá válik.

Az újrafogalmazás sokszor a valódi áttörés

Sok előrelépés akkor történik, amikor a kérdést mechanikusabb formában írod át.

Példák:

• „befejezhető-e a válasz már látott információból?”,
• „mi a legolcsóbb prefix-összefoglaló, amit fenn tudok tartani?”,
• „mi marad igaz minden lépés után?”,
• „globális információ kell, vagy elég a lokális állapot?”

Ez sokszor a híd a zavar és a patternfelismerés között.

A debugging előnye

A problémafelbontás az első wrong answer után is erős eszköz.

Ha egy megoldás elbukik, bontsd fel a hibát:

• félreértetted a contractot,
• hiányos az állapot,
• hibás a tranzíció,
• nem igaz az invariáns,
• vagy hiányzik egy edge case?

Ez sokkal gyorsabb út, mint véletlenszerűen foltozni a kódot.

Az interjús kommunikációs előny

Az interjúztatók gyakran a gondolkodás minőségét jutalmazzák, nem csak a végső kódot.

Ha kimondod:

• mi a contract,
• mely edge case-ekkel számoltál,
• milyen invariánst akarsz,
• és miért elég az általad választott állapot,

akkor a gondolkodásod már a kész kód előtt is erősnek látszik.

8. Interjúkérdések

Q: Mit jelent a problémafelbontás algoritmikus interjúban?
A: Azt a folyamatot, amelyben a promptot kisebb döntésekre bontod, például input/output modellezésre, constraint-ekre, edge case-ekre, állapotra és invariánsokra, még az implementáció előtt.

Q: Miért ilyen fontosak a constraint-ek?
A: Mert kizárják az irreális megoldásokat, és megmutatják, milyen komplexitási tartomány elfogadható.

Q: Mi az invariáns egyszerű nyelven?
A: Olyan állítás, ami az algoritmus futása alatt végig igaz marad, és stabil támpontot ad a ciklus helyességéhez.

Q: Miért érdemes baseline megoldással kezdeni?
A: Mert a baseline tisztázza a feladatot, és megmutatja, mit kell valóban optimalizálni, ahelyett hogy túl korán próbálnál okos lenni.

Q: Mi az egyik legbiztosabb jele annak, hogy hiányzik a problémafelbontás?
A: Az, amikor gyorsan elkezdesz kódolni, de nem tudod világosan elmondani az output contractot, az edge case-eket vagy az állapotváltozók jelentését.

9. Fogalomtár

Fogalom	Definíció
contract	A függvény pontos input-output viselkedése, amit teljesítenie kell.
edge case	Határeseti vagy szokatlan input, amely próbára teszi a logika helyességét.
invariáns	Olyan állítás, amely végig igaz marad a futás során.
állapot	Az az információ, amely egyik lépésből a következőbe átkerül.
tranzíció	Az a frissítési szabály, amely az egyik állapotból a következőt létrehozza.
baseline	Egyszerű első megoldás, amely segít a helyesség és komplexitás megértésében az optimalizálás előtt.
újrafogalmazás	A prompt operatívabb formába írása, hogy könnyebb legyen megoldani.

10. Cheatsheet

• Patternválasztás előtt modellezd az inputot és az outputot.
• A constraint-et tervezési jelként olvasd, ne dekorációként.
• Korán sorolj fel legalább három edge case-t.
• Definiáld a legkisebb elégséges állapotot.
• Mondd ki egy mondatban az invariánst.
• Írd le, hogyan változik az állapot lépésről lépésre.
• Baseline nélkül ne optimalizálj.
• A homályos promptot írd át operatív kérdéssé.
• Ha nehéz debugolni, a hibát bontsd fel, ne csak a kódot foltozd.
• Az erős interjús válasz a reasoning contractot is elmagyarázza, nem csak a ciklust.