[Powered by Google Translate] [Seminar: Tekniske Interviews] [Kenny Yu, Harvard University] [Dette er CS50.] [CS50.TV] Hej alle, jeg er Kenny. Jeg er i øjeblikket en junior studere datalogi. Jeg er en tidligere CS TF, og jeg ville ønske, jeg havde, da jeg var en underclassman, og det er derfor, jeg giver dette seminar. Så jeg håber du nyder det. Dette seminar er om tekniske interviews, og alle mine ressourcer kan findes på dette link, dette link lige her, et par af ressourcer. Så jeg lavede en liste over problemer, faktisk en hel del problemer. Også en generel ressourcer side, hvor vi kan finde tips om, hvordan man forberede sig til et interview, tips om, hvad du skal gøre i løbet af en egentlig interview, samt hvordan man griber problemer og ressourcer til senere brug. Det er alt sammen online. Og bare for at indlede denne seminar, en ansvarsfraskrivelse, som dette bør ikke - dit interview forberedelse bør ikke være begrænset til denne liste. Dette er kun ment som en guide, og du bør helt sikkert tage alt hvad jeg siger med et gran salt, men også bruge alt, hvad jeg bruges til at hjælpe dig i din interview forberedelse. 

Jeg har tænkt mig at fremskynde gennem de næste par dias så vi kan få de faktiske case studies. Strukturen i et interview for et software engineering postion, typisk er 30 til 45 minutter, flere runder, afhængig af selskabet. Ofte vil du blive kodning på en hvid bord. Så en hvid bord som dette, men ofte på en mindre skala. Hvis du har en telefon interview, vil du sandsynligvis bruge enten collabedit eller et Google Doc, så de kan se du bor kodning mens du bliver interviewet over telefonen. Et interview selv er typisk 2 eller 3 problemer teste din computer science viden. Og det vil næsten helt sikkert indebære kodning. De typer af spørgsmål, som du vil se er normalt datastrukturer og algoritmer. Og ved at gøre den slags problemer, de vil bede dig, vil, hvad er tid og rum kompleksitet, big O? Ofte beder også højere niveau spørgsmål, så, at designe et system, hvordan ville du sætte din kode? Hvilke grænseflader, hvad klasser, hvad moduler, du har i dit system, og hvordan disse interagerer sammen? Så datastrukturer og algoritmer, samt designe systemer. 

Nogle generelle tips, før vi dykker ind i vores case studies. Jeg tror den vigtigste regel er altid tænker højt. Interviewet formodes at være din chance for at vise din tankeproces. Pointen med samtalen er for intervieweren at vurdere hvordan du tænker og hvordan du går gennem et problem. Det værste du kan gøre er at være tavs gennem hele interviewet. Det er bare ikke godt. Når du får et spørgsmål, du også ønsker at sikre, at du forstår spørgsmålet. Så gentage spørgsmålet tilbage i dine egne ord og forsøge at arbejde grundige et par enkle testcases at sikre, at du forstår spørgsmålet. Arbejde gennem et par testcases vil også give dig en intuition om, hvordan man løser dette problem. Du kan endda opdage et par mønstre til at hjælpe dig med at løse problemet. Deres store tip er ikke at blive frustreret. Må ikke blive frustreret. Interviews er udfordrende, men det værste du kan gøre, ud over at være tavs, skal synligt frustreret. Du ønsker ikke at give det indtryk at en interviewer. En ting, som du - så mange mennesker, når de går ind i et interview, de forsøger at forsøge at finde den bedste løsning først, når der virkelig, er der normalt en grelt indlysende løsning. Det kan være langsom, kan det være ineffektiv, men du skal bare oplyse det, bare så du har et udgangspunkt, hvorfra man kan arbejde bedre. Også under henvisning til, at opløsningen er langsom med hensyn til big O tidskompleksitet eller rum kompleksitet, vil vise intervieweren, at du forstår disse spørgsmål, når du skriver kode. Så vær ikke bange for at komme op med den enkleste algoritme 1:e og derefter arbejde bedre derfra. Eventuelle spørgsmål indtil videre? Okay. 

