[Powered by Google Translate] [Seminarium: Tekniska Intervjuer] [Kenny Yu, Harvard University] [Detta är CS50.] [CS50.TV] Hej alla, jag Kenny. Jag är för närvarande en junior studerar datavetenskap. Jag är en före detta CS TF, och jag önskar att jag hade det när jag var underclassman, och det är därför jag ger detta seminarium. Så jag hoppas att ni uppskattar det. Seminariet handlar om tekniska intervjuer, och alla mina resurser kan hittas på den här länken, den här länken här, ett par resurser. Så jag gjorde en lista över problem, faktiskt, en hel del problem. Också en generell resurser där vi kan hitta tips om hur man förbereder för en intervju, tips om vad du ska göra under en verklig intervju, liksom hur man skall närma problem och resurser för framtida referens. Det är allt på nätet. Och bara för att inleda seminariet en ansvarsfriskrivning, så här ska inte - din intervju förberedelse bör inte begränsas till denna lista. Detta är bara tänkt att vara en guide, och du bör definitivt ta allt jag säger med en nypa salt, men även använda allt jag använde för att hjälpa dig i din intervju förberedelse. 

Jag ska skynda igenom de närmaste bilder så vi kan få de faktiska fallstudier. Strukturen för en intervju för en software engineering fältbrytning, typiskt är det 30 till 45 minuter, flera omgångar, beroende på företaget. Ofta du kommer att kodning på en whiteboard. Så en whiteboard som denna, men ofta i mindre skala. Om du har en telefon intervju, kommer du antagligen att använda antingen collabedit eller en Google Doc, så att de kan se du bor kodning medan du intervjuas över telefon. En intervju själv är typiskt 2 eller 3 problem testa dina kunskaper datavetenskap. Och det kommer nästan definitivt innebära kodning. De typer av frågor som du ser är oftast datastrukturer och algoritmer. Och att göra den här typen av problem, De kommer att fråga dig, liksom, är vad tid och rum komplexitet, Big O? Ofta också be högre nivå frågor, så utforma ett system, hur skulle du lägga ut din kod? Vilka gränssnitt, vilka klasser, vad moduler du har i ditt system, och hur dessa interagerar med varandra? Så datastrukturer och algoritmer samt utforma system. 

Några allmänna tips innan vi dyker in i våra fallstudier. Jag tror att den viktigaste regeln alltid tänka högt. Intervjun är tänkt att vara din chans att visa upp din tankeprocess. Poängen med intervjun är att intervjuaren att bedöma hur du tänker och hur du går igenom ett problem. Det värsta du kan göra är att vara tyst under hela intervjun. Det är bara inte bra. När du får en fråga, vill du också se till att du förstår frågan. Så upprepa frågan tillbaka med egna ord och försök att arbeta grundligt några enkla testfall se till att du förstår frågan. Arbeta igenom några testfall kan också ge dig en intuition om hur man kan lösa detta problem. Du kan även upptäcka några mönster för att hjälpa dig att lösa problemet. Deras stora tips är att inte bli frustrerad. Bli inte frustrerad. Intervjuer är utmanande, men det värsta du kan göra, förutom att vara tyst, är att vara synligt frustrerad. Du vill inte ge det intrycket att en intervjuare. En sak som du - så många människor, när de går in i en intervju, de försöker att försöka hitta den bästa lösningen först, när det verkligen, det finns oftast en alldeles uppenbart lösning. Det kan vara långsam, kan det vara ineffektivt, men du bör bara ange det, bara så att du har en utgångspunkt för att fungera bättre. Dessutom pekar ut lösningen är långsam, i termer av Big O tid komplexitet eller utrymme komplexitet, kommer att visa att intervjuaren att du förstår dessa frågor när du skriver kod. Så var inte rädd att komma med den enklaste algoritmen 1. och sedan arbeta bättre därifrån. Eventuella frågor hittills? Okej. 

