[Powered by Google Translate] [Seminário: Entrevistas Técnicas]
[Kenny Yu, da Universidade de Harvard]
[Esta é CS50.] [CS50.TV]
Oi a todos, eu sou o Kenny. Atualmente sou informática júnior estudar.
Eu sou um ex-CS TF, e eu desejo que eu tive isso quando eu era um underclassman,
e é por isso que eu estou dando este seminário.
Então eu espero que você goste.
Este seminário é de cerca de entrevistas técnicas,
e todos os meus recursos podem ser encontrados neste link,
este link aqui, um casal de recursos.
Então eu fiz uma lista de problemas, na verdade, alguns problemas.
Também uma página de recursos em geral, onde podemos encontrar dicas
sobre como se preparar para uma entrevista,
dicas sobre o que você deve fazer durante uma entrevista real,
bem como a forma de abordar os problemas e recursos para referência futura.
É tudo online.
E só para prefaciar este seminário, um aviso,
como este não deveria - sua preparação para entrevistas
não se deve limitar a esta lista.
Isso serve apenas para ser um guia,
e você deve definitivamente dar tudo que eu digo com um grão de sal,
mas também usar tudo que eu costumava ajudá-lo em sua preparação para entrevistas.
>> Eu estou indo para acelerar através dos próximos slides
para que possamos chegar aos estudos de casos reais.
A estrutura de uma entrevista para um postion engenharia de software,
é tipicamente 30 a 45 minutos,
múltiplos ciclos, dependendo da empresa.
Muitas vezes você vai ser a codificação em um quadro branco.
Assim, um quadro branco como este, mas muitas vezes em uma escala menor.
Se você está tendo uma entrevista por telefone, você provavelmente vai estar usando
ou collabedit ou um Google Doc para que eles possam vê-lo ao vivo de codificação
enquanto você está sendo entrevistado por telefone.
Uma entrevista em si é tipicamente 2 ou 3 problemas
testar o seu conhecimento de informática.
E vai quase certamente envolvem codificação.
Os tipos de perguntas que você verá são geralmente estruturas de dados e algoritmos.
E, ao fazer estes tipos de problemas,
eles vão pedir-lhe, assim, o que é o tempo ea complexidade do espaço, grande O?
Muitas vezes, eles também pedir maior nível de perguntas,
assim, projetar um sistema,
como é que você colocar para fora seu código?
Quais interfaces, o que as classes, quais módulos você tem em seu sistema,
e como estes interagem entre si?
Assim estruturas de dados e algoritmos, bem como sistemas de projeto.
>> Algumas dicas gerais, antes de mergulhar em nossos estudos de caso.
Acho que a regra mais importante é sempre estar pensando em voz alta.
A entrevista é suposto ser a sua chance de mostrar o seu processo de pensamento.
O ponto da entrevista é para o entrevistador para avaliar
como você pensa e como você passar por um problema.
A pior coisa que você pode fazer é ficar em silêncio durante toda a entrevista.
Isso é apenas não é bom.
Quando você tem uma pergunta, você também quer ter a certeza de que você entendeu a pergunta.
Então, repito a pergunta de volta em suas próprias palavras
e tentativa de trabalhar completas alguns casos de teste simples
para ter certeza de que entendeu a pergunta.
Trabalhando através de alguns casos de teste também lhe dará uma intuição sobre como resolver este problema.
Você pode até descobrir alguns padrões para ajudar a resolver o problema.
Sua grande dica é não ficar frustrado.
Não fique frustrado.
Entrevistas são um desafio, mas a pior coisa que você pode fazer,
para além de ser silencioso, é para ser visivelmente frustrado.
Você não quer dar a impressão de que a um entrevistador.
Uma coisa que você - assim, muitas pessoas, quando eles entram em uma entrevista,
eles tentam tentar encontrar a melhor solução em primeiro lugar,
quando, na verdade, há, normalmente, uma solução muito óbvio.
Pode ser lento, pode ser ineficiente, mas você deve apenas afirmar que,
Só para você ter um ponto de partida para trabalhar melhor.
Além disso, a apontar para fora a solução é lenta, em termos de
O grande complexidade de tempo ou a complexidade do espaço,
irá demonstrar para o entrevistador que você entenda
estas questões ao escrever código.
Portanto, não tenha medo de vir para cima com o mais simples algoritmo de primeira
e, então, trabalhar melhor a partir daí.
Todas as perguntas até agora? Okay.
>> Então vamos mergulhar no nosso primeiro problema.
"Dado um conjunto de n inteiros, escreva uma função que embaralha a matriz
em tal lugar que todas as permutações dos n inteiros são igualmente prováveis. "
E assumir que você tem disponível um gerador de número aleatório
que gera um número inteiro na gama de 0 a i, gama de metade.
Será que todo mundo entender essa questão?
Eu dar-lhe um array de inteiros n, e eu quero que você embaralhar-lo.
No meu diretório, escrevi alguns programas para demonstrar o que eu quero dizer.
Eu estou indo para baralhar uma matriz de 20 elementos,
a partir de -10 a 9,
e eu quero que a saída de uma lista como esta.
Então, esta é a minha matriz entrada classificada, e eu quero que você embaralhar-lo.
Nós vamos fazer isso de novo.
Será que todo mundo entendeu a pergunta? Okay.
Então cabe a você.
Quais são algumas idéias? Você pode fazê-lo como n ^ 2, n log n, n?
Aberto a sugestões.
Okay. Então, uma idéia, sugerida pelo Emmy,
é primeiro calcular um número aleatório, inteiro aleatório, em um intervalo de 0 a 20.
Assim, assumir a nossa matriz tem um comprimento de 20.
No nosso diagrama de 20 elementos,
esta é a nossa matriz de entrada.
E agora, a sugestão é criar uma nova matriz,
por isso esta será a matriz de saída.
E baseado no i retornado por rand -
Então, se eu era, vamos dizer, 17,
copiar o elemento 17 para a primeira posição.
Agora precisamos apagar - precisamos mudar todos os elementos aqui
de forma que temos uma lacuna no final e não há buracos no meio.
E agora nós repita o processo.
Agora vamos escolher um novo inteiro aleatório entre 0 e 19.
Temos um i novo aqui, e nós copiamos este elemento para essa posição.
Então mudamos os itens sobre os e repita o processo até que temos a nossa gama completa de novo.
Qual é o tempo de execução deste algoritmo?
Bem, vamos considerar o impacto desta.
Estamos mudando a cada elemento.
Quando remover esta i, estamos mudando todos os elementos depois para a esquerda.
E isso é um O custo (n)
porque o que se remover o primeiro elemento?
Assim, para cada remoção, remover -
cada remoção incorre uma operação de O (n),
e uma vez que temos n remoções, isso leva a um baralhar O (n ^ 2).
Okay. Então bom começo. Bom começo.
>> Outra sugestão é usar algo conhecido como o shuffle Knuth,
ou o shuffle Fisher-Yates.
E é realmente um shuffle tempo linear.
E a idéia é muito semelhante.
Mais uma vez, temos a nossa matriz de entrada,
mas em vez de utilizar duas matrizes para a entrada / saída,
usamos a primeira porção da matriz para controlar a porção embaralhadas,
e estamos a acompanhar, e depois deixamos o resto da nossa matriz para a parte unshuffled.
Então, aqui está o que eu quero dizer. Começamos com - podemos escolher um i,
uma matriz a partir de 0 a 20.
Nosso atual do ponteiro está apontando para o primeiro índice.
Nós escolhemos alguns aqui i
e agora vamos trocar.
Assim, se este era 5 e esta foi 4,
a matriz resultante terá 5 aqui e 4 aqui.
E agora, notamos um marcador aqui.
Tudo para a esquerda é embaralhado,
e tudo para a direita está unshuffled.
E agora podemos repetir o processo.
Nós escolhemos um índice aleatório entre 1 e 20 agora.
Então suponho que o nosso novo i é aqui.
Agora vamos trocar este i com a nossa posição atual de novo aqui.
Então nós fazemos uma troca de e para trás como este.
Deixe-me trazer o código para torná-lo mais concreto.
Nós começamos com a nossa escolha de i -
começamos com i igual a 0, nós escolhemos um local aleatório j
na porção unshuffled da matriz, i a n-1.
Então, se eu estou aqui, escolher um índice aleatório entre aqui e no resto da matriz,
e trocamos.
Este é todo o código necessário para baralhar a sua matriz.
Alguma pergunta?
>> Bem, uma pergunta é necessária, por que isso é correto?
Porque é que todas as permutações igualmente prováveis?
E eu não vou passar pela prova disso,
mas muitos problemas em ciência da computação pode ser comprovada através de indução.
Como muitos de vocês estão familiarizados com a indução?
Okay. Cool.
Assim, você pode provar a correção do algoritmo por indução simples,
onde a sua hipótese de indução seria, suponha que
meu shuffle retorna todas as permutações igualmente provável
até os elementos que eu primeiro.
Agora, considere i + 1.
E pelo jeito que escolhemos o nosso índice j para trocar,
isso leva a - e então você trabalhar os detalhes,
pelo menos, uma prova cheia de porque este algoritmo retorna
cada permutação com probabilidade igualmente prováveis.
>> Todo o problema, mesmo ao lado.
Assim, "dado um array de inteiros, postive, zero, negativo,
escrever uma função que calcula a soma máxima
de qualquer subarray continueous da matriz de entrada. "
Um exemplo aqui é, no caso em que todos os números são positivos,
em seguida, atualmente a melhor opção é levar todo o conjunto.
1, 2, 3, 4, é igual a 10.
Quando você tem alguns aspectos negativos lá,
neste caso, nós só queremos os dois primeiros
porque escolher -1 e / ou -3 trará nossa soma para baixo.
Às vezes, pode ter de começar no meio da matriz.
Às vezes queremos escolher nada, mas é melhor não tomar nada.
E às vezes é melhor tomar a queda,
porque a coisa depois que ele é super grande. Então, alguma idéia?
(Estudante, ininteligível) >> Yeah.
E se eu não tomar -1.
Em seguida, eu escolho 1.000 e 20.000,
ou eu apenas escolher o 3 bilhões.
Bem, a melhor opção é levar todos os números.
Este -1, apesar de ser negativo,
toda a soma é maior do que os que não a tomar -1.
Portanto, uma das dicas que eu mencionei anteriormente era para dizer o óbvio claramente
e a solução de força bruta em primeiro lugar.
Qual é a solução de força bruta neste problema? Sim?
[Jane] Bem, eu acho que a solução de força bruta
seria somar todas as combinações possíveis (ininteligível).
[Yu] Okay. Então Jane idéia é levar todos os possíveis -
Estou parafraseando - é levar cada subarray possível, contínua,
calcular a sua soma, em seguida, tomar o máximo de todas as possíveis subarrays contínuas.
O que identifica um subarray na minha matriz de entrada?
Como que duas coisas que eu preciso? Sim?
(Estudante, ininteligível) direito. >>
Um limite inferior no índice e um índice limite superior
determina unicamente uma submatriz contínua.
[Estudante Feminino] Estamos estimando que é uma matriz de números únicos?
[Yu] Não. Então, a pergunta é, será que estamos assumindo a nossa matriz -
é a nossa matriz de todos os números originais, ea resposta é não.
>> Se usarmos a nossa solução de força bruta, então os índices de início / fim
exclusivamente determina nossa subarray contínua.
Então, se nós iterar para todas as entradas possíveis de início,
e para todas as entradas finais> ou = para começar, e <n,
você calcular a soma, e então tomamos o montante máximo que temos visto até agora.
Isto está claro?
O que é o O grande desta solução?
Timewise.
Não é bem N ^ 2.
Note-se que nós iterar de 0 a n,
de modo que é um loop for.
Repetimos novamente quase o começo até o fim, outro para loop.
E agora, dentro disso, temos que resumir cada entrada,
de modo que é outro para loop. Portanto, temos três aninhados loops, n ^ 3.
Okay. Isso vale como um ponto de partida.
Nossa solução não é pior do que n ^ 3.
Será que todo mundo entender a solução de força bruta?
>> Okay. A melhor solução é usar uma idéia chamada de programação dinâmica.
Se você tomar CS124, que é Algoritmos e Estruturas de Dados,
você vai se tornar muito familiarizado com esta técnica.
E a idéia é, tentar construir soluções para pequenos problemas em primeiro lugar.
O que quero dizer com isto é, atualmente temos que se preocupar com duas coisas: início e término.
E isso é irritante. O que se poderia se livrar de um desses parâmetros?
Uma idéia é - nós dado o nosso problema original,
encontrar a soma máxima de qualquer subarray no intervalo [O, n-1].
E agora temos um novo subproblema, onde sabemos que, em nossa atual índice i,
sabemos que devemos concluir lá. Nosso subarray deve terminar no índice atual.
Assim, o problema restante é, por onde devemos começar a nossa subarray?
Será que isto faz sentido? Okay.
Então eu codificado isto, e vamos ver o que isto significa.
No codirectory, há um programa chamado subarray,
e leva o número de itens,
e retorna a soma subarray máxima na minha lista de embaralhadas.
Portanto, neste caso, a nossa subarray máxima é de 3.
E que é tomada apenas usando 2 e 1.
Vamos executá-lo novamente. É também 3.
Mas, desta vez, observe como chegamos a 3.
Pegamos o - nós tomarmos a 3 em si
porque está cercado por negativos em ambos os lados,
que vai trazer uma soma <3.
Vamos correr em 10 itens.
Desta vez é 7, tomamos a 3 e 4 de liderança.
Desta vez é 8, e obtemos que tomando 1, 4 e 3.
Então, para dar-lhe uma intuição sobre como podemos resolver este problema transformado,
vamos dar uma olhada neste subarray.
Nós estamos dando esta matriz de entrada, e nós sabemos que a resposta é 8.
Tomamos o 1, 4, e 3.
Mas vamos ver como é que realmente tenho essa resposta.
Vamos olhar para o subarray máxima que terminou em cada um desses índices.
Qual é a subarray máxima que tem que terminar na primeira posição?
[Estudante] Zero. >> Zero. Só não tomar a -5.
Aqui vai ser 0 também. Sim?
(Ininteligível, estudante)
[Yu] Oh, desculpe, é um -3.
Portanto, este é um grupo 2, isto é um -3.
Okay. Então -4, o que é o subarray máxima para acabar com essa posição
onde -4 é em? Zero.
Um? 1, 5, 8.
Agora, tenho que terminar no local onde está em -2.
Então, 6, 5, 7, e o último é de 4.
Sabendo que estas são as minhas entradas
para o problema transformou onde deve terminar em cada um desses índices,
então a minha resposta final é justo, fazer uma varredura em todo,
e ter o número máximo.
Portanto, neste caso, é 8.
Isto implica que o subarray máxima termina neste índice,
e começou em algum lugar antes.
Será que todo mundo entender isso subarray transformado?
>> Okay. Bem, vamos descobrir a recorrência para isso.
Vamos considerar apenas as entradas primeiros.
Então, aqui foi de 0, 0, 0, 1, 5, 8.
E então houve um -2 aqui, e que trouxe para baixo a 6.
Então, se eu chamar a entrada na posição i subproblema (i),
como posso usar a resposta a um subproblema anterior
para responder a esta subproblema?
Se eu olhar para, vamos dizer, essa entrada.
Como posso calcular a resposta 6 olhando
uma combinação dessa matriz e as respostas para subproblemas anteriores desta série? Sim?
[Estudante Feminino] Você toma a matriz de somas
na posição correcta antes de que, para que o 8,
e então você adiciona o subproblema atual.
[Yu] Então a sugestão é olhar para esses dois números,
este número e este número.
Portanto, este 8 refere-se à resposta para o subproblema (i - 1).
E vamos chamar minha entrada matriz A.
A fim de encontrar uma submatriz máxima que termina na posição i,
Eu tenho duas escolhas: eu pode continuar a subarray
que terminou no índice anterior, ou iniciar uma nova matriz.
Se eu fosse para continuar a subarray que começou no índice anterior,
em seguida, o montante máximo que pode conseguir é a resposta para o subproblema anterior
mais a entrada da matriz atual.
Mas, eu também tem a opção de iniciar um novo subarray,
caso em que a soma é igual a 0.
Portanto, a resposta é o máximo de 0, subproblema i - 1, mais a entrada da matriz atual.
Será que essa recorrência faz sentido?
Nosso recorrência, como acabamos de descobrir, é subproblema i
é igual ao máximo do subproblema anterior mais a minha entrada matriz atual,
o que significa que continua a subarray anterior,
ou 0, iniciar um subarray novo em meu índice atual.
E uma vez que nós construímos esta tabela de soluções, então a nossa resposta final,
basta fazer uma varredura linear em toda a matriz subproblema
e ter o número máximo.
Esta é uma implementação exata do que eu disse.
Então, criamos uma matriz subproblema novo, subproblemas.
A primeira entrada é 0 ou a primeira entrada, o máximo desses dois.
E para o resto dos subproblemas
usamos a repetição exata que acabara de descobrir.
Agora vamos calcular o valor máximo da nossa matriz subproblemas, e essa é a nossa resposta final.
>> Então, quanto espaço estamos usando neste algoritmo?
Se você só tomada CS50, então você pode não ter discutido muito espaço.
Bem, uma coisa a se notar é que eu chamei malloc aqui com tamanho n.
O que isso lhe sugere?
Este algoritmo utiliza o espaço linear.
Podemos fazer melhor?
Existe alguma coisa que você percebe o que é desnecessário para calcular a resposta final?
Eu acho que a melhor pergunta é, que informação
não precisamos levar todo o caminho até o fim?
Agora, se olharmos para estas duas linhas,
que só se preocupam com o subproblema anterior,
e nós só se preocupam com o máximo que já vimos até agora.
Para calcular a resposta final, nós não precisamos de toda a matriz.
Nós só precisamos do último número, dois últimos números.
Último número para a matriz subproblema, e último número para o máximo.
Então, na verdade, pode-se fundir esses laços juntos
e ir de espaço a espaço linear constante.
Soma atual, até agora, aqui, substitui a função do subproblema, nossa matriz subproblema.
Soma tão atual, até agora, é a resposta para o subproblema anterior.
E que soma, até agora, toma o lugar do nosso máximo.
Nós calcular o valor máximo à medida que avançamos.
E assim vamos de espaço linear para o espaço constante,
e também temos uma solução para o nosso problema linear subarray.
>> Esses tipos de perguntas que você vai ter durante uma entrevista.
Qual é a complexidade de tempo, o que é a complexidade do espaço?
Você pode fazer melhor? Existem coisas que são desnecessários para manter em torno?
Eu fiz isso para destacar análises que você deve tomar em seu próprio
como você está trabalhando com esses problemas.
Sempre estar se perguntando: "Posso fazer melhor?"
Na verdade, podemos fazer melhor que isso?
Uma espécie de pegadinha. Você não pode, porque você precisa
, pelo menos, ler a entrada para o problema.
Assim, o fato de que você precisa ler pelo menos a entrada para o problema
significa que você não pode fazer melhor do que o tempo linear,
e você não pode fazer melhor do que o espaço constante.
Portanto, este é, de facto, a melhor solução para este problema.
Perguntas? Okay.
>> Problema do mercado de ações:
"Dado um conjunto de n inteiros, positivo, zero ou negativo,
que representam o preço de uma ação mais n dias,
escrever uma função para calcular o lucro máximo que você pode fazer
uma vez que você compra e vende exatamente um estoque dentro desses n dias. "
Essencialmente, queremos comprar na baixa e vender na alta.
E nós queremos descobrir o melhor lucro que podemos fazer.
Voltando ao meu ponta, o que é a resposta mais simples imediatamente claro, mas é lento?
Sim? (Estudante, ininteligível) >> Sim.
>> Então você teria apenas que ir embora e olhar para os preços das ações
em cada ponto no tempo, (ininteligível).
[Yu] Ok, então sua solução - sua sugestão de computação
o menor e computar o maior não significa necessariamente trabalhar
porque o mais elevado podem ocorrer antes de mais baixa.
Então, qual é a solução de força bruta para este problema?
Quais são as duas coisas que eu preciso determinar de maneira única o lucro que eu faço? Direito.
A solução de força bruta é - oh, então, a sugestão de Jorge é que só preciso dois dias
exclusivamente para determinar o lucro desses dois dias.
Então vamos calcular cada par, como comprar / vender,
calcular o lucro, o que pode ser negativo ou positivo ou zero.
Calcule o lucro máximo que fazemos após a iteração sobre todos os pares de dias.
Essa será a nossa resposta final.
E que a solução vai ser O (n ^ 2), porque não há n escolher dois pares -
de dias que você pode escolher entre os dias finais.
Ok, então eu não vou passar por cima da solução de força bruta aqui.
Eu vou dizer-lhe que há uma solução n log n.
O algoritmo que você sabe atualmente que é n log n?
Não é uma pergunta capciosa.
>> Merge sort. Merge sort é n log n,
e, na verdade, uma maneira de resolver esse problema é usar
um tipo merge sort de idéia chamada, em geral, dividir e conquistar.
E a ideia é a seguinte.
Você quer calcular a melhor compra / venda par na meia esquerda.
Encontre o melhor lucro que você pode fazer, apenas com o n primeiro em dois dias.
Então você quer oompute a melhor compra / venda par na metade direita,
para n o último dois dias.
E agora a pergunta é, como se fundem estas soluções juntos de novo?
Sim? (Ininteligível, estudante)
Ok >>. Então deixe-me tirar uma foto.
Sim? (George, ininteligível)
>> Exatamente. Solução George é exatamente certo.
Assim, sua sugestão é, primeiro calcular o melhor par de compra / venda,
e que ocorre na metade esquerda, então vamos chamar isso de esquerda, à esquerda.
Melhor comprar / vender par que ocorre na meia direita.
Mas, se comparado apenas estes dois números, estamos perdendo o caso
onde comprar aqui e vender em algum lugar do meia direita.
Nós compramos na metade esquerda, vender na metade direita.
E a melhor forma de calcular o melhor par de compra / venda que abrange ambas as metades
é calcular o mínimo aqui e calcular o valor máximo aqui
e tomar a sua diferença.
Assim, os dois casos em que o par de compra / venda ocorre somente aqui,
Apenas aqui, ou em ambas as metades é definida por estas três números.
Assim, o nosso algoritmo para fundir nossas soluções de volta,
queremos calcular o melhor par de compra / venda
onde comprar na metade esquerda e vender na meia direita.
E a melhor maneira de fazer isso é calcular o menor preço no primeiro semestre,
o preço mais alto na meia direita, e tomar a sua diferença.
Os lucros resultantes três, esses três números, você tirar o máximo de três,
e que é o melhor lucro que você pode fazer sobre estes primeiros dias e fim.
Aqui as linhas importantes estão em vermelho.
Esta é uma chamada recursiva para calcular a resposta na meia esquerda.
Esta é uma chamada recursiva para calcular a resposta na meia direita.
Estes dois circuitos para calcular o mínimo eo máximo na metade esquerda e direita, respectivamente.
Agora eu calcular o lucro que abrange as duas metades,
ea resposta final é o máximo de três.
Okay.
>> Então, com certeza, temos um algoritmo, mas a grande questão é,
o que é a complexidade de tempo deste?
E a razão pela qual eu mencionei merge sort é que essa forma de dividir a resposta
em dois e, em seguida, fundindo nossas soluções juntos novamente
é exatamente a forma de classificação por intercalação.
Então deixe-me passar o tempo.
Se nós definimos uma função t (n) para ser o número de etapas
de n dias,
nossas duas chamadas recursivas
são cada custará t (n / 2),
e há duas dessas ligações.
Agora eu preciso calcular o valor mínimo da metade esquerda,
que I pode fazer em n / 2 hora, mais o máximo da metade direita.
Então, este é apenas o n.
E depois mais algum trabalho constante.
E esta equação recorrência
é exatamente a equação de recorrência para merge sort.
E todos nós sabemos que tipo de mesclagem é n log n tempo.
Portanto, nosso algoritmo é também n log n tempo.
Será que esta iteração faz sentido?
Apenas uma breve recapitulação do presente:
T (n) é o número de passos para calcular o máximo de lucro
ao longo do dia n.
A maneira como nos separamos nossas chamadas recursivas
é chamando a nossa solução nos primeiros dias n / 2,
de modo que é uma chamada,
e, em seguida, chamamos novamente no segundo semestre.
Então, isso é duas chamadas.
E, então, encontrar um mínimo na metade esquerda, o que podemos fazer em tempo linear,
encontrar o máximo da meia direita, o que podemos fazer em tempo linear.
Então n / 2 + n / 2 é apenas n.
Então nós temos um trabalho constante, que é como fazer aritmética.
Esta equação de recorrência é exatamente a equação de recorrência para merge sort.
Por isso, nosso algoritmo shuffle é também n log n.
Então, quanto espaço estamos usando?
Vamos voltar para o código.
>> A melhor pergunta é, quantos quadros de pilha que nós já temos em determinado momento?
Como estamos utilizando a recursividade,
o número de quadros de pilha determina a nossa utilização do espaço.
Vamos considerar n = 8.
Chamamos embaralhe 8,
que irá chamar embaralhe as quatro primeiras entradas,
que irá chamar um shuffle nas duas primeiras entradas.
Portanto, a nossa pilha é - esta é a nossa pilha.
E então nós chamamos baralhar novamente em 1,
e é isso que o nosso caso base é, por isso, retornar imediatamente.
Será que já tem mais que esta pilha de quadros muitos?
Não. Porque cada vez que fazemos uma invocação,
uma invocação recursiva para shuffle,
dividimos nosso tamanho pela metade.
Assim, o número máximo de quadros de pilha que já têm a qualquer momento
é da ordem de quadros de log n pilha.
Cada quadro de pilha tem espaço constante,
e, portanto, a quantidade de espaço total,
a quantidade máxima de espaço que sempre uso é O espaço (log n)
onde n é o número de dias.
>> Agora, sempre pergunte a si mesmo: "Podemos fazer melhor?"
E, em particular, podemos reduzir isso a um problema que já foi resolvido?
Uma dica: só discutiu dois outros problemas antes disso, e não vai ser shuffle.
Podemos converter este problema do mercado de ações para o problema subarray máxima.
Como podemos fazer isso?
Um de vocês? Emmy?
(Emmy, ininteligível)
[Yu] Exatamente.
Assim, o problema subarray máxima,
estamos à procura de uma soma sobre um subarray contínua.
E a sugestão de Emmy para o problema stocks,
considerar as mudanças, ou os deltas.
E um retrato disso é - este é o preço de uma ação,
mas se tomamos a diferença entre cada dia consecutivo -
assim vemos que o preço máximo, o lucro máximo que poderia fazer
é se comprar aqui e vender aqui.
Mas vamos olhar para a contínua - vamos olhar para o problema subarray.
Então, aqui, nós podemos fazer - indo daqui para ali,
temos uma mudança positiva, e então ir daqui até aqui temos uma variação negativa.
Mas, então, vai daqui até aqui temos uma grande mudança positiva.
E estas são as mudanças que deseja somar-se para receber o nosso lucro final.
Então nós temos mudanças mais negativas aqui.
A chave para reduzir nosso problema estoque em nosso problema subarray máxima
é considerar os deltas entre dias.
Então nós criamos uma nova matriz chamada deltas,
inicializar a primeira entrada a 0,
e então para cada delta (i), deixe que seja a diferença
da minha matriz de entrada (i), e matriz (i - 1).
Então chamamos o nosso procedimento de rotina para um subarray máxima
passando em uma matriz delta.
E porque subarray máxima é de tempo linear,
e esta redução, este processo de criação dessa matriz delta,
É também tempo linear,
então a solução final para as ações é O (n) O trabalho, além de trabalho (n), ainda é O trabalho (n).
Portanto, temos uma solução em tempo linear para o nosso problema.
Será que todo mundo entender essa transformação?
>> Em geral, é uma boa idéia que você deve ter sempre
é tentar reduzir um novo problema que você está vendo.
Se isso parece familiar para um problema antigo,
tentar reduzi-lo a um problema antigo.
E se você pode usar todas as ferramentas que você usou no velho problema
para resolver o problema novo.
Então, para encerrar, entrevistas técnicas são desafiadoras.
Estes problemas são, provavelmente, alguns dos problemas mais difíceis
que você pode ver em uma entrevista,
por isso, se você não entender todos os problemas que eu só cobertos, está tudo bem.
Estes são alguns dos problemas mais difíceis.
Prática, prática, prática.
Eu dei um monte de problemas no folheto, então definitivamente verificar os para fora.
E boa sorte em suas entrevistas. Todos os meus recursos são postados neste link,
e um dos meus amigos seniores se ofereceu para fazer simulações de entrevistas técnicas,
por isso, se você estiver interessado, e-mail Will Yao nesse endereço de e-mail.
Se você tem alguma dúvida, você pode me perguntar.
Vocês têm questões específicas relacionadas com entrevistas técnicas
ou quaisquer problemas que vimos até agora?
Okay. Bem, boa sorte em suas entrevistas.
[CS50.TV]