Sådan løses problemer med glidende vinduer

Problemer med glidende vinduer er en type problemer, der ofte bliver spurgt under software engineering-interviews og et, vi underviser på Outco. De er en undergruppe af dynamiske programmeringsproblemer, skønt fremgangsmåden til løsning af dem er meget forskellig fra den, der bruges til at løse tabulerings- eller memoiseringsproblemer. Så forskellig faktisk, at det for mange ingeniører ikke umiddelbart er klart, at der overhovedet er en forbindelse mellem de to.

Dette blogindlæg har til formål at rydde en masse forvirring omkring at løse denne form for problem og besvare nogle almindelige spørgsmål, som ingeniører typisk har. Forhåbentlig vil det vise, at fremgangsmåden faktisk er relativt ligetil, hvis du har den rette tænkning, og når du først har løst et par af disse problemer, skal du være i stand til at løse enhver variation af dem, der bliver kastet din vej.

Hvordan identificerer du dem?

Så den første ting, du vil være i stand til at gøre, er at identificere et problem, der bruger et skydevinduet-paradigme. Heldigvis er der nogle almindelige gaver:

  • Problemet involverer en datastruktur, der er ordnet og kan gentages som en matrix eller en streng
  • Du leder efter en eller anden subrange i den matrix / streng, som en længste, korteste eller målværdi.
  • Der er en tilsyneladende naiv eller brute kraftopløsning, der kører i O (N²), O (2 ^ N) eller en anden stor tidskompleksitet.

Men den største gave er, at den ting, du leder efter, ofte er en form for optimal, ligesom den længste sekvens eller den korteste rækkefølge af noget, der tilfredsstiller en given tilstand nøjagtigt.

Og det fantastiske ved glideproblemer er, at det meste af tiden kan løses i O (N) tid og O (1) rumkompleksitet.

I Bit Flip er du for eksempel på udkig efter den længste kontinuerlige sekvens på 1s, som du kan danne i en given række 0s og 1s, hvis du har evnen til at vende et antal af disse 0s til 1s.

I Minimum Window Substring søger du efter den korteste rækkefølge af tegn i en streng, der indeholder alle tegnene i et givet sæt.

Hvorfor er denne dynamiske programmering?

Denne søgning efter et optimalt tip om forholdet mellem glidevindsproblemer og andre dynamiske problemer. Du bruger problemets optimale substrukturegenskap for at garantere, at en optimal løsning på et underproblem kan genbruges for at hjælpe dig med at finde den optimale løsning på et større problem.

Du bruger også det faktum, at der er overlappende delproblemer i den naive tilgang, for at reducere det arbejde, du skal gøre. Tag problemet med minimumsvinduesubstring. Du får en streng, og et sæt tegn, du skal kigge efter i den streng. Der kan være flere overlappende underlag, der indeholder alle de tegn, du leder efter, men du vil kun have den korteste. Disse tegn kan også være i enhver rækkefølge.

Her er et eksempel:

Streng: “ADOBECODEBANC”
Tegn: “ABC”

Den naive måde at nærme sig dette på ville være at først scanne gennem strengen, se på ALLE underlag i længde 3 og kontrollere, om de indeholder de tegn, du leder efter. Hvis du ikke kan finde nogen af ​​længde 3, kan du prøve alle underlag med længde 4, 5, 6 og 7 osv. Indtil du når længden på strengen.

Hvis du når det punkt, ved du, at disse figurer ikke er derinde.

Dette er virkelig ineffektivt og kører i O (N²) tid. Og hvad der sker, er, at du går glip af en masse god information om hver pas ved at begrænse dig selv til at se på vinduer med fast længde, og du undersøger en række dele af strengen, som ikke behøver at blive re- undersøgt.

Du kaster meget godt arbejde ud, og du gør en masse nytteløst arbejde igen.

Det er her ideen om et vindue kommer ind.

Dit vindue repræsenterer det aktuelle afsnit af den streng / array, som du "ser på", og der er normalt nogle oplysninger gemt sammen med det i form af konstanter. I det mindste vil det have 2 pegepunkter, hvoraf det ene indikerer det indeks, der svarer til begyndelsen af ​​vinduet, og et, der angiver slutningen af ​​vinduet.

Du vil normalt holde styr på den tidligere bedste løsning, du har fundet, hvis nogen, og nogle andre aktuelle oplysninger om det vindue, der tager O (1) -plads. Jeg ser, at mange ingeniører bliver udløst af O (1) plads, men alt dette betyder, at den mængde hukommelse, du bruger, ikke skaleres med inputstørrelsen. Så ting som en aktuel_sum-variabel eller antal bit-flips (i bit-flip-problemet) tilbage, eller endda antallet af tegn, som du stadig har brug for at finde (da der er et fast antal ASCII-tegn).