Så låt oss dyka in vår första problemet. "Givet en rad n heltal, skriva en funktion som blandar arrayen på plats så att alla permutationer av de n heltalen är lika sannolika. " Och antar att du har tillgång till en slumpmässigt heltal generator som genererar ett heltal inom ett intervall från 0 till i, halv intervall. Förstår alla denna fråga? Jag ger dig en rad n heltal, och jag vill att du blanda det. I min katalog, skrev jag några program att visa vad jag menar. Jag ska blanda en mängd 20 element, från -10 till +9, och jag vill att du ska mata en lista som denna. Så det här är min sorterade inputuppställningen, och jag vill att du ska blanda det. Vi ska göra det igen. Förstår alla frågan? Okej. Så det är upp till dig. Vad är några idéer? Kan du göra det som n ^ 2, n log n, n? Öppen för förslag. Okej. Så en idé, som föreslagits av Emmy, först beräkna ett slumptal, slumpmässigt heltal, i ett område från 0 till 20. Så antar vår grupp har en längd av 20. I vår diagram av 20 element, Detta är vårt bidrag array. Och nu är hennes förslag att skapa en ny array, så kommer detta att vara den utgående matrisen. Och baseras på den jag återvände från rand - så om jag var, låt oss säga, 17, kopiera den 17 elementet i det första läget. Nu måste vi ta bort - vi måste flytta alla element här över så att vi har en lucka i slutet och inga hål i mitten. Och nu har vi upprepa processen. Nu väljer vi en ny slumpmässigt heltal mellan 0 och 19. Vi har en ny jag här, och vi kopierar detta element i denna position. Då vi flytta objekt över och vi upprepar processen tills vi har vår fulla ny array. Vad är körtiden för denna algoritm? Nåväl, låt oss betrakta effekterna av detta. Vi skiftar varje element. När vi tar bort detta jag, vi flytta alla element efter det till vänster. Och det är en O (n) kostnad eftersom vad händer om vi tar bort det första elementet? Så för varje uttag, tar vi bort - varje uttag medför en O (n) drift, och eftersom vi har n flyttning leder detta till en O (n ^ 2) shuffle. Okej. Så bra start. Bra start. 

Ett annat förslag är att använda något som kallas Knuth shuffle, eller Fisher-Yates shuffle. Och det är faktiskt en linjär tid shuffle. Och tanken är mycket lika. Återigen har vi vår inputuppställningen, men i stället för att använda två uppsättningar för vår ingång / utgång, vi använder den första delen av matrisen för att hålla reda på vår skyfflade del, och vi håller koll, och då lämnar vi resten av vår grupp för unshuffled delen. Så här är vad jag menar. Vi börjar med - vi väljer en i, en array från 0 till 20. Vår nuvarande pekare pekar på första indexet. Vi väljer några jag här och nu har vi byter. Så om detta var 5 och detta var 4, den resulterande matrisen har 5 här och 4 här. Och nu har vi notera en markör här. Allt till vänster är blandade, och allt till höger unshuffled. Och nu kan vi upprepa processen. Vi väljer en slumpmässig index mellan 1 och 20 nu. Så antar vår nya jag är här. Nu har vi byta detta jag med vår nuvarande ny position här. Så vi en byta fram och tillbaka så här. Låt mig ta upp koden för att göra det mer konkret. Vi börjar med vårt val av i - vi börjar med i lika med 0, plocka vi ett slumpmässigt läge j i unshuffled delen av matrisen, till i n-1. Så om jag är här, välj en slumpmässig index mellan här och resten av arrayen, och vi byter. Detta är koden som krävs för att blanda din array. Några frågor? 

Tja, en behövde fråga, varför är detta korrekt? Varför är varje permutation lika troligt? Och jag kommer inte att gå igenom bevis på detta, men många problem i datavetenskap kan bevisas genom induktion. Hur många av er känner till induktion? Okej. Cool. Så du kan bevisa riktigheten av denna algoritm genom enkel induktion, där din induktion hypotes skulle vara, antar att min Shuffle tillbaka varje permutation lika sannolika upp till det första jag elementen. Nu anser jag + 1. Och genom det sätt vi väljer vårt index j för att byta, detta leder till - och sedan utarbeta detaljerna, åtminstone en fullt bevis för varför detta Algoritmen återgår Varje permutation med lika sannolika sannolikhet. 