Så lad os dykke ned i vores første problem. "Givet et array af n heltal, skrive en funktion, der blander array på plads, således at alle permutationer af n heltal er lige sandsynlige. " Og antager at du har til rådighed et tilfældigt heltal generator der genererer et helt tal i området fra 0 til I, halvt interval. Skal alle forstår dette spørgsmål? Jeg giver dig en vifte af n heltal, og jeg vil have dig til at blande det. I min mappe, skrev jeg et par programmer til at vise, hvad jeg mener. Jeg har tænkt mig at blande et array af 20 elementer, fra -10 til 9, og jeg vil have dig til at udsende en liste som denne. Så dette er min sorteres inputarrayet, og jeg vil have dig til at blande det. Vi vil gøre det igen. Skal alle forstå spørgsmålet? Okay. Så det er op til dig. Hvad er nogle ideer? Kan du gøre det som n ^ 2, n log n, n? Åben for forslag. Okay. Så en idé, foreslået af Emmy, først beregne et tilfældigt tal, tilfældigt heltal, i området 0-20. Så påtage os vores matrix har en længde på 20. I vores diagram af 20 elementer, dette er vores input array. Og nu, hendes forslag er at skabe et nyt array, så det bliver output array. Og baseret på den jeg vendte tilbage ved rand - så hvis jeg var, lad os sige, 17, kopiere det 17. element i den første stilling. Nu skal vi til at slette - vi er nødt til at flytte alle de elementer, der her over, så vi har en åbning ved enden og ingen huller i midten. Og nu vi gentage processen. Nu skal vi vælge et nyt tilfældigt heltal mellem 0 og 19. Vi har en ny jeg her, og vi kopiere dette element i denne position. Så vi flytter elementer over og vi gentage processen, indtil vi har vores fulde nyt array. Hvad er driftstiden for denne algoritme? Nå, lad os overveje konsekvenserne af dette. Vi er ved at skifte hvert element. Når vi fjerner denne i, er vi flytte alle elementer efter det til venstre. Og det er en O (n) omkostninger for hvad nu hvis vi fjerner det første element? Så for hver udsendelse, fjerner vi - hver fjernelse lider et O (n) operation, og da vi har n flytninger fører dette til et O (n ^ 2) shuffle. Okay. Så god start. God start. 

Et andet forslag er at bruge noget kendt som Knuth shuffle, eller Fisher-Yates shuffle. Og det er faktisk en lineær tid shuffle. Og ideen er meget ens. Igen har vi vores input array, men i stedet for at bruge to arrays for vores input / output, Vi bruger den første del af sættet til at holde styr på vores blandet portion, og vi holder styr, og så må vi overlade resten af ​​vores array til den unshuffled del. Så her er hvad jeg mener. Vi starter med - vi vælger et i, et array 0-20. Vores nuværende pointer peger på den første indeks. Vi vælger nogle jeg her og nu vi bytte. Så hvis dette var 5 og dette var 4, det resulterende array have 5 her og 4 her. Og nu vi konstatere en markør her. Alt til venstre er blandet, og alt til højre er unshuffled. Og nu kan vi gentage processen. Vi vælger et tilfældigt indeks mellem 1 og 20 nu. Så formoder vores nye i er her. Nu skal vi bytte denne i med vores nuværende nye position her. Så vi gør en bytte frem og tilbage på denne måde. Lad mig hente koden for at gøre det mere konkret. Vi starter med vores valg af i - vi starter med i lig med 0, vi vælger en tilfældig placering j i unshuffled del af sættet, at i n-1. Så hvis jeg er her, skal du vælge en tilfældig indeks mellem her og resten af ​​array, og vi bytte. Dette er koden nødvendig for at blande din array. Eventuelle spørgsmål? 

Tja, en nødvendig Spørgsmålet er, hvorfor er dette korrekt? Hvorfor er hver permutation lige sandsynlige? Og jeg vil ikke gå gennem bevis for dette, men mange problemer i datalogi kan bevises ved induktion. Hvor mange af jer er bekendt med induktion? Okay. Cool. Så du kan bevise rigtigheden af ​​denne algoritme ved simpel induktion, hvor din induktion hypotese ville være, antage, at min shuffle returnerer hver permutation lige sandsynlige op til de første Jeg elementer. Nu mener jeg, + 1. Og ved den måde, vi vælger vores indeks j til at bytte, dette fører til - og så skal du finde ud af detaljerne, mindst en hel bevis på, hvorfor denne algoritme returnerer hver permutation med lige sandsynlige sandsynlighed. 