Men når du først har valgt hvilke variabler du vil gemme, er alt hvad du skal tænke på, to ting: Hvornår vokser jeg dette vindue? Og hvornår krymper jeg det?

Forskellige slags Windows

Der er flere former for problemer med skydevinduer. Den vigtigste, vi vil tale om i dag, er den første slags, men der er et par andre, der er værd at nævne, der vil komme ind i et andet indlæg.

1) Hurtig / langsom

Disse har en hurtig markør, der vokser dit vindue under en bestemt betingelse. Så for et minimumsvinduesubstring vil du øge dit vindue, indtil du har et vindue, der indeholder alle de tegn, du leder efter.

Det vil også have en langsom markør, der krymper vinduet. Når du først har fundet et gyldigt vindue med den hurtige markør, vil du begynde at skyde den langsomme markør op, indtil du ikke længere har et gyldigt vindue.

Så når du har en substring, der indeholder alle de tegn, du leder efter, så vil du begynde at krympe det ved at flytte den langsomme markør op, indtil du ikke længere har en gyldig substring (hvilket betyder at du ikke længere har har alle de figurer, du leder efter)

2) Hurtig / opsamling

Dette ligner den første slags, bortset fra, i stedet for at øge den langsomme markør op, flytter du den bare op til den hurtige markørs placering og fortsætter derefter med at flytte den hurtige markør op. Den slags "hopper" til indekset for hurtigviseren, når en bestemt betingelse er opfyldt.

Dette fremgår af problemet Maks fortløbende sum. Her får du en liste over heltal, positive og negative, og du leder efter en rækkefølge i rækkefølge, der summerer til det største beløb. Nøgleindsigt: Den langsomme markør "hopper" til den hurtige markørs indeks, når den aktuelle sum ender med at blive negativ. Mere om, hvordan dette fungerer senere.

For eksempel i matrisen: [1, 2, 3, -7, 7, 2, -12, 6] ville resultatet være: 9 (7 + 2)

Igen ser du efter en slags optimale (dvs. den maksimale sum).

3) Hurtig / lagging

Denne er lidt anderledes, men i det væsentlige henviser den langsomme markør ganske enkelt til et eller to indekser bag den hurtige markør, og det holder styr på det valg, du har valgt.

I House Robber-problemet prøver du at se, hvad den maksimale mængde guld, du kan stjæle fra huse, der ikke er ved siden af ​​hinanden. Her er valget, om du skal stjæle fra det nuværende hus eller ej, da du i stedet kunne have stjålet fra det * forrige * hus.

Det optimale, du leder efter, er den maksimale mængde guld, du kan stjæle.

4) For / bag

Disse er forskellige, for i stedet for at have begge pegere, der rejser forfra, har du en fra fronten og den anden bagfra. Et eksempel på dette er regnvandsproblemet, hvor du beregner den maksimale mængde regnvand, du kan fange i et givet terræn. Igen ser du efter en maksimal værdi, skønt logikken er lidt anderledes, optimerer du stadig en brute force O (N²) løsning.

Disse fire mønstre bør ikke overraske. Når alt kommer til alt er der kun så mange måder, du kan bevæge to pegere gennem en matrix eller streng på lineær tid.

Problemer, der bruger hver type

Se efter "Key Insights"

En sidste ting at overveje med disse problemer er den vigtigste indsigt, der "låser op" problemet. Jeg taler om det lidt mere i mit andet indlæg om, hvordan man generelt nærmer mig algoritmeproblemer. Det indebærer normalt at trække nogle faktum ud fra begrænsningerne i problemet, der hjælper dig med at se på det på en anden måde.

I House Robber-problemet kan du for eksempel ikke rane tilstødende huse, men alle huse har en positiv mængde guld (hvilket betyder, at du ikke kan rane et hus og have mindre guld efter at have frarøvet det). Den vigtigste indsigt her er, at den maksimale afstand mellem de to huse, du berøver, vil være to. Hvis du havde tre huse mellem røverier, kunne du bare rane det i midten af ​​de tre, og du vil blive garanteret at øge mængden af ​​guld, du stjæler.

For Bit Flip-problemet behøver du ikke faktisk at mutere arrayet i problemet, du skal bare holde styr på, hvor mange vend du har tilbage. Når du vokser dit vindue, trækker du fra dette nummer, indtil du har udtømt alle dine flips, og derefter krymper du dit vindue, indtil du støder på et nul og får en flip back.