Okej, nästa problem. Så "ges en rad av heltal, positiv, noll, negativ, skriva en funktion som beräknar den maximala summan varje continueous subanordningen av inputuppställningen. " Ett exempel här är, i det fall där alla siffror är positiva, då närvarande det bästa valet är att ta hela uppsättningen. 1, 2, 3, 4, är lika med 10. När du har vissa negativa där, I det här fallet vill vi bara de två första eftersom valet -1 och / eller -3 kommer att föra vår summa ner. Ibland har vi kanske måste starta i mitten av fältet. Ibland vill vi välja någonting alls, det är bäst att inte ta något. Och ibland är det bättre att ta fallet, eftersom sak efter det är super stort. Så några idéer? (Elev, obegripligt) >> Ja. Anta att jag inte tar -1. Sedan antingen väljer jag 1.000 och 20.000, eller jag väljer bara 3 miljarder. Tja, är det bästa valet för att ta alla nummer. Detta -1, trots att negativ, hela summan är bättre än var jag inte ta -1. Så en av de tips jag nämnde tidigare var att ange tydligt uppenbara och den brute force lösningen först. Vilken är den brute force lösningen i detta problem? Ja? [Jane] Jag tror det brute force lösningen skulle vara att lägga upp alla möjliga kombinationer (obegripliga). [Yu] Okej. Så Jane idé är att ta alla möjliga - Jag är parafras - är att ta alla möjliga kontinuerlig subsystemet, beräkna sin summa, och sedan ta högst alla möjliga kontinuerliga subanordningar. Vad identifierar en subarray i min inputuppställningen? Liksom, vad två saker behöver jag? Ja? (Elev, obegripligt) >> höger. En lägre gräns för index och en övre gräns index unikt bestämmer en kontinuerlig undersystem. [Kvinnlig student] Är vi uppskatta att det är en rad unika nummer? [Yu] Nej Så hennes fråga, vi antar vår array - är vår matris alla unika nummer, och svaret är nej. 

Om vi ​​använder vår brute force-lösning, då start / slut index unikt avgör vår ständiga subsystemet. Så om vi upprepa för alla möjliga start poster, och för alla slut poster> eller = för att starta, och <n, du beräkna summan, och sedan tar vi det högsta belopp vi har sett hittills. Är det klart? Vad är den stora O av denna lösning? Tidsmässigt. Inte helt n ^ 2. Notera att vi itererar från 0 till n, så det är en för slinga. Vi iterera igen från nästan början till slut, en annan för slinga. Och nu, inom denna måste vi summera varje post, så det är en annan för slinga. Så vi har tre nästlade loopar, n ^ 3. Okej. Detta går som en startpunkt. Vår lösning är inte värre än n ^ 3. Förstår alla de brute force lösningen? 