Okay, næste problem. Så "givet et array af heltal, postive, nul, negative, skrive en funktion, der beregner den maksimale sum enhver continueous subarray af inputarrayet. " Et eksempel her er, i det tilfælde, hvor alle tal er positive, så i øjeblikket det bedste valg er at tage hele array. 1, 2, 3, 4, = 10. Når du har nogle negativer derinde, i dette tilfælde vil vi blot de to første fordi du vælger -1 og / eller -3 vil bringe vores sum ned. Nogle gange er vi måske nødt til at starte i midten af ​​array. Nogle gange er vi ønsker at vælge noget som helst, det er bedst ikke at tage noget som helst. Og nogle gange er det bedre at tage skraldet, fordi ting efter det er super stor. Så nogen ideer? (Studerende, uforståelig) >> Ja. Antag jeg ikke tage -1. Så enten jeg vælger 1.000 og 20.000, eller jeg bare vælge den 3 mia. Nå, det bedste valg er at tage alle de tal. Denne -1, til trods for at være negativ, hele summen er bedre end var jeg ikke til at tage -1. Så en af ​​de tips jeg nævnte tidligere var at angive tydeligt indlysende og det brute force løsning først. Hvad er det brute force løsning på dette problem? Ja? [Jane] Tja, jeg tror det brute force løsning ville være at lægge alle de mulige kombinationer (uforståelig). [Yu] Okay. Så Jane idé er at tage alle mulige - Jeg parafraserer - er at tage alle mulige kontinuerlig subarray, beregne sin sum, og derefter tage den største af alle de mulige kontinuerlige subarrays. Hvad entydigt identificerer en subarray i mit input array? Ligesom, hvad to ting skal jeg bruge? Ja? (Studerende, uforståelig) >> Højre. En nedre grænse på indeks og en øvre grænse indeks entydigt bestemmer en kontinuerlig subarray. [Kvinde elev] Er vi anslå at det er en vifte af unikke numre? [Yu] Nej Så hendes spørgsmål er, er vi antager vores array - er vores array alle unikke numre, og svaret er nej. 

Hvis vi bruger vores brute force løsning, så start / slut indekser entydigt bestemmer vores kontinuerlige subarray. Så hvis vi gentage til alle mulige start poster, og for alle endelige indtastninger> eller = for at starte, og <n, du beregne summen, og så må vi tage den maksimale sum, vi har set hidtil. Er det forstået? Hvad er den store O i denne løsning? Tidsmæssigt. Ikke helt n ^ 2. Bemærk, at vi gentage fra 0 til n, så det er en for-løkke. Vi gentage igen fra næsten begyndelsen til enden, en anden for løkke. Og nu, inden det er vi nødt til opsummere hver indrejse, så det er en anden for-løkke. Så vi har tre indlejrede for-løkker, n ^ 3. Okay. Dette går som udgangspunkt. Vores løsning er ikke værre end n ^ 3. Skal alle forstår brute force løsning? 

