coding interview university
1.0.0
Originalmente, criei isso como uma pequena lista de tópicos de estudo para se tornar um engenheiro de software, mas cresceu até se tornar a grande lista que você vê hoje. Depois de passar por esse plano de estudos, fui contratado como Engenheiro de Desenvolvimento de Software na Amazon! Você provavelmente não terá que estudar tanto quanto eu. De qualquer forma, tudo que você precisa está aqui.
Estudei cerca de 8 a 12 horas por dia, durante vários meses. Esta é a minha história: por que estudei em tempo integral por 8 meses para uma entrevista no Google
Observação: você não precisará estudar tanto quanto eu. Perdi muito tempo com coisas que não precisava saber. Mais informações sobre isso estão abaixo. Vou ajudá-lo a chegar lá sem desperdiçar seu precioso tempo.
Os itens listados aqui irão prepará-lo bem para uma entrevista técnica em praticamente qualquer empresa de software, incluindo os gigantes: Amazon, Facebook, Google e Microsoft.
Boa sorte para você!
Bahasa Indonésia
búlgaro
Espanhol
Alemão
Japonês (日本語)
Marathi
polonês
Português Brasileiro
russo
Tiếng Việt – Vietnamita
Urdu - اردو
Usbeque
বাংলা - Bangla
ខ្មែរ - Khmer
简体中文
繁體中文
afrikaans
árabe
Francês
grego
italiano
Coreano (한국어)
Malaiala
Persa - Farsi
Telugu
Tailandês
turco
Українська
עברית
Adeus
Torne-se um patrocinador e apoie a Coding Interview University!
Este é meu plano de estudos de vários meses para me tornar engenheiro de software em uma grande empresa.
Obrigatório:
Um pouco de experiência com codificação (variáveis, loops, métodos/funções, etc)
Paciência
Tempo
Observe que este é um plano de estudo para engenharia de software , não para engenharia front-end ou desenvolvimento full-stack. Existem realmente ótimos roteiros e cursos para essas carreiras em outros lugares (consulte https://roadmap.sh/ para obter mais informações).
Há muito o que aprender em um programa universitário de Ciência da Computação, mas apenas saber cerca de 75% é suficiente para uma entrevista, e é isso que abordo aqui. Para um programa autodidata completo de ciência da computação, os recursos para meu plano de estudos foram incluídos no Roteiro de Ciência da Computação de Kamran Ahmed: https://roadmap.sh/computer-science
O que é?
Por que usá-lo?
Como usar
Não sinta que você não é inteligente o suficiente
Uma nota sobre recursos de vídeo
Escolha uma linguagem de programação
Livros sobre estruturas de dados e algoritmos
Livros de preparação para entrevistas
Não cometa meus erros
O que você não verá coberto
O Plano Diário
Prática de perguntas de codificação
Problemas de codificação
Complexidade algorítmica/Big-O/Análise assintótica
Estruturas de dados
Matrizes
Listas vinculadas
Pilha
Fila
Tabela hash
Mais conhecimento
Pesquisa binária
Operações bit a bit
Árvores
Árvores - Introdução
Árvores de pesquisa binária: BSTs
Heap / Fila de prioridade / Heap binário
árvores de pesquisa balanceadas (conceito geral, não detalhes)
travessias: pré-ordem, ordem interna, pós-ordem, BFS, DFS
Classificando
seleção
inserção
heapsort
classificação rápida
mesclagem
Gráficos
dirigido
não direcionado
matriz de adjacência
lista de adjacências
travessias: BFS, DFS
Ainda mais conhecimento
Recursão
Programação Dinâmica
Padrões de projeto
Combinatória (n escolha k) e probabilidade
Algoritmos NP, NP-Completo e Aproximação
Como os computadores processam um programa
Caches
Processos e Threads
Teste
Pesquisa e manipulação de strings
Tenta
Números de ponto flutuante
Unicode
Endianismo
Rede
Revisão Final
Atualize seu currículo
Encontre um emprego
Processo de entrevista e preparação geral para entrevista
Esteja pensando em quando a entrevista chegar
Tenha perguntas para o entrevistador
Depois de conseguir o emprego
---------------- Tudo abaixo deste ponto é opcional ----------------
Livros Adicionais
Design de sistema, escalabilidade, tratamento de dados (se você tiver mais de 4 anos de experiência)
Aprendizagem Adicional
Árvores AVL
Espalhar árvores
Árvores vermelhas/pretas
2-3 árvores de pesquisa
2-3-4 árvores (também conhecidas como 2-4 árvores)
Árvores N-árias (K-árias, M-árias)
Árvores B
Compiladores
Emacs e vi(m)
Ferramentas de linha de comando Unix
Teoria da informação
Paridade e Código de Hamming
Entropia
Criptografia
Compressão
Segurança Informática
Coleta de lixo
Programação Paralela
Sistemas de mensagens, serialização e filas
UM*
Transformada Rápida de Fourier
Filtro Bloom
HyperLogLog
Hashing sensível à localidade
van Emde Boas Árvores
Estruturas de dados aumentadas
Árvores de pesquisa balanceadas
Árvores kD
Pular listas
Fluxos de rede
Conjuntos disjuntos e localização de união
Matemática para processamento rápido
Armadilha
Programação Linear
Geometria, casco convexo
Matemática discreta
Detalhes adicionais sobre alguns assuntos
Série de vídeos
Cursos de Ciência da Computação
Artigos
Se você deseja trabalhar como engenheiro de software para uma grande empresa, estas são as coisas que você precisa saber.
Se você perdeu a oportunidade de se formar em ciência da computação, como eu, isso o recuperará e salvará quatro anos de sua vida.
Quando comecei este projeto, eu não sabia distinguir uma pilha de uma pilha, não sabia nada de Big-O, nem nada sobre árvores, ou como percorrer um gráfico. Se eu tivesse que codificar um algoritmo de classificação, posso dizer que teria sido terrível. Todas as estruturas de dados que já usei foram incorporadas à linguagem e eu não sabia como elas funcionavam nos bastidores. Nunca tive que gerenciar a memória, a menos que um processo que estava executando apresentasse um erro de "falta de memória" e então eu teria que encontrar uma solução alternativa. Usei alguns arrays multidimensionais e milhares de arrays associativos em minha vida, mas nunca criei estruturas de dados do zero.
É um plano longo. Pode levar meses. Se você já estiver familiarizado com muito disso, levará muito menos tempo.
⬆ voltar ao topo
Tudo abaixo é um esboço e você deve abordar os itens em ordem, de cima para baixo.
Estou usando o tipo de redução especial do GitHub, incluindo listas de tarefas para acompanhar o progresso.
Mais sobre descontos no estilo GitHub
Nesta página, clique no botão Código próximo ao topo e clique em "Baixar ZIP". Descompacte o arquivo e você poderá trabalhar com os arquivos de texto.
Se você estiver aberto em um editor de código que entenda markdown, verá tudo bem formatado.
Crie um novo branch para poder verificar itens como este, basta colocar um x entre colchetes: [x]
Bifurque o repositório GitHub: https://github.com/jwasham/coding-interview-university clicando no botão Fork.
Clone em seu repositório local:
git clone https://github.com/<YOUR_GITHUB_USERNAME>/coding-interview-university.gitcd coding-interview-university git remoto adicionar upstream https://github.com/jwasham/coding-interview-university.git git remote set-url --push upstream DISABLE # para que você não envie seu progresso pessoal de volta ao repositório original
Marque todas as caixas com X depois de concluir suas alterações:
git commit -am "Progresso pessoal marcado"git pull upstream main # mantém seu fork atualizado com as alterações do repogit push original # apenas envia para seu fork
⬆ voltar ao topo
Engenheiros de software bem-sucedidos são inteligentes, mas muitos têm a insegurança de não serem inteligentes o suficiente.
Os vídeos a seguir podem ajudá-lo a superar essa insegurança:
O mito do programador genial
É perigoso ir sozinho: lutando contra monstros invisíveis na tecnologia
⬆ voltar ao topo
Alguns vídeos estão disponíveis apenas através da inscrição em um curso Coursera ou EdX. Eles são chamados de MOOCs. Às vezes as aulas não acontecem, então você tem que esperar alguns meses e não tem acesso.
Seria ótimo substituir os recursos dos cursos on-line por fontes públicas gratuitas e sempre disponíveis, como vídeos do YouTube (de preferência palestras universitárias), para que vocês possam estudá-los a qualquer momento, e não apenas quando um curso on-line específico estiver em andamento.
⬆ voltar ao topo
Você precisará escolher uma linguagem de programação para as entrevistas de codificação que realizar, mas também precisará encontrar uma linguagem que possa usar para estudar conceitos de ciência da computação.
De preferência, o idioma seria o mesmo, de modo que você só precisa ser proficiente em um.
Quando fiz o plano de estudos, usei 2 linguagens na maior parte: C e Python
C: Nível muito baixo. Permite que você lide com ponteiros e alocação/desalocação de memória, para que você sinta as estruturas de dados e algoritmos em seus ossos. Em linguagens de nível superior como Python ou Java, eles ficam ocultos para você. No trabalho diário, isso é ótimo, mas quando você aprende como essas estruturas de dados de baixo nível são construídas, é ótimo se sentir próximo do metal.
Este é um livro curto, mas lhe dará um ótimo domínio da linguagem C e, se você praticar um pouco, rapidamente se tornará proficiente. Compreender C ajuda você a entender como funcionam os programas e a memória.
Você não precisa se aprofundar muito no livro (ou mesmo terminá-lo). Basta chegar onde você se sente confortável lendo e escrevendo em C.
C está em todo lugar. Você verá exemplos em livros, palestras, vídeos, em todos os lugares enquanto estuda.
A linguagem de programação C, 2ª edição
Python: Moderno e muito expressivo, aprendi porque é super útil e também me permite escrever menos código em uma entrevista.
Esta é a minha preferência. Você faz o que quiser, é claro.
Talvez você não precise, mas aqui estão alguns sites para aprender um novo idioma:
Exercício
Guerras de código
HackerEarth
Tópicos do escalonador (Java, C++)
Desafios da comunidade Programiz PRO)
Você pode usar uma linguagem com a qual se sinta confortável para fazer a parte de codificação da entrevista, mas para grandes empresas, estas são escolhas sólidas:
C++
Java
Pitão
Você também pode usá-los, mas leia primeiro. Pode haver advertências:
JavaScript
Rubi
Aqui está um artigo que escrevi sobre a escolha de um idioma para a entrevista: Escolha um idioma para a entrevista de codificação. Este é o artigo original no qual minha postagem se baseou: Escolhendo uma linguagem de programação para entrevistas
Você precisa estar muito confortável no idioma e ter conhecimento.
Leia mais sobre escolhas:
Escolha o idioma certo para sua entrevista de codificação
Veja recursos específicos do idioma aqui
⬆ voltar ao topo
Este livro formará sua base para a ciência da computação.
Basta escolher um, em um idioma com o qual você se sinta confortável. Você lerá e codificará muito.
Algoritmos em C, Partes 1-5 (Bundle), 3ª Edição
Fundamentos, estruturas de dados, classificação, pesquisa e algoritmos gráficos
Estruturas de dados e algoritmos em Python
por Goodrich, Tamassia, Goldwasser
Eu adorei esse livro. Cobriu tudo e muito mais.
Código pitônico
meu brilhante relatório de livro: https://startupnextdoor.com/book-report-data-structures-and-algorithms-in-python/
Sua escolha:
Goodrich, Tamassia, Goldwasser
Estruturas de dados e algoritmos em Java
Sedgewick e Wayne:
Algoritmos I
Algoritmos II
Algoritmos
Curso gratuito do Coursera que cobre o livro (ministrado pelos autores!):
Sua escolha:
Goodrich, Tamassia e Monte
Estruturas de dados e algoritmos em C++, 2ª edição
Sedgewick e Wayne
Algoritmos em C++, Partes 1-4: Fundamentos, Estrutura de Dados, Classificação, Pesquisa
Algoritmos em C++ Parte 5: Algoritmos Gráficos
⬆ voltar ao topo
Você não precisa comprar um monte desses. Honestamente, "Cracking the Coding Interview" provavelmente é suficiente, mas comprei mais para ter mais prática. Mas eu sempre faço demais.
Eu comprei ambos. Eles me deram muita prática.
Programação de entrevistas expostas: codificando seu caminho durante a entrevista, 4ª edição
Respostas em C++ e Java
Este é um bom aquecimento para a entrevista decifrando a codificação
Não é muito difícil. A maioria dos problemas pode ser mais fácil do que você verá em uma entrevista (pelo que li)
Entrevista decifrando a codificação, 6ª edição
respostas em Java
Escolha um:
Elementos de entrevistas de programação (versão C++)
Elementos de entrevistas de programação em Python
Elementos de entrevistas de programação (versão Java) - Projeto complementar - Esboço de método e casos de teste para cada problema do livro
⬆ voltar ao topo
Essa lista cresceu ao longo de muitos meses e, sim, saiu do controle.
Aqui estão alguns erros que cometi para que você tenha uma experiência melhor. E você economizará meses de tempo.
Assisti horas de vídeos e fiz muitas anotações e, meses depois, havia muitas coisas das quais não me lembrava. Passei 3 dias revisando minhas anotações e fazendo flashcards, para poder revisar. Eu não precisava de todo esse conhecimento.
Por favor, leia para não cometer meus erros:
Retendo o conhecimento da ciência da computação.
Para resolver o problema, criei um pequeno site de flashcards onde poderia adicionar flashcards de 2 tipos: geral e código. Cada cartão tem uma formatação diferente. Criei um site voltado para dispositivos móveis, para poder revisar no meu telefone ou tablet, onde quer que esteja.
Faça o seu gratuitamente:
Repositório de site de flashcards
NÃO RECOMENDO usar meus flashcards. São muitos e a maioria deles são curiosidades que você não precisa.
Mas se você não quiser me ouvir, aqui vai:
Meu banco de dados de cartões flash (1200 cartões):
Meu banco de dados de cartões flash (extremo - 1.800 cartões):
Tenha em mente que exagerei e tenho cartões cobrindo tudo, desde linguagem assembly e curiosidades sobre Python até aprendizado de máquina e estatísticas. É demais para o que é necessário.
Nota sobre os flashcards: na primeira vez que você reconhecer que sabe a resposta, não a marque como conhecida. Você tem que ver o mesmo cartão e respondê-lo várias vezes corretamente antes de realmente saber. A repetição aprofundará esse conhecimento em seu cérebro.
Uma alternativa ao uso do meu site de flashcards é o Anki, que me foi recomendado inúmeras vezes. Ele usa um sistema de repetição para ajudá-lo a lembrar. É fácil de usar, está disponível em todas as plataformas e possui um sistema de sincronização em nuvem. Custa US$ 25 no iOS, mas é gratuito em outras plataformas.
Meu banco de dados de flashcards no formato Anki: https://ankiweb.net/shared/info/25173560 (obrigado @xiewenya).
Alguns alunos mencionaram problemas de formatação com espaços em branco que podem ser corrigidos fazendo o seguinte: abrir o baralho, editar o cartão, clicar nos cartões, selecionar o botão de opção "estilo" e adicionar o membro "espaço em branco: pré;" para a classe do cartão.
ISSO É MUITO IMPORTANTE.
Comece a codificar as perguntas da entrevista enquanto aprende estruturas de dados e algoritmos.
Você precisa aplicar o que está aprendendo para resolver problemas, ou você esquecerá. Eu cometi esse erro.
Depois de aprender um tópico e se sentir confortável com ele, por exemplo, listas vinculadas :
Abra um dos livros de entrevistas de codificação (ou sites com problemas de codificação, listados abaixo)
Faça 2 ou 3 perguntas sobre listas vinculadas.
Passe para o próximo tópico de aprendizagem.
Mais tarde, volte e resolva mais 2 ou 3 problemas de lista vinculada.
Faça isso com cada novo tópico que você aprender.
Continue resolvendo problemas enquanto aprende tudo isso, não depois.
Você não está sendo contratado pelo conhecimento, mas pela forma como aplica o conhecimento.
Existem muitos recursos para isso, listados abaixo. Continue.
Existem muitas distrações que podem consumir um tempo valioso. Foco e concentração são difíceis. Ligue alguma música sem letra e você conseguirá se concentrar muito bem.
⬆ voltar ao topo
Estas são tecnologias predominantes, mas não fazem parte deste plano de estudo:
JavaScript
HTML, CSS e outras tecnologias front-end
SQL
⬆ voltar ao topo
Este curso aborda muitos assuntos. Cada um provavelmente levará alguns dias, ou talvez até uma semana ou mais. Depende da sua programação.
A cada dia, escolha o próximo assunto da lista, assista a alguns vídeos sobre esse assunto e, em seguida, escreva uma implementação dessa estrutura de dados ou algoritmo na linguagem que você escolheu para este curso.
Você pode ver meu código aqui:
C
C++
Pitão
Você não precisa memorizar todos os algoritmos. Você só precisa entendê-lo o suficiente para poder escrever sua própria implementação.
⬆ voltar ao topo
Why is this here? I'm not ready to interview.
Então volte e leia isto.
Por que você precisa praticar a resolução de problemas de programação:
Reconhecimento de problemas e onde as estruturas de dados e algoritmos corretos se encaixam
Reunindo requisitos para o problema
Falando sobre o problema como faria na entrevista
Codificação em um quadro branco ou papel, não em um computador
Criando complexidade de tempo e espaço para suas soluções (veja Big-O abaixo)
Testando suas soluções
Há uma ótima introdução para solução metódica e comunicativa de problemas em uma entrevista. Você também aprenderá isso nos livros de entrevistas de programação, mas achei excelente: Tela de design de algoritmo
Escreva o código em um quadro branco ou papel, não em um computador. Teste com alguns exemplos de entrada. Em seguida, digite-o e teste-o em um computador.
Se você não tiver um quadro branco em casa, compre um bloco de desenho grande em uma loja de arte. Você pode sentar no sofá e praticar. Este é o meu "quadro branco do sofá". Adicionei a caneta na foto apenas para escalar. Se você usar uma caneta, desejará poder apagar. Fica confuso rapidamente. Eu uso lápis e borracha.
A prática de perguntas de codificação não consiste em memorizar respostas para problemas de programação.
⬆ voltar ao topo
Não se esqueça dos seus principais livros de entrevistas sobre codificação aqui.
Resolvendo Problemas:
Como encontrar uma solução
Como dissecar uma declaração de problema do Topcoder
Vídeos de perguntas de entrevista de codificação:
IDeserve (88 vídeos)
Tushar Roy (5 listas de reprodução)
Excelente para orientações sobre soluções de problemas
Nick White - Soluções LeetCode (187 vídeos)
Boas explicações da solução e do código
Você pode assistir vários em pouco tempo
FisherCoder - Soluções LeetCode
Locais de desafio/prática:
Código Leet
Meu site favorito sobre problemas de codificação. Vale a pena o dinheiro da assinatura durante os 1-2 meses que você provavelmente estará preparando.
Veja os vídeos de Nick White e FisherCoder acima para instruções passo a passo do código.
Classificação Hacker
TopCoder
Forças de código
Codilidade
Geeks para Geeks
AlgoExpert
Criado pelos engenheiros do Google, este também é um excelente recurso para aprimorar suas habilidades.
Projeto Euler
muito focado em matemática e não muito adequado para codificação de entrevistas
⬆ voltar ao topo
Tudo bem, chega de conversa, vamos aprender!
Mas não se esqueça de resolver os problemas de codificação acima enquanto aprende!
Nada para implementar aqui, você está apenas assistindo vídeos e fazendo anotações! Yay!
Há muitos vídeos aqui. Apenas assista o suficiente até entender. Você sempre pode voltar e revisar.
Não se preocupe se você não entender toda a matemática por trás disso.
Você só precisa entender como expressar a complexidade de um algoritmo em termos de Big-O.
Harvard CS50 - Notação Assintótica (vídeo)
Big O Notations (tutorial rápido geral) (vídeo)
Big O Notation (e Omega e Theta) - melhor explicação matemática (vídeo)
Skiena (vídeo)
UC Berkeley Big O (vídeo)
Análise Amortizada (vídeo)
TopCoder (inclui relações de recorrência e teorema mestre):
Complexidade Computacional: Seção 1
Complexidade Computacional: Seção 2
Folha de dicas
[Review] Analisando Algoritmos (playlist) em 18 minutos (vídeo)
Bem, isso é o suficiente.
Quando você passa pela "Entrevista decifrando a codificação", há um capítulo sobre isso e, no final, há um teste para ver se você consegue identificar a complexidade do tempo de execução de diferentes algoritmos. É uma super revisão e teste.
⬆ voltar ao topo
contíguo na memória, então a proximidade ajuda no desempenho
espaço necessário = (capacidade do array, que é >= n) * tamanho do item, mas mesmo que seja 2n, ainda O(n)
O(1) para adicionar/remover no final (amortizado para alocações para mais espaço), indexar ou atualizar
O(n) para inserir/remover em outro lugar
Pratique a codificação usando arrays e ponteiros e matemática de ponteiros para pular para um índice em vez de usar indexação.
Nova matriz de dados brutos com memória alocada
size() - número de itens
capacidade() - número de itens que pode conter
está_vazio()
at(index) - retorna o item em um determinado índice, explode se o índice estiver fora dos limites
empurrar (item)
insert(index, item) - insere o item no índice, desloca o valor desse índice e os elementos finais para a direita
prepend(item) - pode usar insert acima no índice 0
pop() - remove do final, retorna valor
delete(index) - exclui item no índice, deslocando todos os elementos finais para a esquerda
remove(item) - procura por valor e remove o índice que o contém (mesmo que em vários lugares)
find(item) - procura o valor e retorna o primeiro índice com esse valor, -1 se não for encontrado
resize(new_capacity) // função privada
pode alocar array int nos bastidores, mas não usar seus recursos
comece com 16 ou, se o número inicial for maior, use potência de 2 - 16, 32, 64, 128
quando atingir a capacidade, redimensione para dobrar o tamanho
ao estourar um item, se o tamanho for 1/4 da capacidade, redimensione para metade
Matrizes CS50 Universidade de Harvard
Matrizes (vídeo)
UC Berkeley CS61B - Linear and Multi-Dim Arrays (vídeo) (comece a assistir a partir de 15m 32s)
Matrizes dinâmicas (vídeo)
Matrizes irregulares (vídeo)
Sobre matrizes:
Implemente um vetor (matriz mutável com redimensionamento automático):
Tempo
Espaço
Descrição (vídeo)
Não há necessidade de implementar
size() - retorna o número de elementos de dados na lista
vazio() - bool retorna verdadeiro se estiver vazio
value_at(index) - retorna o valor do enésimo item (começando em 0 para o primeiro)
push_front(value) - adiciona um item ao início da lista
pop_front() – remove o item da frente e retorna seu valor
push_back(value) - adiciona um item no final
pop_back() - remove o item final e retorna seu valor
front() - obtém o valor do item frontal
back() - obtém o valor do item final
insert(index, value) - insere o valor no índice, para que o item atual nesse índice seja apontado pelo novo item no índice
erase(index) - remove o nó em determinado índice
value_n_from_end(n) - retorna o valor do nó na enésima posição do final da lista
reverse() - inverte a lista
remove_value(value) - remove o primeiro item da lista com este valor
Ponteiros para ponteiros
Listas vinculadas principais versus matrizes (vídeo)
No mundo real, listas vinculadas versus matrizes (vídeo)
Listas vinculadas CS50 Harvard University - isso constrói a intuição.
Listas vinculadas individualmente (vídeo)
CS 61B - Listas Vinculadas 1 (vídeo)
CS 61B - Listas Vinculadas 2 (vídeo)
[Revisão] Listas vinculadas em 4 minutos (vídeo)
Descrição:
Código C (vídeo) - não o vídeo inteiro, apenas partes sobre a estrutura do Node e alocação de memória
Lista vinculada versus matrizes:
Por que você deve evitar listas vinculadas (vídeo)
Entendi: você precisa de conhecimento de ponteiro para ponteiro: (para quando você passa um ponteiro para uma função que pode alterar o endereço para onde esse ponteiro aponta) Esta página é apenas para entender ptr para ptr. Eu não recomendo esse estilo de travessia de lista. A legibilidade e a facilidade de manutenção sofrem devido à inteligência.
Implementar (fiz com ponteiro de cauda e sem):
Lista duplamente vinculada
Pilhas (vídeo)
[Revisão] Pilhas em 3 minutos (vídeo)
Não implementarei. Implementar com o array é trivial
uma implementação ruim usando uma lista vinculada onde você enfileira no início e desenfileira no final seria O(n) porque você precisaria do penúltimo elemento, causando uma travessia completa de cada desenfileiramento
enfileirar: O(1) (amortizado, lista vinculada e array [sondagem])
desenfileirar: O (1) (lista vinculada e array)
vazio: O(1) (lista vinculada e array)
enqueue(value) – adiciona item no final do armazenamento disponível
dequeue() - retorna o valor e remove o elemento adicionado menos recentemente
vazio()
completo()
enqueue(value) - adiciona valor em uma posição na cauda
dequeue() - retorna o valor e remove o elemento adicionado menos recentemente (frente)
vazio()
Fila (vídeo)
Buffer circular/FIFO
[Revisão] Filas em 3 minutos (vídeo)
Implemente usando lista vinculada, com ponteiro final:
Implemente usando um array de tamanho fixo:
Custo:
hash(k, m) - m é o tamanho da tabela hash
add(key, value) - se a chave já existir, atualize o valor
existe (chave)
pegar (chave)
remover (chave)
Tabelas de hash principais (vídeo)
Estruturas de dados (vídeo)
Problema na lista telefônica (vídeo)
tabelas hash distribuídas:
Uploads instantâneos e otimização de armazenamento no Dropbox (vídeo)
Tabelas Hash Distribuídas (vídeo)
Hashing com encadeamento (vídeo)
Duplicação de mesa, Karp-Rabin (vídeo)
Endereçamento aberto, hash criptográfico (vídeo)
PyCon 2010: O Poderoso Dicionário (vídeo)
PyCon 2017: O dicionário ainda mais poderoso (vídeo)
Randomização (avançada): Hashing universal e perfeito (vídeo)
(Avançado) Hashing perfeito (vídeo)
[Revisão] Tabelas hash em 4 minutos (vídeo)
Vídeos:
Cursos on-line:
Implementar com array usando sondagem linear
⬆ voltar ao topo
pesquisa binária (em uma matriz classificada de inteiros)
pesquisa binária usando recursão
Pesquisa binária (vídeo)
Pesquisa binária (vídeo)
detalhe
planta
[Review] Pesquisa binária em 4 minutos (vídeo)
Implementar:
Inteiro Absoluto
Trocar
4 maneiras de contar bits em um byte (vídeo)
Contar bits
Como contar o número de bits definidos em um número inteiro de 32 bits
Binário: pontos positivos e negativos (por que usamos o complemento de dois) (vídeo)
Complemento de 1s
Complemento de 2s
palavras
Boa introdução: manipulação de bits (vídeo)
Tutorial de programação C 2-10: Operadores bit a bit (vídeo)
Manipulação de bits
Operação bit a bit
Bithacks
O pequeno brincalhão
O Bit Twiddler interativo
Bit Hacks (vídeo)
Pratique Operações
você deve conhecer muitas das potências de 2 de (2 ^ 1 a 2 ^ 16 e 2 ^ 32)
Folha de dicas de bits
Obtenha uma boa compreensão da manipulação de bits com: &, |, ^, ~, >>, <<
Complemento de 2s e 1s
Contar bits definidos
Trocar valores:
Valor absoluto:
⬆ voltar ao topo
Notas do BFS:
Notas do DFS:
ordem de nível (BFS, usando fila)
complexidade de tempo: O (n)
complexidade do espaço: melhor: O(1), pior: O(n/2)=O(n)
complexidade de tempo: O (n)
complexidade do espaço: melhor: O(log n) - média. pior altura da árvore: O (n)
em ordem (DFS: esquerda, própria, direita)
pós-ordem (DFS: esquerda, direita, próprio)
pré-encomenda (DFS: self, left, right)
Introdução às árvores (vídeo)
Travessia de árvore (vídeo)
BFS (pesquisa em largura) e DFS (pesquisa em profundidade) (vídeo)
[Revisão] Pesquisa ampla em 4 minutos (vídeo)
[Revisão] Pesquisa em profundidade em 4 minutos (vídeo)
[Revisão] Tree Traversal (playlist) em 11 minutos (vídeo)
insert // insere valor na árvore
get_node_count // obtém a contagem dos valores armazenados
print_values // imprime os valores na árvore, do mínimo ao máximo
delete_tree
is_in_tree // retorna verdadeiro se um determinado valor existir na árvore
get_height // retorna a altura em nós (a altura do nó único é 1)
get_min // retorna o valor mínimo armazenado na árvore
get_max // retorna o valor máximo armazenado na árvore
is_binary_search_tree
excluir_valor
get_sucessor // retorna o próximo valor mais alto na árvore após determinado valor, -1 se nenhum
Árvore de pesquisa binária - Implementação em C/C++ (vídeo)
Implementação BST - alocação de memória em pilha e heap (vídeo)
Encontre o elemento mínimo e máximo em uma árvore de pesquisa binária (vídeo)
Encontre a altura de uma árvore binária (vídeo)
Travessia de árvore binária - estratégias em largura e em profundidade (vídeo)
Árvore binária: passagem de ordem de nível (vídeo)
Travessia de árvore binária: pré-encomenda, inordem, pós-ordem (vídeo)
Verifique se uma árvore binária é uma árvore de pesquisa binária ou não (vídeo)
Exclua um nó da árvore de pesquisa binária (vídeo)
Sucessor Inorder em uma árvore de pesquisa binária (vídeo)
Revisão da árvore de pesquisa binária (vídeo)
Introdução (vídeo)
MIT (vídeo)
C/C++:
Implementar:
inserir
sift_up - necessário para inserção
get_max – retorna o item máximo, sem removê-lo
get_size() - retorna o número de elementos armazenados
is_empty() – retorna verdadeiro se o heap não contiver elementos
extract_max - retorna o item máximo, removendo-o
sift_down - necessário para extract_max
remove(x) - remove item no índice x
heapify - cria um heap a partir de uma matriz de elementos, necessários para heap_sort
heap_sort() - pegue um array não classificado e transforme-o em um array classificado usando um heap máximo ou heap mínimo
visualizado como uma árvore, mas geralmente é linear no armazenamento (matriz, lista vinculada)
Pilha
Introdução (vídeo)
Árvores binárias (vídeo)
Observação sobre a altura da árvore (vídeo)
Operações Básicas (vídeo)
Árvores binárias completas (vídeo)
Pseudocódigo (vídeo)
Heap Sort - salta para o início (vídeo)
Classificação de heap (vídeo)
Construindo uma pilha (vídeo)
MIT 6.006 Introdução a Algoritmos: Heaps Binários
CS 61B Aula 24: Filas prioritárias (vídeo)
BuildHeap de tempo linear (heap máximo)
[Review] Heap (playlist) em 13 minutos (vídeo)
Implemente um heap máximo:
⬆ voltar ao topo
Notas:
Eu não recomendaria classificar uma lista vinculada, mas a classificação por mesclagem é possível.
Mesclar classificação para lista vinculada
Classificando a estabilidade do algoritmo
Estabilidade em algoritmos de classificação
Estabilidade em algoritmos de classificação
Algoritmos de classificação - Estabilidade
sem classificação de bolha - é terrível - O (n ^ 2), exceto quando n <= 16
Implemente classificações e conheça o melhor/pior caso, complexidade média de cada um:
Estabilidade nos algoritmos de classificação ("O Quicksort é estável?")
Quais algoritmos podem ser usados em listas vinculadas? Qual em matrizes? Qual dos dois?
Para heapsort, consulte a estrutura de dados Heap acima. A classificação de heap é ótima, mas não estável
Sedgewick - Mergesort (5 vídeos)
1. Mesclarsort
2. Mergesort de baixo para cima
3. Classificando a Complexidade
4. Comparadores
5. Estabilidade
Sedgewick - Quicksort (4 vídeos)
1. Classificação rápida
2. Seleção
3. Chaves duplicadas
4. Classificações do sistema
Universidade da Califórnia em Berkeley:
CS 61B Aula 29: Classificação I (vídeo)
CS 61B Aula 30: Classificação II (vídeo)
CS 61B Aula 32: Classificação III (vídeo)
CS 61B Aula 33: Classificação V (vídeo)
CS 61B 21/04/2014: Classificação Radix (vídeo)
Classificação por bolha (vídeo)
Analisando a classificação por bolha (vídeo)
Classificação por inserção, classificação por mesclagem (vídeo)
Classificação por inserção (vídeo)
Mesclar classificação (vídeo)
Classificação rápida (vídeo)
Classificação por seleção (vídeo)
Mesclar código de classificação:
Usando matriz de saída (C)
Usando matriz de saída (Python)
No local (C++)
Código de classificação rápida:
Implementação (C)
Implementação (C)
Implementação (Python)
[Revisão] Classificação (playlist) em 18 minutos
Classificação rápida em 4 minutos (vídeo)
Classificação de heap em 4 minutos (vídeo)
Mesclar classificação em 3 minutos (vídeo)
Classificação por bolha em 2 minutos (vídeo)
Classificação de seleção em 3 minutos (vídeo)
Classificação por inserção em 2 minutos (vídeo)
Implementar:
Mergesort: O(n log n) média e pior
