[Powered by Google Translate] [Seminar: Technische Interviews]
[Kenny Yu, Harvard University]
[Dies ist CS50.] [CS50.TV]
Hallo allerseits, ich bin Kenny. Ich bin derzeit ein Junior-Studium der Informatik.
Ich bin ein ehemaliger CS TF, und ich wünschte, ich hätte, wenn ich ein Underclassman war,
und das ist, warum ich geben dieses Seminar bin.
Also ich hoffe es gefällt euch.
Dieses Seminar ist über technische Interviews,
und alle meine Ressourcen können unter diesem Link gefunden werden,
dieser Link hier, ein paar Ressourcen.
Also machte ich eine Liste von Problemen, eigentlich durchaus ein paar Probleme.
Auch eine allgemeine Ressourcen-Seite, wo wir Tipps finden
wie Sie für ein Vorstellungsgespräch vorbereiten,
Tipps, was Sie sollten während eines tatsächlichen Interview zu machen,
und wie die Probleme und Ressourcen für zukünftige Referenz zu nähern.
Es ist alles online.
Und nur um Vorwort Dieses Seminar, einen wichtigen Hinweis,
wie diese sollten nicht - Ihre Vorbereitung auf ein Vorstellungsgespräch
sollte nicht auf diese Liste begrenzt.
Dies soll nur ein Leitfaden sein,
und Sie sollten auf jeden Fall alles, was ich sagen mit einem Körnchen Salz,
aber auch alles, was ich verwendet, um Sie in Ihrer Vorbereitung auf ein Vorstellungsgespräch zu helfen.
>> Ich werde zu beschleunigen durch die nächsten paar Folien
so können wir den tatsächlichen Fallstudien erhalten.
Die Struktur eines Interviews für eine Software-Engineering-Positionen,
typischerweise sind es 30 bis 45 Minuten,
mehrere Runden, abhängig von der Firma.
Oft werden Sie auf eine weiße Tafel werden Codierung.
So eine weiße Tafel wie diese, aber oft in einem kleineren Maßstab.
Wenn Sie ein Telefon-Interview, werden Sie wahrscheinlich mit
entweder collabedit oder ein Google Doc damit sie sehen können, Sie leben Kodierung
während du sie über das Telefon befragt.
Ein Interview selbst ist in der Regel 2 oder 3 Probleme
Testen Sie Ihre EDV Kenntnisse.
Und es wird fast definitiv beinhalten Codierung.
Die Arten von Fragen, die Sie sehen, sind in der Regel Datenstrukturen und Algorithmen.
Und dabei diese Art von Problemen,
sie werden dich fragen, wie ist es, was die Zeit und Raum Komplexität, große O?
Oft bitten sie auch auf höherer Ebene Fragen,
so, ein System zu entwerfen,
Wie würden Sie das Layout Ihrer Code?
Welche Schnittstellen, welche Klassen, welche Module Sie in Ihrem System haben,
und wie wirken sich diese miteinander interagieren?
So Datenstrukturen und Algorithmen sowie Entwicklung von Systemen.
>> Einige allgemeine Tipps, bevor wir in unsere Fallstudien zu tauchen.
Ich denke, die wichtigste Regel ist immer werden laut gedacht.
Das Interview soll Ihre Chance zu zeigen Sie Ihren Denkprozess.
Der Punkt des Interviews ist der Interviewer zu beurteilen
wie Sie denken und wie Sie durch ein Problem gehen.
Das Schlimmste, was Sie tun können, ist zu schweigen während des gesamten Interviews.
Das ist einfach nicht gut.
Wenn Sie eine Frage gegeben werden, Sie wollen auch sicherstellen, dass Sie verstehen, die Frage.
So wiederholen Sie die Frage zurück in Ihren eigenen Worten
und versuchen zu arbeiten gründliche ein paar einfache Testfälle
um sicherzustellen, dass Sie verstehen die Frage nicht.
Arbeiten durch ein paar Testfälle wird Ihnen auch eine Intuition, wie man dieses Problem lösen.
Vielleicht entdecken Sie sogar ein paar Muster, damit Sie das Problem lösen.
Ihr großer Tipp ist nicht frustriert.
Nicht frustriert.
Interviews sind anspruchsvoll, aber das Schlimmste, was Sie tun können,
zusätzlich zu schweigen, ist die sichtbare frustriert werden.
Sie wollen nicht den Eindruck in einem Interview zu geben.
Eine Sache, die Sie - so viele Menschen, wenn sie gehen in einem Interview,
sie versuchen, um zu versuchen, die beste Lösung zuerst finden,
wenn wirklich, es gibt in der Regel eine eklatant Lösung.
Es könnte sein, langsam, kann es sein, ineffizient, aber Sie sollten nur sagen, es
nur so haben Sie einen Ausgangspunkt, von dem besser funktionieren.
Auch zeigt die Lösung langsam ist, in Bezug auf
big O Zeitkomplexität und Raum Komplexität,
wird dem Interviewer, dass Sie verstehen, zeigen,
diese Probleme beim Schreiben von Code.
So haben Sie keine Angst, sich mit den einfachsten Algorithmus zuerst
und dann besser arbeiten von dort aus.
Fragen so weit? Okay.
>> So lasst uns in unsere erste Problem zu tauchen.
"Angesichts einer Reihe von n Zahlen, schreiben Sie eine Funktion, die das Array mischt
an Ort und Stelle, so dass alle Permutationen der n Zahlen gleich wahrscheinlich sind. "
Und nehmen Sie zur Verfügung haben eine Zufallszahl-Generator
das erzeugt eine ganze Zahl in einem Bereich von 0 bis i, halb-Bereich.
Hat jeder verstehen, diese Frage?
Ich gebe Ihnen eine Reihe von n Zahlen, und ich möchte, dass du mische es.
In meinem Verzeichnis, schrieb ich ein paar Programme zu zeigen, was ich meine.
Ich bin zu mischen eine Reihe von 20 Elementen gehen,
von -10 bis +9,
und ich möchte, dass du eine Liste wie diese auszugeben.
Also das ist meine sortierten Arrays input, und ich möchte, dass du mische es.
Wir werden es wieder tun.
Hat jeder die Frage verstehen? Okay.
So ist es bis zu Ihnen.
Was sind einige Ideen? Kannst du es als n ^ 2, n log n, n?
Offen für Vorschläge.
Okay. So eine Idee, die von Emmy vorgeschlagen,
zunächst eine Zufallszahl zu berechnen, Zufallsganzzahl, in einem Bereich von 0 bis 20 ist.
Also nehmen unsere Array hat eine Länge von 20.
In unserem Diagramm von 20 Elementen,
dies ist unsere Eingabe-Array.
Und nun ist ihr Vorschlag, ein neues Array erstellen,
so wird dies der Ausgang Array sein.
Und auf dem i von rand zurückgegeben werden -
Also, wenn ich war, sagen wir, 17,
Kopieren Sie die 17. in die erste Position.
Jetzt müssen wir zu löschen - wir müssen alle Elemente hier verschieben
über, so dass wir eine Lücke am Ende und keine Löcher in der Mitte haben.
Und jetzt haben wir den Vorgang wiederholen.
Jetzt holen wir eine neue Zufallszahl zwischen 0 und 19.
Wir haben eine neue i hier, und wir kopieren dieses Element in dieser Position.
Dann verschieben wir Produkte vorbei und wir wiederholen Sie den Vorgang, bis wir unsere volle neue Array.
Was ist die Laufzeit dieses Algorithmus?
Nun, betrachten wir die Auswirkungen dieser.
Wir verlagern jedes Element.
Wenn wir diese entfernen i, wir verschieben alle Elemente, nachdem sie auf der linken Seite.
Und das ist ein O (n) Kosten
denn was, wenn wir das erste Element zu entfernen?
So, für jeden Abgang, entfernen wir -
Jeder Umzug kostet eine O (n)-Operation,
und da wir n Umzüge haben, führt dies zu einem O (n ^ 2) shuffle.
Okay. So guter Anfang. Guter Start.
>> Ein weiterer Vorschlag ist, um etwas bekannt als Knuth shuffle,
oder die Fisher-Yates shuffle.
Und es ist eigentlich eine lineare Zeit shuffle.
Und die Idee ist sehr ähnlich.
Auch hier haben wir unsere Eingabe-Array,
aber statt mit zwei Arrays für unsere Eingang / Ausgang,
verwenden wir den ersten Abschnitt des Arrays zu verfolgen unserer umgeordneten Abschnitts zu halten,
und wir behalten, und dann verlassen wir den Rest unseres Array für die unshuffled Abschnitt.
Also hier ist was ich meine. Wir starten mit - wählen wir eine i,
ein Array von 0 bis 20 ist.
Unsere aktuellen Zeiger auf den ersten Index zeigt.
Wir wählen einige ich hier
und jetzt haben wir tauschen.
Also, wenn dies war 5 und das war 4,
das resultierende Array 5 hier und 4 hier zu haben.
Und jetzt stellen wir fest, einen Marker hier.
Alles auf der linken Seite wird gemischt,
und alles, was auf der rechten Seite ist unshuffled.
Und jetzt können wir den Vorgang wiederholen.
Wir wählen einen zufälligen Index zwischen 1 und 20 jetzt.
So nehme unsere neue i ist hier.
Jetzt tauschen wir dieses i mit unseren aktuellen neuen Position hier.
Also haben wir ein Swapping hin und her, wie diese.
Lassen Sie mich bringen Sie den Code, um es konkreter.
Wir beginnen mit unserer Wahl von i -
beginnen wir mit i auf 0 gleich, wählen wir eine zufällige Position j
im unshuffled Abschnittes des Feldes, bis i n-1.
Also, wenn ich hier bin, wählen Sie eine zufällige Index zwischen hier und dem Rest des Feldes,
und wir tauschen.
Dies ist der gesamte Code notwendig, mische dein Array.
Haben Sie Fragen?
>> Nun, eine Frage benötigt wird, warum ist das so richtig?
Warum ist jede Permutation gleich wahrscheinlich?
Und ich werde nicht durch den Beweis dafür zu gehen,
aber viele Probleme in der Informatik können durch Induktion bewiesen werden.
Wie viele von euch sind vertraut mit Induktion?
Okay. Cool.
So können Sie beweisen die Korrektheit dieses Algorithmus durch einfache Induktion,
wo Ihre Induktionsannahme wäre, anzunehmen, dass
meinen Shuffle gibt jede Permutation gleich wahrscheinlich
bis zu den ersten i Elemente.
Betrachten wir nun i + 1.
Und durch die Art, wie wir wählen unsere Index j zu tauschen,
dies führt zu - und dann die Einzelheiten auszuarbeiten,
mindestens ein voller Beweis, warum dieser Algorithmus liefert
jede Permutation mit gleicher Wahrscheinlichkeit Wahrscheinlichkeit.
>> Alles klar, nächste Problem.
So "ein Array von Ganzzahlen, postive, null, negativ gegeben,
eine Funktion schreiben, die maximale Summe berechnet
jeder continueous Subarray des Eingabe-Arrays. "
Ein Beispiel dafür ist in dem Fall, wo alle Zahlen sind positiv,
Dann derzeit die beste Wahl ist, um das gesamte Array zu nehmen.
1, 2, 3, 4, 10 entspricht.
Wenn Sie einige Negative haben dort
In diesem Fall wollen wir nur die ersten beiden
weil die Wahl -1 und / oder -3 bringt unseren Summe nach unten.
Manchmal müssen möglicherweise in der Mitte des Arrays zu starten.
Manchmal wollen wir gar nichts zu wählen, es ist am besten, nichts mitnehmen.
Und manchmal ist es besser, nehmen Sie den Fall,
weil die Sache nach ist es super groß. Also irgendwelche Ideen?
(Student, unverständlich) >> Ja.
Angenommen, ich weiß nicht -1 nehmen.
Dann entweder wähle ich 1.000 und 20.000,
oder ich wählen Sie einfach die 3 Milliarden Euro.
Nun, das ist die beste Wahl, um alle Nummern zu nehmen.
Diese -1, obwohl negativ,
die ganze Summe ist besser, als wenn ich nicht auf -1 zu nehmen.
So einer der Tipps, die ich bereits erwähnt war es, die klar auf der Hand angeben
und die Brute-Force-Lösung zuerst.
Was ist der Brute-Force-Lösung für dieses Problem? Yeah?
[Jane] Nun, ich denke die Brute-Force-Lösung
wäre addieren sich alle möglichen Kombinationen (unverständlich).
[Yu] Okay. So Jane Idee ist es, jede mögliche nehmen -
Ich bin paraphrasieren - ist jede mögliche kontinuierliche Subarray nehmen,
Berechnung ihrer Summe, und nehmen Sie dann das Maximum aller möglichen kontinuierlichen Subarrays.
Was eindeutig eine Untergruppe in meinen Input Array?
Gefällt, was zwei Dinge brauche ich? Yeah?
(Student, unverständlich) >> Richtig.
Ein unterer auf dem Index, und einer oberen Grenze Index gebundenen
eindeutig bestimmt eine kontinuierliche Subarray.
[Studentin] Sind wir schätzen, es ist eine Reihe von einzigartigen Zahlen?
[Yu] Nein So ihre Frage ist, gehen wir davon aus unser Angebot -
ist unser Angebot alle eindeutige Nummern, und die Antwort ist nein.
>> Wenn wir unsere Brute-Force-Lösung, dann die Start / End-Indizes
eindeutig bestimmt unsere kontinuierliche Teilmatrix.
Also, wenn wir für alle möglichen Start-Einträge durchlaufen,
und für alle Ende Einträge> oder = zu starten, und <n,
Sie berechnen die Summe, und dann nehmen wir die maximale Summe, die wir bisher gesehen haben.
Ist das klar?
Was ist das große O dieser Lösung?
Zeitlich.
Nicht ganz ^ 2 n.
Beachte, dass wir von 0 bis n durchlaufen,
so das ist ein for-Schleife.
Wir erneut durchlaufen aus fast Anfang bis zum Ende, eine andere für Schleife.
Und nun, innerhalb dieser, haben wir zu summieren jeden Eintrag,
so das ist eine andere for-Schleife. So haben wir drei verschachtelten for-Schleifen, n ^ 3.
Okay. Dies geht als Ausgangspunkt.
Unsere Lösung ist nicht schlechter als n ^ 3.
Hat jeder verstehen, die Brute-Force-Lösung?
>> Okay. Eine bessere Lösung ist mit einer Idee namens dynamische Programmierung.
Wenn Sie cs124 zu nehmen, ist die Algorithmen und Datenstrukturen,
Sie werden sich sehr vertraut mit dieser Technik.
Und die Idee ist, versuchen aufzubauen Lösungen für kleinere Probleme zuerst.
Was ich damit meine ist, haben wir im Augenblick um zwei Dinge kümmern: Anfang und Ende.
Und das ist ärgerlich. Was, wenn wir loswerden könnte einen dieser Parameter?
Eine Idee ist, - wir sind aufgrund unserer ursprünglichen Problems,
Neben dem maximalen Summe jede Subarray in einem Bereich [O, n-1].
Und jetzt haben wir eine neue Teilproblem, wo wir wissen, in unserer aktuellen Index i,
wir wissen, wir müssen es schließen. Unsere Subarray muss am aktuellen Index zu beenden.
So das verbleibende Problem ist, sollten, wo wir beginnen unsere Subarray?
Ist das sinnvoll? Okay.
Also habe ich dieses up codiert, und lassen Sie uns an, was bedeutet dies aussehen.
In der codirectory, gibt es ein Programm namens Subarray,
und es dauert Anzahl von Elementen,
und es gibt die maximale Untergruppe Summe in meinem gemischt Liste.
So dass in diesem Fall, ist unser maximalen Unterarray 3.
Und das ist nur mit Hilfe von 2 und 1 übernommen.
Lasst uns wieder zu starten. Es ist auch 3.
Aber dieses Mal, festzustellen, wie wir die 3 bekam.
Wir nahmen das - wir nehmen Sie die 3 selbst
weil es von Negativen auf beiden Seiten umgeben,
was bringt eine Summe <3.
Lasst uns auf 10 Artikel laufen.
Dieses Mal ist es 7, nehmen wir die führende 3 und 4.
Dieses Mal ist es 8, und wir erhalten, dass, indem sie 1, 4 und 3.
So geben Sie eine Intuition, wie wir lösen dieses transformierte Problem,
Werfen wir einen Blick auf diese Teilmatrix.
Wir dieses Eingabe-Array gegeben, und wir wissen, die Antwort ist 8.
Wir nehmen den 1, 4, und 3.
Aber lassen Sie uns an, wie wir eigentlich die Antwort zu suchen.
Lassen Sie uns bei der maximalen Subarray, das an jeder dieser Indizes endete aussehen.
Was ist die maximale Untergruppe, die an der ersten Position enden muss?
[Student] Zero. >> Zero. Nur nehmen Sie nicht die -5.
Hier es geht um 0 als gut. Yeah?
(Student, unverständlich)
[Yu] Oh, sorry, es ist ein -3.
Dies ist also eine 2, ist dies ein -3.
Okay. So -4, was ist die maximale Untergruppe, um diese Position zu beenden
wo -4 ist? Zero.
One? 1, 5, 8.
Jetzt muss ich an der Stelle, wo -2 ist am Ende.
So 6, 5, 7, und die letzte für 4 steht.
Wissend, dass dies meine Einträge sind
für das transformierte Problem, wo ich an jedem dieser Indizes enden muss,
dann meine endgültige Antwort ist einfach, nehmen Sie eine Schleife über,
und nehmen Sie die maximale Anzahl.
Also in diesem Fall ist es 8.
Dies bedeutet, dass die maximale Untergruppe bei diesem Index endet,
und begann irgendwo davor.
Hat jeder verstehen diese verwandelt Subarray?
>> Okay. Nun, lasst uns herausfinden, die Wiederholung für diese.
Betrachten wir nur die ersten Einträge.
So ist es hier betrug 0, 0, 0, 1, 5, 8.
Und dann gab es eine -2 hier, und das brachte ihn auf 6.
Also, wenn ich rufe den Eintrag an Position i Teilproblem (i),
wie kann ich die Antwort auf einen früheren Teilproblem
um dieses Teilproblem zu beantworten?
Wenn ich zu schauen, sagen wir, diesen Eintrag.
Wie kann ich berechnen die Antwort 6 Dazu suchen Sie in
eine Kombination aus diesem Array und den Antworten auf frühere Teilprobleme in diesem Array? Ja?
[Studentin] Du nimmst das Array von Summen
in der Position kurz vor dem, so dass die 8,
und fügen Sie dann die aktuelle Teilproblem.
[Yu] So ihr Vorschlag ist, an diesen beiden Zahlen anschaut,
diese Anzahl und diese Anzahl.
Also das 8 bezieht sich auf die Antwort auf die Teilproblem (i - 1).
Und nennen wir meinen Input Array A.
Um eine maximale Subarray, das an der Position i endet finden,
Ich habe zwei Möglichkeiten: Ich kann entweder weiterhin die Subarray
das endete am vorherigen Index, oder starten Sie ein neues Array.
Wenn ich das Unterfeld, die am vorherigen Index begann fortsetzen,
dann ist die maximale Summe, die ich erreichen kann, ist die Antwort auf die vorherige Teilproblem
plus die aktuelle Array-Eintrag.
Aber ich habe auch die Wahl der Beginn einer neuen Untergruppe,
in welchem ​​Fall die Summe für 0 steht.
Die Antwort ist also max von 0, Teilproblem i - 1, plus die aktuelle Array-Eintrag.
Bedeutet dies Rezidiv sinnvoll?
Unsere Wiederkehr, wie wir gerade entdeckt, ist Teilproblem i
ist gleich dem Maximum der letzten Teilproblem plus meine aktuelle Array-Eintrag,
Das bedeutet weiterhin die vorherige Subarray,
oder 0, starten Sie eine neue Untergruppe an meinem aktuellen Index.
Und einmal haben wir diese Tabelle von Lösungen gebaut, dann unsere endgültige Antwort,
einfach eine lineare Schleife über dem Teilproblem array
und nehmen Sie die maximale Anzahl.
Dies ist eine exakte Umsetzung dessen, was ich gerade gesagt habe.
So schaffen wir eine neue Teilproblem Array Teilprobleme.
Der erste Beitrag ist entweder 0 oder der erste Eintrag der maximale dieser beiden.
Und für den Rest der Teilprobleme
verwenden wir die genaue Wiederholung wir gerade entdeckt.
Jetzt berechnen wir die maximale unserer Teilprobleme Array, und das ist unsere endgültige Antwort.
>> So, wie viel Speicherplatz verwenden wir in diesem Algorithmus?
Wenn Sie nur CS50 genommen haben, dann könnten Sie nicht Raum diskutiert sehr viel haben.
Nun, das ist eine Sache zu beachten, dass ich malloc hier genannt mit der Größe n.
Was bedeutet das für Sie vorschlagen?
Dieser Algorithmus verwendet linearen Raum.
Können wir besser machen?
Gibt es etwas, dass Sie feststellen, dass es unnötig, die endgültige Antwort zu berechnen?
Ich denke, eine bessere Frage ist, welche Informationen
brauchen wir nicht den ganzen Weg bis zum Ende zu führen?
Nun, wenn wir uns mit diesen beiden Linien,
wir nur über den vorherigen Teilproblem kümmern,
und wir nur über die maximale wir je gesehen habe, so weit zu kümmern.
Um unsere endgültige Antwort zu berechnen, brauchen wir nicht das gesamte Array.
Wir brauchen nur die letzte Zahl, die beiden letzten Zahlen.
Last-Nummer für den Teilproblem Array, und die letzte Zahl für das Maximum.
Also, in der Tat, können wir diese Schlaufen miteinander verschmelzen
sowie aus linearen Raum konstanten Raum gehen.
Aktuelle Summe so weit, hier ersetzt die Rolle der Teilproblem, unsere Teilproblem Array.
So aktuelle Summe, so weit ist die Antwort auf die vorherige Teilproblem.
Und diese Summe, so weit, tritt an die Stelle unserer max.
Wir berechnen die maximale wie wir entlang gehen.
Und so gehen wir von linearen Raum eine konstante Raum,
und wir haben auch eine lineare Lösung für unsere Subarray Problem.
>> Diese Art von Fragen, die Ihnen während eines Interviews zu bekommen.
Was ist die Zeit Komplexität, was ist der Raum Komplexität?
Können Sie es besser? Gibt es Dinge, die unnötig zu halten in der Nähe sind?
Ich tat dies, um Analysen, die Sie auf eigene Faust sollten markieren
wie Sie durch diese Probleme.
Immer fragen sich: "Kann ich besser machen?"
In der Tat können wir besser machen als das?
Sortieren einer Fangfrage. Sie können nicht, weil Sie brauchen
zumindest lesen die Eingabe für das Problem.
So ist die Tatsache, dass Sie benötigen mindestens lesen Sie den Eingang auf das Problem
bedeutet, dass Sie nicht besser als die lineare Zeit,
und Sie können nichts Besseres tun, als konstante Raum.
So ist dies in der Tat, die beste Lösung für dieses Problem.
Haben Sie Fragen? Okay.
>> Börse Problem:
"Bei einer Anordnung von n ganze Zahlen sind, positiv, Null oder negativ ist,
das stellen die Kurs einer Aktie über n Tage,
eine Funktion schreiben, den maximalen Gewinn können Sie berechnen
gegeben, dass Sie kaufen und verkaufen genau 1 lieferbar innerhalb dieser n Tage. "
Im Grunde wollen wir billig kaufen, teuer verkaufen.
Und wir wollen herausfinden, das beste Ergebnis können wir machen.
Gehen wir zurück zu meinem Tipp, was ist das sofort klar, einfachste Antwort, aber es ist zu langsam?
Ja? (Student, unverständlich) >> Ja.
>> Also würde man nur wenn gehen und schauen Sie sich die Aktienkurse
an jedem Punkt in der Zeit, (unverständlich).
[Yu] Okay, so ihre Lösung - ihr Vorschlag Computing
die niedrigste und die Berechnung der höchsten nicht unbedingt arbeiten
weil die höchste könnte vor dem niedrigsten auftreten.
Also, was ist die Brute-Force-Lösung für dieses Problem?
Was sind die zwei Dinge, die ich brauche, um eindeutig zu bestimmen den Gewinn ich machen? Right.
Die Brute-Force-Lösung ist - oh, ja, ist George Vorschlag brauchen wir nur 2 Tage
zur eindeutigen Bestimmung der Gewinn von diesen zwei Tagen.
So berechnen wir jedes Paar, wie Kauf / Verkauf,
Berechnung des Gewinns, die positiv oder negativ sein oder Null könnte.
Berechnen Sie den maximalen Gewinn, dass wir nach der Iteration über alle Paare von Tagen.
Das wird unsere letzte Antwort sein.
Und diese Lösung wird O (n ^ 2) sein, denn es gibt n wählen zwei Paare -
der Tage, die Sie zu Ende Tag wählen können.
Okay, ich werde mich nicht über die Brute-Force-Lösung finden Sie hier.
Ich werde Ihnen sagen, dass es ein n log n Lösung.
Welchen Algorithmus Sie derzeit wissen, dass es n log n?
Es ist nicht eine Fangfrage.
>> Mergesort. Mergesort ist n log n,
und in der Tat ist eine Möglichkeit zur Lösung dieses Problems zu bedienen
a merge sort Art von Idee genannt, im Allgemeinen, zu teilen und zu erobern.
Und die Idee ist wie folgt.
Sie wollen das Beste kaufen berechnen / Verkauf Paar in der linken Hälfte.
Finden Sie die besten profitieren Sie machen, können nur mit dem ersten n über zwei Tage.
Dann möchten Sie den besten Kauf oompute / Verkauf Paar auf der rechten Hälfte,
so dass die letzten n über zwei Tage.
Und jetzt ist die Frage, wie können wir verschmelzen diese Lösungen wieder zusammen?
Ja? (Student, unverständlich)
>> Okay. Also lassen Sie mich ein Bild zeichnen.
Ja? (George, unverständlich)
>> Genau. George-Lösung ist genau richtig.
So sein Vorschlag ist, berechnen zunächst die best buy / sell Paar,
und das geschieht in der linken Hälfte, so nennen wir es links, links.
Best buy / sell-Paar, das in der rechten Hälfte auftritt.
Aber wenn wir diese beiden Zahlen nur im Vergleich, verpassen wir den Fall
wo wir hier kaufen und verkaufen irgendwo in der rechten Hälfte.
Wir kaufen in der linken Hälfte, in der rechten Hälfte zu verkaufen.
Und der beste Weg, um die best buy / sell Paar, beide Hälften überspannt berechnen
ist die Mindestzahl hier berechnen und berechnen Sie die maximale hier
und nehmen ihre Differenz.
So die beiden Fälle, in denen das Buy / Sell-Paar tritt nur hier,
nur hier, oder auf beiden Hälften wird durch diese drei Nummern definiert.
So unser Algorithmus, um unsere Lösungen zurück miteinander verschmelzen,
wollen wir die best buy / sell Paar berechnen
wo wir auf der linken Hälfte kaufen und verkaufen auf der rechten Hälfte.
Und der beste Weg, dies zu tun ist, um den niedrigsten Preis in der ersten Hälfte zu berechnen,
der höchste Preis in der rechten Hälfte, und nehmen ihre Differenz.
Die resultierenden drei Gewinne, diese drei Zahlen, nehmen Sie das Maximum der drei,
und das ist der beste Gewinn, den Sie über diese erste und Ende Tag machen kann.
Hier werden die wichtigsten Linien sind in rot.
Dies ist ein rekursiver Aufruf, die Antwort in der linken Hälfte berechnen.
Dies ist ein rekursiver Aufruf, die Antwort in der rechten Hälfte berechnen.
Diese zwei for-Schleifen berechnen die min und max auf der linken und rechten Hälfte sind.
Jetzt berechne ich den Gewinn, die beide Hälften überspannt,
und die endgültige Antwort ist die maximale dieser drei.
Okay.
>> So, sicher, wir haben einen Algorithmus, aber die größere Frage ist,
was ist die Zeit Komplexität this?
Und der Grund, warum ich erwähnt Mergesort ist, dass diese Form der Antwort unterteilen
in zwei und dann die Verschmelzung unserer Lösungen wieder zusammen
ist genau die Form von Mergesort.
Also lassen Sie mich durch die Dauer gehen.
Wenn wir definiert eine Funktion t (n), um die Anzahl von Schritten sein,
für n Tage,
unsere zwei rekursive Aufrufe
jeweils werde t (n / 2) kosten,
und es gibt zwei dieser Anrufe.
Jetzt muss ich das Minimum der linken Hälfte zu berechnen,
was kann ich in n / 2, plus dem Maximum der rechten Hälfte zu tun.
So ist dies nur n.
Und dann plus eine Konstante Arbeit.
Und diese Rekursionsgleichung
ist genau die Rekursionsgleichung für Mergesort.
Und wir alle wissen, dass Mergesort n log n Zeit ist.
Daher ist unser Algorithmus log n Zeit n.
Hat diese Iteration sinnvoll?
Nur eine kurze Zusammenfassung davon:
T (n) ist die Anzahl der Schritte, um den maximalen Gewinn zu berechnen
im Verlauf von n Tagen.
Die Art und Weise teilen wir unsere rekursive Aufrufe
wird durch den Aufruf unserer Lösung auf den ersten n / 2 Tage,
so das ist ein Anruf,
und dann rufen wir wieder auf der zweiten Hälfte.
Also das ist, zwei Anrufe.
Und dann finden wir ein Minimum auf der linken Hälfte, die wir in der linearen Zeit zu tun,
finden Sie das Maximum der rechten Hälfte, die wir in linearer Zeit tun können.
So n / 2 + n / 2 ist nur n.
Dann haben wir etwas ständige Arbeit, die wie Rechnen ist.
Diese Rekursionsgleichung ist genau die Rekursionsgleichung für Mergesort.
Daher ist unsere shuffle Algorithmus auch n log n.
So, wie viel Speicherplatz verwenden wir?
Gehen wir zurück zu dem Code.
>> Eine bessere Frage ist, wie viele Stack-Frames, die wir je zu einem bestimmten Zeitpunkt haben?
Da wir mit Rekursion
die Anzahl der Stack-Frames bestimmt unser Raumnutzung.
Betrachten wir n = 8.
Wir nennen Shuffle 8,
was wird Shuffle auf den ersten vier Einträge nennen,
die rufen einen Shuffle auf den ersten beiden Einträge.
Also unsere Stack ist - das ist unser Stack.
Und dann nennen wir mischen wieder auf 1,
und das ist, was unsere Basis Fall ist, so dass wir sofort zurück.
Haben wir jemals mehr als diese vielen Stack-Frames?
Nein, denn jedes Mal, wenn wir einen Aufruf,
eine rekursive Aufruf zu mischen,
teilen wir unsere Größe in zwei Hälften.
So dass die maximale Anzahl der Stack-Frames wir jemals zu einem bestimmten Zeitpunkt
in der Größenordnung von log n Stapelrahmen.
Jeder Stack-Frame hat eine konstante Raum,
und damit die Gesamtmenge der Raum,
der Höchstbetrag der Raum, den wir jemals verwenden ist O (log n) Raum
wobei n die Anzahl von Tagen.
>> Nun, sich immer fragen: "Können wir besser machen?"
Und vor allem können wir die dies zu einem Problem, das wir bereits gelöst haben?
Ein Tipp: wir nur diskutiert zwei weitere Probleme, bevor diese, und es ist nicht zu shuffle.
Wir können dieses Aktienmarkt Problem in der maximalen Subarray Problem zu konvertieren.
Wie können wir das tun?
Einer von euch? Emmy?
(Emmy, unverständlich)
[Yu] Genau.
So ist die maximale Subarray Problem,
wir für eine Summe mit Blick auf eine kontinuierliche Teilmatrix.
Und Emmy Vorschlag für die Aktien Problem,
betrachten die Änderungen oder die Deltas.
Und ein Bild davon - das ist der Preis einer Aktie,
aber wenn wir nahm die Differenz zwischen jedem Tag in Folge -
so sehen wir, dass der maximale Preis, maximalen Profit könnten wir
ist, wenn wir hier kaufen und verkaufen hier.
Aber lassen Sie uns auf die kontinuierliche aussehen - wir bei der Subarray Problem zu suchen.
Also hier können wir - gehen von hier nach hier,
Wir haben eine positive Veränderung, und dann gehen von hier nach hier haben wir eine negative Veränderung.
Aber dann gehen von hier nach hier haben wir eine riesige positive Veränderung.
Und das sind die Veränderungen, die wir wollen, summieren sich zu unserem letzten Gewinn zu erhalten.
Dann haben wir mehr negative Veränderungen hier.
Der Schlüssel zur Verringerung unserer Aktie Problem in unsere maximale Subarray Problem
ist es, die Deltas zwischen Tag betrachten.
So schaffen wir ein neues Array namens Deltas,
Initialisieren des ersten Eintrags auf 0,
und dann für jeden Delta-(i), zulassen, dass die Differenz
meiner Eingangsanordnung (i), und Array (i - 1).
Dann rufen wir unsere Routine für eine maximale Untergruppe
Übergabe eines Deltas Array.
Und weil maximale Untergruppe ist die lineare Zeit,
und diese Reduktion, dieser Prozess der Erstellung dieses Delta-Array,
ist auch die lineare Zeit,
dann die endgültige Lösung für Aktien O (n) Arbeit plus O (n) Arbeit ist, ist immer noch O (n) Arbeit.
So haben wir eine lineare Zeit Lösung für unser Problem.
Hat jeder verstehen diese Transformation?
>> Im Allgemeinen ist eine gute Idee, dass Sie sollten immer
wird versuchen, ein neues Problem, dass Sie sehen, zu reduzieren.
Wenn es wirkt vertraut für ein altes Problem,
versuchen, die Reduktion auf ein altes Problem.
Und wenn Sie können alle Tools, die Sie auf dem alten Problem verwendet
das neue Problem zu lösen.
So zu wickeln sind technische Interviews Herausforderung.
Diese Probleme sind wahrscheinlich einige der schwierigsten Probleme
dass Sie vielleicht in einem Interview zu sehen,
so, wenn Sie nicht verstehen, all die Probleme, die ich gerade bedeckt ist, ist es okay.
Dies sind einige der schwierigsten Probleme.
Üben, üben, üben.
Ich habe eine Menge Probleme in der Handreichung, so auf jeden Fall überprüfen die out.
Und viel Glück auf Ihrem Interviews. Alle meine Ressourcen werden unter diesem Link gepostet,
und einer meiner älteren Freunde hat angeboten, mock technischen Interviews zu tun,
Wenn Sie also interessiert sind, werden E-Mail Yao in diesem E-Mail-Adresse.
Wenn Sie Fragen haben, können Sie mich fragen.
Habt ihr spezielle Fragen im Zusammenhang mit technischen Interviews
oder irgendwelche Probleme, die wir bisher gesehen haben?
Okay. Nun, viel Glück auf Ihrem Interviews.
[CS50.TV]