Okej. En bättre lösning är att använda en idé som kallas dynamisk programmering. Om du tar CS124, vilket Algoritmer och datastrukturer, du kommer att bli väl förtrogen med denna teknik. Och tanken är att försöka att bygga upp lösningar till mindre problem först. Vad jag menar med detta är, har vi för närvarande att oroa två saker: start och slut. Och det är irriterande. Tänk om vi kunde bli av med en av dessa parametrar? En idé är att - vi med tanke på vår ursprungliga problemet, hitta den maximala summan av alla subsystemet i intervallet [O, N-1]. Och nu har vi en ny delproblem, där vi vet, i vår nuvarande index i, Vi vet att vi måste sluta där. Vår subarray måste sluta på det aktuella indexet. Så den återstående problemet är, bör där vi börjar vår subarray? Verkar denna mening? Okej. Så jag har kodat upp detta, och låt oss titta på vad detta innebär. I codirectory finns det ett program som heter undersystem, och det tar flera poster, och den returnerar den maximala subarray summan i min blandade lista. Så i detta fall är vår maximala undersystemet 3. Och det har tagit genom att bara använda 2 och 1. Vi kör det igen. Det är också 3. Men den här gången, notera hur vi fick 3. Vi tog - vi bara ta 3 själv eftersom det är omgivet av negativ på båda sidor, vilket kommer att medföra en summa <3. Låt oss köra på 10 punkter. Den här gången är det 7 tar vi den ledande 3 och 4. Den här gången är det 8, och vi får att genom att ta 1, 4 och 3. Så för att ge dig en intuition om hur vi kan lösa detta omvandlas problemet, låt oss ta en titt på denna subarray. Vi ges denna ingång array, och vi vet att svaret är 8. Vi tar 1, 4 och 3. Men låt oss titta på hur vi faktiskt fick det svaret. Låt oss titta på den maximala subarray som slutade på alla dessa index. Vad är den maximala subarray som måste sluta på den första positionen? [Student] Zero. >> Zero. Bara tar inte -5. Här kommer att bli 0 också. Ja? (Elev, obegripligt) [Yu] Åh, förlåt, det är en -3. Så detta är en 2, är detta en -3. Okej. Så -4, vad är den maximala subarray att avsluta den positionen där -4 är? Noll. En? 1, 5, 8. Nu måste jag sluta vid den plats där -2 är. Så 6, 5, 7, och den sista är 4. Att veta att dessa är mina inlägg för den transformerade problemet där jag måste sluta på alla dessa index, då min sista svaret är bara, ta ett svep över, och ta det maximala antalet. Så i det här fallet är det 8. Detta innebär att den maximala subanordningen slutar vid detta index, och började någonstans innan. Förstår alla detta transformerade subarray? 

Okej. Nåväl, låt oss räkna ut återfall för detta. Låt oss betrakta bara de första posterna. Så här var 0, 0, 0, 1, 5, 8. Och då var det en -2 här, och som förde det ner till 6. Så om jag ringer posten i position i delproblem (i), Hur kan jag använda svaret på en tidigare delproblem att besvara denna delproblem? Om jag tittar på, låt oss säga, den här posten. Hur kan jag beräkna svaret 6 genom att titta på en kombination av denna array och svaren på tidigare delproblem i denna array? Ja? [Kvinnlig student] Du tar rad summor i positionen precis innan det, så det 8, och sedan lägga till den aktuella subproblemet. [Yu] Så hennes förslag är att titta på dessa två siffror, detta antal och detta antal. Så detta 8 hänvisar till svaret på subproblemet (i - 1). Och låt oss kalla min A. inputuppställningen För att hitta en maximal undersystem som slutar vid position i, Jag har två val: Jag kan antingen fortsätta subarray som slutade på föregående index, eller starta en ny array. Om jag skulle fortsätta subarray som började i föregående index, då det högsta belopp jag kan uppnå är svaret på den föregående subproblemet plus aktuella arrayen posten. Men har jag också valet att starta ett nytt undersystem, i vilket fall summan är 0. Så svaret är max 0, delproblem i - 1, plus den aktuella matrisen posten. Gör denna återkommande mening? Vår återkommande, som vi just upptäckt är delproblem i är lika med den högsta av föregående subproblemet plus min nuvarande uppsättning inträde, vilket betyder att fortsätta den tidigare subsystemet, eller 0, starta en ny undergrupp på min nuvarande index. Och när vi byggt upp denna tabell av lösningar, då vårt slutgiltiga svar, bara göra en linjär sveper över subproblemet array och ta det maximala antalet. Detta är en exakt tillämpning av det jag just sa. Så vi skapar en ny delproblem array, delproblem. Den första posten är antingen 0 eller den första posten, den högsta av dessa två. Och för resten av delproblem Vi använder exakt upprepning vi just upptäckt. Nu har vi beräkna maximalt våra delproblem array, och det är vårt slutgiltiga svar. 