Okay. En bedre løsning er anvendelse af en idé kaldet dynamisk programmering. Hvis du tager CS124, som er Algoritmer og datastrukturer, vil du blive meget fortrolig med denne teknik. Og ideen er, så prøv at opbygge løsninger til mindre problemer først. Hvad jeg mener med dette er, vi har i øjeblikket at bekymre sig om to ting: start og slut. Og det er irriterende. Hvad hvis vi kunne slippe af med en af ​​disse parametre? En idé er at - vi er klar givet vores oprindelige problem, finde den maksimale sum af en subarray i et interval [O, n-1]. Og nu har vi en ny subproblem, hvor vi ved, i vores nuværende indeks i, Vi ved, at vi må konkludere, at der. Vores subarray skal slutte på det aktuelle indeks. Så tilbageværende problem er, hvor skal vi starte vores subarray? Giver det mening? Okay. Så jeg har kodet det op, og lad os se på, hvad dette betyder. I codirectory, er der et program kaldet subarray, og det tager antal varer, og returnerer den maksimale subarray sum på min blandet liste. Så i dette tilfælde, er vores maksimale subarray 3. Og det har taget ved blot at bruge 2 og 1. Lad os køre den igen. Det er også 3. Men denne gang, bemærke, hvordan vi fik den 3. Vi tog - vi bare tage 3 selv fordi det er omgivet af negativer på begge sider, som vil bringe en sum <3. Lad os køre på 10 punkter. Denne gang er det 7, tager vi den førende 3 og 4. Denne gang er det 8, og vi får at ved at tage 1, 4 og 3. Så for at give dig en intuition om, hvordan vi kan løse dette transformeret problem, lad os tage et kig på denne subarray. Vi er givet dette input array, og vi kender svaret er 8. Vi tager 1, 4, og 3. Men lad os se på, hvordan vi rent faktisk fik det svar. Lad os se på den maksimale subarray, der endte på hvert af disse indeks. Hvad er den maksimale subarray der skal ende i den første position? [Student] Zero. >> Zero. Bare ikke tage -5. Her kommer til at være 0 så godt. Ja? (Studerende, uforståelig) [Yu] Åh, undskyld, det er en -3. Så dette er en 2, er dette en -3. Okay. Så -4, hvad er den maksimale subarray at afslutte denne position hvor -4 er på? Zero. One? 1, 5, 8. Nu må jeg slutte på det sted, hvor -2 er på. Så 6, 5, 7 og den sidste er 4. Vel vidende, at disse er mine poster for den transformerede problem, hvor jeg skal ende på hvert af disse indeks, så mit endelige svar er bare, tage en feje tværs, og tage det maksimale antal. Så i dette tilfælde er det 8. Dette indebærer, at den maksimale subarray slutter ved dette indeks, , og begyndte andet sted før det. Skal alle forstå dette transformeret subarray? 

Okay. Nå, lad os finde ud af gentagelse for dette. Lad os overveje bare de første par poster. Så her var det 0, 0, 0, 1, 5, 8. Og så var der en -2 her, og det bragte det ned til 6. Så hvis jeg kalder indrejse ved position i subproblem (i), hvordan kan jeg bruge svaret til en tidligere subproblem at besvare dette subproblem? Hvis jeg ser på, lad os sige, denne post. Hvordan kan jeg beregne svaret 6 ved at kigge på en kombination af dette array, og svarene på tidligere delproblemer i denne array? Ja? [Kvinde elev] Du tager den vifte af beløb i positionen lige før det, så de 8, og du derefter tilføje den aktuelle subproblem. [Yu] Så hendes forslag er at se på disse to tal, dette nummer og dette nummer. Så dette 8 henviser til svaret for subproblem (i - 1). Og lad os kalde min inputarrayet A. For at finde en maksimal subarray der ender i position i, Jeg har to valgmuligheder: Jeg kan enten fortsætte subarray der endte på det foregående indeks, eller starte et nyt array. Hvis jeg skulle fortsætte den subarray, der startede på det foregående indeks, så den maksimale sum jeg kan opnå, er svaret på det foregående subproblem plus den aktuelle array-post. Men jeg har også valget af at starte en ny subarray, i hvilket tilfælde summen er 0. Så svaret er max på 0, subproblem i - 1, plus den aktuelle array-post. Betyder dette tilbagefald mening? Vores tilbagefald, som vi har lige opdaget, er subproblem i er lig med den maksimale af den tidligere subproblem plus min nuværende array-post, hvilket betyder, fortsætter det forrige subarray, eller 0, starte en ny subarray på min nuværende indeks. Og når vi har opbygget denne tabel af løsninger, så vores endelige svar, bare lave en lineær fejer hen over subproblem-array og tage det maksimale antal. Dette er en nøjagtig gennemførelse af det, jeg lige har sagt. Så vi opretter en ny subproblem array, delproblemer. Den første post er enten 0 eller den første post, det maksimale af de to. Og resten af ​​delproblemer vi bruger den nøjagtige gentagelse vi lige opdaget. Nu skal vi beregne det maksimale af vores delproblemer array, og det er vores endelige svar. 

