[Powered by Google Translate] [Seminarium: Techniczne Wywiady]
[Kenny Yu, Harvard University]
[To jest CS50.] [CS50.TV]
Witam wszystkich, jestem Kenny. Jestem obecnie młodszy studiowania informatyki.
Jestem byłym CS TF, i chciałbym mieć to, kiedy byłem Underclassman,
i dlatego daję tym seminarium.
Więc mam nadzieję, że się spodoba.
To seminarium jest o technicznych wywiadów
i wszystkie moje zasoby można znaleźć pod tym linkiem,
ten link tutaj, kilka zasobów.
Więc zrobiłem listę problemów, faktycznie, sporo problemów.
Także ogólnie strona zasobów, gdzie możemy znaleźć wskazówki
jak przygotować się do rozmowy kwalifikacyjnej
wskazówek na temat tego, co należy zrobić w czasie rzeczywistym rozmowy,
, jak również w jaki sposób podejść do problemów i zasobów w przyszłości.
To wszystko online.
I właśnie do przedmowa tego seminarium, zrzeczenie się,
jak to nie powinno - przygotowań do rozmowy
nie powinna być ograniczona do tej listy.
To jest tylko ma być przewodnikiem,
i powinno się brać wszystko, co mówię z przymrużeniem oka,
ale również wykorzystać wszystko, co używane, aby pomóc Ci w przygotowaniu do rozmowy kwalifikacyjnej.
>> Zamierzam przyspieszyć zmianę kilku następnych slajdach
więc możemy dostać się do rzeczywistych studiów przypadków.
Struktura wywiadzie dla postion inżynierii oprogramowania,
zwykle jest to 30 do 45 minut,
kilka rund, w zależności od firmy.
Często będziesz kodowania na tablicy.
Więc jak to biała tablica, ale często w mniejszej skali.
Jeśli masz rozmowę telefoniczną, prawdopodobnie będziesz używać
albo collabedit lub Google Doc, aby mogli zobaczyć żyjesz kodowania
gdy jesteś przesłuchiwania przez telefon.
Wywiad sam w sobie jest zazwyczaj 2 lub 3 problemy
testuje swoją wiedzę informatyczną.
I to prawie na pewno obejmować kodowania.
Rodzaje pytań, na które będzie można zobaczyć zazwyczaj struktury danych i algorytmy.
I czyniąc tego rodzaju problemów,
poprosi cię, jak, to, co jest czas i złożoność przestrzeni, duży O?
Często również zapytać nadrzędne pytania
Tak więc, system projektowania,
jak można ułożyć swój kod?
Co interfejsy, jakie ćwiczenia, jakie moduły masz w systemie,
i jak one współdziałają ze sobą?
Więc struktury danych i algorytmy oraz systemy projektowania.
>> Kilka ogólnych wskazówek Zanim zagłębimy się w naszych studiach przypadku.
Myślę, że najważniejszą zasadą jest zawsze głośno myślę.
Wywiad ma być Twoja szansa, aby pokazać swój proces myślenia.
Punkt wywiadu jest wywiad, aby ocenić
jak myślisz i jak można przejść przez problem.
Najgorsze co można zrobić, to milczeć przez cały wywiad.
To po prostu nie jest dobre.
Kiedy dostaniesz pytanie, chcemy także upewnić się, że rozumiem pytanie.
Więc powtórzyć pytanie z powrotem własnymi słowami
i próba pracy gruntownych kilka prostych przypadków testowych
upewnić się, że rozumiem pytanie.
Praca przez kilka przypadków testowych udzielają też intuicję, w jaki sposób rozwiązać ten problem.
Można nawet odkryć kilka wzorców, które pomogą Ci rozwiązać problem.
Ich duża wskazówka jest nie denerwować.
Nie sfrustrowani.
Rozmowy są trudne, ale najgorsze, co można zrobić,
oprócz tego, że milczy, należy wyraźnie sfrustrowany.
Nie chcesz dać takie wrażenie na wywiad.
Jedna rzecz, że - tak, wiele osób, gdy idą do wywiadu,
próbują spróbować znaleźć najlepsze rozwiązanie pierwsze,
kiedy tak naprawdę, to zwykle rażąco oczywiste rozwiązanie.
To może być powolne, może być nieskuteczne, ale należy po prostu podać go,
tak więc masz punkt wyjścia, z którego można pracować lepiej.
Ponadto wskazuje się na rozwiązanie jest powolne, w zakresie
duża złożoność O lub złożoność przestrzeni,
będzie udowodnić, że rozumie ankietera
te kwestie podczas pisania kodu.
Więc nie bój się wymyślić najprostszym algorytmie
i lepiej tam.
Wszelkie pytania do tej pory? Okay.
>> Warto więc zagłębić się nasz pierwszy problem.
"Biorąc pod uwagę wartości całkowitych n, napisać funkcję tasuje tablicę
w miejscu takim, że wszystkie permutacje liczb całkowitych n są jednakowo prawdopodobne. "
I że masz dostępne losowy generator liczb całkowitych
który generuje liczbę całkowitą w zakresie od 0 do i, zakres pół.
Czy wszyscy rozumieją to pytanie?
Daję ci tablicę liczb całkowitych n, i chcę Ci Shuffle to.
W moim katalogu, napisałem kilka programów, aby wykazać, co mam na myśli.
Idę shuffle tablicę 20 elementów,
od -10 do +9,
i chcę Ci wyeksportować listę takiego.
Więc to jest mój posortowana tablica wejściowa, i chcę Ci Shuffle to.
Zrobimy to jeszcze raz.
Czy wszyscy rozumiem pytanie? Okay.
Więc to zależy od Ciebie.
Jakie są pomysły? Można to zrobić jak n ^ 2, n log n, n?
Otwarty na propozycje.
Okay. Więc jeden pomysł, zaproponowany przez Emmy,
jest najpierw obliczyć liczbę losową, losową liczbę całkowitą, w zakresie od 0 do 20.
Więc zakładamy nasza tablica ma długość 20.
W naszym schemacie 20 elementów,
to jest nasza tablica wejściowa.
I teraz, jej propozycja jest, aby utworzyć nową tablicę,
więc będzie tablicy wyjściowej.
I na podstawie i zwrócony przez rand -
więc gdybym był, powiedzmy, 17,
skopiować 17-gi element do pierwszej pozycji.
Teraz musimy usunąć - musimy przenieść wszystkie elementy tutaj
się tak, że mamy lukę na końcu i nie ma dziury w środku.
A teraz mamy powtórzyć proces.
Teraz możemy wybrać nowy losową liczbę całkowitą z przedziału od 0 do 19 lat.
Mamy nowy I tu, i skopiować ten element do tej pozycji.
Następnie przesunąć elementy nad i powtarzamy proces, aż mamy pełne nową tablicę.
Co to jest czas pracy tego algorytmu?
Cóż, brać pod uwagę wpływ tego.
Przenoszeni jesteśmy każdy element.
Gdy usuwamy to ja, my przenosimy wszystkie elementy po niej w lewo.
I to O (n) kosztów
bo co, jeśli usuwamy pierwszy element?
Więc dla każdego wyprowadzenia, usuwamy -
Każda przeprowadzka ponosi O (n) operacji,
a ponieważ mamy n przeprowadzki, prowadzi to do (n ^ 2) O shuffle.
Okay. Tak dobry start. Dobry początek.
>> Kolejna propozycja to użyć czegoś znanego jako shuffle Knuth,
lub Fisher-Yates shuffle.
I to jest rzeczywiście liniowy Shuffle czas.
A pomysł jest bardzo podobny.
Znowu mamy tablicę wejście,
ale zamiast dwóch tablic dla naszego wejścia / wyjścia,
używamy pierwszą część tablicy do śledzenia naszego przetasowana porcji
i śledzić, a potem zostawić resztę naszej tablicy na unshuffled porcji.
Więc tutaj jest to, co mam na myśli. Zaczniemy - mamy wyboru i,
tablicy od 0 do 20.
Nasz obecny wskaźnik jest skierowany do pierwszego indeksu.
Mamy do wyboru kilka i tu
a teraz zamienić.
Więc jeśli to było 5 i to było 4,
array końcowy będzie miał 5 Tu i 4 tutaj.
I teraz możemy zauważyć znacznik tutaj.
Wszystko na lewo jest wymieszane,
i wszystko, co do prawa jest unshuffled.
I teraz możemy powtórzyć proces.
Mamy do wyboru losowego indeksu pomiędzy 1 a 20 teraz.
Więc załóżmy, że nasz nowy i jest tutaj.
Teraz możemy zamienić to I z naszego aktualnego położenia nowego tutaj.
Więc robimy swapping iz powrotem jak ten.
Pozwól mi otworzyć kod, aby to bardziej konkretne.
Zaczynamy z naszego wyboru i -
zaczynamy i równa 0, możemy wybrać losowy j lokalizacji
w unshuffled części tablicy, i do n-1.
Więc jeśli jestem tutaj, wybrać losowy indeks pomiędzy tu i resztę tablicy,
i swap.
To jest cały kod niezbędny shuffle swoją tablicę.
Masz pytanie?
>> Cóż, trzeba było pytanie, dlaczego jest to prawidłowe?
Dlaczego każda permutacja jednakowo prawdopodobne?
I nie będzie przejść przez dowód tego,
ale wiele problemów w informatyce można udowodnić przez indukcję.
Jak wielu z was zna indukcji?
Okay. Cool.
Więc można udowodnić słuszność tego algorytmu przez prostą indukcję,
gdzie hipoteza indukcyjna byłoby zakładać, że
moja Shuffle zwraca każdy permutacji jednakowo prawdopodobne
do pierwszych elementów i.
Teraz rozważmy i + 1.
A przy okazji możemy wybrać nasz j indeks swap,
prowadzi to do - a potem opracować szczegóły,
co najmniej pełny dowód, dlaczego ten algorytm zwraca
każda permutacja z prawdopodobieństwem jednakowo prawdopodobne.
>> Dobra, następny problem.
Więc "podano tablicę liczb całkowitych, dodatnią, zero, ujemna,
napisać funkcję obliczającą maksymalną kwotę
każdego continueous subarray tablicy wejściowego ".
Przykładem jest, w przypadku, gdy wszystkie liczby są pozytywne,
następnie aktualnie najlepiej jest zabrać całą tablicę.
1, 2, 3, 4, jest równa 10.
Gdy masz jakieś negatywy w tam,
w tym przypadku chcemy tylko dwa pierwsze
ponieważ wybór -1 i / lub -3 przyniesie naszą sumę dół.
Czasami musimy zacząć w środku tablicy.
Czasami chcemy wybrać w ogóle nic, to najlepiej nie brać nic.
A czasem lepiej jest wziąć upadek,
bo coś po niej jest super duży. Więc jakieś pomysły?
(Student, niezrozumiały) >> Tak.
Załóżmy, że nie biorę -1.
Wtedy albo wybrać 1.000 i 20.000,
lub po prostu wybierz 3 miliardy.
Cóż, najlepiej jest podjąć wszystkie numery.
Ten -1, mimo że negatywny,
suma całości były lepsze niż nie podjąć -1.
Więc jednym z porad, o których wspomniałem wcześniej było określenie wyraźnie oczywiste
i brute force rozwiązanie pierwsze.
Co to jest brute force w rozwiązanie tego problemu? Tak?
[Jane] Cóż, myślę, że roztwór brute force
byłoby dodać wszystkie możliwe kombinacje (niezrozumiałe).
[Yu] Dobra. Więc pomysł Jane jest do podjęcia wszelkich możliwych -
Jestem parafrazując - jest do podjęcia wszelkich możliwych ciągłego subarray,
obliczyć jego sumę, a następnie podjąć maksymalnie wszystkie możliwe subarrays ciągłych.
Co jednoznacznie identyfikuje subarray w mojej tablicy wejściowej?
Podoba Ci się to, co dwie rzeczy są potrzebne? Tak?
(Student, niezrozumiały) >> Racja.
Dolna granica na indeksie i górnego indeksu związanego
jednoznacznie określa ciągły subarray.
[Studentka] Czy jesteśmy szacowania to tablica unikatowych numerów?
[Yu] No więc jej pytanie jest, czy my zakładając naszą tablicę -
to nasza tablica wszystkie unikatowe numery, a odpowiedź brzmi: nie.
>> Jeśli używamy naszej brutalnej rozwiązanie siłowe, to start / end indeksy
jednoznacznie określa nasz ciągły subarray.
Jeśli więc iteracyjne dla wszystkich możliwych pozycji startowych,
i wszystkich zapisów końcowych> lub = zacząć i <n,
można obliczyć sumę, a następnie bierzemy maksymalną kwotę widzieliśmy do tej pory.
Czy to jasne?
Co to jest duże O z tego rozwiązania?
Timewise.
Nie dość n ^ 2.
Zauważ, że iteracyjne od 0 do n,
tak że jest jeden dla pętli.
Mamy iteracyjne ponownie od prawie początku do końca, drugi dla pętli.
A teraz, w ciągu, musimy podsumować każdy wpis,
tak że jest inny dla pętli. Więc mamy trzy zagnieżdżone pętle, n ^ 3.
Okay. Wykracza to jako punkt wyjścia.
Nasze rozwiązanie jest nie gorsza niż n ^ 3.
Czy wszyscy rozumieją brute force rozwiązanie?
>> Okay. Lepszym rozwiązaniem jest użycie pomysł o nazwie programowanie dynamiczne.
Zażycie CS124, który jest Algorytmy i struktury danych,
zostaniesz bardzo dobrze zaznajomieni z tej techniki.
A pomysł, starają się budować rozwiązania mniejszych problemów w pierwszej kolejności.
Co mam na myśli to, ale aktualnie nie martwić się o dwie rzeczy: początek i koniec.
I to jest denerwujące. Co zrobić, jeśli możemy się pozbyć jednego z tych parametrów?
Jednym z pomysłów jest - jesteśmy podany nasz oryginalny problem,
znaleźć maksymalną wartość jakiejkolwiek subarray zakresu [O, N-1].
A teraz mamy nowy subproblem, gdzie wiemy, w naszym indeksu i,
wiemy, musimy stwierdzić, tam. Nasza subarray musi kończyć w bieżącym indeksie.
Więc pozostała problemem jest to, w którym powinniśmy zacząć naszą subarray?
Czy to ma sens? Okay.
Tak już zakodowane ten fakt, i spójrzmy, co to oznacza.
W codirectory, jest program o nazwie subarray,
i ma liczbę pozycji,
i zwraca maksymalną sumę subarray moim przetasowana listy.
Tak więc, w tym przypadku, to nasza ilość subarray 3.
I to podjęte tylko przy użyciu 2 i 1.
Przyjrzyjmy się jeszcze raz. To także 3.
Ale tym razem, zauważyć, jak dostaliśmy 3.
Wzięliśmy - my po prostu wziąć się 3
ponieważ jest otoczony z obu stron ujemnych,
który przyniesie suma <3.
Przyjrzyjmy się na 10 pozycji.
Tym razem jest to 7, bierzemy wiodącą 3 i 4.
Tym razem jest to 8, a my otrzymujemy, że, biorąc 1, 4 i 3.
Tak, aby dać Ci intuicji, w jaki sposób możemy rozwiązać ten przekształcił problem,
rzućmy okiem na subarray.
Jesteśmy biorąc pod uwagę ten parametr tablica i wiemy, że odpowiedź jest 8.
Bierzemy 1, 4 i 3.
Ale spójrzmy na to, jak tak naprawdę mam to odpowiedź.
Spójrzmy na maksymalnej subarray zakończonym na każdy z tych wskaźników.
Co jest, że maksymalna subarray musi kończy się na pierwszej pozycji?
[Student] Zero. >> Zero. Po prostu nie wziąć -5.
Tutaj to będzie 0, jak również. Tak?
(Student, niezrozumiały)
[Yu] Oh, przepraszam, to jest -3.
Więc to jest 2, to jest -3.
Okay. Więc -4, co maksymalna subarray zakończyć tę pozycję
gdzie -4 jest? Zero.
One? 1, 5, 8.
Teraz muszę kończyć w miejscu, gdzie jest na -2.
Tak 6, 5, 7, a ostatni z nich jest 4.
Wiedząc, że to są moje wpisy
dla przekształconej problemu gdzie muszę zakończyć na każdym z tych wskaźników,
wtedy moja ostateczna odpowiedź jest po prostu, wziąć rozmach całej,
i wziąć maksymalną liczbę.
Tak więc, w tym przypadku jest to 8.
Oznacza to, że ilość subarray kończy w tym indeksie
i zaczął gdzieś przed nim.
Czy wszyscy rozumieją ten przekształcił subarray?
>> Okay. Cóż, dowiedzieć się nawrót do tego.
Rozważmy tylko kilka pierwszych wpisów.
Więc o to, 0, 0, 0, 1, 5, 8.
A potem było -2, oraz że przyniósł go do 6.
Więc jeśli zadzwonię wpis w pozycji i subproblem (i),
jak można używać odpowiedź do poprzedniego subproblem
aby odpowiedzieć na to subproblem?
Gdy patrzę na, powiedzmy, ten wpis.
Jak mogę obliczyć odpowiedź 6 patrząc na
Połączenie tej tablicy i odpowiedź na poprzednie podzagadnień w tej tablicy? Tak?
[Studentka] wziąć tablicę kwot
w położeniu tuż przed nią, to 8
a następnie dodać bieżący subproblem.
[Yu] Więc jej sugestia jest patrzeć na tych dwóch liczb,
ta liczba, a ich liczba.
Więc to 8 odnosi się do odpowiedzi na subproblem (i - 1).
I nazwijmy mojej tablicy wejście A.
W celu znalezienia maksymalny subarray, który kończy się w pozycji I,
Mam dwie opcje: można albo kontynuować subarray
, który zakończył się na poprzednim indeksu, lub rozpocząć nową tablicę.
Jeśli miałbym kontynuować subarray które rozpoczęły się w poprzednim indeksie,
to maksymalna suma mogę osiągnąć to odpowiedź na poprzednie subproblem
oraz aktualna pozycja tablicy.
Ale ja też mam wybór rozpoczęciem nowego subarray,
w takim przypadku suma 0..
Więc odpowiedź jest max 0, subproblem i - 1, plus bieżąca pozycja tablicy.
Czy to nawrót sens?
Nasza nawrót, jak to właśnie odkrył, jest subproblem i
jest równa maksimum poprzedniej subproblem Plus mój bieżący wpis tablicy
co oznacza kontynuować dotychczasową subarray,
lub 0, rozpocząć nową subarray w moim obecnym indeksie.
I raz zbudowaliśmy tę tabelę rozwiązań, nasza ostateczna odpowiedź,
zrób liniowy zamiatać całej macierzy subproblem
i wziąć maksymalną liczbę.
To jest dokładna realizacja tego, co właśnie powiedział.
Więc tworzymy nową tablicę subproblem, podzagadnień.
Pierwsza pozycja to 0 albo pierwszy wpis, maksymalna z tych dwóch.
I dla pozostałych podzagadnień
używamy dokładnej powtórzeniu właśnie odkrył.
Teraz możemy obliczyć maksimum naszej tablicy podzagadnień, i to jest nasza ostateczna odpowiedź.
>> Więc ile miejsca mamy w tym przy użyciu algorytmu?
Jeśli tylko podjąć CS50, to może nie omówiono przestrzeń bardzo.
Cóż, jedna rzecz, należy stwierdzić, że zadzwoniłem malloc tutaj zn wielkości.
Co to proponuję dla ciebie?
Algorytm ten wykorzystuje przestrzeni liniowej.
Możemy zrobić lepiej?
Czy istnieje coś, co można zauważyć, że nie jest konieczne, aby obliczyć ostateczną odpowiedź?
Chyba lepiej pytanie, jakie informacje
nie musimy przeprowadzić przez całą drogę do końca?
Teraz, jeśli spojrzymy na te dwie linie,
interesują nas tylko poprzedniego subproblem,
a my tylko dbamy o maksimum jakie widzieliśmy do tej pory.
Aby obliczyć naszą ostateczną odpowiedź, że nie potrzebujemy całej tablicy.
Musimy tylko ostatni numer, ostatnie dwie cyfry.
Ostatni numer na tablicy subproblem i numer ostatniego dla maksimum.
Tak więc, w rzeczywistości można razem łączą te pętle
i przejść z przestrzeni liniowej do stałego miejsca.
Ta suma dotychczas, tu zastępuje rolę subproblem, naszej tablicy subproblem.
Więc prąd suma, jak dotąd, jest odpowiedzią na poprzedni subproblem.
Oraz że suma, do tej pory, zajmuje miejsce naszego max.
Obliczamy maksymalnie jak iść.
I tak przechodzimy od przestrzeni liniowej do stałej przestrzeni,
i mamy także liniową rozwiązanie naszego problemu subarray.
>> Tego rodzaju pytania będzie można uzyskać podczas rozmowy kwalifikacyjnej.
Co to jest złożoność, co to jest złożoność przestrzeń?
Można to zrobić lepiej? Czy są rzeczy, które są potrzebne do utrzymania w pobliżu?
Zrobiłem to, aby podświetlić analiz, które należy wykonać na własną rękę
jak pracujesz przez te problemy.
Zawsze się zastanawiasz: "Czy mogę to zrobić lepiej?"
W rzeczywistości, można zrobić lepiej?
Rodzaju podchwytliwe pytanie. Nie można, bo trzeba
przeczytać przynajmniej wejście do problemu.
Tak więc fakt, że należy przeczytać przynajmniej wejście problemu
Oznacza to, że nie można zrobić lepiej niż czasu linearnego,
i nie można zrobić lepiej niż stałego miejsca.
Jest to więc w rzeczywistości, najlepszym rozwiązaniem tego problemu.
Pytania? Okay.
>> Problem giełdzie:
"Biorąc pod uwagę wartości całkowitych n, dodatnie, zerowe lub ujemne,
które reprezentują cenę zapasów na dzień n,
napisać funkcję do obliczania maksymalnych zysków można dokonać
zważywszy, że można kupić i sprzedać dokładnie 1 akcji w tych n dni. "
Zasadniczo, chcemy kupić niskie, sprzedać drogo.
I chcemy, aby dowiedzieć się najlepsze zysku możemy zrobić.
Wracając do mojej końcówki, co jest od razu jasne, najprostsza odpowiedź, ale to jest wolny?
Tak? (Student, niezrozumiały) >> Tak.
>> Więc możesz sobie iść, choć i spojrzeć na ceny akcji
na każdy punkt w czasie, (niezrozumiałe).
[Yu] Okay, więc jej rozwiązanie - jej propozycja informatyki
Najniższa i najwyższa obliczenia niekoniecznie pracować
ponieważ może wystąpić przed najwyższy najniższy.
Więc co to jest brute force rozwiązanie tego problemu?
Jakie są dwie rzeczy, które trzeba jednoznacznie określić zysk daję? Racja.
Brute force jest rozwiązanie - oh, tak, propozycja Jerzego jest musimy tylko dwa dni
, aby jednoznacznie ustalić wynik tych dwóch dni.
Więc obliczyć każdą parę, jak kupić / sprzedać,
obliczyć zyski, które mogą być ujemne lub dodatnie lub zero.
Oblicz maksymalny zysk, że robimy po iterowanie wszystkich par dni.
To będzie nasza ostateczna odpowiedź.
Oraz że rozwiązanie będzie O (n ^ 2), ponieważ nie jest n wybrać dwie pary -
z dni, które można wybierać spośród dni końcowych.
Ok, więc nie mam zamiaru iść na brutalnej siły rozwiązanie tutaj.
I powiem ci, że istnieje n log n roztwór.
Jaki algorytm masz obecnie wiadomo, że jest n log n?
To nie jest podchwytliwe pytanie.
>> Scalanie sortowania. Scalanie sortowania jest n log n,
i faktycznie, jednym ze sposobów rozwiązania tego problemu jest użycie
rodzaj sort merge idei nazywa, w ogóle, dziel i rządź.
Pomysł i jest w następujący sposób.
Chcesz obliczyć najlepszą kupić / sprzedać parę w lewej połowie.
Znajdź najlepsze zyski można dokonać, tylko z pierwszym n ciągu dwóch dni.
Potem chcesz oompute najlepsze kupić / sprzedać parę na prawej połowie,
tak ostatnio n na dwa dni.
I teraz pytanie, w jaki sposób połączyć te rozwiązania, wraz z powrotem?
Tak? (Student, niezrozumiały)
>> Okay. Więc pozwól mi narysować obrazek.
Tak? (George, niezrozumiały)
>> Dokładnie. Rozwiązanie Jerzego jest dokładnie prawo.
Więc jego propozycja jest najpierw wylicza najlepszy kupić / sprzedać parę,
i że występuje w lewej połowie, tak nazwijmy, że w lewo, w lewo.
Najlepiej kupić / sprzedać parę, która występuje w prawej połowie.
Ale jeśli tylko porównać te dwie liczby, brakuje nam sprawę
gdzie tu kupić i sprzedać gdzieś w prawej połowie.
Kupujemy w lewej połowie, sprzedawać w prawej połowie.
A najlepszym sposobem, aby obliczyć najlepszą kupić / sprzedać parę, która obejmuje obie połówki
jest obliczenie minimum tutaj i obliczyć maksymalną tutaj
i biorą ich różnicę.
Więc dwóch przypadkach, gdzie kupić / sprzedać parę występuje tylko tutaj,
tylko tu, lub na obu połówkach jest określone przez te trzy numerów.
Więc nasz algorytm scalić nasze rozwiązania wraz z powrotem,
chcemy obliczyć najlepszą kupić / sprzedać parę
gdzie kupić na lewym pół i sprzedać na prawej połowie.
A najlepszym sposobem na to jest do obliczenia najniższą cenę w pierwszym półroczu,
Najwyższa cena w prawej połowie, i wziąć ich różnicę.
Powstały trzy zyski, te trzy numery, można podjąć maksymalnie trzech,
i jest to najlepszy wynik można zrobić w ciągu tych pierwszych dni i koniec.
Tutaj ważne linie są w kolorze czerwonym.
Jest to wywołanie rekurencyjne obliczyć odpowiedź w lewej połowie.
Jest to wywołanie rekurencyjne obliczyć odpowiedź w prawej połowie.
Te dwie pętle obliczyć min i max na pół lewej i prawej.
Teraz obliczyć zysk, który obejmuje obie połówki,
i końcowy jest maksymalna odpowiedź z tych trzech.
Okay.
>> Tak, na pewno, mamy algorytm, ale większe pytanie,
co to jest złożoność tego?
I dlatego wspomniałem sortowanie korespondencji seryjnej, że ta forma dzielenia odpowiedź
na dwie części, a następnie łączenia naszych rozwiązań wraz z powrotem
jest dokładnie formą sortowania korespondencji seryjnej.
Więc pozwól mi przejść przez okres.
Jeżeli określony w funkcji n (t) jest liczba etapów
na dzień n,
nasze dwa połączenia rekurencyjne
są każdy będzie kosztować T (n / 2),
i nie dwa z tych połączeń.
Teraz trzeba obliczyć minimum lewej części,
co mogę zrobić w n / 2 godziny, plus maksymalnie prawej połowie.
Więc jest to po prostu n.
A następnie oraz pewnej stałej pracy.
I to równanie nawrotu
jest dokładnie równanie nawrotów sortowanie korespondencji seryjnej.
A wszyscy wiemy, że sort merge log n n czas.
Dlatego nasz algorytm jest również n log n godzinę.
Czy to iteracja sens?
Tylko krótkie podsumowanie tego:
T (N) to ilość stopni w celu obliczenia maksymalnej zysk
w ciągu dni, n.
Sposób podzieliliśmy nasze rekurencyjnych wywołań
jest wywołanie nasze rozwiązanie na pierwszych n / 2 dni,
tak że jest jedno połączenie,
a potem zadzwonić ponownie na drugiej połowie.
Więc to dwa zaproszenia.
I wtedy możemy znaleźć minimum na lewej połowie, co możemy zrobić w czasie liniowym,
znaleźć maksymalnie prawej połowie, co możemy zrobić w czasie liniowym.
Tak n / 2 + N / 2 jest tylko N.
Następnie mamy jakąś stałą pracę, która jest jak arytmetyki.
Równanie to nawrót jest dokładnie równanie nawrotów sortowanie korespondencji seryjnej.
Stąd nasz algorytm shuffle jest także n log n.
Więc ile miejsca mamy przy użyciu?
Wróćmy do kodu.
>> Lepsze pytanie, ile ramek stosu mamy kiedykolwiek w danym momencie?
Ponieważ używamy rekurencji,
liczba ramek stosu określa nasz wykorzystania przestrzeni.
Rozważmy n = 8.
Wzywamy shuffle 8,
która wywoła shuffle pierwszych czterech wjazdów,
które nazywamy shuffle pierwszych dwóch pozycji.
Więc nasz stack jest - to jest nasz stos.
I wtedy nazywamy shuffle, ponownie 1,
i to, co w naszym przykładzie jest podstawa, więc natychmiast.
Czy kiedykolwiek mieć więcej niż to wiele ramek stosu?
Nie, ponieważ za każdym razem robimy inwokację,
recursive inwokacja do shuffle
dzielimy naszą wielkość w połowie.
Tak więc maksymalną ilość klatek stosu kiedykolwiek mają w danym momencie
jest na zlecenie dziennika n stos ramek.
Każda ramka stosu ma stałą przestrzeń,
a zatem całkowita ilość miejsca,
maksymalną ilość miejsca, jakie kiedykolwiek użyć jest O (log n) przestrzeń
w którym n oznacza liczbę dni.
>> Teraz, zawsze należy zadać sobie pytanie: "Czy możemy zrobić lepiej?"
A w szczególności, możemy zmniejszyć to na problem mamy już rozwiązany?
Podpowiedź: tylko omówiła dwa inne problemy przed tym, i nie będzie to shuffle.
Możemy przekształcić ten problem giełdowe do maksymalnej problemu subarray.
W jaki sposób możemy to zrobić?
Jeden z was? Emmy?
(Emmy, niezrozumiały)
[Yu] Dokładnie.
Więc maksymalnej problemu subarray,
szukamy sumy w ciągłym subarray.
Emmy i sugestia jest dla problemu zasobów,
rozważyć zmiany, lub delty.
I obraz jest - to jest cena akcji,
ale jeśli wzięliśmy różnicę pomiędzy każdy kolejny dzień -
Widzimy zatem, że maksymalna cena, maksymalny zysk moglibyśmy
jest, jeśli kupimy tutaj i sprzedać tutaj.
Ale spójrzmy na ciągły - spójrzmy na problem subarray.
Więc tutaj, możemy - idąc stąd dotąd,
mamy pozytywne zmiany, a następnie przechodząc stąd tutaj mamy negatywny zmianę.
Ale potem się stąd tutaj mamy ogromne pozytywne zmiany.
I są to zmiany, które chcemy zsumować, aby nasz ostateczny zysk.
Wtedy mamy więcej negatywnych zmian tutaj.
Kluczem do redukcji zapasów naszego problemu do naszej maksymalnej problemu subarray
jest rozważenie delty między dzień.
Więc tworzymy nową tablicę o nazwie delty,
zainicjować pierwszy wpis do 0,
, a następnie dla każdej delta (i), które pozwalają się różnica
z moja tablica wejściowa (i), i tablicy (i - 1).
Wtedy nazywamy naszą rutynową procedurę dla maksymalnej subarray
przechodzącą w tablicy A Delta.
A ponieważ ilość subarray jest liniowy czas,
i zmniejszenie to ten proces tworzenia tego delta tablicę,
jest również czas liniowy,
następnie końcowy roztwór do zasobów jest O (n) oraz pracy O (n) pracy, jest nadal O (n) pracy.
Mamy więc rozwiązanie liniowego czasu do naszego problemu.
Czy wszyscy rozumieją tę transformację?
>> W ogóle, to dobry pomysł, że zawsze należy mieć
jest spróbować zmniejszyć nowy problem, który widzisz.
Jeśli wygląda znajomo do starego problemu,
spróbuj zmniejszyć go do starego problemu.
I jeśli można użyć wszystkich narzędzi, które zostały zamieszczone na stary problem
rozwiązać nowy problem.
Tak, aby zakończyć, techniczne wywiady są wyzwaniem.
Problemy te są prawdopodobnie niektóre problemy trudniejszych
, które można zobaczyć w wywiadzie,
więc jeśli nie rozumiesz wszystkich problemów, które po prostu uwzględnione, to w porządku.
Są to niektóre z problemów, bardziej ambitnych.
Praktyka, praktyka, praktyka.
Dałem dużo problemów w materiałach informacyjnych, więc na pewno ci się sprawdzić.
I powodzenia na swoich wywiadów. Wszystkie moje zasoby są wywieszone w ten link,
i jeden z moich starszych przyjaciół zaproponował zrobić mock technicznych wywiadów,
więc jeśli jesteś zainteresowany, e-mail będzie Yao w tym adresu e-mail.
Jeżeli masz jakieś pytania, możesz mnie zapytać.
Czy faceci mają konkretne pytania dotyczące technicznych wywiadów
lub jakieś problemy, które widzieliśmy do tej pory?
Okay. Powodzenia na swoich wywiadów.
[CS50.TV]