Så hur mycket utrymme vi använder i denna algoritm? Om du bara har tagit CS50, då du kanske inte har diskuterat utrymme mycket. Tja, är en sak att konstatera att jag ringde malloc här med storlek N. Vad tyder på att för dig? Denna algoritm använder linjär utrymme. Kan vi göra bättre? Finns det något som du märker att är onödigt att beräkna det slutliga svaret? Jag antar att en bättre fråga är, vilken information behöver vi inte bära hela vägen till slutet? Om vi ​​nu tittar på dessa två linjer, Vi bryr sig bara om den tidigare subproblemet, och vi bryr sig bara om det maximala som vi någonsin har sett hittills. För att beräkna vårt slutgiltiga svar, behöver vi inte hela uppsättningen. Vi behöver bara den sista siffran två sista siffrorna. Senaste numret för subproblemet array, och sista numret för maximal. Så i själva verket kan vi smälta dessa slingor tillsammans och gå från linjär utrymme till konstant utrymme. Aktuell summa hittills, här ersätter roll subproblemet, vår subproblemet array. Så nuvarande summa, hittills, är svaret på den föregående subproblemet. Och den summan hittills ersätter vår max. Vi beräknar den maximala som vi går tillsammans. Och så går vi från linjär utrymme till konstant utrymme, och vi har också en linjär lösning för vår subarray problem. 

Dessa typer av frågor du kommer att få under en intervju. Vad är klockan komplexitet, vad är det utrymme komplexitet? Kan du göra det bättre? Finns det saker som är onödigt att hålla runt? Jag gjorde detta för att markera analyser som du bör ta på egen hand som du går igenom dessa problem. Alltid fråga dig själv: "Kan jag göra bättre?" I själva verket kan vi göra bättre än så här? Sortera på en kuggfråga. Du kan inte, eftersom du måste åtminstone läsa ingången till problemet. Så det faktum att du måste åtminstone läsa ingången till problemet innebär att du inte kan göra bättre än linjär tid, och du kan inte göra bättre än konstant utrymme. Så detta är i själva verket den bästa lösningen på detta problem. Frågor? Okej. 

Aktiemarknaden problem: "Givet en rad n heltal, positiv, noll eller negativ, som representerar priset på en aktie under n dagar, skriva en funktion för att beräkna den maximala vinsten du kan göra med tanke på att du köper och säljer exakt 1 lager inom dessa n dag. " I huvudsak vill vi köpa billigt, sälj dyrt. Och vi vill räkna ut det bästa resultatet vi kan göra. Att gå tillbaka till mitt tips, vad är omedelbart klar, enklaste svaret, men det är långsam? Ja? (Elev, obegripligt) >> Ja. >> Så du skulle bara gå igenom och titta på aktiekurserna vid varje tidpunkt, (ohörbart). [Yu] Okej, så hennes lösning - hennes förslag av datorer det lägsta och beräkna den högsta fungerar inte nödvändigtvis eftersom den högsta kan inträffa innan den lägsta. Så vad är brute force lösningen på detta problem? Vilka är de två saker som jag behöver för att unikt fastställa vinsten jag gör? Rätt. Den brute force lösningen är - Åh, så är George förslag vi behöver bara två dagar att entydigt fastställa vinsten på dessa två dagar. Så vi beräkna varje par, vilja köpa / sälja, beräkna den vinst, som kan vara negativt eller positivt eller noll. Beräkna den maximala vinst som vi gör efter iteration över alla par dagar. Det kommer att vara vårt slutgiltiga svar. Och denna lösning blir O (n ^ 2), eftersom det är n välja två par - dagar som du kan välja mellan sista dagarna. Okej, så jag tänker inte gå över brute force lösningen här. Jag ska berätta för er att det finns en n log n-lösning. Vilken algoritm vet du nu det är n log n? Det är inte en kuggfråga. 