Så hvor meget plads bruger vi i denne algoritme? Hvis du kun har taget CS50, så skal du måske ikke har diskuteret plads meget. Tja, en ting at bemærke er, at jeg ringede malloc her med størrelsen n. Hvad betyder det foreslå dig? Denne algoritme anvender lineær plads. Kan vi gøre det bedre? Er der noget, du bemærker, at er unødvendigt at beregne det endelige svar? Jeg gætte et bedre spørgsmål er, hvilke oplysninger behøver vi ikke at bære hele vejen igennem til slutningen? Nu, hvis vi ser på disse to linjer, vi kun interesserer os for den tidligere subproblem, og vi kun bekymrer sig om det maksimale, vi nogensinde har set hidtil. For at beregne vores endelige svar, behøver vi ikke hele array. Vi har kun brug for det sidste nummer, sidste to numre. Sidste nummer for subproblem array, og sidste tal for den maksimale. Så faktisk kan vi smelte disse sløjfer sammen og gå fra lineær plads til konstant space. Løbende sum hidtil her, erstatter den rolle subproblem, vores subproblem array. Så aktuelle sum, indtil videre, er svaret på det foregående subproblem. Og dette beløb hidtil træder i stedet for vores max. Vi beregner det maksimale, som vi hen ad vejen. Og så går vi fra lineær plads til konstant rum, og vi har også en lineær løsning på vores subarray problem. 

Disse former for spørgsmål, du får i løbet af et interview. Hvad er den tid kompleksitet, hvad er den plads kompleksitet? Kan du gøre det bedre? Er der ting, der er unødvendige for at holde rundt? Jeg gjorde det for at fremhæve analyser, som du bør tage på egen hånd som du arbejder gennem disse problemer. Altid spørge dig selv, "Kan jeg gøre det bedre?" Faktisk kan vi gøre det bedre end dette? Sorter af et trick spørgsmål. Du kan ikke, fordi du har brug for i det mindste læse indgangen på problemet. Så det faktum, at du skal i det mindste læse input til problemet betyder, at du ikke kan gøre det bedre end den lineære tid, og du kan ikke gøre det bedre end konstant rum. Så dette er faktisk den bedste løsning på dette problem. Spørgsmål? Okay. 

Aktiemarked problem: "Givet et array af n heltal, positive, nul eller negativ, der repræsenterer prisen for en bestand over n dage, skrive en funktion til at beregne den maksimale profit, du kan gøre i betragtning af at du køber og sælger præcis 1 bestand inden for disse n dage. " Grundlæggende ønsker vi at købe lav, sælge højt. Og vi ønsker at finde ud af den bedste resultat, vi kan gøre. Går tilbage til min tip, hvad er det umiddelbart klart, enkleste svar, men det er langsom? Ja? (Studerende, uforståelig) >> Ja. >> Så du vil bare gå selv og se på aktiekurserne ved hvert tidspunkt, (uforståelig). [Yu] Okay, så hendes løsning - hendes forslag om computing den laveste og beregne den højeste fungerer ikke nødvendigvis idet det højeste kan forekomme før det laveste. Så hvad er det brute force løsning på dette problem? Hvad er de to ting, som jeg har brug for at entydigt bestemme den fortjeneste jeg gøre? Right. Den brute force løsning er - åh, ja, George forslag er, at vi kun nødvendigt med to dages til entydigt at fastsætte fortjenesten på disse to dage. Så vi beregne hvert par, gerne købe / sælge, beregne den fortjeneste, som kunne være negativ eller positiv eller nul. Beregn den maksimale profit, at vi gør efter iteration over alle par af dage. Det vil være vores endelige svar. Og denne løsning vil være O (n ^ 2), fordi der er n vælge to par - af dage, som du kan vælge mellem sidste dage. Okay, så jeg har ikke tænkt mig at gå over den brute force løsning her. Jeg har tænkt mig at fortælle dig, at der er en n log n løsning. Hvilken algoritme du i øjeblikket ved, det er n log n? Det er ikke et trick spørgsmål. 

