[Powered by Google Translate] [Seminario: Entrevistas Técnicas]
[Kenny Yu, da Universidade de Harvard]
[Esta é CS50.] [CS50.TV]
Ola a todos, eu son o Kenny. Actualmente son informática Júnior estudar.
Eu son un ex-CS TF, e eu desexo que eu tiven iso cando eu era un underclassman,
e é por iso que eu estou dando este seminario.
Entón eu espero que che guste.
Este seminario é de preto de entrevistas técnicas,
e todos os meus recursos poden ser atopados nesta ligazón,
este enlace aquí, unha parella de recursos.
Entón eu fixen unha lista de problemas, de feito, algúns problemas.
Tamén unha páxina de recursos en xeral, onde podemos atopar consellos
sobre como se preparar para unha entrevista,
suxestións sobre o que ten que facer durante unha entrevista real,
así como a forma de abordar os problemas e recursos para referencia futura.
É todo online.
E só para prefaciar este seminario, un aviso,
como este non debería - a súa preparación para entrevistas
non se debe limitar a esta lista.
Isto só serve para ser un guía,
e ten que definitivamente dar todo o que eu digo con un gran de sal,
pero tamén usar todo o que eu adoitaba axudar na súa preparación para entrevistas.
>> Eu estou indo para acelerar a través dos seguintes diapositivas
para que poidamos chegar aos estudos de casos reais.
A estrutura dunha entrevista a un postion enxeñaría de software,
é tipicamente 30 a 45 minutos,
múltiples ciclos, dependendo da empresa.
Moitas veces vai ser a codificación nun cadro branco.
Así, un cadro branco como este, pero moitas veces nunha escala menor.
Se vostede está tendo unha entrevista por teléfono, probablemente vai estar usando
ou collabedit ou un Google Doc para que poidan velo en directo de codificación
mentres está sendo entrevistado por teléfono.
Nunha entrevista en si é tipicamente 2 ou 3 problemas
probar o seu coñecemento de informática.
E vai case certamente implica codificación.
Os tipos de preguntas que ver son xeralmente estruturas de datos e algoritmos.
E, ao facer este tipo de problemas,
eles van pedir-lle, así, o que é o tempo ea complexidade do espazo, grande?
Moitas veces, eles tamén pedir maior nivel de preguntas,
Así, proxectar un sistema,
como é que pór para fóra o seu código?
Cales interfaces, que as clases, que módulos ten no seu sistema,
e como estes interactúan entre si?
Así estruturas de datos e algoritmos, así como sistemas de proxecto.
>> Algunhas suxestións xerais, antes de mergullar nos nosos estudios de caso.
Creo que a regra máis importante é estar sempre a pensar en voz alta.
A entrevista é suposta ser a súa oportunidade de amosar o seu proceso de pensamento.
O punto da entrevista é para o entrevistador para avaliar
como pensa e como pasar por un problema.
A peor cousa que pode facer é estar en silencio durante toda a entrevista.
Isto é só non é bo.
Cando ten unha pregunta, tamén quere ter a certeza de que entendeu a pregunta.
Entón, repito a pregunta de volta nas súas propias palabras
e intento de traballar completas nalgúns casos de proba simple
para estar seguro de que entendeu a pregunta.
Traballando a través de algúns casos de proba tamén lle dará unha intuición sobre como solucionar este problema.
Pode até descubrir algúns patróns para axudar a resolver o problema.
A súa gran Consello é non ficar frustrado.
Non sexa errado.
Entrevistas son un reto, pero a peor cousa que pode facer,
ademais de ser silencioso, é para ser visiblemente frustrado.
Non quere dar a impresión de que a un entrevistador.
Unha cousa que - así, moitas persoas, cando eles entran nunha entrevista,
eles tentan tratar de atopar a mellor solución en primeiro lugar,
cando, en realidade, hai normalmente unha solución moi evidente.
Pode ser lento, pode ser ineficiente, pero ten que só afirmar que,
Só para que vostede un punto de partida para traballar mellor.
Ademais, a apuntar para fóra a solución é lenta, en termos de
O gran complexidade de tempo ou a complexidade do espazo,
ha demostrar a entrevistador que entenda
estas cuestións ao escribir código.
Polo tanto, non teña medo de vir cara arriba con o máis simple algoritmo de primeira
e, entón, traballar mellor a partir de aí.
Todas as preguntas ata agora? Okay.
>> Entón imos mergullar no noso primeiro problema.
"Dado un conxunto de n enteiros, escriba unha función que embaralha a matriz
en tal lugar que todas as permutacións dos n enteiros son igualmente probables. "
E asumir que ten dispoñible un xerador de número aleatorio
que xera un número enteiro na gama de 0 a i, gama da metade.
Será que todo o mundo entender esta cuestión?
Eu darlle un array de enteiros n, e quero que embaralhar-lo.
No meu directorio, escribín algúns programas para demostrar o que quero dicir.
Eu estou indo a barallar unha matriz de 20 elementos,
a partir de -10 a 9,
e quero que a saída dunha lista como esta.
Entón, esta é a miña matriz entrada clasificada, e quero que embaralhar-lo.
Nós imos facelo de novo.
Será que todo o mundo entendeu a pregunta? Okay.
Entón cabe a vostede.
Cales son algunhas ideas? Podes facelo como n ^ 2, n log n, n?
Aberto a suxestións.
Okay. Entón, unha idea, suxerida polo Emmy,
é primeiro calcular un número aleatorio, enteiro aleatorio, nun intervalo de 0 a 20.
Así, asumir a nosa matriz ten unha lonxitude de 20.
No noso diagrama de 20 elementos,
Esta é a nosa matriz de entrada.
E agora, a suxestión é crear unha nova matriz,
por iso esta será a matriz de saída.
Está baseado no I retornado por Rand -
Entón, se eu era, imos dicir, 17,
copiar o elemento 17 para a primeira posición.
Agora necesitamos borrar - necesitamos cambiar todos os elementos aquí
de forma que temos unha lagoa ao final e non hai buratos no medio.
E agora nós repita o proceso.
Agora imos escoller un novo enteiro aleatorio entre 0 e 19.
Temos un i novo aquí, e copiamos este elemento para esa posición.
Entón cambiamos os elementos sobre os e repita o proceso ata que temos a nosa gama completa de novo.
Cal é o tempo de execución deste algoritmo?
Ben, imos considerar o impacto desta.
Estamos cambiando a cada elemento.
Cando eliminar esta i, estamos cambiando todos os elementos despois á esquerda.
E iso é un O custo (n)
porque o que se elimina o primeiro elemento?
Así, para cada retirada, eliminar -
Cada retirada incorre nunha operación de O (n),
e unha vez que temos n remocións, iso leva a un barallar O (n ^ 2).
Okay. Entón bo comezo. Bo comezo.
>> Outra suxestión é usar algo coñecido como o shuffle Knuth,
ou o shuffle Fisher-Yates.
E é realmente un shuffle tempo lineal.
E a idea é moi semellante.
Unha vez máis, temos a nosa matriz de entrada,
pero en vez de utilizar dúas matrices para a entrada / saída,
usamos a primeira porción da matriz para controlar a porción embaralhadas,
e estamos a seguir, e despois deixamos o resto da nosa matriz para a parte unshuffled.
Entón, aquí está o que quero dicir. Comezamos con - podemos escoller un i,
unha matriz a partir de 0 a 20.
O noso actual do punteiro está apuntando para o primeiro índice.
Nós escoller algúns aquí i
e agora imos cambiar.
Así, se este era 5 e esta foi 4,
a matriz resultante terá 5 aquí e 4 aquí.
E agora, notamos un marcador aquí.
Todo para a esquerda é embaralhado,
e todo a dereita está unshuffled.
E agora podemos repetir o proceso.
Nós escoller un índice chou entre 1 e 20 agora.
Entón supoño que o noso novo i é aquí.
Agora imos cambiar este i coa nosa posición actual de novo aquí.
Entón nós facemos un troco de e cara atrás como este.
Deixe-me traer o código para facelo máis concreto.
Nós comezamos coa nosa selección de i -
comezamos con i igual a 0, nós escoller un lugar ao chou j
na porción unshuffled da matriz, i an-1.
Entón, se eu estou aquí, escoller un índice chou entre aquí e no resto da matriz,
e trocamos.
Este é todo o código necesario para barallar a súa matriz.
Algunha pregunta?
>> Ben, unha pregunta é necesaria, por que iso é correcto?
Por que todas as permutacións igualmente probables?
E eu non vou pasar pola proba diso,
pero moitos problemas en ciencia da computación pode ser comprobada a través de indución.
Como moitos de vostedes está familiarizado coa indución?
Okay. Cool.
Así, pode probar a corrección do algoritmo por indución simple,
onde a súa hipótese de indución sería, supoña que
meu shuffle retorna todas as permutacións igualmente probable
ata elementos que primeiro.
Agora, considere i + 1.
E polo xeito que escollemos o noso índice j para intercambiar,
iso leva a - e entón traballar os detalles,
polo menos, unha proba chea de porque este algoritmo retorna
Cada intercambio con probabilidade igualmente probables.
>> Todo o problema, mesmo ao lado.
Así, "dado un array de enteiros, postive, cero, negativo,
escribir unha función que calcula a suma máxima
de calquera subarray continueous da matriz de entrada. "
Un exemplo aquí é, no caso de que todos os números son positivos,
a continuación, actualmente a mellor opción é levar todo o conxunto.
1, 2, 3, 4, é igual a 10.
Cando ten algúns aspectos negativos alí,
neste caso, nós só queremos os dous primeiros
porque escoller -1 e / ou -3 traerá nosa suma abaixo.
Ás veces, pode ter que comezar no medio da matriz.
Ás veces queremos elixir nada, pero o mellor é non tomar nada.
E ás veces é mellor tomar a caída,
porque a cousa despois que é super grande. Entón, algunha idea?
(Estudante, inintelixible) >> Yeah.
E se eu non tomar -1.
A continuación, eu escollo 1.000 e 20.000,
ou eu só escoller o 3 millóns.
Ben, a mellor opción é levar todos os números.
Este -1, a pesar de ser negativo,
toda a suma é maior que os que non a tomar -1.
Polo tanto, unha das suxestións que eu mencionen anteriormente era para dicir o evidente claramente
É a solución de forza bruta en primeiro lugar.
Cal é a solución de forza bruta neste problema? Si?
[Jane] Ben, eu creo que a solución de forza bruta
sería sumar todas as combinacións posíbeis (inintelixible).
[Yu] Okay. Entón Jane idea é levar todos os posibles -
Estou parafraseando - é levar cada subarray posible, continua,
calcular a súa suma, a continuación, tomar o máximo de todas as posibles subarrays continuas.
O que identifica un subarray na miña matriz de entrada?
Como dúas cousas que eu teño? Si?
(Estudante, inintelixible) dereito. >>
Un límite inferior no índice e un índice límite superior
determina únicamente unha submatriz continua.
[Estudante Feminino] Estamos estimando que é unha matriz de números únicos?
[Yu] Non Entón, a pregunta é, será que estamos asumindo a nosa matriz -
é a nosa matriz de todos os números orixinais, ea resposta é non.
>> Se usarmos a nosa solución de forza bruta, entón os índices de inicio / fin
exclusivamente determina nosa subarray continua.
Entón, se nós iterar para todas as entradas posíbeis de inicio,
e para todas as entradas finais> ou = para comezar, e <n,
vostede calcular a suma, e entón tomamos o importe máximo que vimos ata agora.
Isto está claro?
Que é o gran esta solución?
Timewise.
Non é así N ^ 2.
Nótese que nós iterar de 0 a n,
de xeito que é un loop for.
Repetimos novamente case o comezo ata o final, outro para loop.
E agora, dentro diso, temos que resumir cada entrada,
de xeito que é outro para loop. Polo tanto, temos tres aniñados loops, n ^ 3.
Okay. Iso vale como un punto de partida.
A nosa solución non é peor que n ^ 3.
Será que todo o mundo entender a solución de forza bruta?
>> Okay. A mellor solución é usar unha idea chamada de programación dinámica.
Se tomar CS124, que é Algoritmos e estruturas de datos,
vai converterse moi familiarizado con esta técnica.
E a idea é, tentar construír solucións para pequenos problemas, en primeiro lugar.
O que quero dicir con isto é, actualmente temos que se preocupar con dúas cousas: inicio e finalización.
E iso é irritante. O que se podería librarse dun deses parámetros?
Unha idea é - nós dado o noso problema orixinal,
atopar a suma máxima de calquera subarray no intervalo [O, N-1].
E agora temos un novo subproblema, onde sabemos que, na nosa actual índice i,
sabemos que temos que concluír alí. O noso subarray debe terminar o índice actual.
Así, o problema restante é, por onde debemos comezar a nosa subarray?
Será que isto ten sentido? Okay.
Entón eu codificado isto, e imos ver o que isto significa.
No codirectory, hai un programa chamado subarray,
e leva o número de elementos,
e retorna a suma subarray máxima na miña lista de embaralhadas.
Polo tanto, neste caso, a nosa subarray máxima é de 3.
E que se toma só usando 2 e 1.
Imos executa-lo de novo. É tamén 3.
Pero esta vez, observe como chegamos a 3.
Pegamos o - nós tomamos a 3 en si
porque está rodeado por negativos en ambos os lados,
que vai traer unha suma <3.
Imos correr en 10 elementos.
Esta vez é 7, tomamos a 3 e 4 de liderado.
Esta vez é 8, e obtemos que tomando 1, 4 e 3.
Entón, para darlle unha intuición sobre como podemos solucionar este problema transformado,
imos dar un ollo neste subarray.
Estamos dando esta matriz de entrada, e sabemos que a resposta é 8.
Tomamos o 1, 4 e 3.
Pero imos ver como é que realmente teño esa resposta.
Imos ollar para o subarray máxima que terminou en cada un destes índices.
Cal é a subarray máxima que ten que rematar na primeira posición?
[Estudante] Cero. >> Cero. Só non tomar a -5.
Aquí vai ser 0 tamén. Si?
(Inintelixible, estudante)
[Yu] Oh, desculpe, é un -3.
Polo tanto, este é un grupo 2, é dicir un -3.
Okay. Entón -4, o que é o subarray máxima para acabar con esa posición
onde -4 é en? Cero.
Un? 1, 5, 8.
Agora teño que rematar no local onde está -2.
Entón, 6, 5, 7, eo último é de 4.
Sabendo que estas son as miñas entradas
para o problema transformou onde debe rematar en cada un destes índices,
entón a miña resposta final é xusto, facer unha pescudas en todo,
e ter o número máximo.
Polo tanto, neste caso, é 8.
Isto implica que o subarray máxima remata neste índice,
e comezou en algún lugar antes.
Será que todo o mundo entender iso subarray converter?
>> Okay. Ben, imos descubrir a recorrencia para iso.
Imos considerar só as entradas primeiros.
Entón, aquí foi de 0, 0, 0, 1, 5, 8.
E entón houbo un -2 aquí, e que trouxo para abaixo a 6.
Entón, se eu chamar a entrada na posición i subproblema (i),
como podo utilizar a resposta a un subproblema anterior
Para responder a esta subproblema?
Se eu ollar para, imos dicir, esa entrada.
Como podo calcular a resposta 6 mirando
unha combinación desa matriz e as respostas a subproblemas anteriores desta serie? Si?
[Estudante Feminino] Vostede toma a matriz de sumas
na posición correcta antes de que, para que o 8,
e entón engade o subproblema actual.
[Yu] Entón a suxestión é mirar para estes dous números,
Este número é este número.
Polo tanto, este 8 refírese á resposta a subproblema (i - 1).
E imos chamar miña entrada matriz A.
Co fin de atopar unha submatriz máxima que remata na posición i,
Eu teño dúas opcións: eu pode continuar subarray
que rematou no índice anterior, ou iniciar unha nova matriz.
Se eu fose para continuar a subarray que comezou no índice anterior,
a continuación, o importe máximo que se pode conseguir é a resposta para o subproblema anterior
máis a entrada da matriz actual.
Pero eu tamén ten a opción de iniciar un novo subarray,
caso en que a suma é igual a 0.
Polo tanto, a resposta é o máximo de 0, subproblema i - 1, máis a entrada da matriz actual.
Será que esa recorrencia ten sentido?
O noso recorrencia, coma acabamos de descubrir, é subproblema i
é igual ao máximo do subproblema anterior máis a miña entrada matriz actual,
o que significa que segue a subarray anterior,
ou 0, iniciar un subarray novo no meu índice actual.
E unha vez que nós construímos esta táboa de solucións, entón a nosa resposta final,
basta facer unha pescudas lineal en toda a matriz subproblema
e ter o número máximo.
Esta é unha implementación exacta do que eu dixen.
Entón, creamos unha matriz subproblema novo, subproblemas.
A primeira entrada é 0 ou a primeira entrada, o máximo destes dous.
E para o resto dos subproblemas
usan a repetición exacta que acaba de descubrir.
Agora imos calcular o valor máximo da nosa matriz subproblemas, e esa é a nosa resposta final.
>> Entón, canto espazo estamos usando este algoritmo?
Se só toma CS50, entón pode non ter discutido moito espazo.
Ben, unha cousa a notar é que eu chamei malloc aquí con tamaño n.
O que isto lle suxire?
Este algoritmo utiliza o espazo linear.
Podemos facer mellor?
¿Hai algunha cousa que entender o que é necesario para calcular a resposta final?
Eu creo que a mellor pregunta é, que información
non necesitamos levar todo o camiño ata o final?
Agora, se miramos para estas dúas liñas,
que só se preocupan o subproblema anterior,
e nós só se preocupan o máximo que vimos ata agora.
Para calcular a resposta final, nós non necesitamos de toda a matriz.
Nós só necesitamos do último número, dous últimos números.
Último número para a matriz subproblema, e último número ao máximo.
Entón, en realidade, pode-se fundir eses lazos xuntos
e ir de espazo a espazo lineal constante.
Suma actual, ata agora, aquí, substitúe a función do subproblema, a nosa matriz subproblema.
Suma tan actual, ata agora, é a resposta para o subproblema anterior.
E que suma ata agora toma o lugar do noso máximo.
Nós calcular o valor máximo a medida que avanzamos.
E así imos de espazo lineal para o espazo constante,
e tamén temos unha solución para o noso problema lineal subarray.
>> Estes tipos de preguntas que vai ter durante unha entrevista.
Cal é a complexidade de tempo, o que é a complexidade do espazo?
Podes facer mellor? Existen cousas que son innecesarios para manter en torno?
Eu fixen isto para destacar análises que ten que tomar no seu propio
como se está a traballar con estes problemas.
Sempre estar se pregunta: "Podo facer mellor?"
En realidade, podemos facer mellor que iso?
Unha especie de pegadinha. Vostede non pode, porque precisa
Polo menos ler a entrada para o problema.
Así, o feito de que precisa ler polo menos a entrada para o problema
significa que non pode facer mellor do que o tempo lineal,
e non pode facer mellor do que o espazo constante.
Polo tanto, este é, de feito, a mellor solución para este problema.
Preguntas? Okay.
>> Problema do mercado de accións:
"Dado un conxunto de n enteiros, positivos, cero ou negativo,
que representan o prezo dunha acción máis n días
escribir unha función para calcular o beneficio máximo que pode facer
unha vez que compra e vende exactamente un stock dentro deses n días. "
Esencialmente, queremos mercar na baixa e vender na alta.
E queremos descubrir o mellor beneficio que podemos facer.
Volvendo ao meu punta, o que é a resposta máis simple inmediatamente claro, pero é lento?
Si? (Estudante, inintelixible) >> Si
>> Entón tería só que ir e ollar para os prezos das accións
en cada punto no tempo, (inintelixible).
[Yu] Ok, entón a súa solución - súa suxestión de computación
menor e computar o maior non significa necesariamente traballar
porque o máis elevado poden ocorrer antes de máis baixa.
Entón, cal é a solución de forza bruta para este problema?
Cales son as dúas cousas que eu teño determinar de xeito único o beneficio que fago? Dereito.
A solución de forza bruta é - oh, entón, a suxestión de Jorge é que só teño dous días
exclusivamente para determinar o beneficio destes dous días.
Entón imos calcular cada par, como comprar / vender,
calcular o beneficio, o que pode ser negativo ou positivo ou cero.
Calcule o beneficio máximo que facemos despois da iteração sobre todos os pares de días.
Esa será a nosa resposta final.
E que a solución vai ser o (n ^ 2), porque non hai n escoller dous pares -
de días que pode escoller entre os días finais.
Ok, entón eu non vou pasar por riba da solución de forza bruta aquí.
Eu vou dicir-lle que hai unha solución n log n.
O algoritmo que sabe actualmente que é n log n?
Non é unha pregunta capciosa.
>> Merge sort. Merge sort é n log n,
e, en realidade, unha forma de resolver este problema é usar
un tipo merge sort de idea chamada, en xeral, dividir e conquistar.
E a idea é a seguinte.
Quere calcular a mellor compra / venda par na media esquerda.
Atopar o mellor beneficio que pode facer, só co n primeiro en dous días.
Entón quere oompute mellor compra / venda par na metade dereita,
para n último dous días.
E agora a pregunta é, como se funden estas solucións xuntos de novo?
Si? (Inintelixible, estudante)
Ok >>. Entón deixe-me tirar unha foto.
Si? (George, inintelixible)
>> Exactamente. Resolución George é exactamente correcto.
Así, a súa suxestión é, primeiro calcular o mellor par de compra / venda,
e que ocorre na metade esquerda, entón imos chamar iso de esquerda, á esquerda.
Mellor mercar / vender par que ocorre na media dereita.
Pero se se compara só estes dous números, estamos perdendo o caso
onde mercar aquí e vender en algún lugar do media dereita.
Nós compramos na metade esquerda, vender na metade dereita.
E a mellor forma de calcular o mellor par de compra / venda que abrangue ambas as metades
é calcular o mínimo aquí e calcular o valor máximo aquí
e tomar a súa diferenza.
Así, os dous casos en que o par de compra / venda ocorre só aquí,
Só aquí, ou en ambas as metades é definida por estas tres números.
Así, o noso algoritmo para fundir nosas solucións de volta,
queremos calcular o mellor par de compra / venda
onde mercar na metade esquerda e vender na media dereita.
E a mellor forma de facelo é calcular o menor prezo no primeiro semestre,
o prezo máis alto na media dereita, e tomar a súa diferenza.
Os beneficios resultantes tres, eses tres números, aproveitar o máximo de tres,
e que é o mellor beneficio que pode facer sobre estes primeiros días e fin.
Aquí as liñas importantes están en vermello.
Esta é unha chamada recursiva para calcular a resposta na media esquerda.
Esta é unha chamada recursiva para calcular a resposta na media dereita.
Estes dous circuítos para calcular o mínimo eo máximo na metade esquerda e dereita, respectivamente.
Agora eu calcular o beneficio que abrangue as dúas metades,
ea resposta final é o máximo de tres.
Okay.
>> Entón, por suposto, temos un algoritmo, pero a gran cuestión é,
o que é a complexidade de tempo deste?
E a razón pola que eu mencionen merge sort é que esa forma de dividir a resposta
en dous e, a continuación, fundindo as nosas solucións xuntos de novo
é exactamente a forma de clasificación por intercalação.
Entón deixe-me pasar o tempo.
Se definimos unha función t (n) para ser o número de etapas
de n días
nosas dúas chamadas recursivas
son cada custará t (n / 2),
e hai dúas desas conexións.
Agora eu teño calcular o valor mínimo da metade esquerda,
que i pode facer en n / 2 hora, máis o máximo da metade dereita.
Entón, este é só o n.
E despois algún traballo constante.
E esta ecuación recorrencia
é exactamente a ecuación de recorrencia para merge sort.
E todos sabemos que tipo de mesclagem é n log n tempo.
Polo tanto, o noso algoritmo é tamén n log n tempo.
Será que esta iteração ten sentido?
Só unha breve recapitulación do presente:
T (n) é o número de pasos para calcular o máximo de lucro
ao longo do día n.
O xeito como nos separamos nosas chamadas recursivas
e chamando a nosa solución nos primeiros días n / 2,
de xeito que é unha chamada,
e, a continuación, chamamos de novo no segundo semestre.
Entón, iso é dúas chamadas.
E, entón, atopar un mínimo na metade esquerda, o que podemos facer en tempo lineal,
atopar o máximo da metade dereita, o que podemos facer en tempo lineal.
Entón N / 2 + n / 2 é só n.
Entón temos un traballo constante, que é como facer aritmética.
Esta ecuación de recorrencia é exactamente a ecuación de recorrencia para merge sort.
Por iso, o noso algoritmo shuffle é tamén n log n.
Entón, canto espazo estamos a usar?
Imos volver para o código.
>> A mellor pregunta é, cantos cadros de pila que xa temos en determinado momento?
Como estamos utilizando a recursividade,
o número de cadros de pila determina a nosa utilización do espazo.
Imos considerar n = 8.
Chamamos embaralhe 8,
que ha chamar embaralhe as catro primeiras entradas,
que pode chamar un shuffle nas dúas primeiras entradas.
Polo tanto, a nosa pila é - esta é a nosa pila.
E entón chamamos barallar de novo en 1,
e iso é o que o noso caso base é, por iso, volver inmediatamente.
Será que xa ten máis que esta pila de cadros moitos?
Non porque cada vez que facemos unha invocación,
unha invocación recursiva para shuffle,
dividimos o noso tamaño á metade.
Así, o número máximo de cadros de pila que xa teñen en calquera momento
é da orde de cadros de rexistro n pila.
Cada cadro de pila ten espazo constante,
e, polo tanto, a cantidade de espazo total,
a cantidade máxima de espazo que sempre uso é o espazo (log n)
onde n é o número de días.
>> Agora, sempre pregunta a si mesmo: "Podemos facer mellor?"
E, en particular, podemos reducir tanto a un problema que xa foi resolto?
Unha información: só discutiu outros dous problemas antes diso, e non vai ser shuffle.
Podemos converter este problema do mercado de accións para o problema subarray máxima.
Como podemos facer iso?
Un de vós? Emmy?
(Emmy, inintelixible)
[Yu] Exactamente.
Así, o problema subarray máxima,
Estamos á procura de unha suma sobre un subarray continua.
E a suxestión de Emmy para o problema stocks,
considerar os cambios, ou os deltas.
É un retrato diso é - este é o prezo dunha acción,
pero se tomamos a diferenza entre cada día consecutivo -
así vemos que o prezo máximo, o beneficio máximo que podería facer
é comprar aquí e vender aquí.
Pero imos ollar para a continua - imos ollar para o problema subarray.
Entón, aquí, podemos facer - ir de aquí para alí,
temos unha mudanza positiva, e entón ir de aquí ata aquí temos unha variación negativa.
Pero, entón, vai aquí ata aquí temos unha gran mudanza positiva.
E estas son as modificacións que quere sumar-se para recibir o noso beneficio final.
Entón temos cambios máis negativas aquí.
A clave para reducir o noso problema stock no noso problema subarray máxima
é considerar os deltas entre días.
Entón nós creamos unha nova matriz chamada deltas,
arrincar a primeira entrada a 0,
e entón para cada delta (i), deixe que sexa a diferenza
da miña matriz de entrada (i), e matriz (i - 1).
Entón chamamos o noso procedemento de rutina para un subarray máxima
pasando dunha matriz delta.
E porque subarray máxima é de tempo lineal,
e esta redución, este proceso de creación desta matriz delta,
É tamén tempo lineal,
entón a solución final para as accións é O (n) O traballo, ademais de traballo (n), aínda é o traballo (n).
Polo tanto, temos unha solución a tempo lineal para o noso problema.
Será que todo o mundo entender esa transformación?
>> En xeral, é unha boa idea que ten que ter sempre
é tentar reducir un novo problema que está a ver.
Se isto parece familiar para un problema antigo,
tentar reduci-lo a un problema antigo.
E se pode usar todas as ferramentas que usou no vello problema
para resolver o problema novo.
Entón, para pechar, entrevistas técnicas son reto.
Estes problemas son, probablemente, algúns dos problemas máis difíciles
que se pode ver nunha entrevista,
por iso, se non entender todos os problemas que eu só cubertos, está todo ben.
Estes son algúns dos problemas máis difíciles.
Práctica, práctica, práctica.
Eu dei unha morea de problemas no folleto, entón definitivamente comprobar os para fóra.
, E boa sorte nas súas entrevistas. Todos os meus recursos son publicados nesta ligazón,
e un dos meus amigos seniores se ofreceu para facer simulacións de entrevistas técnicas,
por iso, se vostede está interesado, e-mail Will Yao nese enderezo de correo-e.
Se ten algunha dúbida, pode me preguntar.
Vostedes teñen cuestións específicas relacionadas coa entrevistas técnicas
ou os problemas que vimos ata agora?
Okay. Ben, boa sorte nas súas entrevistas.
[CS50.TV]