[Powered by Google Translate] [Seminario: Interviste tecnici]
[Kenny Yu, Harvard University]
[Questo è CS50.] [CS50.TV]
Ciao a tutti, io sono Kenny. Sono attualmente una scienza giovane computer di studiare.
Sono un ex CS TF, e vorrei avere questo quando ero un Underclassman,
ed è per questo che sto dando questo seminario.
Quindi spero che vi piaccia.
Questo seminario è di colloqui tecnici,
e tutte le mie risorse si possono trovare a questo link,
questo link qui, un paio di risorse.
Così ho fatto una lista di problemi, in realtà, non pochi problemi.
Anche una pagina di risorse in cui si possono trovare le punte
su come prepararsi per un colloquio,
consigli su cosa si dovrebbe fare durante un colloquio vero e proprio,
e come affrontare i problemi e le risorse per riferimento futuro.
E 'tutto on-line.
E proprio far precedere questo seminario, un disclaimer,
in questo modo non dovrebbe - la vostra preparazione intervista
non dovrebbe essere limitato a questa lista.
Questo il solo scopo di essere una guida,
e si dovrebbe dare tutto quello che dico con un grano di sale,
ma anche utilizzare tutto quello che ho usato per aiutarvi nella vostra preparazione intervista.
>> Io vado a scorrere più velocemente le prossime diapositive
in modo che possiamo arrivare a casi di studio reali.
La struttura di un colloquio per un postion ingegneria del software,
di solito è 30 a 45 minuti,
più cicli, a seconda della compagnia.
Spesso sarete codifica su un bordo bianco.
Quindi un bordo bianco come questo, ma spesso su scala minore.
Se hai un colloquio telefonico, probabilmente sarete utilizzando
sia collabedit o un documento di Google in modo che possano vederti Live Coding
mentre si sta intervistato al telefono.
Un intervista stessa è in genere 2 o 3 problemi
prova la tua conoscenza informatica.
E sarà quasi sicuramente coinvolgere codifica.
I tipi di domande che vedrete sono in genere strutture di dati e algoritmi.
E nel fare questo tipo di problemi,
che vi chiederà, come, che cosa è il tempo e la complessità dello spazio, grande O?
Spesso chiedono anche di livello superiore domande,
così, la progettazione di un sistema,
come è possibile definire il layout del codice?
Quali interfacce, quali classi, quali moduli non avete nel vostro sistema,
e come questi interagiscono tra loro?
Quindi strutture dati e algoritmi e sistemi di progettazione.
>> Alcuni consigli generali Prima di tuffarci in per i nostri case study.
Credo che la regola più importante è essere sempre pensando ad alta voce.
L'intervista dovrebbe essere la tua occasione per mostrare il vostro processo di pensiero.
Il punto del colloquio è per l'intervistatore di valutare
come si pensa e come si passa attraverso un problema.
La cosa peggiore che puoi fare è rimanere in silenzio durante tutta l'intervista.
E 'solo non va bene.
Quando si è data una domanda, anche voi volete essere sicuri di capire la domanda.
Quindi ripeto la domanda di ritorno con parole tue
e tentare di lavorare approfonditi alcuni casi di test semplici
per essere sicuri di capire la domanda.
Grazie alla collaborazione di un paio di casi di test vi darà anche l'intuizione su come risolvere questo problema.
Si potrebbe anche scoprire alcuni modelli per aiutarti a risolvere il problema.
La loro punta grande è quello di non ottenere frustrati.
Non frustrato.
Le interviste sono impegnativi, ma la cosa peggiore che si può fare,
oltre ad essere silenzioso, deve essere visibilmente frustrati.
Non si vuole dare questa impressione di un intervistatore.
Una cosa che - così, molte persone, quando vanno in una intervista,
tentativo per cercare di trovare la soluzione migliore prima,
quando in realtà, di solito c'è una soluzione lampante.
Potrebbe essere lenta, potrebbe essere inefficiente, ma si dovrebbe semplicemente indicare,
in modo da avere un punto di partenza da cui partire per lavorare meglio.
Inoltre, indicando la soluzione è lento, in termini di
O grande complessità tempo e la complessità dello spazio,
dimostrerà all'intervistatore di aver capito
questi problemi durante la scrittura del codice.
Quindi non abbiate paura di venire con il più semplice primo algoritmo
e poi lavorare meglio da lì.
Tutte le domande fino ad ora? Va bene.
>> Quindi cerchiamo di tuffarsi nel nostro primo problema.
"Dato un array di interi n, scrivere una funzione che mescola la matrice
sul posto in modo tale che tutte le permutazioni degli interi n siano equiprobabili. "
E suppone che si abbia a disposizione un generatore casuale di numeri interi
che genera un numero intero nell'intervallo da 0 a I, a metà scala.
Ha tutti a capire questa domanda?
Vi do un array di interi n, e voglio che tu lo shuffle.
Nella mia directory, ho scritto alcuni programmi per dimostrare quello che voglio dire.
Ho intenzione di mescolare un array di 20 elementi,
da -10 a +9,
e voglio che per produrre una lista come questa.
Quindi questa è la mia matrice di input ordinato, e voglio che tu lo shuffle.
Lo faremo di nuovo.
Ha tutti capito la domanda? Va bene.
Quindi sta a voi.
Quali sono alcune idee? Puoi farlo come n ^ 2, n log n, n?
Aperto ai suggerimenti.
Va bene. Così un idea, suggerita da Emmy,
è prima calcolare un numero casuale, intero casuale, in un intervallo da 0 a 20.
Quindi assumere la nostra gamma ha una lunghezza di 20.
Nel nostro diagramma di 20 elementi,
questa è la nostra matrice di input.
E ora, il suo suggerimento è quello di creare un nuovo array,
quindi questa sarà la matrice di output.
E sulla base di l'i restituito da rand -
quindi se mi è stato, diciamo, 17,
copiare l'elemento 17a nella prima posizione.
Ora abbiamo bisogno di eliminare - abbiamo bisogno di spostare tutti gli elementi qui
sopra in modo da avere uno spazio alla fine e senza fori nel mezzo.
E ora si ripete il processo.
Ora scegliere un nuovo numero intero casuale compreso tra 0 e 19.
Abbiamo un nuovo io qui, e copiamo questo elemento in questa posizione.
Poi ci spostiamo oggetti più e si ripete il processo fino a quando abbiamo la nostra gamma completa nuova.
Qual è il tempo di esecuzione di questo algoritmo?
Bene, prendiamo in considerazione l'impatto di questo.
Stiamo spostando ogni elemento.
Quando si rimuove questo i, stiamo spostando tutti gli elementi dopo a sinistra.
E questo è un O (n) costo
perché quello che se togliamo il primo elemento?
Così, per ogni prelievo, togliamo -
ogni rimozione costa O (n) operazioni,
e dal momento che abbiamo n traslochi, questo porta ad un (n ^ 2) O casuale.
Va bene. Quindi buon inizio. Buon inizio.
>> Un altro suggerimento è quello di usare qualcosa di noto come il riordino Knuth,
o il Fisher-Yates shuffle.
Ed è in realtà un riordino tempo lineare.
E l'idea è molto simile.
Ancora una volta, abbiamo la nostra matrice di input,
ma invece di utilizzare due array per il nostro ingresso / uscita,
usiamo la prima porzione della matrice per tenere traccia della nostra porzione mescolate,
e teniamo traccia, e poi lasciare il resto della nostra gamma per la parte unshuffled.
Quindi, ecco quello che voglio dire. Iniziamo con - abbiamo scelto una i,
un array da 0 a 20.
La nostra corrente del puntatore punta al primo indice.
Abbiamo scelto un po 'di qui i
e ora ci scambiamo.
Quindi, se questo era il 5 e questo era 4,
la matrice risultante avrà 5 qui e 4 qui.
E ora si nota un marcatore qui.
Tutto a sinistra viene mescolato,
e tutto a destra è unshuffled.
E ora siamo in grado di ripetere il processo.
Abbiamo scelto un indice casuale compreso tra 1 e 20 ora.
Supponiamo che il nostro nuovo i è qui.
Ora ci scambiamo questo i con la nostra attuale posizione di nuovo qui.
Quindi facciamo un scambiare avanti e indietro in questo modo.
Permettetemi di richiamare il codice per renderlo più concreto.
Si comincia con la nostra scelta di i -
partiamo con i uguale a 0, si sceglie un luogo a caso j
nella porzione unshuffled della matrice, i a n-1.
Quindi, se sono qui, scegliere un indice casuale tra qui e il resto della matrice,
e ci scambiamo.
Questo è tutto il codice necessario per mischiare l'array.
Hai ancora domande?
>> Bene, una domanda è necessario, perché è corretto?
Perché ogni permutazione stessa probabilità?
E non passerà attraverso la prova di questo,
ma molti problemi in informatica può essere dimostrato attraverso l'induzione.
Quanti di voi hanno familiarità con l'induzione?
Va bene. Cool.
Così si può dimostrare la correttezza di questo algoritmo per induzione semplice,
in cui la tua ipotesi di induzione sarebbe, supporre che
il mio casuale restituisce ogni permutazione equiprobabili
fino agli elementi in primo luogo ho.
Ora, si consideri i + 1.
E dal modo in cui scegliere il nostro indice j per scambiare,
questo porta a - e poi definire i dettagli,
almeno una prova completa del perché questo algoritmo restituisce
ogni permutazione con probabilità la stessa probabilità.
>> Va bene, problema successivo.
Così "dato un array di interi, postive, zero, negativo,
scrivere una funzione che calcola la somma massima
di qualsiasi sottomatrice continueous della matrice di input. "
Qui è un esempio, nel caso in cui tutti i numeri sono positivi,
quindi attualmente la scelta migliore è quella di prendere l'intera matrice.
1, 2, 3, 4, è uguale a 10.
Quando si dispone di alcuni aspetti negativi in ​​là,
in questo caso si vogliono solo i primi due
perché la scelta -1 e / o -3 porterà la nostra somma verso il basso.
A volte potrebbe essere necessario avviare al centro della matrice.
A volte ci vuole scegliere niente, ma è meglio non prendere nulla.
E a volte è meglio prendere la caduta,
perché la cosa dopo che è super grande. Quindi, tutte le idee?
(Studente, incomprensibile) >> Si '.
Supponiamo che io non prendo -1.
Allora o scelgo 1.000 e 20.000,
o mi basta scegliere i 3 miliardi di euro.
Beh, la scelta migliore è quella di prendere tutti i numeri.
Questo -1, pur essendo negativi,
l'intera somma è meglio che non fossi a prendere -1.
Così uno dei consigli che ho menzionato in precedenza è stato quello di indicare la chiaramente evidente
e la soluzione di forza bruta prima.
Qual è la soluzione di forza bruta in questo problema? Si '?
[Jane] Beh, credo che la soluzione di forza bruta
sarebbe quella di aggiungere a tutte le combinazioni possibili (incomprensibile).
[Yu] Ok. Così Jane idea è quella di prendere ogni possibile precauzione -
Sto parafrasando - è quello di prendere ogni subarray possibile, continua,
calcolare la somma, e poi prendere il massimo di tutti i sottoarray possibili continue.
Ciò che identifica in modo univoco una sottomatrice nel mio array di input?
Quali, due cose ho bisogno? Si '?
(Studente, incomprensibile) destra >>.
Un limite inferiore per l'indice e un indice limite superiore
determina univocamente una sottomatrice continuo.
[Studentessa] Stiamo stimando che è un array di numeri unici?
[Yu] No. Quindi la domanda è, stiamo assumendo le nostre offerte -
è la nostra matrice di tutti i numeri unici, e la risposta è no.
>> Se usiamo la nostra soluzione di forza bruta, quindi di inizio / fine indici
determina univocamente il nostro subarray continuo.
Quindi, se iterare per tutte le voci di avvio possibili,
e per tutte le voci finali> o = per iniziare, e <n,
si calcola la somma, e poi prendiamo la somma massima che abbiamo visto finora.
E 'chiaro?
Qual è la grande O di questa soluzione?
TimeWise.
Non proprio n ^ 2.
Si noti che l'iterazione da 0 a n,
così che è uno per ciclo.
Siamo di nuovo scorrere da quasi dall'inizio alla fine, un altro ciclo for.
E ora, al suo interno, dobbiamo riassumere ogni voce,
quindi questo è un altro ciclo for. Quindi abbiamo tre cicli for nidificati, n ^ 3.
Va bene. Questo va come punto di partenza.
La nostra soluzione non è peggiore di n ^ 3.
Ha capire a tutti la soluzione di forza bruta?
>> Va bene. Una soluzione migliore è usando un concetto chiamato programmazione dinamica.
Se si prende CS124, che è Algoritmi e Strutture Dati,
si diventa molto familiare con questa tecnica.
E l'idea è, cercare di costruire soluzioni ai problemi più piccoli per primi.
Quello che voglio dire con questo è, al momento non abbiamo preoccuparsi di due cose: di inizio e fine.
E questo è fastidioso. E se riusciva a liberarsi di uno di questi parametri?
Un'idea è quella di - siamo dato il nostro problema originale,
trovare la somma massima di ogni subarray in un intervallo [O, n-1].
E ora abbiamo un sottoproblema in cui sappiamo, nel nostro indice corrente i,
sappiamo che dobbiamo concludere lì. Il nostro subarray deve terminare in corrispondenza dell'indice corrente.
Quindi il problema che rimane è, da dove iniziamo il nostro sottomatrice?
Questo ha senso? Va bene.
Così ho codificato questo, e diamo un'occhiata a ciò che questo significa.
Nel codirectory, c'è un programma chiamato sottoarray,
e prende il numero di elementi,
e restituisce la somma massima sottoarray nella mia lista mescolate.
Quindi, in questo caso, la sottomatrice massima è 3.
E che ha preso da solo utilizzando 2 e 1.
Facciamo funzionare ancora. E 'anche 3.
Ma questa volta, si noti come abbiamo ottenuto il 3.
Abbiamo preso il - dobbiamo prendere il 3 stesso
perché è circondato da negativi su entrambi i lati,
che porterà una somma <3.
Corriamo su 10 elementi.
Questa volta è 7, prendiamo il principale 3 e 4.
Questa volta è 8, e si ottiene che prendendo 1, 4 e 3.
Quindi, per dare un'intuizione su come possiamo risolvere questo problema trasformato,
diamo uno sguardo a questo sottoarray.
Siamo in questa matrice di input, e sappiamo che la risposta è 8.
Prendiamo l'1, 4, e 3.
Ma diamo un'occhiata a come in realtà abbiamo ottenuto la risposta.
Guardiamo il sottoarray massimo che si è conclusa a ciascuno di questi indici.
Qual è la sottomatrice massima che deve terminare in prima posizione?
[Studente] Zero. Zero >>. Basta non prendere il -5.
Qui sta andando a 0 pure. Si '?
(Studente, incomprensibile)
[Yu] Oh, mi dispiace, è un -3.
Quindi questo è un 2, questo è un -3.
Va bene. Quindi -4, qual è il sottoarray massima per terminare quella posizione
dove è -4 a? Zero.
Uno? 1, 5, 8.
Ora, deve terminare nel punto in cui è -2 a.
Quindi 6, 5, 7, e l'ultimo è 4.
Sapendo che queste sono le mie voci
per il problema trasformato dove mi scade a ciascuno di questi indici,
allora la mia risposta definitiva è solo, prendere un spazzano,
e prendere il numero massimo.
Quindi in questo caso è 8.
Questo implica che il subarray massima termina a questo indice,
e ha iniziato da qualche parte prima di esso.
Ha capire a tutti questa sottomatrice trasformata?
>> Va bene. Bene, cerchiamo di capire la ricorrenza per questo.
Prendiamo in considerazione solo le prime voci.
Così qui era 0, 0, 0, 1, 5, 8.
E poi c'era un -2 qui, e che ha portato fino a 6.
Quindi, se io chiamo la voce nella posizione i sottoproblema (i),
come posso utilizzare la risposta ad un sottoproblema precedente
per rispondere a questa sottoproblema?
Se guardo, diciamo, questa voce.
Come faccio a calcolare la risposta 6, cercando in
una combinazione di questo array e le risposte a sottoproblemi precedenti in questo array? Sì?
[Studentessa] Si prende la matrice delle somme
nella giusta posizione prima, così l'8,
e poi si aggiunge il sottoproblema corrente.
[Yu] Così il suo suggerimento è quello di guardare a questi due numeri,
questo numero e questo numero.
Quindi questo 8 si riferisce alla risposta per il sottoproblema (i - 1).
E diciamo la mia A. matrice di input
Per trovare una sottomatrice massimo che termina nella posizione i,
Ho due scelte: io posso scegliere se continuare il sottoarray
che si è conclusa in corrispondenza dell'indice precedente, o iniziare un nuovo array.
Se dovessi continuare il sottoarray che è iniziato in corrispondenza dell'indice precedente,
allora la somma massima che può raggiungere è la risposta alla precedente sottoproblema
più la voce matrice corrente.
Ma, ho anche la scelta di iniziare una sottomatrice nuovo,
nel qual caso la somma è 0.
Quindi la risposta è massima di 0, sottoproblema i - 1, più la voce matrice corrente.
Ha questa ricorrenza ha senso?
La ricorrenza, come abbiamo appena scoperto, è sottoproblema i
è pari al massimo del sottoproblema precedente più il mio ingresso corrente di matrice,
il che significa continuare il subarray precedente,
o 0, avviare una sottomatrice nuova al mio indice corrente.
E una volta che abbiamo costruito questa tabella di soluzioni, allora la nostra risposta definitiva,
basta fare una scansione lineare su tutta la matrice sottoproblema
e prendere il numero massimo.
Si tratta di una implementazione esatta di quello che ho appena detto.
Quindi creare un nuovo array sottoproblema, sottoproblemi.
La prima voce è 0 o la prima voce, il massimo di quei due.
E per il resto dei sottoproblemi
usiamo la ricorrenza esatta abbiamo appena scoperto.
Ora si calcola il massimo della nostra matrice sottoproblemi, e questa è la nostra risposta definitiva.
>> Quindi, quanto spazio stiamo usando in questo algoritmo?
Se hai solo preso CS50, allora si potrebbe non aver discusso molto spazio.
Beh, una cosa da notare è che ho chiamato qui con malloc dimensione n.
Che cosa suggerisce?
Questo algoritmo utilizza lo spazio lineare.
Possiamo fare di meglio?
C'è qualcosa che ti accorgi che non è necessaria per calcolare la risposta definitiva?
Credo che una domanda migliore è, quali informazioni
Non abbiamo bisogno di portare tutta la strada fino alla fine?
Ora, se guardiamo a queste due linee,
ci interessa solo il sottoproblema precedente,
e che ci interessa solo il massimo che abbiamo mai visto finora.
Per calcolare la nostra risposta definitiva, non abbiamo bisogno di tutto l'array.
Abbiamo solo bisogno l'ultimo numero, ultimi due numeri.
Ultimo numero per l'array sottoproblema, e ultimo numero per il massimo.
Così, infatti, si può fondere insieme queste anse
e passare dallo spazio lineare spazio costante.
Somma di corrente fino ad ora, qui, sostituisce il ruolo dei sottoproblemi, la nostra gamma sottoproblema.
Somma Quindi corrente, fino ad ora, è la risposta al sottoproblema precedente.
E tale somma, fino ad ora, prende il posto del nostro max.
Calcoliamo il massimo come andiamo avanti.
E così si passa da uno spazio lineare di spazio costante,
e abbiamo anche una soluzione al nostro problema lineare subarray.
>> Questi tipi di domande che si ottiene nel corso di un'intervista.
Qual è la complessità temporale, ciò che è la complessità spazio?
Puoi fare di meglio? Ci sono cose che non sono necessari per mantenere in giro?
Ho fatto questo per evidenziare le analisi che si dovrebbe prendere da solo
come si sta lavorando con questi problemi.
Sempre essere se stessi chiedendo: "Posso fare di meglio?"
In effetti, si può fare di meglio?
Una specie di domanda trabocchetto. Non è possibile, perché è necessario
almeno leggere l'input al problema.
Quindi il fatto che avete bisogno di almeno leggere l'input al problema
significa che non si può fare meglio di un tempo lineare,
e non si può fare meglio di spazio costante.
Quindi questo è, infatti, la migliore soluzione a questo problema.
Domande? Va bene.
>> Borsa problema:
"Dato un array di interi n, positivo, zero, o negativo,
che rappresentano il prezzo di uno stock in n giorni,
scrivere una funzione per calcolare il profitto massimo che si può fare
dato che si comprano e vendono esattamente 1 magazzino all'interno di questi n giorni. "
In sostanza, vogliamo comprare a poco, vendere alto.
E vogliamo capire il miglior risultato che possiamo fare.
Tornando al mio suggerimento, qual è il subito chiaro, risposta più semplice, ma è lento?
Sì? (Studente, incomprensibile) >> sì.
>> Quindi sarebbe andato comunque e guardare i prezzi delle azioni
in ogni momento, (incomprensibile).
[Yu] Ok, quindi la sua soluzione - il suo suggerimento di calcolo
il più basso e il più alto calcolo non funziona necessariamente
perché la più alta può essere preceduta più basso.
Allora, qual è la soluzione la forza bruta per questo problema?
Quali sono le due cose che ho bisogno di determinare in modo univoco il profitto che faccio? Giusto.
La soluzione è la forza bruta - oh, così, il suggerimento di George è che abbiamo solo bisogno di due giorni
di determinare in modo univoco il risultato di questi due giorni.
Così si calcola ogni coppia, come acquisto / vendita,
calcolare il profitto, che potrebbe essere negativo o positivo o nullo.
Calcolare il massimo profitto che facciamo dopo l'iterazione di tutte le coppie di giorni.
Questa sarà la nostra risposta definitiva.
E che la soluzione sarà O (n ^ 2), perché non vi è n scegliere due coppie -
di giorni in cui è possibile scegliere tra i giorni fine.
Ok, quindi non ho intenzione di andare oltre la soluzione di forza bruta qui.
Ho intenzione di dirvi che c'è una soluzione di n log n.
Che algoritmo si sa che attualmente è n log n?
Non è una domanda trabocchetto.
>> Merge sort. Merge sort è n log n,
e in effetti, un modo per risolvere questo problema è quello di utilizzare
una sorta di ordinamento per fusione di idea chiamato, in generale, divide et impera.
E l'idea è la seguente.
Si desidera calcolare il miglior acquisto / vendita coppia nella metà sinistra.
Trova il miglior profitto si può fare, solo con prime n in due giorni.
Poi si desidera oompute il miglior acquisto / vendita coppia nella metà destra,
così l'ultimo n in due giorni.
E ora la domanda è: come possiamo unire queste soluzioni di nuovo insieme?
Sì? (Studente, incomprensibile)
Va bene >>. Permettetemi quindi di fare un disegno.
Sì? (George, incomprensibile)
>> Esattamente. Soluzione di George è esattamente giusto.
Quindi, il suo suggerimento è, in primo luogo calcolare il miglior acquisto / vendita coppia,
e che si verifica nella metà sinistra, quindi diciamo che a sinistra, a sinistra.
Best buy / vendita coppia che si verifica nella parte destra.
Ma se solo in confronto questi due numeri, ci manca il caso
dove comprare qui e vendere da qualche parte nella metà destra.
Compriamo nella metà sinistra, vendere nella metà destra.
E il modo migliore per calcolare il miglior acquisto / vendita coppia che si estende su entrambe le metà
è calcolare il minimo qui e calcolare il massimo qui
e prendere la loro differenza.
Così i due casi in cui il buy / sell coppia si verifica solo qui,
solo qui, o su entrambe le metà è definita da questi tre numeri.
Quindi, il nostro algoritmo di fondere le nostre soluzioni di nuovo insieme,
vogliamo calcolare il miglior acquisto / vendita coppia
dove si compra nella metà sinistra e vendere nella metà destra.
E il modo migliore per farlo è quello di calcolare il prezzo più basso nel primo tempo,
il prezzo più alto nella parte destra, e prendere la loro differenza.
Le risultanti tre profitti, questi tre numeri, si prende il massimo dei tre,
e questo è il miglior profitto si può fare in questi primi giorni e la fine.
Qui le linee importanti sono in rosso.
Questa è una chiamata ricorsiva per calcolare la risposta nella metà sinistra.
Questa è una chiamata ricorsiva per calcolare la risposta nella parte destra.
Questi due cicli per calcolare il minimo e il massimo sulla metà sinistra e destra, rispettivamente.
Ora calcolare il profitto che si estende su entrambe le metà,
e la risposta finale è il massimo di questi tre.
Va bene.
>> Quindi, certo, abbiamo un algoritmo, ma il problema più grande è,
qual è la complessità temporale di questo?
E la ragione per cui ho detto merge sort è che questa forma di dividere la risposta
in due e quindi unendo le nostre soluzioni di nuovo insieme
è esattamente la forma di merge sort.
Quindi, mi lasci andare per tutta la durata.
Se si definisce una funzione t (n) per il numero di passi
per n giorni,
i nostri due chiamate ricorsive
sono ciascuno costerà t (n / 2),
e ci sono due di queste chiamate.
Ora devo calcolare il minimo della metà sinistra,
che posso fare in n / 2 ora, più il massimo della metà destra.
Quindi questo è solo n.
E poi, oltre a un lavoro costante.
E questa ricorrenza equazione
è esattamente l'equazione di ricorrenza per merge sort.
E noi tutti sappiamo che merge sort è log n n tempo.
Pertanto, il nostro algoritmo è anche n log n tempo.
Ha questa iterazione senso?
Solo un breve riassunto di questo:
T (n) è il numero di passi per calcolare il massimo profitto
nel corso di n giorni.
Il modo in cui ci siamo lasciati alle nostre chiamate ricorsive
è chiamando la nostra soluzione nei primi giorni n / 2,
così che è una chiamata,
e poi chiamare di nuovo nella seconda metà.
Ecco, questo è due chiamate.
E poi troviamo un minimo nella metà di sinistra, che si può fare in tempo lineare,
trovare il massimo della metà di destra, che si può fare in tempo lineare.
Quindi n / 2 + n / 2 è solo n.
Poi abbiamo un lavoro costante, che è come fare calcoli.
Questa equazione ricorrenza è esattamente l'equazione di ricorrenza per merge sort.
Quindi, il nostro algoritmo shuffle è anche n log n.
Quindi, quanto spazio stiamo usando?
Torniamo al codice.
>> Una domanda migliore è, come molti stack frame abbiamo mai avuto in un dato momento?
Dal momento che stiamo usando la ricorsione,
il numero di stack frame determina il nostro utilizzo dello spazio.
Consideriamo n = 8.
Chiediamo la riproduzione casuale 8,
che chiamerà la riproduzione casuale delle prime quattro voci,
che chiamerà uno shuffle sulle prime due voci.
Così il nostro stack è - questo è il nostro stack.
E poi chiediamo casuale di nuovo il 1 °,
e questo è quello che il nostro scenario di base è, così torniamo subito.
Abbiamo sempre più di questo stack frame molti?
No, perché ogni volta che facciamo una chiamata,
una chiamata ricorsiva per la riproduzione casuale,
dividiamo la nostra dimensione a metà.
Così il numero massimo di stack frame abbiamo mai avuto in un dato momento
è dell'ordine di fotogrammi log n pila.
Ogni stack frame, dispone di spazi costante,
e quindi la quantità totale di spazio,
la quantità massima di spazio che abbiamo mai usare è O (log n) lo spazio
dove n è il numero di giorni.
>> Ora, sempre chiedetevi: "Possiamo fare di meglio?"
E in particolare, si può ridurre ad un problema che abbiamo già risolto?
Un suggerimento: abbiamo solo discusso due altri problemi prima di questo, e non sarà casuale.
Siamo in grado di convertire il problema del mercato azionario nel problema sottoarray massima.
Come possiamo fare questo?
Uno di voi? Emmy?
(Emmy, incomprensibile)
[Yu] Esattamente.
Quindi il problema sottoarray massima,
stiamo cercando una somma su una sottomatrice continuo.
E suggerimento di Emmy per il problema delle scorte,
esaminare le modifiche o le delta.
E una foto di questo è - questo è il prezzo di un titolo,
ma se abbiamo preso la differenza tra ogni giorno consecutivo -
così vediamo che il prezzo massimo, il massimo profitto potremmo fare
è se si compra qui e vendere qui.
Ma vediamo il continuo - guardiamo il problema sottoarray.
Così qui, possiamo fare - andare da qui a qui,
abbiamo un cambiamento positivo, e poi andare da qui a qui abbiamo una variazione negativa.
Ma poi, passando da qui a qui abbiamo un grande cambiamento positivo.
E questi sono i cambiamenti che vogliamo riassumere per ottenere il nostro risultato finale.
Poi ci sono i cambiamenti più negative qui.
La chiave per ridurre il nostro problema nel nostro magazzino problema sottoarray massima
è quello di considerare i delta tra i giorni.
Quindi creare un nuovo array chiamato delta,
inizializzare la prima voce a 0,
e quindi per ogni delta (i), lasciare che sia la differenza
della mia matrice di input (i), e array (i - 1).
Poi chiamiamo la nostra procedura di routine per una sottomatrice massima
passando array a delta.
E poiché subarray massimo è il tempo lineare,
e questa riduzione, questo processo di creazione di questo array delta,
è anche il tempo lineare,
quindi la soluzione finale per le azioni è O (n) di lavoro più O (n) di lavoro, è ancora O (n) di lavoro.
Così abbiamo una soluzione lineare tempo per il nostro problema.
Ha tutti a capire questa trasformazione?
>> In generale, una buona idea che si dovrebbe sempre avere
è cercare di ridurre un problema nuovo che si sta vedendo.
Se sembra familiare a un vecchio problema,
provare a ridurre a un vecchio problema.
E se è possibile utilizzare tutti gli strumenti che avete usato il vecchio problema
per risolvere il nuovo problema.
Quindi, per concludere, colloqui tecnici sono impegnative.
Questi problemi sono probabilmente alcuni dei problemi più difficili
che si potrebbe vedere in una intervista,
quindi se non capisco tutti i problemi che ho appena coperti, va tutto bene.
Questi sono alcuni dei problemi più difficili.
Pratica, pratica, pratica.
Ho dato un sacco di problemi nel volantino, quindi sicuramente controllare quelli fuori.
E buona fortuna per le tue interviste. Tutte le mie risorse sono pubblicate a questo link,
e uno dei miei amici anziani si è offerta di fare finti colloqui tecnici,
quindi se siete interessati, e-mail Will Yao a questo indirizzo e-mail.
Se avete qualche domanda, puoi chiedere a me.
Voi ragazzi avete domande specifiche relative a colloqui tecnici
o tutti i problemi che abbiamo visto fino ad ora?
Va bene. Beh, buona fortuna per le tue interviste.
[CS50.TV]