Merge sort. Merge Sortera är n log n, och i själva verket är ett sätt att lösa detta problem att använda en sammanslagning slags slags idé som kallas i allmänhet söndra och härska. Och tanken är som följer. Du vill beräkna den bästa köp / sälj par i den vänstra halvan. Hitta det bästa resultatet du kan göra, bara med den första n under två dagar. Då du vill oompute bästa köp / sälj par på den högra halvan, så att den sista n över två dagar. Och nu är frågan, hur ska vi slå ihop dessa lösningar tillsammans igen? Ja? (Elev, obegripligt) >> Okej. Så låt mig rita en bild. Ja? (George, obegripligt) >> Exakt. Georges lösning är exakt rätt. Så hans förslag är först beräkna den bästa köp / sälj-par, och som förekommer i den vänstra halvan, så låt oss kalla det vänster, vänster. Bästa köp / sälj par som sker i den högra halvan. Men om vi bara jämfört dessa två siffror, vi missar målet där vi köper här och säljer någonstans i den högra halvan. Vi köper i den vänstra halvan, sälja i den högra halvan. Och det bästa sättet att beräkna den bästa köp / sälj-par som sträcker sig över båda halvorna är att beräkna det minsta här och beräkna maximala här och ta deras skillnad. Så två fall där köp / sälj par förekommer bara här, bara här, eller på båda halvorna definieras av dessa tre nummer. Så vår algoritm för att slå ihop våra lösningar tillsammans igen, Vi vill beräkna den bästa köp / sälj-par där vi köper på den vänstra halvan och sälja på den högra halvan. Och det bästa sättet att göra det är att beräkna det lägsta priset under första halvåret, det högsta priset i den högra halvan, och ta deras skillnad. De resulterande tre vinster dessa tre siffror, tar du högst tre, och det är det bästa resultatet du kan göra över dessa första och sista dagarna. Här de viktiga linjerna i rött. Detta är ett rekursivt anrop till beräkna svaret i den vänstra halvan. Detta är ett rekursivt anrop till beräkna svaret i den högra halvan. Dessa två för slingor beräkna min och max på vänster och höger halv, respektive. Nu har jag beräkna den vinst som sträcker sig över båda halvorna, och det slutliga svaret är maximalt av dessa tre. Okej. 

Så, visst, vi har en algoritm, men den större frågan är, Vad är klockan komplexiteten i denna? Och anledningen till att jag nämnde merge sort är att denna form av delar svaret i två och sedan slå ihop våra lösningar tillsammans igen är exakt den form av sammanslagning slag. Så låt mig gå igenom varaktighet. Om vi ​​definierat en funktion t (n) vara antalet steg för n dagar, våra två rekursiva anrop vardera kommer att kosta t (n / 2), och det finns två av dessa samtal. Nu måste jag beräkna minimum den vänstra halvan, som jag kan göra i N / 2 tid, plus maximalt den högra halvan. Så detta är bara n. Och sedan plus någon konstant arbete. Och denna återkommande ekvation är exakt upprepning ekvationen för sammanfogningen sorteringen. Och vi vet alla att merge sort är n log n tid. Därför är vår algoritm även n log n tid. Gör denna iteration mening? Bara en kort resumé av detta: T (n) är antalet steg för att beräkna maximal vinst under loppet av n dagar. Det sätt vi dela upp våra rekursiva anrop är genom att ringa vår lösning på de första n / 2 dagar, så det är ett samtal, och då kallar vi igen på den andra halvan. Så det är två samtal. Och då finner vi ett minimum på den vänstra halvan, som vi kan göra i linjär tid, hitta maximalt den högra halvan, som vi kan göra i linjär tid. Så n / 2 + n / 2 är enbart n. Sedan har vi någon konstant arbete, vilket är som att göra aritmetik. Denna återkommande ekvation är exakt upprepning ekvationen för sammanfogningen sorteringen. Därför är vår shuffle algoritm också n log n. Så hur mycket utrymme använder vi? Låt oss gå tillbaka till koden. 