Flet slags. Flet slags er n log n, og faktisk er én måde at løse dette problem at bruge en sammenfletning slags slags idé kaldes, i almindelighed, del og hersk. Og ideen er som følger. Du ønsker at beregne det bedste køb / salg parret i den venstre halvdel. Find det bedste resultat, du kan gøre, bare med den første n over to dage. Så du ønsker at oompute det bedste køb / salg par på den højre halvdel, så den sidste n over to dage. Og nu er spørgsmålet, hvordan kan vi flette disse løsninger sammen igen? Ja? (Studerende, uforståelig) >> Okay. Så lad mig tegne et billede. Ja? (George, uforståelig) >> Præcis. George løsning er den helt rigtige. Så hans forslag er først beregne den bedste køber / sælger par, og der opstår i den venstre halvdel, så lad os kalde det venstre, venstre. Best køber / sælger par, der opstår i den højre halvdel. Men hvis vi kun sammenlignet disse to tal, vi mangler sagen hvor vi køber her og sælge et eller andet sted i højre halvdel. Vi køber i den venstre halvdel, sælge i højre halvdel. Og den bedste måde at beregne den bedste køber / sælger par, der strækker sig over begge halvdele er at beregne den minimale her og beregne den maksimale her og tage deres forskel. Så de to tilfælde, hvor køber / sælger par forekommer kun her, Kun her, eller på begge halvdele defineres af disse tre tal. Så vores algoritme til at fusionere vores løsninger sammen igen, vi ønsker at beregne den bedste køber / sælger par hvor vi køber på venstre halvdel og sælge på den højre halvdel. Og den bedste måde at gøre det er at beregne den laveste pris i første halvår, den højeste pris i den højre halvdel, og tage deres forskel. De resulterende tre overskud, disse tre tal, du tager det maksimale af de tre, og det er det bedste resultat, du kan gøre i løbet af disse første og slutningen dage. Her er det vigtige linjer er i rødt. Dette er et rekursivt kald til beregning svaret i den venstre halvdel. Dette er et rekursivt kald til beregning svaret i den højre halvdel. Disse to for-løkker beregne min og max til venstre og højre halvdel, henholdsvis. Nu vil jeg beregne den fortjeneste, der spænder over begge halvdele, og det endelige svar er maksimum af disse tre. Okay. 

Så sikker, vi har en algoritme, men det større spørgsmål er, hvad er den tid kompleksiteten af ​​dette? Og grunden til, at jeg nævnte merge art er, at denne form for opdele svaret i to og derefter flette vores løsninger sammen igen er præcis den form for fletningen art. Så lad mig gå igennem varighed. Hvis vi defineret en funktion t (n) er antallet af trin for n dage, vores to rekursive kald hver kommer til at koste t (n / 2), og der er to af disse opkald. Nu har jeg brug for at beregne et minimum af den venstre halvdel, som jeg kan gøre i n / 2 gang, plus maksimum for den højre halvdel. Så dette er blot n. Og så plus nogle konstant arbejde. Og denne gentagelse ligning er netop fornyet ligning for sammenfletning slags. Og vi ved alle, at fletningen slags er n log n tid. Derfor er vores algoritme også n log n tid. Betyder dette iteration mening? Blot en kort resumé af dette: T (n) er antallet af trin til at beregne den maksimale profit i løbet af n dage. Den måde vi delt op vores rekursive kald er ved at kalde vores løsning på de første n / 2 dage, så det er et opkald, og så kalder vi igen på den anden halvdel. Så det er to opkald. Og så finder vi en minimum på venstre halvdel, som vi kan gøre i lineær tid, finde maksimum for den højre halvdel, som vi kan gøre i lineær tid. Så n / 2 + n / 2 er blot n. Så vi har nogle konstant arbejde, der er lyst til at gøre matematik. Denne tilbagevenden ligning er netop fornyet ligning for sammenfletning slags. Derfor er vores shuffle algoritme er også n log n. Så hvor meget plads bruger vi? Lad os gå tilbage til koden. 

