[Powered by Google Translate] [Seminar: Tekniske Intervjuer]
[Kenny Yu, Harvard University]
[Dette er CS50.] [CS50.TV]
Hei alle sammen, jeg er Kenny. Jeg er for tiden en junior studerer informatikk.
Jeg er en tidligere CS TF, og jeg skulle ønske jeg hadde dette da jeg var en underclassman,
og det er derfor jeg gir dette seminaret.
Så jeg håper du liker den.
Dette seminaret er om tekniske intervjuer,
og alle mine ressurser kan bli funnet på denne linken,
denne linken her, et par av ressurser.
Så jeg laget en liste over problemer, faktisk, ganske mange problemer.
Også en generell ressurser siden hvor vi kan finne tips
om hvordan å forberede for et intervju,
tips om hva du bør gjøre under en faktisk intervju,
samt hvordan å nærme problemer og ressurser for fremtidig referanse.
Det er alle på Internett.
Og bare for å forord dette seminaret, en ansvarsfraskrivelse,
som dette bør ikke - intervjuet forberedelse
bør ikke være begrenset til denne listen.
Dette er kun ment som en veiledning,
og du bør definitivt ta alt jeg sier med en klype salt,
men også bruke alt jeg pleide å hjelpe deg i din intervju forberedelse.
>> Jeg kommer til å få fart gjennom de neste par lysbilder
slik at vi kan få til faktiske case studier.
Strukturen i et intervju for en software engineering posisjon,
vanligvis er det 30 til 45 minutter,
flere runder, avhengig av selskapet.
Ofte vil du bli koding på en hvit bord.
Så en hvit bord som dette, men ofte på en mindre skala.
Hvis du har en telefon intervju, vil du sannsynligvis bruke
enten collabedit eller en Google Doc, slik at de kan se du bor koding
mens du blir intervjuet over telefon.
Et intervju i seg selv er vanligvis 2 eller 3 problemer
teste informatikk kunnskap.
Og det vil nesten helt sikkert innebære koding.
De typer spørsmål som du ser er vanligvis datastrukturer og algoritmer.
Og ved å gjøre slike problemer,
de vil spørre deg, liker, er det tid og rom kompleksitet, stor O?
Ofte de ber også høyere nivå spørsmål,
så, designe et system,
hvordan ville du legge ut koden?
Hva grensesnitt, hvilke klasser, hva moduler du har i systemet ditt,
og hvordan disse kommuniserer sammen?
Så datastrukturer og algoritmer, samt utforme systemer.
>> Noen generelle tips før vi dykke inn i våre case-studier.
Jeg tror den viktigste regelen er alltid å tenke høyt.
Intervjuet er ment å være din sjanse til å vise frem din tankeprosess.
Poenget med intervjuet er for intervjueren å måle
hvordan du tenker og hvordan du går gjennom et problem.
Det verste du kan gjøre er å være stille i hele intervjuet.
Det er bare ikke bra.
Når du får et spørsmål, du også ønsker å være sikker på at du forstår spørsmålet.
Så gjentar spørsmålet tilbake med dine egne ord
og forsøke å arbeide grundig noen enkle testtilfeller
å sikre at du forstår spørsmålet.
Arbeider gjennom noen test tilfeller vil også gi deg en intuisjon om hvordan å løse dette problemet.
Du kan selv finne noen mønstre for å hjelpe deg å løse problemet.
Deres stor tips er å ikke bli frustrert.
Ikke bli frustrert.
Intervjuer er utfordrende, men det verste du kan gjøre,
i tillegg til å være stille, er å være synlig frustrert.
Du ønsker ikke å gi det inntrykket til en intervjuer.
En ting som du - så mange mennesker, når de går inn i et intervju,
de forsøker å prøve å finne den beste løsningen først,
når du egentlig er det vanligvis en iøynefallende løsning.
Det kan være treg, kan det være ineffektiv, men du bør bare si det,
bare så du har et utgangspunkt for å arbeide bedre.
Også peker ut løsningen er treg, i form av
big O tidskompleksitet eller plass kompleksitet,
vil demonstrere til intervjueren at du forstår
disse problemene når du skriver koden.
Så ikke vær redd for å komme opp med den enkleste algoritme første
og deretter arbeide bedre derfra.
Eventuelle spørsmål så langt? Okay.
>> Så la oss dykke inn i vår første problem.
"Gitt en rekke n heltall, skrive en funksjon som stokker matrisen
på plass, slik at alle permutasjoner av de n heltallene er like sannsynlig. "
Og anta at du har tilgjengelig en tilfeldig heltall generator
som genererer et heltall i området fra 0 til jeg, halv-serien.
Forstår alle dette spørsmålet?
Jeg gir deg en rekke n heltall, og jeg vil at du skal shuffle det.
I katalogen min, skrev jeg noen programmer for å demonstrere hva jeg mener.
Jeg kommer til å shuffle en rekke 20 elementer,
-10 til 9,
og jeg vil at du skal sende en liste som dette.
Så dette er min sortert innspill array, og jeg vil at du skal shuffle det.
Vi vil gjøre det igjen.
Forstår alle spørsmålet? Okay.
Så det er opp til deg.
Hva er noen ideer? Kan du gjøre det som n ^ 2, n log n, n?
Åpne for forslag.
Okay. Så en idé, foreslått av Emmy,
er først beregne et tilfeldig tall, tilfeldig heltall, i et område fra 0 til 20.
Så anta vårt utvalg har en lengde på 20.
I vår diagram av 20 elementer,
Dette er våre innspill array.
Og nå, er hennes forslag om å opprette en ny array,
så dette blir resultatet array.
Og basert på jeg returnerte etter rand -
så hvis jeg var, la oss si, 17,
kopiere syttende elementet inn i den første stilling.
Nå må vi slette - vi trenger å skifte alle elementene her
over slik at vi har et gap på slutten og ingen hull i midten.
Og nå er vi gjenta prosessen.
Nå er vi plukke en ny tilfeldig heltall mellom 0 og 19.
Vi har en ny jeg her, og kopierer vi dette elementet i denne posisjonen.
Da vi skiftet elementer over og vi gjentar prosessen til vi har vår fulle ny rekke.
Hva er kjøretiden for denne algoritmen?
Vel, la oss vurdere virkningen av dette.
Vi er skiftende hvert element.
Når vi fjerner dette i, er vi skiftende alle elementene etter den til venstre.
Og det er en O (n) for et måltid
fordi hva hvis vi fjerner det første elementet?
Så for hver fjerning, fjerner vi -
hver fjerning medfører en O (n) drift,
og siden vi har n flytting, fører dette til en O (n ^ 2) shuffle.
Okay. Så god start. God start.
>> Et annet forslag er å bruke noe som kalles Knuth shuffle,
eller Fisher-Yates shuffle.
Og det er faktisk en lineær tid shuffle.
Og ideen er veldig lik.
Igjen har vi våre innspill array,
men i stedet for å bruke to arrays for vår input / output,
vi bruker den første del av rekken til å holde styr på vår stokket del,
og vi holde styr, og da vi la resten av matrisen vår for unshuffled delen.
Så her er hva jeg mener. Vi starter med - vi velger en i,
en matrise 0-20.
Vår nåværende pekeren peker til den første indeksen.
Vi velger noen jeg her
og nå har vi bytte.
Så hvis dette var 5, og dette var 4,
den resulterende matrisen vil ha 5 her og 4 her.
Og nå har vi oppmerksom på en markør her.
Alt til venstre er stokket
og alt til høyre er unshuffled.
Og nå kan vi gjenta prosessen.
Vi velger en tilfeldig indeks mellom 1 og 20 nå.
Så antar vår nye jeg er her.
Nå er vi bytte denne i med vår nåværende ny stilling her.
Så vi en byttering frem og tilbake som dette.
La meg få opp koden for å gjøre det mer konkret.
Vi starter med vårt valg av i -
vi starter med i lik 0, henter vi et tilfeldig sted j
i unshuffled parti av matrisen, til i n-1.
Så hvis jeg er her, velge en tilfeldig indeks mellom her og resten av tabellen,
og vi bytte.
Dette er all koden er nødvendig for å shuffle din array.
Eventuelle spørsmål?
>> Vel, trengte ett spørsmål er, hvorfor er dette riktig?
Hvorfor er alle permutasjon like sannsynlig?
Og jeg vil ikke gå gjennom bevis på dette,
men mange problemer i informatikk kan påvises gjennom induksjon.
Hvor mange av dere er kjent med induksjon?
Okay. Cool.
Så du kan bevise riktigheten av denne algoritmen ved enkel induksjon,
hvor induksjon hypotese ville være, anta at
min shuffle returnerer hver permutasjon like sannsynlig
opp til de første jeg elementer.
Nå vurderer jeg + 1.
Og ved måten vi velger våre indeksen j for å bytte,
Dette fører til - og så jobbe ut detaljene,
minst en fullstendig bevis på hvorfor dette algoritmen returnerer
hver permutasjon med like sannsynlig sannsynlighet.
>> Greit, neste problem.
Så "gitt en rekke heltall, postive, null, negativ,
skrive en funksjon som beregner den maksimale sum
i alle continueous subarray av input array. "
Et eksempel her er, i det tilfellet hvor alle tall er positive,
så i dag er det beste valget er å ta hele array.
1, 2, 3, 4, er lik 10.
Når du har noen negative i det,
i dette tilfellet bare vi ønsker de to første
fordi velge -1 og / eller -3 vil bringe vår sum ned.
Noen ganger kan vi kanskje begynne i midten av tabellen.
Noen ganger ønsker vi å velge noe i det hele tatt, det er best å ikke ta noe.
Og noen ganger er det bedre å ta fallet,
fordi ting etter det er super store. Så noen ideer?
(Student, uforståelig) >> Ja.
Antar at jeg ikke tar -1.
Så enten jeg velger 1000 og 20.000,
eller jeg bare velge 3 milliarder kroner.
Vel, er det beste valget for å ta alle tallene.
Dette -1, til tross for å være negativ,
hele summen er bedre enn det som var jeg ikke å ta -1.
Så en av de tipsene jeg nevnte tidligere var å oppgi tydelig opplagt
og brute force løsning først.
Hva er brute force løsningen i dette problemet? Ja?
[Jane] Vel, jeg tror det brute force løsning
ville være å legge opp alle mulige kombinasjoner (uforståelig).
[Yu] Okay. Så Jane idé er å ta alle mulige -
Jeg er parafrasering - er å ta alle mulige kontinuerlig subarray,
beregne summen, og deretter ta maksimalt av alle mulige kontinuerlige subarrays.
Hva identifiserer en subarray i min inngang array?
Liker, hva to ting trenger jeg? Ja?
(Student, uforståelig) >> Høyre.
En nedre grense på indeksen og en øvre bundet indeks
unikt bestemmer en kontinuerlig subarray.
[Kvinne student] Er vi estimere det er en rekke unike numre?
[Yu] Nei Så spørsmålet hennes er, er vi antar vårt utvalg -
er vår rekke alle unike numre, og svaret er nei.
>> Hvis vi bruker vår brute force-løsning, så start / slutt indekser
unikt bestemmer vår kontinuerlige subarray.
Så hvis vi iterate for alle mulige start oppføringer,
og for alle end oppføringer> eller = for å starte, og <n,
du beregne summen, og så tar vi den maksimale summen vi har sett så langt.
Er dette klart?
Hva er den store O av denne løsningen?
Timewise.
Ikke helt n ^ 2.
Merk at vi iterate fra 0 til n,
så det er en for-løkke.
Vi iterate igjen fra nesten begynnelsen til slutten, en annen for loop.
Og nå, i løpet av denne, må vi oppsummere hver oppføring,
så det er en annen for loop. Så vi har tre nestet for løkker, n ^ 3.
Okay. Dette går som et utgangspunkt.
Vår løsning er ikke verre enn n ^ 3.
Forstår alle brute force løsning?
>> Okay. En bedre løsning er å bruke en idé kalles dynamisk programmering.
Hvis du tar CS124, som er Algoritmer og datastrukturer,
vil du bli godt kjent med denne teknikken.
Og ideen er å forsøke å bygge opp løsninger til mindre problemer først.
Hva jeg mener med dette er, men for øyeblikket har å bekymre deg to ting: Start og slutt.
Og det er irriterende. Hva om vi kunne bli kvitt en av disse parametrene?
En idé er å - vi gitt vår opprinnelige problem,
finner den maksimale sum enhver subarray i et område [O, n-1].
Og nå har vi en ny deloppgave, hvor vi vet, i vår nåværende indeksen i,
vi vet at vi må konkludere der. Vår subarray må slutte på dagens indeks.
Så de resterende problemet er, hvor skal vi begynne vår subarray?
Betyr dette fornuftig? Okay.
Så jeg har kodet dette opp, og la oss se på hva dette betyr.
I codirectory, det er et program som heter subarray,
og det tar flere elementer,
og den returnerer maksimal subarray summen i min stokket listen.
Så i dette tilfellet, er vår maksimal subarray 3.
Og det er tatt ved bare å bruke 2 og 1.
La oss kjøre det igjen. Det er også tre.
Men denne gangen, merk hvordan vi fikk 3.
Vi tok - vi bare ta 3 selv
fordi det er omgitt av negativer på begge sider,
som vil bringe en sum <3.
La oss kjøre på 10 elementer.
Denne gangen er det 7, tar vi den ledende 3 og 4.
Denne gangen er det 8, og vi får det ved å ta 1, 4 og 3.
Så for å gi deg en intuisjon om hvordan vi kan løse dette forvandlet problem,
la oss ta en titt på denne subarray.
Vi får denne inngangen array, og vi vet svaret er 8.
Vi tar 1, 4 og 3.
Men la oss se på hvordan vi faktisk fikk det svaret.
La oss se på den maksimale subarray som endte på hver av disse indeksene.
Hva er den maksimale subarray som har til slutt på den første posisjonen?
[Student] Zero. >> Zero. Bare ikke ta den -5.
Her det kommer til å være 0 i tillegg. Ja?
(Student, uforståelig)
[Yu] Oh, beklager, det er en -3.
Så dette er en 2, er dette en -3.
Okay. Så -4, hva er den maksimale subarray å avslutte den posisjonen
der -4 er på? Zero.
One? 1, 5, 8.
Nå må jeg avslutte på stedet der -2 er på.
Så 6, 5, 7, og den siste er 4.
Vel vitende om at disse er mine oppføringer
for den transformerte problem der jeg må slutte på hver av disse indeksene,
så mitt endelige svar er bare, ta en sveip over,
og ta det maksimale antallet.
Så i dette tilfellet er det 8.
Dette innebærer at maksimal subarray ender på denne indeksen,
og startet et sted før det.
Forstår alle dette transformert subarray?
>> Okay. Vel, la oss finne ut tilbakefall for dette.
La oss vurdere bare de første oppføringene.
Så her var det 0, 0, 0, 1, 5, 8.
Og så var det en -2 her, og som brakte den ned til 6.
Så hvis jeg kaller oppføringen i posisjon i deloppgave (i),
hvordan kan jeg bruke svar til en tidligere deloppgave
å svare på dette deloppgave?
Hvis jeg ser på, la oss si, dette innlegget.
Hvordan kan jeg beregne svaret 6 ved å se på
en kombinasjon av denne tabellen og svar på tidligere deloppgaver i denne matrisen? Ja?
[Kvinne student] Du tar rekke summer
i posisjon rett før den, så 8 den,
og deretter legge til gjeldende deloppgave.
[Yu] Så hennes forslag er å se på disse to tallene,
dette nummeret og dette nummeret.
Så dette 8 refererer til svaret for deloppgave (i - 1).
Og la oss kalle min inngang rekke A.
For å finne en maksimal subarray som ender i posisjon i,
Jeg har to valg: Jeg kan enten fortsette subarray
som endte på forrige indeks, eller starte en ny rekke.
Hvis jeg skulle fortsette subarray som startet på den forrige indeks,
så den maksimale summen jeg kan oppnå er svaret på det forrige deloppgave
pluss den gjeldende matrisen oppføring.
Men, jeg har også valg å starte en ny subarray,
i hvilket tilfelle summen er 0..
Så svaret er maks av 0, deloppgave i - 1, pluss dagens utvalg oppføring.
Betyr dette tilbakefall forstand?
Vår tilbakefall, som vi nettopp oppdaget, er deloppgave i
er lik den maksimale av forrige deloppgave pluss min nåværende utvalg oppføring,
som betyr fortsette den forrige subarray,
eller 0, starte en ny subarray på min nåværende indeksen.
Og når vi har bygget opp denne tabellen av løsninger, og vår endelige svaret,
bare gjøre en lineær sveip over deloppgave rekke
og ta det maksimale antallet.
Dette er en nøyaktig gjennomføring av det jeg nettopp sa.
Så lager vi en ny deloppgave array, deloppgaver.
Den første oppføringen er enten 0 eller den første oppføringen, maksimum av de to.
Og for resten av deloppgaver
vi bruker nøyaktig gjentakelse vi bare oppdaget.
Nå er vi beregne maksimalt vår deloppgaver array, og det er vårt endelige svar.
>> Så hvor mye plass vi bruker i denne algoritmen?
Hvis du bare har tatt CS50, så du kanskje ikke har diskutert plass veldig mye.
Vel, en ting å merke seg at jeg ringte malloc her med størrelse n.
Hva foreslår det for deg?
Denne algoritmen benytter lineære plass.
Kan vi gjøre det bedre?
Er det noe som du merker at er unødvendig å beregne det endelige svaret?
Jeg antar et bedre spørsmål er, hva slags informasjon
vi trenger ikke å bære hele veien gjennom til slutt?
Nå, hvis vi ser på disse to linjene,
vi bare bryr seg om den forrige deloppgave,
og vi bare bryr seg om maksimalt vi noensinne har sett så langt.
Å beregne vårt endelige svar, trenger vi ikke hele tabellen.
Vi trenger bare det siste tallet, to siste tallene.
Siste tall for deloppgave array, og siste nummer for det maksimale.
Så, faktisk, kan vi smelte disse loopene sammen
og gå fra lineær plass til konstant plass.
Nåværende sum så langt, her, erstatter rolle deloppgave, vår deloppgave array.
Så dagens sum, så langt, er svaret på det forrige deloppgave.
Og at summen, så langt, tar plassen til maks vår.
Vi beregne maksimalt mens vi går langs.
Og så skal vi gå fra lineær plass til konstant plass,
og vi har også en lineær løsning til våre subarray problem.
>> Slike spørsmål vil du få under et intervju.
Hva er tiden kompleksitet, hva er plass kompleksitet?
Kan du gjøre det bedre? Er det ting som er unødvendig å holde rundt?
Jeg gjorde dette for å markere analyser som du bør ta på egen hånd
som du arbeider gjennom disse problemene.
Alltid spørre deg selv: "Kan jeg gjøre det bedre?"
Faktisk kan vi gjøre bedre enn dette?
Sortering av et lurespørsmål. Du kan ikke, fordi du må
minst lese inngangen til problemet.
Så det faktum at du må minst lese innspill til problemet
betyr at du ikke kan gjøre det bedre enn lineær tid,
og du kan ikke gjøre det bedre enn konstant plass.
Så dette er faktisk den beste løsningen på dette problemet.
Spørsmål? Okay.
>> Aksjemarkedet problem:
"Gitt en rekke n heltall, positive, null eller negativ,
som representerer prisen på en aksje over n dager,
skrive en funksjon for å beregne maksimalt utbytte du kan gjøre
gitt at du kjøper og selger nøyaktig 1 på lager innen disse n dager. "
I hovedsak ønsker vi å kjøpe lavt, selger høy.
Og vi ønsker å finne ut det beste resultat vi kan gjøre.
Går tilbake til mitt tips, hva er umiddelbart klart, enkleste svaret, men det er treg?
Ja? (Student, uforståelig) >> Ja.
>> Så du ville bare gå selv og se på aksjekurser
på hvert punkt i tid, (uforståelige).
[Yu] Ok, så hennes løsning - hennes forslag for databehandling
den laveste og beregne den høyeste ikke nødvendigvis fungere
fordi den høyeste kan oppstå før den laveste.
Så hva er den brute force løsning på dette problemet?
Hva er de to tingene som jeg trenger å unikt bestemme overskuddet jeg gjøre? Høyre.
Den brute force løsningen er - oh, så er George forslag vi trenger bare to dager
å unikt bestemme resultatet av disse to dagene.
Så vi beregne hvert par, liker kjøpe / selge,
beregne fortjeneste, noe som kan være negativt eller positivt eller null.
Beregn maksimal profitt som vi gjør etter iterating over alle par av dagene.
Som vil være vår endelige svaret.
Og at løsningen vil være O (n ^ 2), fordi det er n velge to par -
dager som du kan velge blant siste dagene.
Ok, så jeg har ikke tenkt å gå over brute force løsningen her.
Jeg kommer til å fortelle deg at det er en n log n løsning.
Hva algoritme har du nå vet det er n log n?
Det er ikke et lurespørsmål.
>> Flette slag. Flette sort er n log n,
og faktisk er en måte å løse dette problemet for å bruke
en sammenslåing slags slags idé kalt, generelt, splitt og hersk.
Og tanken er som følger.
Du ønsker å beregne den beste kjøp / salg par i venstre halvdel.
Finn det beste resultat du kan gjøre, bare med de første n over to dager.
Så du ønsker å oompute den beste kjøp / salg par på høyre halvdel,
slik at den siste n over to dager.
Og nå er spørsmålet, hvordan flette vi disse løsningene sammen igjen?
Ja? (Student, uforståelig)
>> Ok. Så la meg tegne et bilde.
Ja? (George, uforståelig)
>> Nettopp. George løsning er helt riktig.
Så hans forslag er først beregne den beste kjøp / salg par,
og som oppstår i venstre halvdel, så la oss kalle det venstre, venstre.
Best kjøp / salg par som oppstår i høyre halvdel.
Men hvis vi bare sammenlignet disse to tallene, vi mangler saken
hvor vi kjøper her og selge et sted i høyre halvdel.
Vi kjøper i venstre halvdel, selge i høyre halvdel.
Og den beste måten å beregne den beste kjøp / salg par som spenner begge omganger
er å beregne minimum her og beregne maksimum her
og ta sin forskjell.
Slik at de to tilfellene hvor kjøpe / selge paret oppstår bare her,
bare her, eller på begge halvdeler er definert av disse tre tallene.
Så vår algoritme for å fusjonere våre løsninger sammen,
vi ønsker å beregne den beste kjøp / salg par
hvor vi kjøper på venstre halvdel og selge på høyre halvdel.
Og den beste måten å gjøre det på er å beregne den laveste prisen i første halvår,
den høyeste prisen i høyre halvdel, og ta sin forskjell.
De resulterende tre profitt, disse tre tallene, tar du maksimalt tre,
og det er det beste resultat kan du gjøre over disse første og slutten dagene.
Her viktige linjer er i rødt.
Dette er en rekursiv samtale for å beregne svaret i venstre halvdel.
Dette er en rekursiv kall til beregne svaret i høyre halvdel.
Disse to for løkker beregne min og maks på venstre og høyre halvdel, henholdsvis.
Nå har jeg beregne fortjeneste som spenner begge omganger,
og det endelige svaret er maksimum av disse tre.
Okay.
>> Så sikker, har vi en algoritme, men større spørsmål er,
Hva er tiden kompleksiteten av denne?
Og grunnen til at jeg nevnte flette typen er at denne formen for deler svaret
i to og deretter flette våre løsninger sammen
er akkurat den formen for flettingen slag.
Så la meg gå gjennom varigheten.
Hvis vi definerer en funksjon T (n) til å være antall trinn
for n dager
våre to rekursive samtaler
er hver kommer til å koste t (n / 2),
og det er to av disse samtalene.
Nå trenger jeg å beregne minimum av venstre halvdel,
som jeg kan gjøre i n / 2 gang, pluss maksimalt høyre halvdel.
Så dette er bare n.
Og så pluss noen konstant arbeid.
Og dette tilbakefall ligningen
er nøyaktig gjentakelse ligningen for flettingen slag.
Og vi vet alle at flettingen sort er n log n tid.
Derfor er vårt algoritmen også n log n tid.
Betyr dette iterasjon forstand?
Bare en kort oppsummering av dette:
T (n) er antallet av trinn for å beregne maksimal profitt
løpet av n dager.
Måten vi delt opp våre rekursive samtaler
er ved å ringe vår løsning på de første n / 2 dager,
så det er en samtale,
og da vi ringe igjen på den andre halvdelen.
Så det er to samtaler.
Og så finner vi et minimum på venstre halvdel, som vi kan gjøre i lineær tid,
Finn den maksimale høyre halvdel, som vi kan gjøre i lineær tid.
So n / 2 + n / 2 er like n.
Så har vi noen konstant arbeid, som er som gjør regning.
Dette tilbakefall ligningen er akkurat tilbakefall ligningen for flettingen slag.
Derfor er vår shuffle algoritmen også n log n.
Så hvor mye plass vi bruker?
La oss gå tilbake til koden.
>> Et bedre spørsmål er, hvor mange stack rammer vi noensinne har til enhver tid?
Siden vi bruker rekursjon,
antall stack rammer bestemmer vår plassbruken.
La oss vurdere n = 8.
Vi kaller shuffle på 8,
som vil kalle shuffle på de fire første oppføringene,
som vil kalle en shuffle på de to første oppføringene.
Så vår stabelen er - dette er vår stabelen.
Og så kaller vi shuffle igjen på 1,
og det er det vår base case er, så vi kommer tilbake med en gang.
Har vi noen gang har mer enn så mange stabel rammer?
Nei Fordi hver gang vi gjør en påkallelse,
en rekursiv påkalling til shuffle,
vi deler vår størrelse i to.
Så det maksimale antallet stack rammer vi noensinne har til enhver tid
er i størrelsesorden av log n stabel rammer.
Hver stabel ramme har konstant plass,
og derfor den totale mengde plass,
den maksimale mengden plass som vi noen gang bruke er O (log n) plass
der n er antall dager.
>> Nå spør deg selv: «Kan vi gjøre det bedre?"
Og i særdeleshet, kan vi redusere dette til et problem vi har allerede løst?
Et hint: vi bare diskutert to andre problemer før dette, og det er ikke til å være shuffle.
Vi kan konvertere dette aksjemarkedet problem i maksimal subarray problemet.
Hvordan kan vi gjøre dette?
En av dere? Emmy?
(Emmy, uforståelig)
[Yu] Nettopp.
Så maksimal subarray problem,
Vi leter etter en sum over en sammenhengende subarray.
Og Emmy forslag for aksjer problem,
vurdere endringer, eller deltaer.
Og et bilde av dette er - dette er prisen på en aksje,
men hvis vi tok forskjellen mellom hver dag på rad -
så ser vi at den høyeste prisen, maksimal profitt vi kunne gjøre
er hvis vi kjøper her og selge her.
Men la oss se på den kontinuerlige - la oss se på subarray problemet.
Så her kan vi gjøre - går herfra til her,
vi har en positiv endring, og deretter gå herfra til her har vi en negativ endring.
Men så, går herfra til her har vi en stor positiv endring.
Og disse er de endringene som vi ønsker å oppsummere å få vår sluttresultat.
Da har vi mer negative endringer her.
Nøkkelen til å redusere vårt lager problem i vår maksimal subarray problem
er å vurdere deltaer mellom dagene.
Så lager vi en ny array kalt deltaer,
initialisere den første oppføringen til å være 0,
og deretter for hver delta (i), la det være forskjellen
av min inngang matrise (i), og matrise (i - 1).
Så vi kaller vår rutine for en maksimal subarray
passerer i et delta fylking.
Og fordi maksimal subarray er lineær tid,
og denne reduksjonen, denne prosessen med å opprette denne delta array,
er også lineær tid,
deretter den endelige løsningen for aksjer er O (n) arbeid pluss O (n) arbeid, er fortsatt O (n) arbeid.
Så vi har en lineær tid løsningen på problemet vårt.
Forstår alle denne transformasjonen?
>> Generelt, en god idé at du bør alltid ha
er å prøve å redusere et nytt problem som du ser.
Hvis det ser kjent ut et gammelt problem,
forsøke å redusere det til et gammelt problem.
Og hvis du kan bruke alle verktøyene som du har brukt på det gamle problemet
å løse det nye problem.
Så for å bryte opp, er tekniske intervjuer utfordrende.
Disse problemene er sannsynligvis noen av de mer vanskelige problemer
som du kan se i et intervju,
så hvis du ikke forstår alle de problemene som jeg bare dekket, er det greit.
Dette er noen av de mer utfordrende problemer.
Øve, øve, øve.
Jeg ga en masse problemer i handout, så definitivt sjekke dem ut.
Og lykke til på dine intervjuer. Alle mine ressurser er lagt ut på denne linken,
og en av mine senior venner har tilbudt seg å gjøre spotte tekniske intervjuer,
så hvis du er interessert, e-post vil Yao på den e-postadressen.
Hvis du har noen spørsmål, kan du spørre meg.
Gjør dere har konkrete spørsmål knyttet til tekniske intervjuer
eller eventuelle problemer vi har sett så langt?
Okay. Vel, lykke til på dine intervjuer.
[CS50.TV]