En bättre fråga är, hur många stack ramar vi någonsin vid en given tidpunkt? Eftersom vi använder rekursion, Antalet stack ramar avgör vårt utrymme användning. Låt oss betrakta n = 8. Vi kallar Blandning på 8, som kommer att kräva Blanda de första fyra posterna, som kommer att kräva en shuffle på de första två posterna. Så vår stack är - det är vår stack. Och då kallar vi blanda igen på 1, och det är vad vår bas fall är, så vi omedelbart återvända. Har vi någonsin har mer än så här många stack ramar? Nej Eftersom varje gång vi gör en åkallan, en rekursiv åkallan att blanda, Vi delar vår storlek i halv. Så det maximala antalet stack ramar vi någonsin vid en given tidpunkt är i storleksordningen av log n stack ramar. Varje stapel ram har konstant utrymme, och därför den totala utrymme, det maximala utrymme vi någonsin använder är O (log n) plats där n är antalet dagar. 

Nu, alltid fråga dig själv, "Kan vi göra bättre?" Och i synnerhet, kan vi minska detta ett problem som vi redan har löst? Ett tips: vi bara diskuterat två andra problem inför detta, och det kommer inte att bli shuffle. Vi kan omvandla detta problem aktiemarknaden i den maximala subarray problemet. Hur kan vi göra det? En av er? Emmy? (Emmy, obegripligt) [Yu] Exakt. Så maximala subsystemet problemet, Vi letar efter en summa under en sammanhängande undersystem. Och Emmy förslag för bestånden problemet, överväga förändringar eller deltan. Och en bild av detta är - detta är priset på en aktie, men om vi tog skillnaden mellan varje rad dag - så ser vi att det högsta priset, maximal vinst vi skulle kunna göra är om vi köper här och säljer här. Men låt oss titta på den kontinuerliga - låt oss titta på subarray problemet. Så här kan vi göra - gå härifrån till hit, Vi har en positiv förändring, och sedan gå härifrån till hit har vi en negativ förändring. Men sedan, går härifrån till hit har vi en enorm positiv förändring. Och det är dessa förändringar som vi vill summera för att få vår slutliga resultatet. Sedan har vi mer negativa förändringar här. Nyckeln till att minska vårt lager problem i vår maximala subarray problem är att betrakta deltan mellan dagarna. Så vi skapar en ny array med namnet deltan, initiera den första posten som 0, och sedan för varje delta (i), låt det vara skillnaden min inputuppställningen (i), och matrisen (i - 1). Sedan kallar vi vår rutin för en maximal undersystem passerar i en Deltas array. Och eftersom maximal subarray är linjär tid, och denna minskning, denna process för att skapa denna delta array, är också linjär tid, då den slutliga lösningen för bestånd är O (n) arbete plus O (n) arbete är fortfarande O (n) arbete. Så vi har en linjär tid lösningen på våra problem. Förstår alla denna omvandling? 

I allmänhet en bra idé att du alltid ska ha är att försöka minska ett nytt problem som du ser. Om det ser bekant för ett gammalt problem, försöka reducera den till ett gammalt problem. Och om du kan använda alla de verktyg som du har använt på det gamla problemet att lösa det nya problemet. Så att slå upp, tekniska intervjuer utmanande. Dessa problem är förmodligen några av de svårare problemen som du kan se i en intervju, så om du inte förstår alla de problem som jag just omfattas, det är okej. Dessa är några av de mer utmanande problem. Öva, öva, öva. Jag gav en hel del problem i allmosor, så definitivt kolla dem ut. Och lycka på dina intervjuer. Alla mina resurser publiceras på denna länk, och en av mina äldre vänner har erbjudit sig att göra håna tekniska intervjuer, så om du är intresserad, e-post kommer Yao på den e-postadressen. Om du har några frågor, kan du be mig. Har ni specifika frågor som rör tekniska intervjuer eller problem som vi har sett så här långt? Okej. Lycka på dina intervjuer. [CS50.TV]