Et bedre spørgsmål er, hvor mange stakrammer vi nogensinde har på et givet tidspunkt? Da vi bruger rekursion, antallet af stakrammer bestemmer vores pladsudnyttelsen. Lad os overveje n = 8. Vi kalder shuffle på 8, som vil kalde shuffle på de første fire poster, som vil kalde en shuffle på de første to poster. Så vores stack er - det er vores stack. Og så kalder vi shuffle igen på 1, og det er hvad vores base case er, så vi vender tilbage med det samme. Har vi nogensinde har mere end så mange stakrammer? Nej Fordi hver gang vi gør en besværgelse, en rekursiv påkaldelse til shuffle, vi deler vores størrelse i halve. Så det maksimale antal stakrammer vi nogensinde har på et givet tidspunkt er på rækkefølgen af ​​logn stak frames. Hver stabel ramme har konstant rum, og derfor den totale mængde plads, den maksimale mængde plads, vi nogensinde bruge, er O (log n) plads hvor n er antallet af dage. 

Nu, altid spørge dig selv, "Kan vi gøre det bedre?" Og i særdeleshed, kan vi reducere dette til et problem, vi allerede har løst? Et vink: vi kun drøftet to andre problemer, før dette, og det kommer ikke til at være shuffle. Vi kan konvertere dette aktiemarkedet problem i den maksimale subarray problem. Hvordan kan vi gøre det? En af jer? Emmy? (Emmy, uforståelig) [Yu] Præcis. Så den maksimale subarray problem, vi leder efter en sum over en kontinuerlig subarray. Og Emmy forslag til bestande problem, overveje de ændringer, eller deltaer. Og et billede af dette er - det er prisen for en aktie, men hvis vi tog forskellen mellem hver dag i træk - så ser vi, at den maksimale pris, maksimal profit vi kunne gøre er, hvis vi køber her og sælge her. Men lad os se på den kontinuerlige - lad os se på det subarray problem. Så her kan vi gøre - gå herfra til her, vi har en positiv forandring, og derefter gå herfra til her har vi en negativ ændring. Men så, går herfra til her har vi en enorm positiv forandring. Og det er disse ændringer, som vi ønsker at opsummere for at få vores endelige resultat. Så har vi mere negative ændringer her. Nøglen til at reducere vores lager problem i vores maksimale subarray problem er at overveje de deltaer mellem dage. Så vi skaber et nyt array kaldet deltaer, initialisere den første indgang til at være 0, og derefter for hver delta (i), lad det være forskellen min inputarrayet (i) og matrix (i - 1). Så vi kalder vores rutine procedure for en maksimal subarray passerer i en delta s array. Og fordi maksimal subarray er lineær tid, og denne reduktion er denne proces med at skabe denne delta array, er også lineær tid, så den endelige løsning for bestande er O (n) arbejde plus O (n) arbejde, er stadig O (n) arbejde. Så vi har en lineær tid løsning på vores problem. Skal alle forstå denne transformation? 

I almindelighed, en god idé, at du altid skal have er at forsøge at reducere et nyt problem, du ser. Hvis det virker bekendt for et gammelt problem, Prøv at reducere den til et gammelt problem. Og hvis du kan bruge alle de værktøjer, du har brugt på den gamle problem at løse det nye problem. Så for at indpakke er tekniske interviews udfordrende. Disse problemer er sandsynligvis nogle af de mere vanskelige problemer at du kan se i et interview, så hvis du ikke forstår alle de problemer, som jeg lige er dækket, det er okay. Disse er nogle af de mere udfordrende problemer. Praksis, praksis, praksis. Jeg gav en masse problemer i handout, så helt sikkert tjekke dem ud. Og held og lykke på dine interviews. Alle mine ressourcer er udstationeret på dette link, og en af ​​mine ældre venner har tilbudt at gøre mock tekniske interviews, så hvis du er interesseret, e-mail vil Yao på denne e-mail-adresse. Hvis du har nogle spørgsmål, kan du spørge mig. Tror du fyre har særlige spørgsmål vedrørende tekniske interviews eller eventuelle problemer, vi har set indtil videre? Okay. Held og lykke på dine interviews. [CS50.TV]