Indpakning af vores eksempel

Så lad os sammenpakke problemet med minimalt vinduesubstring.

Vi etablerede det, vi har brug for for at vokse vores vindue, indtil vi har en gyldig substring, der indeholder alle de bogstaver, vi leder efter, og derefter krympe det vindue, indtil vi ikke længere har en gyldig substring.

Den vigtigste indsigt her er, at det mindste vindue altid vil være afgrænset af bogstaver, som vi søger efter. Hvis det ikke var tilfældet, kunne vi altid forkorte vores vindue men slippe ubrugte tegn fra ved starten eller slutningen.

Nogle andre indsigter at overveje: der kan være gentagelser af visse tegn i vores vindue, og det er okay. Men det antyder, at vi har brug for en slags måde at holde styr på antallet af gentagelser, vi har set i vores vindue, og ikke kun om vi har set en karakter, vi leder efter.

Dette skulle straks indebære brug af et hashkort, hvor tasterne er tegnene, og værdierne er antallet af gange, vi har set et tegn i vores vindue.

Vi har også brug for et heltal for at holde styr på, hvor mange karakterer vi mangler for at fuldføre vores sæt.

Dette ville kun mindskes, når vi ser et tegn i vores vindue, der hører til sættet, men det er ikke set i det pågældende vindue.

Så lad os opsummere algoritmen:

Hvad vi har brug for:

1) En resultatuple (eller to-element array), der repræsenterer start- og slutindekset for den korteste substring, der indeholder alle tegn. Initialiseret til det størst mulige interval (f.eks. [-Infinity, Infinity].
2) Et hash-kort for at holde styr på, hvordan bogstaver i det sæt, du har set i det aktuelle vindue, initialiseret med alle tegn i sættet som taster og alle værdier som 0.
3) En tæller til at holde styr på, når vi ser et nyt bogstav fra sættet, når vi vokser vinduet, eller mister et bogstav fra sættet, når vi krymper vinduet. Initialiseret til antallet af tegn, vi leder efter.
4) En hurtig og langsom markør, begge initialiseret til 0.

Så alt, hvad vi gør, er at have en for-loop, hvor den hurtige markør forøges hver runde.

Inden for det for loop, hvis vi ser et tegn fra hashMap, øger vi dets værdi på kortet.

Hvis dens værdi var 0 på hashkortet før, reducerer vi antallet af tegn, der mangler. Men hvis vi har gentagelser af en karakter, som vi søger efter, erklærer vi ikke disken.

Når du har set alle de tegn, du leder efter, når denne tæller 0 og

Derefter har vi en stund-loop i for-loop, der kun kører, mens antallet af tællere er 0.

Inden for denne løkken, hvis forskellen mellem vores hurtige og langsomme markør er mindre end forskellen mellem hvad der er gemt i vores resultattuple, så kan vi erstatte denne tuple med et nyt mindste vindue. Som standard opdateres det første gang, vi finder et gyldigt vindue.

Så alt, hvad vi gør, er at øge vores langsomme markør. Hvis vi ser et tegn i vores sæt, er vi nødt til at mindske dens værdi i hashMap med 1, når det bevæger sig ud af vores vindue.

Hvis dens værdi i hashMap når 0, steg antallet af tegn, vi mangler, nu til 1, og vi vil bryde ud af mens loop i næste runde.

Og det er hele algoritmen. Her er lysbillederne til de næste trin i vores eksempel:

Og nedenfor er koden i javascript:

Som en udfordring, prøv at tænke over, hvordan du muligvis ændrer denne løsning til at håndtere gentagne tegn i vores sæt. For eksempel: "AABCC". Tænk på hvornår vi ønsker at vokse eller formindske vores vindue, og hvordan vi effektivt kan kontrollere, hvornår disse betingelser er opfyldt.

Forhåbentlig hjælper dette indlæg med at forstå problemer med skydevinduer. Det tager nogen tid at vikle dit hoved rundt, men i sidste ende er det et værdifuldt mønster at kende, og det er ikke ud over nogen med den rigtige intuition.

En god måde at stivne læring på er at forklare din løsning til en anden ingeniør og se, om du kan hjælpe dem med at forstå, hvordan det fungerer.

Hvis du kan lide det, du ser, og ønsker at holde jævne niveauer på algoritmer og datastrukturer, så tjek os på Outco.io. Nye kohorter starter hver måned!