[Powered by Google Translate] [Seminar: Technische Interviews]
[Kenny Yu, Harvard University]
[Dit is CS50.] [CS50.TV]
Hallo iedereen, ik ben Kenny. Ik ben momenteel een junior studie informatica.
Ik ben een ex-CS TF, en ik wou dat ik had dit toen ik een Underclassman,
en dat is waarom ik ben van dit seminar.
Dus ik hoop dat je ervan geniet.
Dit seminar gaat over technische interviews,
en al mijn bronnen is te vinden op deze link,
deze link hier, een paar van de middelen.
Dus maakte ik een lijst van problemen, eigenlijk, nogal wat problemen.
Ook een algemene middelen pagina waar we kunnen vinden tips
over het opstellen voor een interview,
tips over wat u moet doen tijdens een echte interview,
alsook hoe je problemen en de middelen voor toekomstige referentie te benaderen.
Het is allemaal online.
En alleen maar om dit seminar, een disclaimer voorwoord,
als dit mag niet - je interview voorbereiding
mag niet worden beperkt tot deze lijst.
Dit is alleen bedoeld om een ​​gids te zijn,
en je moet zeker alles wat ik zeg met een korreltje zout,
maar ook gebruik maken van alles wat ik gebruikt om u te helpen in uw interview voorbereiding.
>> Ik ga om sneller door de volgende paar dia's
zodat we kunnen krijgen om de werkelijke case studies.
De structuur van een interview voor een software engineering positie,
typisch is 30 tot 45 minuten,
meerdere ronden, afhankelijk van het bedrijf.
Vaak zult u codering op een wit bord.
Dus een wit bord als dit, maar vaak op een kleinere schaal.
Als je met een telefonisch interview, zult u waarschijnlijk worden met behulp van
hetzij collabedit of een Google Doc, zodat ze kunnen zien live coding
terwijl je wordt geïnterviewd over de telefoon.
Een interview zelf is meestal 2 of 3 problemen
het testen van uw informatica kennis.
En het zal bijna zeker te coderen.
De aard van de vragen die u zult zien zijn meestal data structuren en algoritmen.
En in het doen van dit soort problemen,
ze zullen je vragen wilt,, wat is de tijd en ruimte complexiteit, grote O?
Vaak zijn ze ook vragen een hoger niveau vragen,
dus om een ​​systeem,
hoe zou u de lay-out uw code?
Wat interfaces, welke klassen, welke modules heb je in je systeem,
en hoe deze op elkaar inwerken bij elkaar?
Dus datastructuren en algoritmen, alsmede het ontwerpen van systemen.
>> Enkele algemene tips voordat we duiken in onze case studies.
Ik denk dat de belangrijkste regel is altijd denken hardop.
Het interview wordt verondersteld om uw kans om te pronken met uw denkproces zijn.
Het punt van het interview is voor de interviewer te peilen naar
hoe je denkt en hoe je door een probleem.
Het ergste wat je kunt doen is stil zijn gedurende het hele interview.
Dat is gewoon niet goed.
Wanneer u een vraag gegeven, kunt u ook willen ervoor zorgen dat u inzicht in de vraag.
Dus terug de vraag herhalen in uw eigen woorden
en proberen om grondig een paar eenvoudige test cases te werken
om ervoor te zorgen u inzicht in de vraag.
Werken door middel van een enkele test cases zal u ook een intuïtie over hoe dit probleem op te lossen.
Je zou zelfs kunnen ontdekken een paar patronen om u te helpen oplossen van het probleem.
Hun grote tip is om niet gefrustreerd.
Raak niet gefrustreerd.
Interviews zijn uitdagend, maar het ergste wat je kunt doen,
Naast zwijgen, is zichtbaar gefrustreerd.
Je wilt niet die indruk te geven aan een interviewer.
Een ding dat je - zo, veel mensen, wanneer ze gaan in een interview,
ze proberen om te proberen de beste oplossing eerst vinden,
terwijl het in feite, is er meestal een overduidelijk oplossing.
Het is misschien traag, is het misschien inefficiënt, maar je moet gewoon zeggen dat,
gewoon zo heb je een startpunt van waaruit beter te werken.
Ook wijzen de oplossing langzaam qua
big O tijd complexiteit of ruimte complexiteit,
zal tonen aan de interviewer dat u begrijpt
deze problemen bij het schrijven van code.
Dus niet eerst bang om te komen met de meest eenvoudige algoritme
en dan beter werken vanaf daar.
Eventuele vragen tot nu toe? Oke.
>> Dus laten we een duik nemen in ons eerste probleem.
"Bij een array van n gehele getallen, schrijf een functie die de array schudt
in plaats zodat alle permutaties van de n gehele getallen gelijkelijk waarschijnlijk. "
En neem aan dat je beschikken over een willekeurig geheel getal generator
dat genereert een geheel getal in een bereik van 0 tot i, half bereik.
Heeft iedereen begrijpt deze vraag?
Ik geef je een array van n gehele getallen, en ik wil dat je shuffle het.
In mijn map, schreef ik een paar programma's om te laten zien wat ik bedoel.
Ik ga shuffle een array van 20 elementen,
-10 tot 9,
en ik wil dat je een lijst als deze uit te voeren.
Dus dit is mijn gesorteerd input array, en ik wil dat je shuffle het.
We zullen nog een keer doen.
Heeft iedereen begrijpen van de vraag? Oke.
Dus het is aan jou.
Wat zijn sommige ideeën? Kun je het als n ^ 2, n log n, n?
Open voor suggesties.
Oke. Dus een idee, voorgesteld door Emmy,
is eerst een willekeurig getal willekeurig getal in een bereik berekenen 0 tot 20.
Zo nemen onze matrix heeft een lengte van 20.
In onze diagram van 20 elementen,
dit is onze input array.
En nu, haar suggestie is het creëren van een nieuwe array,
dus de uitgang array.
En gebaseerd op de i geretourneerd rand -
dus als ik was, laten we zeggen, 17,
kopieer 17e element in de eerste positie.
Nu moeten we verwijderen - we moeten hier verschuiven alle elementen
om, zodat we een gat aan het einde en geen gaten in het midden hebben.
En nu we het proces herhalen.
Nu kiezen we een nieuw willekeurig geheel getal tussen 0 en 19.
We hebben een nieuwe i hier, en we kopiëren dit element in deze positie.
Dan hebben we verschuiven artikelen over en herhalen we het proces tot we onze volledige nieuwe array.
Wat is de looptijd van dit algoritme?
Nou, laten we eens kijken naar de impact van deze.
We verschuiven elk element.
Als we dit verwijderen i, zijn we verschuiven alle elementen na naar links.
En dat is een O (n) kosten
want wat als we het eerste element te verwijderen?
Dus voor elke verwijdering, verwijderen we -
elke verwijdering loopt een O (n) operatie,
en aangezien we hebben n verhuizingen, leidt dit tot een O (n ^ 2) shuffle.
Oke. Zo goed begin. Goede start.
>> Een andere suggestie is het gebruik van iets dat bekend staat als de Knuth shuffle,
of de Fisher-Yates shuffle.
En het is eigenlijk een lineaire tijd shuffle.
Het idee is zeer vergelijkbaar.
Nogmaals, we hebben onze input array,
maar in plaats van met behulp van twee arrays voor onze input / output,
we het eerste gedeelte van de matrix te houden van onze geschud gedeelte,
en we houden, en dan gaan we de rest van ons aanbod te laten voor de unshuffled gedeelte.
Dus hier is wat ik bedoel. We beginnen met - we kiezen een i,
een array van 0 tot 20.
Onze huidige pointer wijst naar de eerste index.
We kiezen een aantal i hier
en nu zijn we ruilen.
Als dit 5 en dit was 4,
de resulterende array zal hier hebben 5 hier en 4.
En nu zien we een marker hier.
Alles wat naar links wordt geschud,
en alles aan de rechterkant wordt unshuffled.
En nu kunnen we het proces herhalen.
We kiezen een willekeurige index tussen 1 en 20 nu.
Dus stel onze nieuwe i is hier.
Nu we dit ik hier wisselen met onze huidige nieuwe positie.
Dus we een ruilen heen en weer als deze.
Laat me brengen de code om het meer concreet.
We beginnen met onze keuze van i -
we beginnen met i gelijk is aan 0, kiezen we een willekeurige locatie j
in de unshuffled gedeelte van de matrix, om i n-1.
Dus als ik hier ben, kies dan een willekeurige index tussen hier en de rest van de array,
en we wisselen.
Dit is allemaal de code die nodig is om shuffle uw array.
Nog vragen?
>> Nou ja, een nodig vraag is, waarom is dit juist?
Waarom is elke permutatie even waarschijnlijk?
En ik zal niet gaan door het bewijs van deze,
maar veel problemen in de informatica kan worden aangetoond door middel van inductie.
Hoeveel van u bekend bent met inductie?
Oke. Cool.
Dus je kunt bewijzen dat de correctheid van dit algoritme door eenvoudige inductie,
waar uw inductiehypothese zou zijn, gaan ervan uit dat
mijn shuffle weer elke permutatie even waarschijnlijk
tot de eerste elementen i.
Nu, overweeg dan i + 1.
En door de manier waarop we kiezen onze index j om te ruilen,
dit leidt tot - en dan werk je de details,
ten minste een volledig bewijs van waarom dit algoritme terug
elke permutatie met even waarschijnlijk waarschijnlijkheid.
>> Oke, volgende probleem.
Dus "gegeven een array van integers, postive, nul, negatief,
schrijf een functie die het maximale bedrag berekent
van elke continueous subarray van de input array. "
Een voorbeeld is, in het geval waarin alle getallen positief,
dan is op dit moment de beste keuze is om de hele reeks.
1, 2, 3, 4, gelijk aan 10.
Wanneer u een aantal negatieven hebben daar,
in dit geval willen we gewoon de eerste twee
omdat het kiezen van -1 en / of -3 brengt ons som naar beneden.
Soms we zouden moeten beginnen in het midden van de array.
Soms willen we helemaal niets te kiezen, het is het beste om niets nemen.
En soms is het beter om de val,
omdat de zaak nadat het is super groot. Dus even welke ideeën?
(Student, onverstaanbaar) >> Ja.
Stel dat ik niet -1 nemen.
Dan ofwel kies ik 1.000 en 20.000,
of ik gewoon kiezen voor de 3 miljard.
Nou, de beste keuze is om alle nummers.
Dit -1, ondanks het feit dat negatieve,
de gehele som is beter dan I waren niet op -1 nemen.
Dus een van de tips die ik eerder noemde was de duidelijk moge duidelijk zijn
en de brute kracht oplossing eerst.
Wat is de brute kracht oplossing in dit probleem? Ja?
[Jane] Nou, ik denk dat de brute kracht oplossing
zou zijn om toe te voegen op alle mogelijke combinaties (onverstaanbaar).
[Yu] Oke. Dus Jane's idee is om alle mogelijke -
Ik ben parafraseren - is het nemen van alle mogelijke continue subarray,
berekenen de som, en neem dan het maximum van alle mogelijke continue subarrays.
Wat een unieke identificatie van een subarray in mijn input array?
Zoals, wat twee dingen heb ik nodig? Ja?
(Student, onverstaanbaar) >> Juist.
Een ondergrens op de index en een bovengrens index
unieke bepaalt een continue subarray.
[Vrouwelijke student] Zijn we schatten dat het een serie van unieke nummers?
[Yu] Nee Dus haar vraag is, gaan we uit van ons aanbod -
is ons aanbod alle unieke nummers, en het antwoord is nee.
>> Als we gebruik maken van onze brute kracht oplossing, dan is de start / eind indices
unieke bepaalt onze continue subarray.
Dus als we bovenstaande bewerking voor alle mogelijke start inzendingen,
en voor alle eind inzendingen> of = om te beginnen, en <n,
berekent u de som, en dan nemen we de maximale som die we tot nu toe hebben gezien.
Is dit duidelijk?
Wat is de big O van deze oplossing?
Timewise.
Niet helemaal n ^ 2.
Merk op dat we herhalen van 0 tot n,
dus dat is een for-lus.
We herhalen nogmaals van bijna het begin tot het einde, een ander for-lus.
En nu, binnen die moeten we vatten elk item,
dus dat is een ander for-lus. Dus we hebben drie geneste for-lussen, n ^ 3.
Oke. Dit gaat als uitgangspunt.
Onze oplossing is niet slechter dan n ^ 3.
Heeft iedereen begrijpen van de brute kracht oplossing?
>> Oke. Een betere oplossing is het gebruik van een idee genaamd dynamisch programmeren.
Als u CS124, dat is Algoritmen en datastructuren,
word je zeer vertrouwd met deze techniek.
En het idee is, proberen op te bouwen oplossingen voor kleinere problemen eerst.
Wat ik bedoel is, dat we op dit moment zorgen te maken over twee dingen: begin en einde.
En dat is vervelend. Wat als we konden ontdoen van een van deze parameters?
Een idee is om - we gezien onze oorspronkelijke probleem,
vindt de maximale som van elke subarray tussen [O, n-1].
En nu hebben we een nieuw deelprobleem, waar we weten, in onze huidige index i,
we weten dat we moeten daar af te sluiten. Onze subarray moet eindigen aan de huidige index.
Dus het resterende probleem is, moeten waar we beginnen onze subarray?
Is dit logisch? Oke.
Dus ik heb gecodeerd dit op, en laten we eens kijken naar wat dit betekent.
In de codirectory, is er een programma genaamd subarray,
en het duurt aantal items,
en geeft hij de maximale subarray bedrag in mijn geschud lijst.
Dus in dit geval maximaal onze subarray 3.
En dat is genomen door gewoon met behulp van 2 en 1.
Laten we het opnieuw draaien. Het is ook 3.
Maar deze keer, let op hoe we de 3 kregen.
We namen de - we gewoon de 3 zelf
omdat het is omgeven door de negatieven aan beide zijden,
die een bedrag brengen <3.
Laten we draaien op 10 items.
Deze keer is het 7, nemen we de leidende 3 en 4.
Deze keer is 8 en we dat verkrijgen door 1, 4 en 3.
Dus om u een idee te geven over hoe we dit oplossen getransformeerd probleem,
laten we eens een kijkje op deze subarray.
We krijgen deze input array, en we weten dat het antwoord is 8.
We nemen de 1, 4, en 3.
Maar laten we eens kijken hoe we kregen eigenlijk dat antwoord.
Laten we eens kijken naar de maximale subarray die eindigde op elk van deze indices.
Wat is de maximale subarray die moet eindigen bij de eerste positie?
[Student] Zero. >> Zero. Gewoon niet nemen de -5.
Hier gaat worden 0 ook. Ja?
(Student, onverstaanbaar)
[Yu] Oh, sorry, het is een -3.
Dit is dus een 2, dit is een -3.
Oke. Dus -4, wat is de maximale subarray om die positie te beëindigen
waar -4 is op? Zero.
Een? 1, 5, 8.
Nu moet ik eindigen op de plaats waar -2 is op.
Dus 6, 5, 7 en de laatste 4.
Wetende dat dit zijn mijn gegevens
voor de getransformeerde probleem waar ik moet eindigen bij elk van deze indices,
dan is mijn definitieve antwoord is gewoon, neem een ​​sweep over,
en neem het maximale aantal.
Dus in dit geval is het 8.
Dit betekent dat de maximale subarray eindigt deze index,
en begon ergens voordat het.
Heeft iedereen dit begrijpen getransformeerd subarray?
>> Oke. Nou, laten we erachter te komen de herhaling voor.
Laten we eens kijken naar de eerste paar inzendingen.
Hier was 0, 0, 0, 1, 5, 8.
En dan was er een -2 hier, en dat bracht het naar beneden tot 6.
Dus als ik de ingang op positie i deelprobleem (i),
hoe kan ik het antwoord gebruiken om een ​​vorige deelprobleem
dit deelprobleem beantwoorden?
Als ik kijk naar, laten we zeggen, dit bericht.
Hoe kan ik het antwoord 6 berekenen door te kijken naar
een combinatie van deze array en de antwoorden op eerdere deelproblemen in deze array? Ja?
[Vrouwelijke student] Je neemt de array van bedragen
in de positie vlak voor, dus de 8,
en dan voegt u de huidige deelprobleem.
[Yu] Dus haar suggestie is om te kijken naar deze twee getallen,
dit aantal en dit aantal.
Dus 8 de antwoord voor de deelprobleem (i - 1).
En laten we mijn input array A.
Om een ​​maximale subarray die eindigt op positie i vinden,
Ik heb twee keuzes: ik kan doorgaan met de subarray
dat eindigde bij de vorige index, of start een nieuwe array.
Als ik de subarray die begon bij de vorige index blijven,
dan het maximale bedrag kan ik bereiken is het antwoord op de vorige deelprobleem
plus de huidige array invoer.
Maar, ik heb ook de keuze van het starten van een nieuwe subarray,
in welk geval de som is 0.
Dus het antwoord is max van 0, deelprobleem i - 1, plus de huidige array invoer.
Betekent dit herhaling zinvol?
Onze herhaling, zoals we net ontdekt, is deelprobleem i
is gelijk aan het maximum van de voorgaande deelprobleem plus mijn huidige array vermelding
waardoor verder de vorige subarray,
of 0, start een nieuwe subarray bij mijn huidige index.
En als we eenmaal hebben opgebouwd deze tafel van oplossingen, dan is onze definitieve antwoord,
gewoon een lineaire sweep over het deelprobleem reeks
en neem het maximale aantal.
Dit is een exacte uitvoering van wat ik net zei.
Dus maken we een nieuwe deelprobleem array deelproblemen.
De eerste regel is 0 of de eerste invoer, het maximum van deze twee.
En voor de rest van de deelproblemen
gebruiken we de exacte herhaling we net ontdekt.
Nu berekenen we het maximum van onze deelproblemen array, en dat is onze uiteindelijke antwoord.
>> Dus hoeveel ruimte gebruiken we in dit algoritme?
Als je alleen genomen CS50, dan heb je misschien nog niet besproken ruimte heel veel.
Nou, een ding om op te merken is dat ik de naam hier malloc met grootte n.
Wat betekent die suggereren voor u?
Dit algoritme lineaire ruimte.
Kan er beter?
Is er iets dat je merkt dat niet nodig is om het definitieve antwoord te berekenen?
Ik denk dat een betere vraag is, welke informatie
hoeven we niet de hele weg te dragen tot het einde?
Nu, als we kijken naar deze twee lijnen,
we alleen de zorg over de vorige deelprobleem,
en we alleen de zorg over het maximale wat we ooit hebben gezien tot nu toe.
Om onze uiteindelijke antwoord te berekenen, hoeven we niet de hele array.
We hebben alleen het laatste nummer, laatste twee getallen.
Laatste nummer voor de deelprobleem array en laatste nummer voor het maximum.
Dus, in feite, kunnen we samensmelten deze lussen
en gaan van lineaire ruimte constant ruimte.
Huidige bedrag tot nu toe, hier, vervangt de rol van deelprobleem, onze deelprobleem array.
Dus de huidige som, tot nu toe, is het antwoord op de vorige deelprobleem.
En dat bedrag, tot nu toe, neemt de plaats in van onze max.
We berekenen de maximale terwijl we verder gaan.
En zo gaan we van lineaire ruimte om een ​​constante ruimte,
en we hebben ook een lineaire oplossing voor ons subarray probleem.
>> Dit soort vragen krijg je tijdens een interview.
Wat is de tijd complexiteit, wat is de ruimte complexiteit?
Kan jij dat ook? Zijn er dingen die niet nodig zijn om in de buurt?
Ik deed dit om analyses die je moet nemen op uw eigen markeren
als je werkt door middel van deze problemen.
Altijd jezelf de vraag: "Kan ik het beter doen?"
In feite, kan het beter dan dit?
Soort van een strikvraag. Je kunt niet, want je moet
ten minste over de ingang voor het probleem.
Dus het feit dat je nodig hebt om in ieder geval te lezen de ingang van het probleem
betekent dat je niet beter kan doen dan de lineaire tijd,
en je kan niet beter doen dan constant de ruimte.
Dit is dus in feite de beste oplossing voor dit probleem.
Vragen? Oke.
>> Beurs probleem:
"Bij een array van n gehele getallen, positief, nul of negatief,
dat vertegenwoordigen de prijs van een aandeel meer dan n dagen,
schrijf een functie om de maximale winst die u kunt maken berekenen
gezien het feit dat u koopt en precies 1 voorraad te verkopen binnen deze n dagen. "
In wezen willen we laag kopen, hoog verkopen.
En we willen achterhalen van de beste winst die we kunnen maken.
Terug te gaan naar mijn tip, wat is de direct duidelijk en eenvoudigste antwoord, maar het is traag?
Ja? (Student, onverstaanbaar) >> Ja.
>> Dus je zou gewoon al gaan kijken naar de aandelenkoersen
op elk punt in de tijd, (onverstaanbaar).
[Yu] Oke, dus haar oplossing - haar suggestie van de computer
de laagste en het berekenen van de hoogste niet noodzakelijkerwijs werkt
omdat de hoogste kan plaatsvinden voordat de laagste.
Dus wat is de brute kracht oplossing voor dit probleem?
Wat zijn de twee dingen die ik nodig heb om uniek te bepalen van de winst die ik maak? Juist.
De brute kracht oplossing is - oh, ja, George's suggestie is dat we alleen maar moet minimaal twee dagen
als unieke bepalen van de winst van die twee dagen.
Dus we berekenen elk paar, wil kopen / verkopen,
berekenen van de winst, die zouden kunnen worden negatief of positief of nul.
Bereken de maximale winst die we maken na itereren over alle paren van dagen.
Dat zal onze uiteindelijke antwoord.
En die oplossing wordt O (n ^ 2), omdat er n kiezen twee paar -
dagen dat u kunt kiezen uit eind dagen.
Oke, dus ik ben niet van plan hier te gaan over de brute kracht oplossing.
Ik ga je vertellen dat er een n log n oplossing.
Wat algoritme heb je momenteel dat is n log n?
Het is geen strikvraag.
>> Samenvoegen soort. Samenvoegen soort is n log n,
en in feite een manier om dit probleem te gebruiken
een merge sort soort idee genaamd, in het algemeen, verdeel en heers.
Het idee is als volgt.
U wilt de beste koop te berekenen / paar verkopen in de linker helft.
Vind de beste winst die je kunt maken met alleen de eerste n over twee dagen.
Dan wil je de beste koop oompute / paar verkopen op de rechter helft,
dus de laatste n over twee dagen.
En nu de vraag is, hoe gaan we nu samenvoegen deze oplossingen weer bij elkaar?
Ja? (Student, onverstaanbaar)
>> Oke. Dus laat me een tekening.
Ja? (George, onverstaanbaar)
>> Precies. George's oplossing is precies goed.
Dus zijn suggestie is in de eerste berekenen de beste koop / verkoop paar,
en dat gebeurt in de linker helft, dus laten we noemen dat links, links.
Beste kopen / verkopen paar dat zich voordoet in de rechter helft.
Maar als we alleen vergeleken deze twee getallen, we missen het geval
waar we hier kopen en verkopen ergens in de rechter helft.
Wij kopen in de linker helft, verkopen in de rechter helft.
En de beste manier om de beste koop / verkoop paar dat beide helften overspant berekenen
is de minimale hier berekenen en hier berekenen de maximum
en nemen hun verschil.
Dus de twee gevallen waarin de buy / sell paar treedt alleen hier,
alleen hier, of beide helften bestaat uit deze drie cijfers.
Dus ons algoritme om onze oplossingen samen te voegen weer bij elkaar,
We willen de beste koop / verkoop pair berekenen
waar kopen we op de linker helft en verkopen op de rechter helft.
En de beste manier om dat te doen is om de laagste prijs te berekenen in de eerste helft,
de hoogste prijs in de rechter helft, en nemen hun verschil.
De resulterende drie winst, deze drie nummers, neem je het maximum van de drie,
en dat is de beste winst die u kunt maken over deze eerste en einde dag.
Hier zijn de belangrijkste lijnen zijn in het rood.
Dit is een recursieve aanroep van het antwoord in de linkerhelft berekenen.
Dit is een recursieve aanroep van het antwoord berekenen in de rechterhelft.
Deze twee lussen voor het berekenen min en max op de linker en rechter respectievelijk.
Nu bereken ik de winst die beide helften overspant,
en het uiteindelijke antwoord is het maximum van deze drie.
Oke.
>> Dus, zeker, we hebben een algoritme, maar de grotere vraag is,
wat is de tijd complexiteit van dit?
En de reden waarom ik noemde merge sort is dat deze vorm van het antwoord te verdelen
in twee en dan samenvoegen onze oplossingen weer bij elkaar
is precies de vorm van merge sort.
Dus laat me gaan door de duur.
Als we gedefinieerd een functie t (n) het aantal stappen worden
voor n dag,
onze twee recursieve aanroepen
elk naar t (n / 2) kosten,
en er is twee van deze gesprekken.
Nu moet ik het minimum van de linker helft berekenen,
die ik kan doen in n / 2 keer, plus het maximum van de rechter helft.
Dus dit is gewoon n.
En dan plus een aantal constante werk.
En deze herhaling vergelijking
is precies de herhaling vergelijking voor merge sort.
En we weten allemaal dat merge sort is n log n tijd.
Daarom wordt ons algoritme ook n log n tijd.
Betekent dit iteratie zinvol?
Even een korte samenvatting van deze:
T (n) is het aantal stappen om maximale winst te berekenen
de loop van n dagen.
De manier waarop we opgesplitst onze recursieve oproepen
is door te bellen onze oplossing op de eerste n / 2 dagen,
dus dat is een oproep,
en dan noemen we weer op de tweede helft.
Dus dat is twee gesprekken.
En dan vinden we een minimum op de linker helft, die we kunnen doen in de lineaire tijd,
vinden het maximum van de rechter helft, die we kunnen doen in de lineaire tijd.
Dus n / 2 + n / 2 is gewoon n.
Dan hebben we een aantal constante werk, dat is als het doen van rekenkunde.
Deze herhaling vergelijking is precies de herhaling vergelijking voor merge sort.
Vandaar dat onze shuffle algoritme is ook n log n.
Dus hoeveel ruimte gebruiken we?
Laten we terug gaan naar de code.
>> Een betere vraag is, hoeveel stack frames die we ooit hebben op een bepaald moment?
Aangezien we met behulp van recursie,
het aantal stack frames bepaalt onze ruimte gebruik.
Laten we eens kijken n = 8.
Wij roepen shuffle op 8,
die zal shuffle een beroep doen op de eerste vier items,
deze zal een shuffle op de eerste twee items.
Dus onze stack is - dit is onze stack.
En dan noemen we shuffle weer op 1,
en dat is wat ons basisscenario is, dus we onmiddellijk terug.
Hebben we ooit meer dan dit aantal stack frames hebben?
Nee, omdat elke keer dat we doen een aanroeping,
een recursieve aanroep op shuffle,
verdelen we onze omvang in de helft.
Dus het maximum aantal stack frames die we ooit hebben op een gegeven moment
is in de orde van log n stapel frames.
Elke stapel frame heeft een constante ruimte,
, zodat de totale hoeveelheid ruimte,
de maximale hoeveelheid ruimte die we ooit gebruiken is O (log n) ruimte
waarbij n het aantal dagen.
>> Nu, altijd afvragen: "Kan het beter?"
En in het bijzonder, kunnen we de prijs dat dit een probleem die we al hebben opgelost?
Een hint: we slechts twee andere problemen besproken voordat dit, en het is niet van plan om shuffle.
We kunnen omzetten beurs probleem in de maximale subarray probleem.
Hoe kunnen we dit doen?
Een van jullie? Emmy?
(Emmy, onverstaanbaar)
[Yu] Precies.
Zodat de maximale subarray probleem
We zijn op zoek naar een som over een continu subarray.
En Emmy's suggestie voor de voorraden probleem,
rekening houden met de veranderingen, of de delta's.
En een foto van deze is - dat is de prijs van een aandeel,
maar als we namen het verschil tussen elke opeenvolgende dag -
zo zien we dat de maximale prijs, maximale winst konden we
is als we hier kopen en verkopen hier.
Maar laten we eens kijken naar de voortdurende - laten we eens kijken naar de subarray probleem.
Dus hier kunnen we - gaan van hier naar hier,
hebben we een positieve verandering, en dan gaan van hier naar hier hebben we een negatieve verandering.
Maar dan, gaat van hier naar hier hebben we een enorme positieve verandering.
En dit zijn de veranderingen die we willen vatten om onze uiteindelijke winst te halen.
Dan hebben we meer negatieve veranderingen hier.
De sleutel tot het verminderen van onze voorraad probleem in onze maximale subarray probleem
is om te overwegen de delta's tussen dagen.
Dus maken we een nieuwe array met de naam delta's,
initialiseren van de eerste binnenkomst op 0,
en dan voor elke delta (i), laat dat zo het verschil
mijn input array (i) en array (i - 1).
Dan noemen we onze routine procedure voor een maximale subarray
passeren in array een delta's.
En omdat maximale subarray is lineaire tijd,
en deze daling, dit proces van het creëren van deze delta array,
Ook lineaire tijd,
dan is de definitieve oplossing voor de bestanden is O (n) werk plus O (n) werk, is nog steeds O (n) werk.
Dus hebben we een lineaire tijd oplossing voor ons probleem.
Heeft iedereen begrijpt deze transformatie?
>> In het algemeen is het een goed idee dat je altijd zou moeten hebben
is proberen om een ​​nieuw probleem dat je ziet verminderen.
Als het ziet er bekend uit voor een oud probleem,
proberen terug te brengen tot een oud probleem.
En als je kunt gebruik maken van alle tools die je hebt gebruikt op het oude probleem
de nieuwe probleem.
Dus om af te ronden, worden technische interviews uitdagend.
Deze problemen zijn waarschijnlijk een van de meest moeilijke problemen
dat je zou kunnen zien in een interview,
dus als je het niet begrijpt alle problemen die ik net bedekt, het is oke.
Dit zijn enkele van de meer uitdagende problemen.
Oefenen, oefenen, oefenen.
Ik gaf veel problemen in de hand-out, dus zeker check deze uit.
En veel geluk op uw interviews. Al mijn bronnen zijn gepost op deze link,
en een van mijn senior vrienden heeft aangeboden om mock technische interviews te doen,
dus als je geïnteresseerd bent, e-mail zal Yao op dat e-mailadres.
Als u nog vragen, dan kunt u het mij vraagt.
Hebben jullie specifieke vragen met betrekking tot technische interviews
of problemen die we tot nu toe gezien?
Oke. Nou, veel geluk op uw interviews.
[CS50.TV]