README-ptbr.md

Universidade de Entrevista de Programação

Originalmente eu criei isso como uma pequena lista to-do de tópicos de estudo para se tornar um engenheiro de software, mas isso cresceu para a grande lista que você vê hoje. Após passar por esse plano de estudo, Eu fui contratado como Engenheiro de Desenvolvimento de Software na Amazon! Você provavelmente não vai precisar estudar tanto quanto eu. De qualquer maneira, tudo que você precisa está aqui.

Os itens listados aqui irão preparar você muito bem para uma entrevista em praticamente qualquer empresa de software, incluindo as gigantes: Amazon, Facebook, Google ou Microsoft.

Boa sorte para todos vocês!

Original: Inglês

• Acompanhe o progresso da tradução aqui!

Tradutores: Marlon Aviz (Contribuições), marceloogeda (Contribuições), laris151 (Contribuições)

Traduções:

• 中文版本
• Tiếng Việt - Vietnamese
• Español
• Português Brasileiro

Traduções em progresso:

• हिन्दी
• עברית
• Bahasa Indonesia
• Arabic
• Turkish
• French
• Russian
• Ukrainian
• Korean(한국어)
• Telugu
• Polish
• German
• Urdu
• Thai
• Greek
• Italian

O que é isso?

Esse é o meu plano de estudo mensal para ir de desenvolvedor web (autodidata, sem formação em Ciência da Computação) à engenheiro de software para uma grande empresa.

Essa longa lista foi extraída e expandida a partir das anotações de treinamento da Google, então essas são as coisas que você precisa saber. Eu adicionei alguns itens extras no final que podem aparecer na entrevista ou serem úteis para resolver um problema. Muitos itens são da obra “Get that job at Google” (Consiga aquele trabalho na Google) de Steve Yegge's e às vezes são expressados palavra-por-palavra nas anotações de treinamento da Google.

Isso é direcionado à engenheiros de software novos ou àqueles que estão migrando de desenvolvimento de software/web para engenharia de software (onde conhecimento de ciência da computação é necessário). Se você tem vários anos de experiência e está alegando muitos anos de experiência com engenharia de software, pode esperar por uma entrevista mais difícil.

Se você tem vários anos de experiência com desenvolvimento de software/web, observe que grandes empresas como Google, Amazon, Facebook e Microsoft consideram engenharia de software como algo distinto de desenvolvimento de software/web e elas requerem conhecimento de ciência da computação.

Se você quer ser um engenheiro de confiabilidade ou engenheiro de sistemas, estude mais da lista opcional (rede, segurança).

---

Índice

• O que é isso?
• Por que usar?
• Como usar?
• Não ache que você não é inteligente o suficiente
• Sobre os recursos em vídeo
• Processo de Entrevista e Preparação Geral para a Entrevista
• Escolha Uma Linguagem para a Entrevista
• Lista de Livros
• Antes de começar
• O que você não verá
• O Plano Diário
• Conhecimento Prévio
• Complexidade Algorítmica / Big-O / Análise assintótica
• Estrutura de Dados
  • Arrays
  • Listas Ligadas
  • Stack
  • Queue (Fila)
  • Tabela hash
• Mais Conhecimento
  • Busca binária
  • Lógica binária
• Árvores
  • Árvores - Anotações e Fundamentos
  • Árvores binárias de busca: ABB
  • Memória Dinâmica (heap) / Filas Prioritárias / Memória Dinâmica Binária (heap binary)
  • árvores de busca balanceadas (conceito geral, não detalhes)
  • transversais: pré-ordem, em-ordem (ordem simétrica), pós-ordem, busca em largura, busca em profundidade
• Ordenação
  • seleção
  • inserção
  • heapsort
  • quicksort
  • ordenação por mistura (merge sort)
• Grafos
  • directed
  • undirected
  • matriz de adjacência
  • lista de adjacência
  • traversals: BFS, DFS
• Ainda Mais Conhecimento
  • Recursão
  • Programação Dinâmica
  • Programação Orientada a Objetos
  • Padrões de Design
  • Combinatórias (n escolhe k) e Probabilidade
  • Algoritmos de Aproximação, NP-Completo e NP
  • Caches
  • Processos e Threads
  • Artigos
  • Testes
  • Agendamento
  • Implementar rotinas de sistema
  • Busca de string e manipulações
  • Tries (ou Árvore de Prefixos)
  • Números de Ponto Flutuantes ("Floating Point Numbers")
  • Unicode
  • Extremidade (ordenação) (ou "endianness" em Inglês)
• Redes
• Design de Sistema, Escalabilidade, Tratamento de Dados (se você tem mais de 4 anos de experiência)
• Revisão Final
• Prática com Questões de Programação
• Exercícios/desafios de programação
• Quando a entrevista estiver se aproximando
• Seu Currículo
• Esteja pensando à respeito para quando a entrevista chegar
• Tenha questões para o entrevistador
• Quando Você Conseguir O Trabalho

---------------- Tudo abaixo é opcional ----------------

• Livros Adicionais
• Aprendizagem Adicional
  • Compiladores
  • Emacs e vi(m)
  • Ferramentas de linha de comando do Unix
  • Teoria da informação
  • Paridade e Código de Hamming
  • Entropia
  • Criptografia
  • Compressão
  • Segurança de Computador
  • Coleta de lixo
  • Programação Paralela
  • Envio de Mensagens, Serialização, e Sistemas de Enfileiramento
  • A*
  • Transformada de Fourier Rápida
  • Filtro de Bloom
  • HyperLogLog
  • Locality-Sensitive Hashing
  • Árvores de van Emde Boas
  • Estruturas de Dados Incrementadas
  • Árvores de busca balanceadas
    • Árvores AVL
    • Árvores Splay
    • Árvores rubro-negras
    • Árvores de busca 2-3
    • Árvores 2-3-4 (também conhecidas como árvores 2-4)
    • Árvores N-ary (K-ary, M-ary)
    • Árvores B
  • Árvores k-D
  • Skiplists
  • Fluxos de Rede
  • Conjuntos Disjuntos e Union-find
  • Matemática para Processamento Rápido
  • Treap
  • Programação Linear
  • Geometria, Envoltória convexa
  • Matemática discreta
  • Aprendizado de Máquina
• Detalhes Adicionais Sobre Alguns Assuntos
• Séries de Vídeos
• Cursos de Ciência da Computação

---

Por que usar?

Quando eu comecei esse projeto, eu não sabia diferenciar memória dinâmica de memória estática, não sabia notação Big-O, árvores, ou como percorrer um grafo. Se eu tivesse que escrever um algoritmo de ordenação, eu posso te dizer que ele não seria muito bom. Todas as estruturas de dados que eu já usei eram construídas dentro da linguagem, e eu não sabia como elas funcionavam por debaixo dos panos. Eu nunca tive que gerenciar memória a não ser que um processo que eu estava rodando desse um erro de "memória insuficiente", nesse caso eu teria que dar um jeito. Eu já usei alguns arrays multidimensionais na minha vida e milhares de arrays associativos, mas eu nunca criei estruturas de dados do zero.

É um longo plano. Você vai levar meses. Se você já é familiarizado com muitas dessas coisas, você vai precisar de muito menos tempo.

Como usar

Tudo abaixo é um esboço, e você deve abordar os itens em ordem de cima para baixo.

Eu estou usando a sintaxe de markdown especial do Github, incluindo listas de tarefas para verificar o progresso.

Crie um novo branch para você verificar itens assim, apenas coloque um x entre os colchetes: [x]

Bifurque (fork) um branch e siga os comandos abaixo

git checkout -b progress

git remote add jwasham https://github.com/jwasham/coding-interview-university

git fetch --all

Marque todas as caixas com X depois que você completar suas alterações

git add .

git commit -m "Marked x"

git rebase jwasham/master

git push --force

Mais sobre a sintaxe de markdown especial do Github

Não ache que você não é inteligente o suficiente

• Engenheiros de software bem sucedidos são inteligentes, mas muitos são inseguros quanto à própria inteligência.
• O mito do Programador Gênio
• É perigoso ir sozinho: Batalhando os monstros invisíveis na indústria de Tecnologia

Sobre os recursos em vídeo

Alguns vídeos estão disponíveis somente ao ingressar em um curso no Coursera, EdX, ou Lynda.com. Esses são chamados de MOOCs (Curso Online Aberto e Massivo). Às vezes as aulas não estão em sessão, nesse caso você terá que esperar alguns meses, portanto não terá acesso até lá. Os cursos da Lynda.com não são gratuitos.

Eu agradeceria a ajuda de vocês em adicionar recursos públicos gratuitos que sempre estejam disponíveis, como vídeos do YouTube para acompanhar os vídeos de curso online.
Eu gosto de usar palestras de universidades;

Processo de Entrevista e Preparação Geral para a Entrevista

• ABC: Always Be Coding

• Whiteboarding (Usando O Quadro Branco)

• Effective Whiteboarding during Programming Interviews (Usando o Quadro Branco Efetivamente durante Entrevistas de Programação)

• Demystifying Tech Recruiting (Desmistificando Recrutamento Técnico)

• Decifrando A Entrevista de Programação Série 1:

  • Gayle L McDowell - Cracking The Coding Interview (video) (Gayle L McDowell - Decifrando A Entrevista de Programação - vídeo)
  • Cracking the Coding Interview with Author Gayle Laakmann McDowell (video) (Decifrando a Entrevista de Programação com o Autor Gayle Laakmann McDowell - vídeo)

• Como Conseguir um Emprego em uma das 4 Gigantes:

  • How to Get a Job at the Big 4 - Amazon, Facebook, Google & Microsoft (video) (Como Conseguir um Emprego em uma das 4 Gigantes - Amazon, Facebook, Google e Microsoft - vídeo)

• Cursos de Preparação:

  • Software Engineer Interview Unleashed (paid course) (Entrevista de Engenheiro de Software Unleashed - curso pago):
    • Aprenda com um ex-entrevistador da Google como se preparar para entrevistas de engenheiro de software.
  • Python for Data Structures, Algorithms, and Interviews! (paid course): (Python para Estrutura de Dados, Algoritmos e Entrevistas! - curso pago)
    • Um curso de preparação para entrevistas focado em Python, que cobre estrutura de dados, algoritmos, entrevistas simuladas e muito mais.

Escolha Uma Linguagem para a Entrevista

Você pode escolher uma linguagem com a qual você esteja confortável para fazer a parte de programação (parte prática) da entrevista, mas para grandes empresas, essas são ótimas opções:

• C++
• Java
• Python

Você também poderia usar essas, mas dê uma lida por aí antes. Podem haver ressalvas:

• JavaScript
• Ruby

Você precisa estar confortável com a linguagem e ser bem informado.

Leia mais sobre as escolhas:

• http://www.byte-by-byte.com/choose-the-right-language-for-your-coding-interview/
• http://blog.codingforinterviews.com/best-programming-language-jobs/

Veja recursos de linguagens aqui

Você vai ver aprendizado de C, C++ e Python incluído abaixo, porque é o que estou aprendendo. Tem alguns livros envolvidos, veja no final.

Lista de Livros

Essa é uma lista menor comparada à que eu usei. Está abreviada para economizar seu tempo.

Preparação para a Entrevista

• Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition (Entrevistas de Programação Expostas: Segredos para Conseguir Seu Próximo Emprego, 2ª Edição)
  • respostas em C++ e Java
  • esse é um bom aquecimento para o Cracking the Coding Interview (Decifrando a Entrevista de Programação)
  • não é muito difícil, a maioria dos problemas poderão ser mais fáceis que aqueles que você verá em uma entrevista (de acordo com o que li)
• Cracking the Coding Interview, 6th Edition (Decifrando a Entrevista de Programação).
  • respostas em Java

Se você tem muito tempo sobrando:

• Elements of Programming Interviews (C++ version) (Elementos de Entrevistas de Programação (Versão C++))
• Elementos de Entrevistas de Programação (Versão Java)
  • livro
  • Projecto de Companheiro - Esboço de Método e Testes para Cada Problema no Livro

Arquitetura de Computador

Se estiver com pouco tempo:

• Write Great Code: Volume 1: Understanding the Machine (Escreva um Excelente Código: Volume 1: Compreendendo a Máquina)
  • O livro foi publicado em 2004, e está meio desatualizado, mas é um recurso incrível para se compreender um computador resumidamente.
  • O autor inventou HLA (High-level Assembly ou, no português, Assembly de alto nível), então considere as menções e exemplos em HLA com cautela. Não é usado amplamente, mas contém exemplos decentes de como o assembly funciona.
  • Esses capítulos valem a pena serem lidos para lhe dar uma boa base:
    • Chapter 2 - Numeric Representation (Capítulo 2 - Representação Numérica)
    • Chapter 3 - Binary Arithmetic and Bit Operations (Capítulo 3 - Aritmética Binária e Operações Bit)
    • Chapter 4 - Floating-Point Representation (Representação em Ponto Flutuante)
    • Chapter 5 - Character Representation (Representação de Caractere)
    • Chapter 6 - Memory Organization and Access (Organização e Acesso de Memória)
    • Chapter 7 - Composite Data Types and Memory Objects (Tipos de Dados Compostos e Objetos de Memória)
    • Chapter 9 - CPU Architecture (Arquitetura de CPU)
    • Chapter 10 - Instruction Set Architecture (Arquitetura de Conjunto de Instruções)
    • Chapter 11 - Memory Architecture and Organization (Arquitetura e Organização de Memória)

Se você tem mais tempo (eu quero esse livro):

• Computer Architecture, Fifth Edition: A Quantitative Approach (Arquitetura de Computador, Quinta Edição: Uma Abordagem Quantitativa)
  • Se quiser uma versão mais rica e atualizada (2011), mas com um tratamento mais longo

Específico de Linguagem

Você precisa escolher uma linguagem para a entrevista (veja acima). Aqui estão minhas recomendações por linguagem. Eu não tenho recursos para todas as linguagens. Contribuições são bem-vindas.

Se você ler um desses, você deverá ter todo conhecimento de estrutura de dados e algoritmos que precisará para começar a resolver problemas de programação. Você pode pular todas as aulas em vídeo nesse projeto, a não ser que você queira uma revisão.

Recursos adicionais específicos a cada linguagem aqui.

C++

Eu não li esses dois, mas eles são muito bem avaliados e escritos por Sedgewick. Ele é incrível.

• Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching (Algoritmos em C++, Partes 1-4: Fundamentos, Estrutura de Dados, Ordenação, Busca).
• Algorithms in C++ Part 5: Graph Algorithms (Algoritmos em C++ Parte 5: Algoritmos de Grafo)

Se você tiver uma recomendação melhor para C++, por favor me informe. Busco por recursos completos.

Java

• Algorithms (Sedgewick and Wayne) (Algoritmos (Sedgewick e Wayne))
  • vídeos com conteúdo do livro (e Sedgewick!):
    • Algorithms I (Algoritmos I)
    • Algorithms II (Algoritmos II)

OU:

• Data Structures and Algorithms in Java (Estrutura de Dados e Algoritmos em Java)
  • por Goodrich, Tamassia, Goldwasser
  • usado como texo opcional para o curso introdutório de Ciência da Computação na Universidade da Califórnia em Berkeley
  • veja o meu resumo sobre a versão em Python abaixo. Esse livro abrange os mesmos tópicos.

Python

• Data Structures and Algorithms in Python (Estrutura de Dados e Algoritmos em Python)
  • por Goodrich, Tamassia, Goldwasser
  • Eu adorei esse livro. Ele cobriu tudo e muito mais.
  • Código pythonico.
  • meu resumo brilhante do livro: https://startupnextdoor.com/book-report-data-structures-and-algorithms-in-python/

Livros Opcionais

Algumas pessoas recomendam esses, mas eu acho que está além do necessário, a não ser que você tenha muitos anos de experiência em engenharia de software e está esperando por uma entrevista muito mais difícil:

• Algorithm Design Manual (Skiena) (Manual de Design de Algoritmo)

  • Como uma revisão e reconhecimento de problema
  • A parte de catálogos de algoritmos está muito além da margem de dificuldade que você terá em uma entrevista.
  • Esse livro tem 2 partes:
    • livro de aula sobre estrutura de dados e algoritmos
      • prós:
        • é uma boa revisão assim como qualquer texto de algoritmos seria
        • boas estórias da experiência dele resolvendo problemas na indústria e na universidade
        • exemplo de código em C
      • contras:
        • pode ser tão denso ou impenetrável quanto CLRS (Introdução a Algoritmos), e em alguns casos, CLRS pode ser uma alternativa melhor para alguns temas
        • capítulos 7, 8 e 9 podem ser sofridos para acompanhar, já que alguns itens não são bem explicados ou requerem mais cérebro do que eu tenho
        • não me entenda mal: Eu gosto de Skiena, do estilo de ensino dele, e maneirismos, mas pode não ser um material do tipo da universidade Stony Brook.
    • catálogo de algoritmos
      • essa é a verdadeira razão para você comprar esse livro.
      • prestes a chegar nessa parte. Vou atualizar aqui assim que eu terminar de ler essa parte.
  • Pode alugar no kindle
  • Half.com é um ótimo recurso para livros com bons preços.
  • Respostas:
    • Solutions (Soluções)
    • Solutions (Soluções)
  • Errata

• Introduction to Algorithms (Introdução à Algoritmos)

  • Importante: Ler esse livro só terá um valor limitado. Esse livro é ótimo para revisão de algoritmos e estrutura de dados, mas não irá te ensinar a escrever um bom código. Você deve ser capaz de codificar uma solução decente eficientemente.
  • Half.com é um ótimo recurso para livros com bons preços.
  • também conhecido como CLR, às vezes CLRS, porque Stein estava atrasado para o negócio

• Programming Pearls (Pérolas de Programação)

  • Os primeiros capítulos apresentam soluções inteligentes para problemas de programação (alguns bem velhos usando suporte magnético)
    mas isso é só uma introdução. Esse é um guia sobre design e arquitetura de programa, parecido com Code Complete, mas muito mais curto.

• "Algorithms and Programming: Problems and Solutions" by Shen ("Algoritmos e Programação: Problemas e Soluções" por Shen)

  • Um bom livro, mas depois de trabalhar nos problemas em várias páginas eu fiquei frustrado com o Pascal, loops do...while, arrays de 1 índice (index), e resultados de satisfação pós-condição pouco claros.
  • Prefiro gastar tempo em problemas de programação de outro livro ou problemas de programação online.

Antes de começar

Essa lista cresceu por longos meses, e sim, ela meio que saiu do controle.

Aqui estão alguns erros que eu cometi para que você tenha uma experiência melhor.

1. Você não se lembrará de tudo

Assisti a horas de vídeos e fiz anotações e meses depois havia muito que eu não lembrava. Eu passei 3 dias revisando minhas anotaçes e fazendo flashcards para que eu pudesse relembrar.

Por favor, leia para que você não cometa os meus erros:

Retaining Computer Science Knowledge

2. Use Flashcards

Para solucionar o problema, eu fiz um pequeno site de flashcards onde eu poderia adicionar dois tipos de flashcards: genérico e código.
Cada cartão tem formatação diferente.

Eu fiz um website focado em mobile para que eu pudesse rever no meu celular, tablet, onde quer que eu esteja.

Faça o seu próprio, grátis:

• Repositório de flashcards
• Minha base de dados de flashcards (antigo - 1200 cartões):
• Minha base de dados de flashcards (novo - 1800 cartões):

Tenha em mente que eu exagerei e tenho cartões abrangendo desde linguagem assembly e trivialidades de Python até aprendizado de máquina e estatísticas. É demais para o que é requerido. 

Nota: A primeira vez que você reconhece 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 conhecê-lo. A repetição colocará esse conhecimento mais aprodundado em seu cérebro.

Uma alternativa ao uso do meu site de flashcards é Anki, que me foi recomendado várias vezes. Ele usa um sistema de repetição para ajuda-lo a se lembrar. É fácil de usar, está disponível em todas as plataformas e possui um sistema de sincronização em nuvem. Ele custa 25 dólares no iOS, mas é gratuito em outras plataformas.

Meu banco de dados de flashcards em formato Anki: https://ankiweb.net/shared/info/25173560 (obrigado @xiewenya)

3. Revise, Revise e Revise

Eu mantenho um conjunto de anotações em ASCII, OSI stack, Notações Big-O, e muito mais. Eu os estudo quando tenho algum tempo livre.

Faça uma pausa durante os problemas de programação por meia hora e passe por seus flashcards.

4. Foco

Há um monte de distrações que podem ocupar um tempo valioso. Foco e concentração são difíceis.

O que você não verá

Essas são tecnologias predominantes, mas não são partes desse plano de estudo:

• SQL
• Javascript
• HTML, CSS, e outras tecnologias de front-end

O Plano Diário

Alguns temas levam um dia, e alguns vão levar vários dias. Alguns são apenas aprendizado sem nada para implementar.

A cada dia eu pego um tema da lista abaixo, assisto vídeos sobre aquele tema, e escrevo uma implementação em:

• C - usando structs e funções que usam struct * e alguma outra coisa como argumentos.
• C++ - sem usar types internos.
• C++ - usando types internos, como std::list da STL para uma lista ligada
• Python - usando types internos (para continuar praticando Python)
• e escrevo testes para garantir que estou fazendo certo, às vezes uso apenas declarações simples de asser()
• Você pode fazer com Java também ou alguma outra linguagem, eu apenas prefiro essas cima.

Você não precisa de todas essas linguagens. Você precisa de apenas uma linguagem para a entrevista.

Por que programar em todas essas linguagens?

• Prática, prática, prática, até eu enjoar e poder implementar sem problemas (algumas tem muitos casos com valores de entrada extremos, ou seja, muito pequenos ou muito grandes, e também têm muitos detalhes de escrituração para lembrar)
• Trabalhar dentro das restrições básicas (alocar/liberar memória sem ajuda de um coletor de lixo (com exceção de Python))
• Fazer uso de types internos para que eu possa ter experiência em usar ferramentas internas para problemas do mundo real (não vou escrever minha própria implementação de lista ligada durante a etapa de produção)

Talvez eu não tenha tempo para fazer tudo isso para cada tema, mas eu vou tentar.

Você pode ver meu código aqui:

• [C] (https://github.com/jwasham/practice-c)
• [C++] (https://github.com/jwasham/practice-cpp)
• [Python] (https://github.com/jwasham/practice-python)

Você não precisa memorizar os detalhes intrínsecos de cada algoritmo.

Escreva código em um quadro branco ou papel, não em um computador. Teste com umas amostras de valores de entrada (input). Depois teste em um computador.

Conhecimento Prévio

• Aprenda C

  • C está em todo lugar. Você vai ver exemplos em livros, aulas, vídeos, em todo lugar enquanto você estiver estudando.
  • C Programming Language, Vol 2 (Linguagem de Programação C, Vol 2)
    • Esse é um livro curto, mas vai te ajudar a ter um ótimo domínio da linguagem C e se você praticar um pouco você irá se tornar proficiente rapidamente. Entender C te ajuda a entender como os programas e a memória funcionam.
    • answers to questions (respostas para as questões)

• Como computadores processam um programa:

  • How does CPU execute program (video) (Como uma CPU executa um programa - vídeo)
  • Machine Code Instructions (video) (Instruções de Código de Máquina - vídeo)

Complexidade Algorítmica / Big-O / Análise assintótica

• nada para implementar

• Harvard CS50 - Asymptotic Notation (video) (Harvard CS50 - Notação Assintótica - vídeo)

• Big O Notations (general quick tutorial) (video) (Notações Big-O (rápido tutorial geral) - vídeo)

• Big O Notation (and Omega and Theta) - best mathematical explanation (video) (Notação Big-O (e Omega e Theta) - melhor explicação matemática - vídeo)

• Skiena:

  • video
  • slides

• A Gentle Introduction to Algorithm Complexity Analysis (Uma Introdução Gentil a Análise de Complexidade Algoritmica)

• Orders of Growth (video) (Ordens de Crescimento - vídeo)

• Asymptotics (video) (Assintóticas - vídeo)

• UC Berkeley Big O (video) (Big-O - Universidade da Califórnia em Berkeley - vídeo)

• UC Berkeley Big Omega (video) (Grande Omega - Universidade da Califórnia em Berkeley - vídeo)

• Amortized Analysis (video) (Análise Amortizada - vídeo)

• Illustrating "Big O" (video) (Ilustrando "Big-O" - vídeo)

• TopCoder (inclui relações de recorrência e teorema mestre):

  • Computational Complexity: Section 1 (Complexidade Computacional: Seção 1)
  • Computational Complexity: Section 2 (Complexidade Computacional: Seção 2)

• Cheat sheet (Folha de Consultas)

  Se alguma das aulas forem muito "matemáticas", você pode pular para o final e ver o vídeo de matemática discreta para ganhar um conhecimento base.

Estrutura de Dados

• Arrays

  • Implementar um vetor de redimensionamento automático.
  • Descrição:
    • Arrays (video)
    • UCBerkley CS61B - Linear and Multi-Dim Arrays (video) (Arrays lineares e multidimensionais - vídeo)
    • Basic Arrays (video) (Arrays básicos - vídeo)
    • Multi-dim (video) (Multidimensionais - vídeo)
    • Dynamic Arrays (video) (Arrays Dinâmicos - vídeo)
    • Jagged Arrays (video) (Arrays Multidimensionais - vídeo)
    • Jagged Arrays (video) (Arrays Multidimensionais - vídeo)
    • Resizing arrays (video) (Arrays Dinâmicos)
  • Implementar um vetor (array mutável com redimensionamento automático):
    • Praticar programação usando arrays e ponteiros, e matemática de ponteiros para pular para um índice ao invés de usar indexação.
    • novo array de dados brutos com memória alocada
      • pode alocar array de números inteiros por de baixo dos panos, só não pode usar seus recursos
      • começa com 16, ou se o número inicial for maior, usar potência de 2 - 16, 32, 64, 128
    • size() - número de itens
    • capacity() - número de itens que pode conter
    • is_empty()
    • at(index) - retorna o item que está no índice fornecido, dá erro se o índice estiver fora da capacidade do array
    • push(item)
    • insert(índice, item) - insere "item" no "índice", muda o valor daquele índice e move os elementos excedentes para a direita
    • prepend(item) - pode usar o insert acima no índice 0
    • pop() - remove do final, retorna o valor
    • delete(índice) - deleta o item no índice fornecido, deslocando todos os elementos excedentes para a esquerda
    • remove(item) - busca pelo valor e remove o índice contendo ele (mesmo que esteja em múltiplos lugares)
    • find(item) - busca pelo valor e retorna o primeiro índice com aquele valor, -1 se não encontrar
    • resize(nova_capacidade) // função privada
      • quando você atinge o limite da capacidade, redimensone para dobrar a capacidade
      • quando estiver usando pop() em um item, se o tamanho for 1/4 da capacidade, redimensionar para a metade da capacidade
  • Tempo
    • O(1) para adicionar/remover no final (amortizado para alocações para mais espaço), índice ou atualização
    • O(n) para inserir/remover em algum outro lugar
  • Espaço
    • contíguo na memória, então proximidade ajuda no desempenho
    • espaço necessário = (capacidade do array, a qual é >= n) * tamanho do item, mas mesmo que seja 2n, ainda será O(n)

• Listas Ligadas

  • Descrição:
    • Singly Linked Lists (video) (listas ligadas individualmente - vídeo)
    • CS 61B - Linked Lists 1 (video) (CS 61B - Listas Ligadas 1 - vídeo)
    • CS 61B - Linked Lists 2 (video) (CS 61B - Listas Ligadas 2 - vídeo)
  • C Code (video) (Código em C - vídeo) - não o vídeo inteiro, apenas as partes sobre estrutura de nodes (nós) e alocação de memória.
  • Listas Ligadas vs Arrays:
    • Core Linked Lists Vs Arrays (video) (Fundamentos de Listas Ligadas vs Arrays - vídeo)
    • In The Real World Linked Lists Vs Arrays (video) (No Mundo Real: Listas Ligadas vs Arrays - vídeo)
  • why you should avoid linked lists (video) (por que você deve evitar listas ligadas - vídeo)
  • Peguei vocês: você precisa de conhecimento de ponteiro para ponteiro: (para quando você passar um ponteiro para uma funcção que poderá mudar o endereço para o qual o ponteiro aponta) Essa página é só para ter uma noção sobre ponteiro para ponteiro. Eu não recomendo o estilo transversal dessa lista. Legibilidade e manutenção sofrem devido à engenhosidade.
    • Pointers to Pointers (Ponteiros para Ponteiros)
  • implementar (eu fiz com e sem ponteiro de cauda, ponteiro que aponta para o último node (nó) da lista):
    • size() - retorna o número de elementos de dados na lista
    • empty() - boleano retorna verdadeiro se estiver vazio
    • value_at(índice) - retorna o valor do item n (começando no 0 para o primeiro)
    • push_front(valor) - adiciona um item no início da lista, logo antes do seu atual primeiro elemento
    • pop_front() - remove o item do início da lista e retorna o seu valor
    • push_back(valor) - adiciona um item no final da lista
    • pop_back() - remove um item do final e retorna seu valor
    • front() - obtém valor do item que está no início da lista
    • back() - obtém valor do item que está no final da lista
    • insert(índice, valor) - insere "valor" no "índice", e depois o item atual naquele índice é apontado pelo novo item no "índice"
    • erase(índice) - remove o node (nó) no índice fornecido
    • value_n_from_end(n) - retorna o valor do node (nó) na posição n a partir do final da lista
    • reverse() - reverte a lista
    • remove_value(valor) - remove o primeiro item na lista com esse valor
  • Listas Ligadas Duplamente
    • Description (video) (Descrição - vídeo)
    • Não há necessidade de implementar

• Stack

  • Stacks (video)
  • Using Stacks Last-In First-Out (video) (Usando Stacks Último a Entrar Primeiro a Sair - vídeo)
  • Não implementarei. Implementar com array é trivial.

• Queue (Fila)

  • Using Queues First-In First-Out(video) (Usando queues FIFO(Primeiro a entrar, último a sair) - vídeo)
  • Queue (video)
  • Circular buffer/FIFO (Buffer circular/Primeiro a entrar, último a sair)
  • Priority Queues (video) (Queues com Prioridade - vídeo)
  • Implementar usando lista ligada, com ponteiro de cauda (aponta para o último elemento de uma lista):
    • enqueue(valor) - adiciona "valor" na posição na cauda (final da lista)
    • dequeue() - retorna um valor e remove o elemento menos recentemente adicionado (início da lista))
    • empty()
  • Implementar usando arrays de tamanho-fixo:
    • enqueue(valor) - adiciona um item no final do armazenamento disponível
    • dequeue() - retorna um valor e remove um elemento menos recentemente adicionado
    • empty()
    • full()
  • Custo:
    • uma implementação ruim usando lista ligada na qual você coloca na fila (enqueue) no head (cabeça/início da lista) e tira da fila (dequeue) no tail (cauda/final da lista) seria O(n) porque você precisaria do penúltimo elemento, causando uma transversal completa a cada dequeue
    • enqueue: O(1) (amortizado, lista ligada e array [sondagem])
    • dequeue: O(1) (lista ligada e array)
    • empty (vazio): O(1) (lista ligada e array)

• Tabela hash

  • vídeos:

    • Hashing with Chaining (video) (Hashing com Encadeamento - vídeo)
    • Table Doubling, Karp-Rabin (video) (Duplicação de Tabela, Karp-Rabin - vídeo)
    • Open Addressing, Cryptographic Hashing (video) (Endereçamento Aberto, Hashing Criptográfico - vídeo)
    • PyCon 2010: The Mighty Dictionary (video) (PyCon 2010: O Poderoso Dicionário (vídeo)
    • (Advanced) Randomization: Universal & Perfect Hashing (video) ((Avançado) Randomização: Hashing Perfeito & Universal - vídeo)
    • (Advanced) Perfect hashing (video) ((Avançado) Hashing perfeito - vídeo)

  • Cursos Online:

    • Understanding Hash Functions (video) (Compreendendo Funções Hash - vídeo)
    • Using Hash Tables (video) (Usando Tabelas Hash - vídeo)
    • Supporting Hashing (video) (Hashing de Suporte - vídeo)
    • Language Support Hash Tables (video) (Tabelas Hash de Suporte de Linguagem - vídeo)
    • Core Hash Tables (video) (Fundamentos de Tabelas Hash - vídeo)
    • Data Structures (video) (Estruturas de Dados - vídeo)
    • Phone Book Problem (video) (Problema da Lista Telefônica (vídeo) )
    • tabelas hash distribuídas:
      • Instant Uploads And Storage Optimization In Dropbox (video) (Uploads Instantâneos E Otimização de Armazenamento no Dropbox - vídeo)
      • Distributed Hash Tables (video) (Tabelas Hash Distribuídas - vídeo)

  • implementar com array usando sondagem linear

    • hash(k, m) - m é o tamanho da tabela hash
    • add(chave, valor) - se a chave já existe, atualizar o valor
    • exists(chave)
    • get(chave)
    • remove(chave)

Mais Conhecimento

• Busca binária

  • Binary Search (video) (Busca Binária - vídeo)
  • Binary Search (video) (Busca Binária - vídeo)
  • detail (detalhes)
  • Implementar:
    • busca binária (em um array ordenado de números inteiros)
    • busca binária usando recursividade

• Lógica binária

  • Bits cheat sheet (Folha de consultas sobre Bits) - você deve conhecer várias das potências de 2 de (2^1 até 2^16 e 2^32)
  • Consiga um bom entendimento sobre manipulação de bits com: &, |, ^, ~, >>, <<
    • words (palavras)
    • Boa introdução: Bit Manipulation (video) (Manipulação de Bit - vídeo)
    • C Programming Tutorial 2-10: Bitwise Operators (video) (Tutorial de Programação em C 2-10: Operadores Binários - vídeo)
    • Bit Manipulation (Manipulação de Bit)
    • Bitwise Operation (Lógica Binária)
    • Bithacks (Snippets/Fragmentos de código, um tipo de cheatsheet (folha de consultas))
    • The Bit Twiddler
    • The Bit Twiddler Interactive (Interativo)
  • Complemento de 2 e 1
    • Binary: Plusses & Minuses (Why We Use Two's Complement) (video) (Binário: Vantagens & Desvantagens (Por Que Usamos Complemento de 2) - vídeo)
    • 1s Complement (Complemento de 1)
    • 2s Complement (Complemento de 2)
  • contagem de bits fixos
    • 4 ways to count bits in a byte (video) (4 maneiras de contar bits em um byte - vídeo)
    • Count Bits (Contagem de Bits)
    • How To Count The Number Of Set Bits In a 32 Bit Integer (Como Contar O Número De Bits Fixos Em um Número inteiro de 32 bits)
  • arredondar para a próxima potência de 2:
    • Round Up To Next Power Of Two (Arredondar Para Cima Para A Próxima Potência De Dois)
  • trocar valores:
    • Swap (Trocar)
  • valor absoluto:
    • Absolute Integer (Número Inteiro Absoluto)

Árvores

• Árvores - Anotações e Fundamentos

  • Series: Core Trees (video) (Série: Fundamentos de Árvores - vídeo)
  • Series: Trees (video) (Série: Árvores - vídeo)
  • contrução básica de árvore
  • transversal
  • algorítmos de manipulação
  • Busca em largura (conhecido no Inglês como BFS ou breadth-first search)
    • MIT (vídeo)
    • ordem de nível (busca em largura, usando filas) complexidade de tempo: O(n) complexidade de espaço: melhor: O(1), pior: O(n/2)=O(n)
  • Busca em profundidade (conhecido no Inglês como DFS ou depth-first search)
    • MIT (vídeo)
    • anotações: complexidade de tempo: O(n) space complexity: melhor: O(log n) - altura média da árvore pior: O(n)
    • em-ordem ou ordem simétrica(na busca em profundidade (ou DFS): percorre subárvore esquerda em ordem simétrica (em-ordem), visita a raiz, percorre subárvore direita em ordem simétrica)
    • pós-ordem (na busca em profundidade (ou DFS): percorre subárvore esquerda em pós-ordem, percorre subárvore direita em pós-ordem, visita a raiz)
    • pré-ordem (na busca em profundidade (ou DFS): visita a raiz, percorre subárvore esquerda em pré-ordem, percorre subárvore direita em pré-ordem)

• Árvores binárias de busca: ABB

  • Binary Search Tree Review (video) (Revisão de Árvores Binárias de Busca - vídeo)
  • Série (vídeo)
    • começa com tabela de símbolos e passa por aplicações de ABB
  • Introduction (video) (Introdução - vídeo)
  • MIT (vídeo)
  • C/C++:
    • Binary search tree - Implementation in C/C++ (video) (Árvore binária de busca - Implementação em C/C++ - vídeo)
    • BST implementation - memory allocation in stack and heap (video) (Implementação de ABB - alocação de memória estática (stack) e dinâmica (heap) - vídeo)
    • Find min and max element in a binary search tree (video) (Encontrar elementos min e max em uma árvore binária de busca - vídeo)
    • Find height of a binary tree (video) (Encontrar altura de uma árvore binária - vídeo)
    • Binary tree traversal - breadth-first and depth-first strategies (video) (Percurso de uma árvore binária - estratégias de busca em largura e busca em profundidade - vídeo)
    • Binary tree: Level Order Traversal (video) (Árvore binária: Percurso de Ordens de Níveis - vídeo)
    • Binary tree traversal: Preorder, Inorder, Postorder (video) (Percurso de árvore binária: Pré-ordem, Em-ordem (ordem simétrica), Pós-ordem - vídeo)
    • Check if a binary tree is binary search tree or not (video) (Verificar se uma árvore binária é uma árvore binária de busca ou não - vídeo)
    • Delete a node from Binary Search Tree (video) (Deletar um nó de uma Árvore Binária de Busca - vídeo)
    • Inorder Successor in a binary search tree (video) (Sucessor Em-ordem em uma árvore binária de busca - vídeo)
  • Implementar:
    • insert // insere um valor na árvore
    • get_node_count // obtém contagem de valores armazenados
    • print_values // exibe os valores na árvore, do min até o max
    • delete_tree
    • is_in_tree // retorna "true" se tal valor existir na árvore
    • get_height // retorna a altura nos nós (altura de 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
    • delete_value
    • get_successor // retorna o próximo maior valor na árvore após dado valor, -1 se não houver nenhum

• Memória Dinâmica (heap) / Filas Prioritárias / Memória Dinâmica Binária (heap binary)

  • visualizada como uma árvore, mas geralmente é linear no armazenamento (array, lista ligada)
  • Heap (Memória DInâmica)
  • Introduction (video) (Introdução - vídeo)
  • Naive Implementations (video) (Implementações Ingênuas - vídeo)
  • Binary Trees (video) (Árvores Binárias - vídeo)
  • Tree Height Remark (video) (Observações sobre Altura de Árvore - vídeo)
  • Basic Operations (video) (Operações Básicas - vídeo)
  • Complete Binary Trees (video) (Árvores Binárias Completas - vídeo)
  • Pseudocode (video) (Pseudocódigo - vídeo)
  • Heap Sort - jumps to start (video) (Algoritmo de Ordenação heapsort - pula para o começo - vídeo)
  • Heap Sort (video) (Algoritmo de Ordenação heapsort - vídeo)
  • Building a heap (video) (Construindo uma memória dinâmica (heap) - vídeo)
  • MIT: Heaps and Heap Sort (video) (MIT: Memórias Dinâmias e heapsort - vídeo)
  • CS 61B Lecture 24: Priority Queues (video) (CS (Ciência da Computação) 61B Aula 24: Filas Prioritárias - vídeo)
  • Linear Time BuildHeap (max-heap) (BuildHeap em Tempo Linear (heap máxima))
  • Implementar uma heap máxima (max-heap):
    • insert
    • sift_up - necessário insert
    • get_max - retorna o item max (maior item), sem removê-lo
    • get_size() - retorna o número de elementos armazenados
    • is_empty() - retorna "true" se o heap não contém elementos
    • extract_max - retorna o item max (maior item), removendo ele
    • sift_down - necessário para extract_max
    • remove(i) - remove o item no índice x
    • heapify - cria um heap a partir de um array de elementos, necessário para heap_sort
    • heap_sort() - pega um array não-ordenado e o transforma em um array ordenado "in-place" (sem gerar um novo array) usando uma heap máxima (max-heap)
      • nota: usando uma heap mínima (min-heap) ao invés de uma heap máxima (max-heap) poderia salvar operações, mas duplicar o espaço necessário (não é possível fazer "in-place")

Ordenação

• Anotações:

  • Implementar ordenações e saber melhor/pior cenário, complexidade média de cada um:
    • sem ordenação por bolha - é terrível - O(n^2), exceto quando n <= 16
  • estabilidade em algoritmos de ordenação ("O algoritmo de ordenação quicksort é estável?")
    • Sorting Algorithm Stability (Artigo da Wikipédia em Inglês sobre Estabilidade de Algoritmo de Ordenação, infelizmente a versão em Português não é tão informativa)
    • Stability In Sorting Algorithms (Estabilidade em Algoritmos de Ordenação)
    • Stability In Sorting Algorithms (Estabilidade em Algoritmos de Ordenação)
    • Sorting Algorithms - Stability (Algoritmos de Ordenação - Estabilidade)
  • Quais algoritmos podem ser usados em listas ligadas? Quais em arrays? Quais em ambos?
    • Eu não recomendaria ordenar uma lista ligada, mas ordenação por mistura (merge sort) é possível de se fazer.
    • Merge Sort For Linked List (Merge Sort Para Listas Ligadas)

• Para heapsort, veja estrutura de dados heap acima. Heapsort é ótimo, mas não é estável.

• Sedgewick - Mergesort (5 vídeos)

  • 1. Mergesort
  • 2. Bottom up Mergesort (Mergesort de baixo para cima)
  • 3. Sorting Complexity (Complexidade de Ordenação)
  • 4. Comparators (Comparadores)
  • 5. Stability (Estabilidade)

• Sedgewick - Quicksort (4 vídeos)

  • 1. Quicksort
  • 2. Selection (Seleção)
  • 3. Duplicate Keys (Chaves Duplicadas)
  • 4. System Sorts (Ordenações de Sistema)

• Universidade da Califórnia em Berkeley:

  • CS 61B Lecture 29: Sorting I (video) (Ciência da Computação 61B Aula 29: Ordenação I - vídeo)
  • CS 61B Lecture 30: Sorting II (video) (Ciência da Computação 61B Aula 30: Ordenação II - vídeo)
  • CS 61B Lecture 32: Sorting III (video) (Ciência da Computação 61B Aula 32: Ordenação III - vídeo)
  • CS 61B Lecture 33: Sorting V (video) (Ciência da Computação 61B Aula 33: Ordenação V - vídeo)

• Bubble Sort (video) (Ordenação por Bolha - vídeo)

• Analyzing Bubble Sort (video) (Analisando Ordenação por Bolha - vídeo)

• Insertion Sort, Merge Sort (video) (Ordenação por Inserção, Ordenação por Mistura - vídeo)

• Insertion Sort (video) (Ordenação por Inserção - vídeo)

• Merge Sort (video) (Ordenação por Mistura - vídeo)

• Quicksort (vídeo)

• Selection Sort (video) (Ordenação por Seleção - vídeo)

• Código de ordenação por mistura:

  • Using output array (C) (Usando array de saída (C))
  • Using output array (Python) (Usando array de saída (Python))
  • In-place (C++)

• Código de algoritmo de ordenação quicksort:

  • Implementation (C) (Implementação em C)
  • Implementation (C) (Implementação em C)
  • Implementation (Python) (Implementação em Python)

• Implementar:

  • Mergesort: O(n log n) caso comum e pior caso
  • Quicksort O(n log n) caso comum
  • Ordenação por seleção e inserção são ambos O(n^2) caso comum e pior caso
  • Para heapsort, veja estrutura de dados heap acima.

• Não é requisitado, mas eu recomendo esses:

  • Sedgewick - Radix Sorts (6 vídeos)
    • 1. Strings em Java
    • 2. Key Indexed Counting (Contagem Indexada por Chaves)
    • 3. Least Significant Digit First String Radix Sort (Radix sort de string de Dígito-Menos-Significativo-Primeiro)
    • 4. Most Significant Digit First String Radix Sort (Radix sort de string de Dígito-Mais-Significativo-Primeiro)
    • 5. 3 Way Radix Quicksort (Quicksort Radix de 3 vias)
    • 6. Suffix Arrays (Arrays de Sufixos)
  • Radix Sort (Radix Sort)
  • Radix Sort (vídeo)
  • Radix Sort, Counting Sort (linear time given constraints) (video) (Radix Sort, Ordenação por Contagem (tempo linear dadas restrições))
  • Randomization: Matrix Multiply, Quicksort, Freivalds' algorithm (video) (Randomização: Multiplicação de Matriz, Quicksort, Algoritmo de Freivalds - vídeo)
  • Sorting in Linear Time (video) (Ordenando em Tempo Linear - vídeo)

Como um resumo, aqui está uma representação visual de 15 algoritmos de ordenação. Se você precisa de mais detalhes sobre o assunto, veja a seção "Ordenação" em Detalhes Adicionais Sobre Alguns Assuntos

Grafos

Grafos podem ser usados para representar muitos problemas na Ciência da Computação, então essa seção é longa, assim como árvores e ordenação também foram.

• Anotações:

  • Há 4 maneiras básicas de representar um grafo na memória:
    • objetos e apontadores
    • matriz de adjacência
    • lista de adjacência
    • mapa de adjacência
  • Famialirize-se com cada representação e seus prós e contras.
  • Busca em Largura (BFS) e Busca em Profundidade (DFS) - saiba a complexidade computacional deles, seus perde-e-ganhas (tradeoffs), e como implementar eles em código real.
  • Quando for perguntado uma questão, busque por uma solução baseada em grafos primeiro, depois se não houver nenhuma, siga em frente.

• Aulas do Skiena - ótima introdução:

  • CSE373 2012 - Lecture 11 - Graph Data Structures (video) (CSE373 2012 - Aula 11 - Estrutura de Dados de Grafos - vídeo)
  • CSE373 2012 - Lecture 12 - Breadth-First Search (video) (CSE373 2012 - Aula 12 - Busca em Largura - vídeo)
  • CSE373 2012 - Lecture 13 - Graph Algorithms (video) (CSE373 2012 - Aula 13 - Algoritmos de Grafos - vídeo)
  • CSE373 2012 - Lecture 14 - Graph Algorithms (con't) (video) (CSE373 2012 - Aula 11 - Algoritmos de Grafos (parte 1) - vídeo)
  • CSE373 2012 - Lecture 15 - Graph Algorithms (con't 2) (video) (CSE373 2012 - Aula 11 - Algoritmos de Grafos (parte 2) - vídeo)
  • CSE373 2012 - Lecture 16 - Graph Algorithms (con't 3) (video) (CSE373 2012 - Aula 11 - Algoritmos de Grafos (parte 3) - vídeo)

• Grafos (revisão e mais):

  • 6.006 Single-Source Shortest Paths Problem (video) (6.006 Problema do Menor Caminho de Fonte-Única - vídeo)
  • 6.006 Dijkstra (vídeo)
  • 6.006 Bellman-Ford (vídeo)
  • 6.006 Speeding Up Dijkstra (video) (6.006 acelerando Dijkstra - vídeo)
  • Aduni: Graph Algorithms I - Topological Sorting, Minimum Spanning Trees, Prim's Algorithm - Lecture 6 (video) (Aduni: Algoritmos de Grafos I - Ordenação Topológica, Árvores de Extensão Mínima, Algoritmo de Prim - Aula 6 - vídeo)
  • Aduni: Graph Algorithms II - DFS, BFS, Kruskal's Algorithm, Union-find Data Structure - Lecture 7 (video) (Aduni: Algoritmos de Grafos II - Busca em Profundidade (DFS), Busca em Largura (BFS), Algoritmo de Kruskal, Estrutura de Dados Union-Find - Aula 7 - vídeo)
  • Aduni: Graph Algorithms III: Shortest Path - Lecture 8 (video) (Aduni: Algoritmos de Grafos III: Menor Caminhno - Aula 8 - vídeo)
  • Aduni: Graph Alg. IV: Intro to geometric algorithms - Lecture 9 (video) (Algoritmos de Grafos IV: Introdução à algoritmos geométricos - Aual 9 - vídeo)
  • CS 61B 2014 (starting at 58:09) (video) (CS 61B 2014 (começando em 58:09) - vídeo)
  • CS 61B 2014: Weighted graphs (video) (CS 61B 2014: Grafos Ponderados - vídeo)
  • Greedy Algorithms: Minimum Spanning Tree (video) (Algoritmos Gulosos: Árvore de Extensão Mínima - vídeo)
  • Strongly Connected Components Kosaraju's Algorithm Graph Algorithm (video) (Componentes Fortemente Conectados, Algoritmo de Kosaraju, Algoritmo de Grafo - vídeo)

• Curso Completo do Coursera:

  • Algorithms on Graphs (video) (Algoritmos em Grafos - vídeo)

• Irei implementar:

  • Busca em Profundidade (DFS) com lista de adjacência (recursivo)
  • Busca em Profundidade (DFS) com lista de adjacência (iterativo com memória estática (stack))
  • Busca em Profundidade (DFS) com matriz de adjacência (recursivo)
  • Busca em Profundidade (DFS) com matriz de adjacência (iterativo com memória estática (stack))
  • Busca em Largura (BFS) com lista de adjacência
  • Busca em Largura (BFS) com matriz de adjacência
  • menor caminho de fonte-única (Dijkstra)
  • árvore de extensão mínima
  • Algoritmos baseados em busca em profundidade (DFS) (ver vídeos da Aduni acima):
    • checar por ciclos (necessário para ordenação topológica, já que nós iremos checar por ciclos antes de começar)
    • ordenação topológica
    • contar componentes conectados em um grafo
    • listar componentes fortemente conectados
    • checar por grafos bipartidos

Você ganhará mais prática com grafos no livro do Skiena (veja a seção de livros abaixo) e os livros da entrevista

Ainda Mais Conhecimento

• Recursão

  • Aulas de Stanford sobre recursão e backtracking:
    • Lecture 8 | Programming Abstractions (video) (Aula 8 | Abstrações de Programação - vídeo)
    • Lecture 9 | Programming Abstractions (video) (Aula 9 | Abstrações de Programação - vídeo)
    • Lecture 10 | Programming Abstractions (video) (Aula 10 | Abstrações de Programação - vídeo)
    • Lecture 11 | Programming Abstractions (video) (Aula 11 | Abstrações de Programação - vídeo)
  • quando é apropriado usá-la
  • como a recursão de cauda é melhor do que nada?
    • What Is Tail Recursion Why Is It So Bad? (O Que É Recursão de Cauda E Por Que Ela É Tão Ruim?)
    • Tail Recursion (video) (Recursão de Cauda - vídeo)

• Programação Dinâmica

  • Esse assunto pode ser bem difícil, já que cada problema solúvel de PD deve ser definido como uma relação de recursão, e isso pode ser complicado.
  • Eu sugiro olhar vários exemplos de problemas de PD até que você tenha um bom entendimento do padrão envolvido.
  • vídeos:
    • os vídeos do Skiena podem ser difíceis de acompanhar já que ele às vezes usa o quadro branco, o qual é pequeno para enxergar
    • Skiena: CSE373 2012 - Lecture 19 - Introduction to Dynamic Programming (video) (Skiena: CSE373 2012 - Aula 19 - Introdução à Programação Dinâmica - vídeo)
    • Skiena: CSE373 2012 - Lecture 20 - Edit Distance (video) (Skiena: CSE373 2012 - Aula 20 - Editar Distância - vídeo)
    • Skiena: CSE373 2012 - Lecture 21 - Dynamic Programming Examples (video) (Skiena: CSE373 2012 - Aula 21 - Exemplos de Programação Dinâmica - vídeo)
    • Skiena: CSE373 2012 - Lecture 22 - Applications of Dynamic Programming (video) (Skiena: CSE373 2012 - Aula 22 - Aplicações de Programação Dinâmica - vídeo)
    • Simonson: Dynamic Programming 0 (starts at 59:18) (video) (Simonson: Programação Dinâmica 0 (começa em 59:18) - vídeo)
    • Simonson: Dynamic Programming I - Lecture 11 (video) (Simonson: Programação Dinâmica I - Aula 11 - vídeo)
    • Simonson: Dynamic programming II - Lecture 12 (video) (Simonson: Programação Dinâmica II - Aula 12 - vídeo)
    • Lista de problemas individuais de PD (cada um é curto): Dynamic Programming (video) (Programação Dinâmica - vídeo)
  • Anotações de Aulas da Yale
    • Dynamic Programming (Programação Dinâmica)
  • Coursera:
    • The RNA secondary structure problem (video) (O problema da estrutura secundária de RNA - vídeo)
    • A dynamic programming algorithm (video) (Um algoritmo de programação dinâmica - vídeo)
    • Illustrating the DP algorithm (video) (Ilustrando o algorítmo de PD - vídeo)
    • Running time of the DP algorithm (video) (Tempo de execução do algoritmo de PD - vídeo)
    • DP vs. recursive implementation (video) (PD vs. implementação recursiva - vídeo)
    • Global pairwise sequence alignment (video) (Alinhamento de sequência em pares global - vídeo)
    • Local pairwise sequence alignment (video) (Alinhamento de sequência em pares local - vídeo)

• Programação Orientada a Objetos

  • Optional: UML 2.0 Series (video) (Opcional: Série UML 2.0 - vídeo)
  • Engenharia de Software Orientada a Objetos: Desenvolvedor de Software Usando UML e Java - 21 vídeo):
    • Pode pular isso se você tem uma boa compreensão de OO e práticas de design em OO.
    • OOSE: Software Dev Using UML and Java (Engenharia de Software Orientada a Objetos: Desenvolvedor de Software usando UML e Java)
  • Princípios de SOLID de POO:
    • Bob Martin SOLID Principles of Object Oriented and Agile Design (video) (Princípios de SOLID de Orientação a Objetos e Design Ágil por Bob Martin)
    • SOLID Design Patterns in C# (video) (Padrões de Design de SOLID em C# - vídeo)
    • SOLID Principles (video) (Princípios de SOLID - vídeo)
    • S - Single Responsibility Principle | Single responsibility to each Object (S - Princípio da Responsabilidade Única)
      • more flavor (mais informações)
    • O - Open/Closed Principal | On production level Objects are ready for extension for not for modification (O - Princípio Aberto/Fechado)
      • more flavor (mais informações)
    • L - Liskov Substitution Principal | Base Class and Derived class follow ‘IS A’ principal (L - Princípio de Substituição de Liskov)
      • more flavor (mais informações)
    • I - Interface segregation principle | clientes não devem ser forçados a implementar interfaces que eles não usam (Princípio da segregação de Interface)
      • Interface Segregation Principle in 5 minutes (video) (Princípio da Segregação de Interface em 5 minutos - vídeo)
      • more flavor (mais informações)
    • D -Dependency Inversion principle | Reduce the dependency In composition of objects. (D - Princípio da Inversão de Dependência)
      • Why Is The Dependency Inversion Principle And Why Is It Important (O Que É O Princípio da Inversão de Dependência E Por Que Ele É Importante)
      • more flavor (mais informações)

• Padrões de design

  • Quick UML review (video) (Revisão rápida de UML - vídeo)
  • Aprenda esses padrões:
    • estratégia
    • singleton (único)
    • adaptador
    • protótipo
    • decorador
    • visitante
    • fábrica, fábrica abstrata
    • fachada
    • observador
    • proxy
    • delegar
    • comandar
    • estado
    • memento
    • iterador
    • composto
    • flyweight (peso-mosca)
  • Chapter 6 (Part 1) - Patterns (video) (Capítulo 6 (Parte 1) - Padrões - vídeo)
  • Chapter 6 (Part 2) - Abstraction-Occurrence, General Hierarchy, Player-Role, Singleton, Observer, Delegation (video) (Capítulo 6 (Parte 2) - Abstração-Ocorrência, Hierarquia Geral, Função-Jogador, Singleton, Observador, Delegação - vídeo)
  • Chapter 6 (Part 3) - Adapter, Facade, Immutable, Read-Only Interface, Proxy (video) (Capítulo 6 (Parte 3) - Adaptador, Fachada, Imutável, Interface Somente Leitura, Proxy - vídeo )
  • Série de vídeos (27 vídeos)
  • Head First Design Patterns (Padrões de Design "Head First" ou "cabeça primeiro" numa tradução literal)
    • Eu sei que o livro canônico é "Design Patterns: Elements of Reusable Object-Oriented Software (Padrões de Design: Elementos de Software Orientado a Objetos reutilizável), mas "Head First" é ótimo para iniciantes em POO.
  • Handy reference: 101 Design Patterns & Tips for Developers (Referência Útil: 101 Dicas e Padrões de Design para Desenvolvedores)
  • Design patterns for humans (Padrões de design para humanos)

• Combinatórias (n escolhe k) e Probabilidade

  • Math Skills: How to find Factorial, Permutation and Combination (Choose) (video) (Habilidades Matemáticas: Como encontrar Fatorial, Permutação e Combinação (Escolha) - vídeo)
  • Make School: Probability (video) (Make School: Probabilidade - vídeo)
  • Make School: More Probability and Markov Chains (video) (Make School: Mais Probabilidade e Cadeias de Markov - vídeo)
  • Khan Academy:
    • Layout do curso
      • Basic Theoretical Probability (Probabilidade Teorética Básica)
    • Apenas os vídeos - 41 (cada um é simples e curto):
      • Probability Explained (video) (Probabilidade Explicada - vídeo)

• Algoritmos de Aproximação, NP-Completo e NP

  • Saiba sobre as classes mais famosas de problemas NP-completo, como o problema do vendedor viajante e o problema da mochila, e seja capaz de reconhecê-los quando um entrevistador lhe perguntar disfarçado.
  • Saiba o que NP-completo significa.
  • Computational Complexity (video) (Complexidade Computacional - vídeo)
  • Simonson:
    • Greedy Algs. II & Intro to NP Completeness (video) (Algoritmos Gulosos II e Introdução à Completude NP - vídeo)
    • NP Completeness II & Reductions (video) (Completude NP II e Reduções - vídeo)
    • NP Completeness III (video) (Completude NP III - vídeo)
    • NP Completeness IV (video) (Completude NP IV - vídeo)
  • Skiena:
    • CSE373 2012 - Lecture 23 - Introduction to NP-Completeness (video) (CSE373 2012 - Aula 23 - Introdução à Completude-NP - vídeo)
    • CSE373 2012 - Lecture 24 - NP-Completeness Proofs (video) (CSE373 2012 - Aula 24 - Provas de Completude-NP - vídeo)
    • CSE373 2012 - Lecture 25 - NP-Completeness Challenge (video) (CSE373 2012 - Aula 25 - Desafio de Completude-NP - vídeo)
  • Complexity: P, NP, NP-completeness, Reductions (video) (Complexidade: P, NP, Completude-NP, Reduções - vídeo)
  • Complexity: Approximation Algorithms (video) (Complexidade: Algoritmos de Aproximação - vídeo)
  • Complexity: Fixed-Parameter Algorithms (video) (Complexidade: Algorítmos de Parâmetro-Fixado - vídeo)
  • Peter Norvig debate soluções tão boas quanto possível para o problema do vendedor viajante:
    • Jupyter Notebook (Caderno de Júpiter)
  • Páginas 1048 - 1140 em CLRS (livro Introdução à Algoritmos) se você o tive.r

• Caches

  • Cache LRU:
    • The Magic of LRU Cache (100 Days of Google Dev) (video) (A Mágica do Cache LRU (100 dias de Google Dev) - vídeo)
    • Implementing LRU (video) (Implementando LRU - vídeo)
    • LeetCode - 146 Cache LRU (C++) (vídeo))
  • cache CPU:
    • MIT 6.004 L15: The Memory Hierarchy (video) (MIT 6.004 L15: A Hierarquia de Memória - vídeo)
    • MIT 6.004 L16: Cache Issues (video) (MIT 6.004 L16: Problemas de Cache - vídeo)

• Processos e Threads

  • Ciência da Computação 162 - Sistemas Operacionais (25 vídeos):
    • para processos e threads veja os vídeos 1-11
    • Operating Systems and System Programming (video) (Sistemas Operacionais e Programação de Sistema - vídeo)
  • What Is The Difference Between A Process And A Thread? (Qual É A Diferença Entre Um Processo E Uma Thread)
  • Cobre:
    • Processos, Threads, Problemas de Simultaneidade
      • diferença entre processos e threads
      • processos
      • threads
      • locks
      • mutexes
      • semáforos
      • monitores
      • como eles funcionam
      • deadlock
      • livelock
    • atividade, interrupções e troca de contexto de CPU
    • Construtos de simultaneidade modernos com processadores de múltiplos núcleos.
    • Paging, segmentation and virtual memory (video) (Paginação, segmentação e memória virtual - vídeo)
    • Interrupts (video) (Interruoções - vídeo)
    • Scheduling (video) (Agendamento - vídeo)
    • Necessidades de recurso de processos (memória: código, armazenamento estático, memória estática (stack), memória dinâmica (heap), e também descritores de arquivo, i/o
    • Necessidades de recurso de threads (o mesmo que acima (menos stack) com outras threads no mesmo processo, mas cada um tem seu próprio pc, contador de stack, registros, e stack)
    • Bifurcação nada mais é que COW (copy-on-write) (somente leitura) até que o novo processo escreva na memória, depois ela faz uma cópia completa.
    • Troca de contexto
      • Como a troca de contexto é iniciada pelo sistema operacional e componentes de hardware subjacentes
  • threads em C++ (série- 10 vídeos)
  • simultaneidade (ou concorrência) em Python (vídeos):
    • Short series on threads (Pequena série sobre threads)
    • Threads em Python
    • Understanding the Python GIL (2010) (Entendendo o GIL de Python)
      • referência
    • David Beazley - Python Concurrency From the Ground Up: LIVE! - PyCon 2015 (David Beazley - Simultaneidade (ou concorrência) Em Python Do Zero: AO VIVO!)
    • Keynote David Beazley - Topics of Interest (Python Asyncio) (Ideia Central de David Beazley - Tópicos de Interesse - Python Asyncio)
    • Mutex em Python

• Artigos

  • Ler tudo de ponta a ponta com total compreensão irá provavelmente levar mais tempo do que você tem. Eu recomendo ser seletivo com os artigos e suas seções.
  • Adora artigos clássicos?
  • 1978: Communicating Sequential Processes (1978: Comunicando Processos Sequenciais)
    • implementado em Go
  • 2003: The Google File System (2003: O Sistema de Arquivos da Google)
    • substituído por Colossus em 2012
  • 2004: MapReduce: Simplified Data Processing on Large Clusters (2004: MapReduce: Processamento de Dados Simplificado em Grandes Aglomerados)
    • substituído, na sua maior parte, por Cloud Dataflow?
  • 2006: Bigtable: A Distributed Storage System for Structured Data (2006: Bigtable: Um Sistema de Armazenamento Distribuído para Data Estruturada)
    • An Inside Look at Google BigQuery (Uma Olhada Por Dentro no BigQuery da Google)
  • 2006: The Chubby Lock Service for Loosely-Coupled Distributed Systems (2006: O Serviço de Lock Gordo para Sistemas Distribuídos Frouxamente Acoplados)
  • 2007: Dynamo: Amazon’s Highly Available Key-value Store (2007: Dynamo: Loja Chave-valor Altamente Disponível da Amazon)
    • O artigo da Dynamo iniciou a revolução NoSQL
  • 2007: What Every Programmer Should Know About Memory (very long, and the author encourages skipping of some sections) (2007: O Que Todo Programador Deve Saber Sobre Memória - bem longo, e o autor encoraja pular algumas seções)
  • 2010: Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010: Dapper, Uma Infraestrutura de Rastreamento de Sistemas Distribuídos de Grande Escala)
  • 2010: Dremel: Interactive Analysis of Web-Scale Datasets (2010: Dremel: Análise Interativa de Conjunto de Dados da Web)
  • 2012: Colossus da Google
    • artigo não disponível
  • 2012: AddressSanitizer: Um Veloz Verificador de Sanidade de Endereço:
    • artigo
    • vídeo
  • 2013: Spanner: Banco de Dados Globalmente Distribuído da Google
    • artigo
    • vídeo
  • 2014: Machine Learning: The High-Interest Credit Card of Technical Debt (2014: Aprendizado de Máquina: O Cartão de Crédito de Alta Taxa de Juros de Débito Técnico)
  • 2015: Continuous Pipelines at Google (2015: Pipelines Contínuas na Google)
  • 2015: High-Availability at Massive Scale: Building Google’s Data Infrastructure for Ads (2015: Alta Disponibilidade em Escalas Massivas: Construindo a Infraestrutura de Dados da Google para Anúncios)
  • 2015: TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems (2015: TensorFlow: Aprendizado de Máquina de Grande Escala em Sistemas Distribuídos Heterogêneos)
  • 2015: How Developers Search for Code: A Case Study (2015: Como Desenvolvedores Buscam por Código: Um Estudo de Caso)
  • 2016: Borg, Omega, e Kubernetes

• Testes

  • Cobrir:
    • como teste de unidade funciona
    • o que são objetos mock
    • o que é teste de integração
    • o que é injeção de dependência
  • Agile Software Testing with James Bach (video) (Teste Ágil de Software com James Bach - vídeo)
  • Open Lecture by James Bach on Software Testing (video) (Aula Aberta por James Bach sobre Teste de Software - vídeo)
  • Steve Freeman - Test-Driven Development (that’s not what we meant) (video) (Steve Freeman - Desenvolvimento Guiado Por Testes (isso não é o que a gente quis dizer) - vídeo)
    • slides
  • TDD is dead. Long live testing. (Desenvolvimento Guiado Por Testes (ou a sigla TDD em Inglês, que significa Test-Driven Development) está morto. Longa vida aos testes.
  • Is TDD dead? (video) (TDD está morto? - vídeo)
  • Série de Vídeos (152 vídeos) - nem todos são necessários (vídeo)
  • Test-Driven Web Development with Python (Desenvolvimento Web Guiado Por Testes com Python)
  • Injeção de dependência:
    • vídeo
    • Tao Of Testing (O Tao Dos Testes)
  • How to write tests (Como escrever testes)

• Agendamento

  • em um SO, como funciona
  • pode ser adquirido a partir de vídeos de Sistemas Operacionais

• Implementar rotinas de sistema

  • entenda o que tem por baixo das APIs de programação que você usa
  • você pode as implementar?

• Busca de string e manipulações

  • Sedgewick - Suffix Arrays (video) (Sedgewick - Arrays de Sufixo - vídeo)
  • Sedgewick - Substring Search (videos) (Sedgewick - Busca de Substring - vídeos)
    • 1. Introduction to Substring Search (1. Introdução à Busca de Substring)
    • 2. Brute-Force Substring Search (Busca de Substring por Força Bruta)
    • 3. Knuth-Morris Pratt
    • 4. Boyer-Moore
    • 5. Rabin-Karp
  • Search pattern in text (video) (Buscar padrão em um texto - vídeo)

  Se você precisa de mais detalhes sobre esse assunto, veja a seção "String Matching" em Detalhes Adicionais Sobre Alguns Assuntos

• Tries (ou Árvore de Prefixos)

  • Note que há tipos diferentes de tries. Alguns tem prefixos, alguns não, e alguns usam string ao invés de bits para rastrear o caminho.
  • Eu li todo o código, mas não irei implementar.
  • Sedgewick - Tries (3 vídeos)
    • 1. Tries R-Way
    • 2. Ternary Search Tries (Tries de Busca Ternária)
    • 3. Character Based Operations (Operações Baseadas Em Caracteres)
  • Notes on Data Structures and Programming Techniques (Anotações sobre Estruturas de Dados e Técnicas de Programação)
  • Vídeos de cursos curtos:
    • Introduction To Tries (video) (Introdução À Tries - vídeo)
    • Performance Of Tries (video) (Desempenho De Tries - vídeo)
    • Implementing A Trie (video) (Implementando Uma Trie - vídeo)
  • The Trie: A Neglected Data Structure (A Trie: Uma Estrutura de Dados Negligenciada)
  • TopCoder - Using Tries (TopCoder - Usando Tries)
  • Stanford Lecture (real world use case) (video) (Aula de Stanfort (caso de uso no mundo real) - vídeo)
  • MIT, Advanced Data Structures, Strings (pode ficar bem obscuro pela metade) (MIT, Estruturas De Dados Avançadas, Strings)

• Números de Ponto Flutuantes ("Floating Point Numbers")

  • simples 8-bit: Representation of Floating Point Numbers - 1 (video - tem um erro nos cálculos - veja a descrição do vídeo) (Representação de Número de Ponto Flutuantes - 1 - vídeo)
  • 32 bit: IEEE754 32-bit floating point binary (video) (IEEE754 Binário de Ponto Flutuante 32-bit - vídeo)

• Unicode

  • The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (O Mínimo Absoluto Que Cada Desenvolvedor de Software Deve Absolutamente, Certamente Saber Sobre Unicode e Conjuntos de Caracteres)
  • What Every Programmer Absolutely, Positively Needs To Know About Encodings And Character Sets To Work With Text (O Que Cada Programador Deve Absolutamente, Certamente Saber Sobre Codificações E Conjuntos de Caracteres Para Trabalhar Com Texto)

• Extremidade (ordenação) (ou "endianness" em Inglês)

  • Big And Little Endian (Grande E Pequeno Extremo)
  • Big Endian Vs Little Endian (video) (Grande Extremo Vs Pequeno Extremo - vídeo)
  • Big And Little Endian Inside/Out (video) (Explicando Grande e Pequeno Extremos - vídeo)
    • Palestra bem técnica para desenvolvedores de kernel. Não se preocupe se grande parte disso for demais para sua cabeça.
    • A primeira metade é suficiente.

• Redes

  • se você tem experiência com redes ou quer se tornar um engenheiro de sistemas, se prepare para questões desse gênero
  • caso contrário, isso é no mínimo bom de saber
  • Khan Academy
  • UDP and TCP: Comparison of Transport Protocols (UDP e TCP: Comparação de Protocolos de Transporte)
  • TCP/IP and the OSI Model Explained! (TCP/IP e o Modelo OSI Explicado)
  • Packet Transmission across the Internet. Networking & TCP/IP tutorial. (Transmissão de Pacote pela Internet. Tutorial de Redes e TCP/IP.)
  • HTTP
  • SSL e HTTPS
  • SSL/TLS
  • HTTP 2.0
  • Série de Vídeos (21 vídeos)
  • Subnetting Demystified - Part 5 CIDR Notation (Desmistificando Subnetting (ou subdivisão de redes, ou ainda sub-endereçamento IP))
  • Sockets:
    • Java - Sockets - Introduction (video) (Java - Sockets - Introdução - vídeo)
    • Socket Programming (video) (Programação de Socket - vídeo)

Design de Sistema, Escalabilidade, Tratamento de Dados

• Você pode presumir que façam perguntas à respeito de design de sistema se você tem mais de 4 anos de experiência.
• Escalabilidade e Design de Sistema são temas bem grandes com muitos tópicos e recursos, já que há muito a se considerar quando se projeta um sistema de software/hardware que pode escalar. Se prepare para gastar um bom tempo nisso.
• Considerações:
  • escalabilidade
    • Refinar grandes conjuntos de dados para valores únicos
    • Transformar um conjunto de dados em outro
    • Tratar quantidades incrivelmente grande de dados
  • design de sistema
    • conjuntos de características
    • interfaces
    • hierarquias de classes
    • projetar um sistema sob certas restrições
    • simplicidade e robustez
    • perde-e-ganhas (tradeoffs)
    • otimização e análise de desempenho
• COMEÇE AQUI: [The System Design Primer]https://github.com/donnemartin/system-design-primer) (A Base de Design de Sistema)
• System Design from HiredInTech (Design de Sistema, por HiredInTech)
• How Do I Prepare To Answer Design Questions In A Technical Inverview? (Como Eu Me Preparo Para Responder Questõs De Design De Sistemas Em Uma Entrevista Técnica)
• 8 Things You Need to Know Before a System Design Interview (8 Coisas Que Você Precisa Saber Antes De Uma Entrevista De Design De Sistema)
• Algorithm design (Design de algoritmo)
• Database Normalization - 1NF, 2NF, 3NF and 4NF (video) (Normalização de Banco de Dados - 1NF, 2NF, 3NF e 4NF - vídeo)
• System Design Interview (Entrevista de Design de Sistema) - Tem vários recursos nesse aqui. Olhe os artigos e exemplos. Eu coloquei alguns deles abaixo.
• How to ace a systems design interview (Como tirar de letra um entrevista de design de sistemas)
• Numbers Everyone Should Know (Números Que Todos Devem Conhecer)
• How long does it take to make a context switch? (Quanto tempo leva para fazer uma troca de contexto?)
• Transactions Across Datacenters (video) (Transações Através de Datacenters - vídeo)
• A plain English introduction to CAP Theorem (Uma introdução à Teorema CAP em Inglês simples)
• Algoritmo de Consenso de Paxos:
  • vídeo curto
  • vídeo mais extenso com exemplos de uso e multi-paxos
  • artigo
• Consistent Hashing (Hashing Consistente)
• Padrões de NoSQL
• Escalabilidade:
  • Ótima visão geral (vídeo)
  • Série curta:
    • Clones
    • Banco de Dados
    • Cache
    • Assincronismo
  • Scalable Web Architecture and Distributed Systems (Sistemas Distribuídos e Arquitetura Web Escaláveis)
  • Fallacies of Distributed Computing Explained (Falácias de Computação Distribuída Explicadas)
  • Pragmatic Programming Techniques (Técnicas Pragmáticas de Programação)
    • extra: Google Pregel Graph Processing (extra: Processador de Grafos Pregel da Google)
  • Jeff Dean - Building Software Systems At Google and Lessons Learned (video) (Jeff Dean - Construindo Sistemas de Software Na Google e Lições Aprendidas - vídeo)
  • Introduction to Architecting Systems for Scale (Introdução à Arquitetando SIstemas para Escalar)
  • Scaling mobile games to a global audience using App Engine and Cloud Datastore (video) (Escalando jogos mobile para uma audiência global usando App Engine e Armazenamento de Dados na Nuvem - vídeo)
  • How Google Does Planet-Scale Engineering for Planet-Scale Infra (video) (Como a Google faz Engenharia de Escala-Global para Infraestrutura de Escala Global - vídeo)
  • The Importance of Algorithms (A Importância de Algoritmos)
  • Sharding
  • Scale at Facebook (2009) (Escalabilidade no Facebook - 2009)
  • Scale at Facebook (2012), "Building for a Billion Users" (video) (Escalabilidade no Facebook - 2012, "Construindo para Bilhões de Usuários" - vídeo)
  • Engineering for the Long Game - Astrid Atkinson Keynote(video) (Engenharia à longo prazo - Ideia Central de Astrid Atkinson - vídeo)
  • 7 Years Of YouTube Scalability Lessons In 30 Minutes (7 Anos de Lições de Escalabilidade do YouTube em 30 minutos)
    • vídeo
  • How PayPal Scaled To Billions Of Transactions Daily Using Just 8VMs (Como PayPal Escalou Para BIlhões De Transações Diárias Usando Apenas 8 Máquinas Virtuais)
  • How to Remove Duplicates in Large Datasets (Como Remover Duplicatas em Grandes Conjuntos de Dados)
  • A look inside Etsy's scale and engineering culture with Jon Cowie (video) (Uma olhada por dentro da cultura de engenharia e escala da Etsy com Jon Cowie - vídeo)
  • What Led Amazon to its Own Microservices Architecture (O Que Levou a Amazon à ter a Própria Arquitetura de Microserviços)
  • To Compress Or Not To Compress, That Was Uber's Question (Comprimir Ou Não Comprimir, Essa Era A Questão Para A Uber)
  • Asyncio Tarantool Queue, Get In The Queue (Fila Asyncio Tarantool, Entre Na Fila)
  • When Should Approximate Query Processing Be Used? (Quando Processamento de Consultas Aproximado Deve Ser Usado?)
  • Google's Transition From Single Datacenter, To Failover, To A Native Multihomed Architecture (Transição da Google de um Único Datacenter, Para Um Failover (tolerância à falhas), Para Uma Arquitetura Nativa Multihomed (ou Multiconectada))
  • Spanner
  • Egnyte Architecture: Lessons Learned In Building And Scaling A Multi Petabyte Distributed System (Arquitetura Egnyte: Lições Aprendidas Ao Construir E Escalar Uma Sistema Distribuído de Múltiplos Petabytes)
  • Machine Learning Driven Programming: A New Programming For A New World (Programação Orientada por Aprendizado de Máquina: Uma Nova Programação Para Um Novo Mundo)
  • The Image Optimization Technology That Serves Millions Of Requests Per Day (A Tecnologia De Otimização De Imagem Que Atende Milhões de Solicitações Por Dia)
  • A Patreon Architecture Short (Arquitetura Patreon Resumida)
  • Tinder: How Does One Of The Largest Recommendation Engines Decide Who You'll See Next? (Tinder: Como Um Dos Maiores Motores de Recomendação Decide A Próxima Pessoa Que Você Vai Ver?)
  • Design Of A Modern Cache (Design De Um Cache Moderno)
  • Live Video Streaming At Facebook Scale (Stream Ao Vivo Ao Nível De Escala Do Facebook)
  • A Beginner's Guide To Scaling To 11 Million+ Users On Amazon's AWS (Uma Guia de Iniciante Para Escalar Para Mais De 11 Milhões De Usuários No AWS Da Amazon)
  • How Does The Use Of Docker Effect Latency? (Como O Uso de Docker Afeta Latência?)
  • Does AMP Counter An Existential Threat To Google? (A AMP Contesta Uma Ameaça Existencial à Google?)
  • A 360 Degree View Of The Entire Netflix Stack (Uma Visão Em 360 Graus De Todo O Stack Da Netflix)
  • Latency Is Everywhere And It Costs You Sales - How To Crush It (Latência Está Em Todo Lugar E Ela Te Custa Vendas - Como Acabar Com Ela)
  • Serverless (bem longo, precisa apenas da essência) (Sem Servidor)
  • What Powers Instagram: Hundreds of Instances, Dozens of Technologies (O Que Alimenta O Instagram: Centenas de Instâncias, Dezenas de Tecnologias)
  • Cinchcast Architecture - Producing 1,500 Hours Of Audio Every Day (Arquitetura Cinchcast - Produzindo 1.500 Horas De Áudio Todo Dia)
  • Justin.Tv's Live Video Broadcasting Architecture (Arquitetura de Transmissão de Vídeo Ao Vivo da Justin.TV)
  • Playfish's Social Gaming Architecture - 50 Million Monthly Users And Growing (Arquitetura de Gaming Social da Playfish - 50 Milhões De Usuários Mensais E Crescendo)
  • TripAdvisor Architecture - 40M Visitors, 200M Dynamic Page Views, 30TB Data (Arquitetura do TripAdvisor - 40M visitantes, 200M Visualizações de Páginas Dinâmicas, 30TB de Dados)
  • PlentyOfFish Architecture (Arquitetura do PlentyOfFish)
  • Salesforce Architecture - How They Handle 1.3 Billion Transactions A Day (Arquitetura do Salesforce - Como Eles Lidam Com 1,3 Bilhões de Transações Por Dia)
  • ESPN's Architecture At Scale - Operating At 100,000 Duh Nuh Nuhs Per Second (Arquitetura da ESPN em Escala - Operando a 100.000 Duh Nuh Nuhs Por Segundo)
  • Veja a seção "Envio de Mensagens, Serialização, e Sistemas de Enfileiramento" bem abaixo para informações sobre algumas das tecnologias que podem "colar" serviços juntos
  • Twitter:
    • O'Reilly MySQL CE 2011: Jeremy Cole, "Big and Small Data at @Twitter" (video) (O'Reilly MySQL CE 2011: Jeremy Cole, "Dados Grandes e Pequenos no @Twitter" - vídeo)
    • Timelines at Scale (Linhas de Tempo em Escala)
  • Para ainda mais informações, veja a série de vídeos "Minerando Conjuntos de Dados Massivos" na seção de Séries de Vídeos.
• Praticando o processo de design de sistema: Aqui estão algumas ideias para tentar trabalhar no papel, cada uma com documentação sobre como ela foi tratada no mundo real:
  • revisão: The System Design Primer (A Base de Design de Sistema)
  • System Design from HiredInTech (Design de Sistema, por HiredInTech)
  • cheat sheet (folha de consultas)
  • fluxo:
    1. Compreenda o problema e seu escopo:
       • defina os casos de uso, com a ajuda do entrevistador
       • sugira funcionalidades adicionais
       • remova itens que o entrevistador considera fora de escopo
       • assuma que alta disponibilidade é requisitada, adicione como um caso de uso
    2. Pense sobre as restrições:
       • pergunte quantas solicitações por mês
       • pergunte quantas solicitações por segundo (eles podem se voluntariar para essa ou estimular você a fazer os cálculos)
       • estime a percentagem de leituras vs. escritas
       • tenha a regra 80/20 em mente quando estiver estimando
       • quantos dados escritos por segundo
       • armazenamento total necessário para 5 anos
       • quantos dados lidos por segundo
    3. Design abstrato:
       • camadas (serviço, dados, caching)
       • infraestrutura: balanço de carga, envio de mensagens
       • breve descrição de qualquer algoritmo chave que movimenta o serviço
       • considere possíveis gargalos (bottleneck) e determine soluções
  • Exercícios:
    • Design a CDN network: old article (Projete uma rede CDN: artigo antigo)
    • Design a random unique ID generation system (Projete um sistema de geração IDs únicos aleatórios)
    • Design an online multiplayer card game (Projete um jogo de cartas de multijogadores online)
    • Design a key-value database (Projete um banco de dados de chave-valor)
    • Design a picture sharing system (Projete um sistema de compartilhamento de fotos)
    • Design a recommendation system (Projete um sistema de recomendação)
    • Design a URL-shortener system: copied from above (Projete um sistema de encurtador de URL: copiado de cima)
    • Design a cache system (Projete um sistema de cache)

---

Revisão Final

Essa seção terá vídeos mais curtos que você pode assistir rapidamente para revisar a maioria dos conceitos importantes.
É legal se você quiser dar uma refrescada na memória.

• Séries de vídeos curtos (2 - 3 minutos) sobre o assunto (23 vídeos)
  • Vídeos
• Séries de vídeos curtos (2 - 5 minutos) sobre o assunto - Michael Sambol (18 vídeos):
  • Vídeos
• Sedgewick Videos - Algorithms I (Vídeos de Sedgewick - Algoritmos I)
  • 01. Union-Find
  • 02. Analysis of Algorithms (Análises de Algoritmos)
  • 03. Stacks and Queues (Memórias Estáticas e Filas)
  • 04. Elementary Sorts (Ordenações Elementares)
  • 05. Mergesort
  • 06. Quicksort
  • 07. Priority Queues (Filas Prioritárias)
  • 08. Elementary Symbol Tables (Tabelas de Símbolos Elementares)
  • 09. Balanced Search Trees (Árvores de Busca Balanceadas)
  • 10. Geometric Applications of BST (Aplicações Geométricas de Árvores de Busca Balanceada)
  • 11. Hash Tables (Tabelas Hash)
• Sedgewick Videos - Algorithms II (Vídeos de Sedgewick - Algoritmos II)
  • 01. Undirected Graphs (Grafos Não Direcionados)
  • 02. Directed Graphs (Grafos Direcionados)
  • 03. Minimum Spanning Trees (Árvores de Extensão Mínima)
  • 04. Shortest Paths (Menores Caminhos)
  • 05. Maximum Flow (Fluxo Máximo)
  • 06. Radix Sorts (Ordenações Radix)
  • 07. Tries (Árvore de Prefixos)
  • 08. Substring Search (Busca de Substring)
  • 09. Regular Expressions (Expressões Regulares)
  • 10. Data Compression (Compressão de Dados)
  • 11. Reductions (Reduções)
  • 12. Linear Programming (Programação Linear)
  • 13. Intractability (Intratabilidade)

---

Prática com Questões de Programação

Agora que você sabe todos os temas de Ciência da Computação acima, é hora de praticar respondendo problemas de programação.

Prática com Questõs de Programação não é sobre memorizar respostas para problemas de programação.

Por que você precisa praticar com problemas de programação:

• reconhecimento de problemas, e onde as devidas estruturas de dados e algoritmos se encaixam
• coleta de requerimentos para o problema
• pensar alto (falar enquanto resolve o problema) assim como você irá fazer em uma entrevista
• escrever código em um quadro branco ou papel, não no computador
• encontrar complexidade de espaço e tempo para suas soluções
• testar suas soluções

Tem uma introdução ótima para resolução de problema metódica e comunicativa em uma entrevista. Você vai adquirir isso dos livros de entrevista de programação, também, mas eu acho isso aqui excelente: Algorithm design canvas (Quadro de design de algoritmo)

Não tem quadro branco em casa? Faz sentido. Eu sou um estranho e tenho um grande quadro branco. Ao invés de um quadro branco, pegue um grande caderno de desenho de uma loja de arte. Você pode sentar no sofá e praticar. Esse é o meu "sofá de quadro branco". Eu adicionei a caneta na foto para comparação de dimensões. Se você usar uma caneta, você vai desejar que você pudesse apagar. Fica uma bagunça bem rápido.

Suplementar:

• Mathematics for Topcoders (Matemática para Topcoders)
• Dynamic Programming – From Novice to Advanced (Programação Dinâmica - De Novato a Avançado)
• MIT Interview Materials (Materiais de Entrevista do MIT)
• Exercises for getting better at a given language (Exercícios para ficar melhor em uma determinada linguagem)

Leia e Faça os Problemas de Programação (nessa ordem):

• Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition (Entrevistas de Programação Expostas: Segredos para Conseguir Seu Próximo Emprego, 2ª Edição)
  • respostas em C, C++ e Java
• Cracking the Coding Interview, 6th Edition (Decifrando a Entrevista de Programação, 6ª Edição)
  • respostas em Java

Veja a Lista de Livros acima

Exercícios/desafios de programação

Depois que você enche o cérebro com novos aprendizados, é hora de botar ele para trabalhar. Faça desafios de programação todo dia, o máximo que você puder.

• How to Find a Solution (Como Encontrar Uma Solução)
• How to Dissect a Topcoder Problem Statement (Como Dissecar Uma Declaração em um Problema do TopCoder)

Vídeos de Questões de Entrevista de Programação:

• IDeserve (88 vídeos)
• Tushar Roy (5 playlists)

Websites de desafios:

• LeetCode
• TopCoder
• Project Euler (focado em matemática)
• Codewars
• HackerEarth
• HackerRank
• Codility
• InterviewCake
• Geeks for Geeks
• InterviewBit
• Sphere Online Judge (spoj)

Repositórios de desafios:

• Interactive Coding Interview Challenges in Python (Desafios Interativos de Entrevista de Programação em Python)

Entrevistas Simuladas:

• Gainlo.co: Entrevistas simuladas com entrevistadores de grandes empresas
• Pramp: Entrevistas simuladas com colegas
• Refdash: Entrevistas simuladas

Quando a entrevista estiver se aproximando

• Decifrando A Entrevista De Programação Série 2 (vídeos):
  • Cracking The Code Interview (Decifrando A Entrevista De Programação)
  • Cracking the Coding Interview - Fullstack Speaker Series (Decifrando A Entrevista De Programação - Série Palestrantes Fullstack)

Seu Currículo

• Veja itens sobre preparo de currículo em "Cracking The Coding Interview" (Decifrando A Entrevista De Programação) e atrás do livro "Programming Interviews Exposed" (Entrevistas de Programação Expostas)

Esteja pensando à respeito para quando a entrevista chegar

Pense em 20 questões da entrevista que você vai ter, seguindo a linha de raciocínio dos itens abaixo. Tenha 2-3 respostas para cada. Tenha uma história, não apenas dados, sobre algo que você realizou.

• Por que você quer esse trabalho?
• Qual um problema difícil que você tenha resolvido?
• Maiores desafios enfrentados?
• Melhores/piores designs que você já viu?
• Ideias para melhorar um produto existente.
• Como você trabalha melhor, como um indivíduo e como parte de uma equipe?
• Quais das suas habilidades ou experiências seriam recursos úteis na função e por quê?
• O que você mais gostou no [trabalho x / projeto y]?
• Qual foi o maior desafio que você enfrentou no [trabalho x / projeto y]?
• Qual foi o bug mais difícil que você enfrentou no [trabalho x / projeto y]?
• O que você aprendeu no [trabalho x / projeto y]?
• O que você teria feito melhor no [trabalho x / projeto y]?

Tenha questões para o entrevistador

Algumas das minhas (eu posso já saber a resposta, mas o quero a opinião deles ou a perspectiva da equipe):

• Quão grande é sua equipe?
• Como é o seu ciclo de desenvolvimento? Você trabalha com modelo em cascata (waterfall)/sprints/método ágil (agile)?
• Correrias por causa de prazos são comuns? Ou tem flexibilidade?
• Como as decisões são tomadas na sua equipe?
• Quantas reuniões você tem por semana?
• Você sente que o seu ambiente de trabalho te ajuda a se concentrar?
• No que você está trabalhando?
• O que você gosta a respeito desse trabalho?
• Como é o balanço vida-trabalho?

Quando Você Conseguir O Trabalho

Parabéns!

Continue aprendendo.

O aprendizado nunca para.

---

*****************************************************************************************************
*****************************************************************************************************

Tudo abaixo deste ponto é opcional.
Ao estudar o que vem a seguir, você vai ter maior exposição a mais conceitos de Ciência da Computação, e está mais bem preparado para 
qualquer trabalho de engenharia de software. Você será um engenheiro de software muito mais completo.

*****************************************************************************************************
*****************************************************************************************************

---

Livros Adicionais

• The Unix Programming Environment (O Ambiente De Programação Unix)
  • velho, mas ótimo
• The Linux Command Line: A Complete Introduction (A Linha De Comando do Linux: Uma Introdução Completa)
  • uma opção moderna
• TCP/IP Illustrated Series (Série TCP/IP Ilustrado)
• Head First Design Patterns (Padrões de Design "Head First")
  • uma introdução gentil a padrões de design
• Design Patterns: Elements of Reusable Object-Oriente​d Software (Padrões de Design: Elementos de Software Orientado a Objetos Reutilizável)
  • também conhecido como o livro "Gang Of Four" (ou GOF, em Português Gangue Dos Quatro)
  • o livro de padrões de design canônico
• UNIX and Linux System Administration Handbook, 4th Edition (Manual de Administração de Sistema do UNIX e Linux, 4ª Edição)

Aprendizagem Adicional

Esses tópicos provavelmente não aparecerão em uma entrevista, mas eu adicionei eles para ajudar você a se tornar um engenheiro de software mais completo, e para você ficar ciente de certas tecnologias e algoritmos, assim você terá mais ferramentas a disposição.

• Compiladores

  • How a Compiler Works in ~1 minute (video) (Como um Compilador Funciona em ~1 minuto - vídeo)
  • Harvard CS50 - Compilers (video) (Harvard CS50 - Compiladores - vídeo)
  • C++ (vídeo)
  • Understanding Compiler Optimization (C++) (video) (Entendendo Otimização de Compilador (C++) - vídeo)

• Emacs e vi(m)

  • Se familiarize com um editor de código baseado em unix
  • vi(m):
    • Editing With vim 01 - Installation, Setup, and The Modes (video) (Editando Com vim 01 - Instalação, Setup, e Os Modos - vídeo)
    • VIM Adventures (Aventuras em VIM)
    • conjunto de 4 vídeos:
      • The vi/vim editor - Lesson 1 (O editor vi/vim - Lição 1)
      • The vi/vim editor - Lesson 2 (O editor vi/vim - Lição 2)
      • The vi/vim editor - Lesson 3 (O editor vi/vim - Lição 3)
      • The vi/vim editor - Lesson 4 (O editor vi/vim - Lição 4)
    • Using Vi Instead of Emacs (Usando Vi Ao Invés de Emacs)
  • emacs:
    • Basics Emacs Tutorial (video) (Tutorial Básico de Emas - vídeo)
    • conjunto de 3 (vídeos):
      • Emacs Tutorial (Beginners) -Part 1- File commands, cut/copy/paste, cursor commands (Tutorial de Emacs (Iniciantes) - Parte 1 - Comandos de Arquivo, cortar/copiar/colar, comandos de cursor)
      • Emacs Tutorial (Beginners) -Part 2- Buffer management, search, M-x grep and rgrep modes (Tutorial de Emacs (Iniciantes) - Parte 2 - Gerenciamento de buffer, pesquisa, modos M-x grep e rgrep)
      • Emacs Tutorial (Beginners) -Part 3- Expressions, Statements, ~/.emacs file and packages (Tutorial de Emacs (Iniciantes) - Parte 3 - Expressões, Declarações, arquivo ~/. emacs e pacotes)
    • Evil Mode: Or, How I Learned to Stop Worrying and Love Emacs (video) (Modo Evil: Ou, Como Eu Aprendi A Parar De Me Preocupar E Amar O Emacs - vídeo)
    • Writing C Programs With Emacs (Escrevendo Programas Em C Com Emacs)
    • (maybe) Org Mode In Depth: Managing Structure (video) ((talvez) Análise Profunda do Modo Org: Gerenciando Estrutura - vídeo)

• Ferramentas de linha de comando do Unix

  • Eu preenchi a lista abaixo com boas ferramentas.
  • bash
  • cat
  • grep
  • sed
  • awk
  • curl or wget
  • sort
  • tr
  • uniq
  • strace
  • tcpdump

• Teoria da informação (vídeos)

  • Khan Academy
  • mais sobre os processos de Markov:
    • Core Markov Text Generation (Fundamentos da Geração de Texto Markov)
    • Core Implementing Markov Text Generation (Fundamentos da Implementação de Geração de Texto Markov)
    • Project = Markov Text Generation Walk Through (Projeto = Passo a Passo de Geração de Texto Markov)
  • Veja mais em MIT 6.050J Série: Informação e Entropia abaixo.

• Paridade e Código de Hamming (vídeos)

  • Introdução
  • Paridade
  • Código de Hamming:
    • Detecção de Erro
    • Correção de Erro
  • Verificação de Erro

• Entropia

  • veja também os vídeos abaixo
  • certifique-se de assistir os vídeos de teoria da informação primeiro
  • Information Theory, Claude Shannon, Entropy, Redundancy, Data Compression & Bits (video) (Teoria da Informação, Claude Shannon, Entropia, Redundância, Compressão de Dados e Bits - vídeo)

• Criptografia

  • veja também os vídeos abaixo
  • certifique-se de assistir os vídeos de teoria da informação primeiro
  • Khan Academy Series (Série da Khan Academy)
  • Cryptography: Hash Functions (Criptografia: Funções Hash)
  • Cryptography: Encryption (Criptografia: Encriptação)

• Compressão

  • certifique-se de assistir os vídeos de teoria da informação primeiro
  • Computerphile (vídeos):
    • Compression (Compressão)
    • Entropy in Compression (Entropia em Compressão)
    • Upside Down Trees (Huffman Trees) (Árvores de Cabeça para Baixo - Árvores Huffman)
    • EXTRA BITS/TRITS - Huffman Trees (BITS/TRITS - Árvores Huffman)
    • Elegant Compression in Text (The LZ 77 Method) (Compressão Elegante em Texto - O Método LZ 77)
    • Text Compression Meets Probabilities (Compressão de Texto e Probabilidades)
  • Compressor Head videos (Vídeos da Série Compressor Head)
  • (opcional) Google Developers Live: GZIP is not enough! (Google Developers Ao Vivo: GZIP não é suficiente)

• Segurança de Computador

  • MIT (23 vídeos)
    • Introduction, Threat Models (Introdução, Modelos de Risco)
    • Control Hijacking Attacks (Ataques que Conseguem Tomar Controle
    • Buffer Overflow Exploits and Defenses (Defesas e Exploits de Buffer Overflow)
    • Privilege Separation (Separação de Privilégio)
    • Capabilities (Capacidades)
    • Sandboxing Native Code (Isolando Código Nativo)
    • Web Security Model (Modelo de Segurança Web)
    • Securing Web Applications (Protegendo Aplicações Web)
    • Symbolic Execution (Execução Simbólica)
    • Network Security (Segurança de Rede)
    • Network Protocols (Protocolos de Rede)
    • Side-Channel Attacks (Ataques Side-Channel)

• Coleta de lixo

  • Compilers (video) (Compiladores - vídeo)
  • GC in Python (video) (Coleta de lixo em Python - vídeo)
  • Deep Dive Java: Garbage Collection is Good! (Mergulhando Fundo em Java: Coleta de Lixo é Bom)
  • Deep Dive Python: Garbage Collection in CPython (video) (Mergulhando Fundo em Python: Coleta de Lixo em CPython - vídeo)

• Programação Paralela

  • Coursera (Scala)
  • Efficient Python for High Performance Parallel Computing (video) (Python Eficiente para Computação Paralela de Alto Desempenho - vídeo)

• Envio de Mensagens, Serialização, e Sistemas de Enfileiramento

  • Thrift
    • Tutorial
  • Protocol Buffers (Buffers de Protocolo)
    • Tutoriais
  • gRPC
    • gRPC 101 for Java Developers (video)
  • Redis
    • Tutorial
  • Amazon SQS (fila)
  • Amazon SNS (pub-sub)
  • RabbitMQ
    • Get Started (Introdução)
  • Celery
    • First Steps With Celery (Primeiros Passos Com Celery)
  • ZeroMQ
    • Intro - Read The Manual (Introdução - Leia O Manual)
  • ActiveMQ
  • Kafka
  • MessagePack
  • Avro

• A*

  • A Search Algorithm (Um Algoritmo de Busca)
  • A* Pathfinding Tutorial (video) (Tutorial de Busca de Caminho com A* - vídeo)
  • A* Pathfinding (E01: algorithm explanation) (video) (Busca de Caminho com A* (E01 - explicação do algoritmo) - vídeo)

• Transformada de Fourier Rápida

  • An Interactive Guide To The Fourier Transform (Uma Guia Interativa Para A Transformada de Fourier)
  • What is a Fourier transform? What is it used for? (O que é a Transformada de Fourier? Para o quê ela é usada?)
  • What is the Fourier Transform? (video) (O que é a Transformada de Fourier? - vídeo)
  • Divide & Conquer: FFT (video) (Dividir e Conquistar: FFT (Transformada de Fourier Rápida) - vídeo)
  • Understanding The FFT (Entendendo a Transformada de Fourier Rápida)

• Filtro de Bloom

  • Dado um filtro de Bloom com m bits e k funções de hash, tanto inserção quanto teste de associação são O(k)
  • Bloom Filters (Filtros de Bloom)
  • Bloom Filters | Mining of Massive Datasets | Stanford University (Filtros de Bloom | Mineração de Conjuntos de Dados Massivos | Universidade de Stanford)
  • Tutorial
  • How To Write A Bloom Filter App (Como Escrever Um Aplicativo De Filtro De Bloom)

• HyperLogLog

  • How To Count A Billion Distinct Objects Using Only 1.5KB Of Memory (Como Contar Um Bilhão De Objetos Distintos Usando Apenas 1,5KB De Memória)

• Locality-Sensitive Hashing

  • usado para determinar a similaridade de documentos
  • o oposto de MD5 ou SHA, os quais são usados para determinar se 2 documentos/strings são exatamente o mesmo.
  • Simhashing (hopefully) made simple (Simhashing (supostamente) simplificado)

• Árvores de van Emde Boas

  • Divide & Conquer: van Emde Boas Trees (video) (Dividir e Conquistar: Árvores van Emde Boas - vídeo)
  • MIT Lecture Notes (Anotações de Aula do MIT)

• Estruturas de Dados Incrementadas

  • CS 61B Lecture 39: Augmenting Data Structures (CS 61B Aula 39: Incrementando Estruturas de Dados)

• Árvores de busca balanceadas

  • Saiba pelo menos um tipo de árvore binária balanceada (e saiba como ela é implementada):

  • "Entre as Árvores de Busca Balanceadas, AVL e árvore 2/3 agora são passado, e árvores red-black (rubro-negras) parecem mais populares. Uma estrutura de dados auto-organizada particularmente interessante é a árvore splay, a qual usa rotações para mover qualquer chave acessada para a raiz."

  • Dessas, eu escolhi implementar a árvore splay. Com base no que eu li, você não vai implementar uma árvore de busca balanceada na sua entrevista. Mas eu queria uma certa exposição à programação de uma dessas árvoes e convenhamos, árvores splay são muito legais. Eu li muito código de árvores rubro-negras.

    • árvore splay: funções de inserir, buscar e deletar Se você acabar implementando uma árvore rubro-negra, tente apenas essas:
    • funções de busca e inserção, pulando a função de deletar

  • Eu quero aprender mais sobre a Árvore B, já que ela é amplamente usada com enormes conjuntos de dados.

  • Self-balancing binary search tree (Árvore binária de busca auto-balanceada)

  • Árvores AVL

    • Ná prática: Pelo que eu vejo, essas não são muito usadas na prática, mas eu consigo ver onde elas seriam usadas: Á arvore AVL é outra estrutura que dá suporte a remoção, inserção e busca O(log n). Ela é mais rigidamente balanceada que as árvores rubro-negras, levando à inserções e remoções mais lentas, mas uma recuperação mais rápida. Isso faz dela um atrativo para estruturas de dados que podem ser construídas uma vez e carregadas sem reconstrução, assim como os dicionários de linguagem (ou dicionários de programas, como os opcodes de um montador (assembler) ou interpretador).
    • MIT AVL Trees / AVL Sort (video) (Árvores AVL / Ordenação AVL, pelo MIT - vídeo)
    • AVL Trees (video) (Árvores AVl - vídeo)
    • AVL Tree Implementation (video) (Implementação de Árvores AVL - vídeo)
    • Split And Merge (Dividir e Fundir)

  • Árvores Splay

    • Ná prática: Árvores splay são normalmente usadas na implementação de caches, alocadores de memória, roteadores, coletores de lixo, compressão de dados, cordas (ou "ropes" no Inglês, que é uma estrutura de dados) (substituição de string usada para longas strings de texto), no Windows NT (em código de memória virtual, rede e sistema de arquivos) etc.
    • CS 61B: Splay Trees (video) (CS 61B: Árvores Splay - vídeo)
    • Aula do MIT: Árvores Splay:
      • Fica bem intenso matematicamente, mas com certeza assista aos 10 últimos minutos.
      • Vídeo

  • Árvores Rubro-Negras

    • essas são uma tradução de uma árvore 2-3 (veja abaixo)
    • Ná prática: Árvores rubro-negras oferecem garantias de pior-caso para tempo de inserção, tempo de exclusão e tempo de busca. Isso não só faz elas serem úteis em aplicações que sejam sensíveis ao tempo como aplicações que funcionam em tempo real, mas isso faz elas serem úteis também em construir blocos para outras estruturas de dados, o que proporciona garantias de pior-caso; por exemplo, muitas estruturas de dados usadas em geometria computacional podem ser baseadas em árvores rubro-negras, e o Agendador Completamente Justo (Completely Fair Scheduler - CFS) usado em kernels de Linux atuais, usa as árvores rubro-negras.. Na versão 8 do Java,, a Coleção HashMap foi modificada para usar uma árvore rubro-negra ao invés de usar uma ListaLigada para armazenar elementos idênticos com hashcodes fracos.
    • Aduni - Algorithms - Lecture 4 (o link pula para o ponto de início) (video) (Aduni - Algoritmos - Aula 4 - vídeo)
    • Aduni - Algorithms - Lecture 5 (video) (Aduni - Algoritmos - Aula 5 - vídeo)
    • Black Tree (Árvore Rubro-Negra)
    • An Introduction To Binary Search And Red Black Tree (Uma Introdução a Busca Binária E Árvore Rubro-Negra)

  • Árvores de busca 2-3

    • Ná prática: árvores 2-3 tem inserções mais rápidas ao custo de buscas mais lentas (já que a altura é mais comparado às árvores AVL).
    • Você raramente usaria árvore 2-3 porque a sua implementação envolve diferentes tipos de nós (nodes). Ao invés da árvore 2-3, as pessoas usam as árvores rubro-negras.
    • 23-Tree Intuition and Definition (video) (Definição e Intuição da Árvore 2-3 - vídeo)
    • Binary View of 23-Tree (Vista Binária da Árvore 2-3)
    • 2-3 Trees (student recitation) (video) (Árvores 2-3 (recitação de estudante) - vídeo)

  • Árvores 2-3-4 (também conhecidas como árvores 2-4)

    • Ná prática: Para cada árvores 2-4, existem árvores rubro-negras correspondentes com elementos de dados na mesma ordem. As operações de inserção e exclusão nas árvores 2-4 são também equivalentes ao color-flipping (numa tradução livre, troca-de-cor) e às rotações nas árvores rubro-negras. Isso torna as árvores 2-4 uma ferramenta importante para compreender a lógica por trás das árvores rubro-negras, e é por isso que muitos textos de introdução a algoritmos introduzem árvores 2-4 logo antes das árvores rubro-negras, mesmo que as árvores 2-4 não são usadas frequentemente na prática.
    • CS 61B Lecture 26: Balanced Search Trees (video) (CS 61B Aula 26: Árvores de Busca Balanceada) - vídeo
    • Bottom Up 234-Trees (video) (Árvores 2-3-4 Descendentes - vídeo)
    • Top Down 234-Trees (video) (Árvores 2-3-4 Ascendentes) - vídeo

  • Árvores N-ary (K-ary, M-ary)

    • nota: o N ou K é o fator ramificador (máximo de ramificações)
    • árvores binárias são uma árvore 2-ary, com um fator de ramificação = 2
    • árvores 2-3 são 3-ary
    • Árvore K-Ary

  • Árvores B

    • curuiosidade: é um mistério, mas o B pode se referir a Boeing, Balanceado ou Bayber (co-inventor)
    • Ná prática: Árvores B são amplamente usadas em bancos de dados. A maioria dos sistemas de arquivos modernos usam árvores B (ou variantes). Além do seu uso em bancos de dados, ás arvores B são também usadas em sistemas de arquivos para permitir acesso aleatório rápido para um bloco arbitrário em um arquivo particular. O problema básico é tornar o endereço de bloco de arquivo em um endereço de bloco de disco (ou talvez em um cilindro-cabeça-setor, do Inglês Cylinder-Head-Sector - CHS).
    • Árvore B
    • Introduction to B-Trees (video) (Introdução a Árvore B - vídeo)
    • B-Tree Definition and Insertion (video) (Definição e Inserção de Árvore B - vídeo)
    • B-Tree Deletion (video) (Exclusão de Árvore B - vídeo)
    • MIT 6.851 - Memory Hierarchy Models (video) (MIT 6.851 - Modelos de Hierarquia de Memória - vídeo) - cobre Árvores B de cache-alheio (do Inglês, cache-oblivious), estruturas de dados muito interessantes - os primeiros 37 minutos são bem técnicos, pode ser pulado (B é tamanho de bloco, tamanho de linha de cache)

• Árvores k-D

  • ótimo para encontrar número de pontos em um retângulo ou objeto de maior dimensão
  • um bom encaixe para vizinhos mais próximos de k
  • Kd Trees (video) (Árvores k-D - vídeo)
  • kNN K-d tree algorithm (video) (Algoritmo de árvore kNN K-d - vídeo)

• Skiplists

  • "Essas são meio que estruturas de dados de um culto" - Skiena
  • Randomization: Skip Lists (video) (Randomização: Skiplists - vídeo)
  • Para animações e um pouco mais de detalhes

• Fluxos de Rede

  • Ford-Fulkerson in 5 minutes — Step by step example (vídeo) (Ford-Fulkerson em 5 minutos - Exemplo com passo a passo - vídeo)
  • Ford-Fulkerson Algorithm (video) (Algoritmo de Ford-Fulkerson)
  • Network Flows (video) (Fluxos de Rede - vídeo)

• Conjuntos Disjuntos e Union-find

  • UCB 61B - Disjoint Sets; Sorting & selection (video) (UCB 61B - Conjuntos Disjuntos; Ordenação e seleção - vídeo)
  • Sedgewick Algorithms - Union-Find (6 videos) (Algoritmos de Sedgewick - Union-find - 6 vídeos)

• Matemática para Processamento Rápido

  • Integer Arithmetic, Karatsuba Multiplication (video) (Aritmética de Números Inteiros, Multiplicação de Karatsuba - vídeo)
  • The Chinese Remainder Theorem (used in cryptography) (video) (O Teorema Chinês do Resto)

• Treap

  • Combinação de árvore binária de busca e um heap (memória dinâmica)
  • Treap
  • Data Structures: Treaps explained (video) (Estruturas de Dados: Treaps explicadas - vídeo)
  • Applications in set operations (Aplicações em Operações de Conjunto)

• Programação Linear (vídeos)

  • Linear Programming (Programação Linear)
  • Finding minimum cost (Encontrando custo mínimo)
  • Finding maximum value (Encontrando valor máximo)
  • Solve Linear Equations with Python - Simplex Algorithm (Resolva Equações Lineares com Python - Algoritmo Simplex)

• Geometria, Envoltória convexa (vídeos)

  • Graph Alg. IV: Intro to geometric algorithms - Lecture 9 (Algoritmos de Gráfico IV: Introdução a algoritmos geométricos - Aula 9)
  • Geometric Algorithms: Graham & Jarvis - Lecture 10 (Algoritmos Geométricos: Graham e Jarvis - Aula 10)
  • Divide & Conquer: Convex Hull, Median Finding (Dividir e Conquistar: Envoltória Convexa, Busca de Ponto Médio)

• Matemática discreta

  • veja os vídeos abaixo

• Aprendizado de Máquina

  • Por que AM?
    • How Google Is Remaking Itself As A Machine Learning First Company (Como A Google Está Se Refazendo Como Uma Empresa Pioneira Em Aprendizado de Máquina)
    • Large-Scale Deep Learning for Intelligent Computer Systems (video) (Aprendizagem Profunda de Grande Escala para Sistemas de Computador Inteligentes - vídeo)
    • Deep Learning and Understandability versus Software Engineering and Verification by Peter Norvig (Aprendizagem Profunda e Compreensibilidade versus Engenharia de Software e Verificação, por Peter Norvig)
  • Google's Cloud Machine learning tools (video) (Ferramentas de aprendizado de máquina na nuvem da Google - vídeo)
  • Google Developers' Machine Learning Recipes (Scikit Learn & Tensorflow) (video) (Receitas de Aprendizado de Máquina do Google Developers (Scikit Learn e Tensorflow) - vídeo)
  • Tensorflow (vídeo)
  • Tensorflow Tutorials (Tutoriais de Tensorflow)
  • Practical Guide to implementing Neural Networks in Python (using Theano) (Guia Prática para implementar Redeus Neurais em Python - usando Theano)
  • Cursos:
    • Ótimo curso iniciante: Aprendizado de Máquina - somente vídeos - veja os vídeos 12-18 para uma revisão de algebra linear (14 e 15 são duplicados)
    • Neural Networks for Machine Learning (Redes Neurais para Aprendizado de Máquina)
    • Google's Deep Learning Nanodegree (Nanodegree de Aprendizagem Profunda da Google)
    • Google/Kaggle Machine Learning Engineer Nanodegree (Nanodegree de Engenheiro de Aprendizado de Máquina da Google/Kaggle)
    • Self-Driving Car Engineer Nanodegree (Nanodegree de Engenheiro de Carro Autônomo)
    • Metis Online Course ($99 for 2 months) (Curso Online do Metis - US$99 por 2 meses)
  • Recursos:
    • Livros:
      • Python Machine Learning (Aprendizado de Máquina em Python)
      • Data Science from Scratch: First Principles with Python (Ciência de Dados do Zero: Primeiros Princípios com Python)
      • Introduction to Machine Learning with Python (Introdução a Aprendizado de Máquina com Python)
    • Machine Learning for Software Engineers (Aprendizado de Máquina para Engenheiros de Software)
    • Data School: http://www.dataschool.io/

--

Detalhes Adicionais Sobre Alguns Assuntos

Eu adicionei esses detalhes para reforçar algumas ideias já apresentadas acima, mas não quis incluir elas
acima porque aí é simplesmente demais. É fácil exagerar em um tema.
Você quer ser contratado nesse século, certo?

• Union-Find

  • Visão Geral
  • Naive Implementation (Implementação Ingênua)
  • Trees (Árvores)
  • Union By Rank
  • Path Compression (Compressão de Caminho)
  • Analysis Optional (Análise - Opcional)

• Mais Programação Dinâmica (vídeos)

  • 6.006: Dynamic Programming I: Fibonacci, Shortest Paths (6.006: Programação Dinâmica I: Fibonacci, Menores Caminhos)
  • 6.006: Dynamic Programming II: Text Justification, Blackjack (6.006: Programação Dinâmica II: Justificação de Texto, Blackjack)
  • 6.006: DP III: Parenthesization, Edit Distance, Knapsack (6.006: PD III: Parêntesisação, Editar Distância, Mochila)
  • 6.006: DP IV: Guitar Fingering, Tetris, Super Mario Bros. (6.006: PD IV: Dedilhado de Guitarra, Tetris, Super Mario Bros.)
  • 6.046: Dynamic Programming & Advanced DP (6.046: Programação Dinâmica e PD Avançada)
  • 6.046: Dynamic Programming: All-Pairs Shortest Paths (6.046: Programação Dinâmica: Menores Caminhos Entre Todos Os Pares)
  • 6.046: Dynamic Programming (student recitation) (6.046: Programação Dinâmica - recitação de estudante)

• Processamento de Gráfos Avançado (vídeos)

  • Synchronous Distributed Algorithms: Symmetry-Breaking. Shortest-Paths Spanning Trees (Algoritmos Distribuídos Síncronos: Quebra de Simetria. Árvores de Extensão De Menores Caminhos)
  • Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees (Algoritmos Distribuídos Assíncronos: Árvores de Extensão De Menores Caminhos)

• MIT Probabilidade (bem matemático, e bem lento, o que é bom para coisas bem matemáticas) (vídeos):

  • MIT 6.042J - Probability Introduction (MIT 6.042J - Introdução a Probabilidade)
  • MIT 6.042J - Conditional Probability (MIT 6.042J - Probabilidade Condicional)
  • MIT 6.042J - Independence (MIT 6.042J - Independência)
  • MIT 6.042J - Random Variables (MIT 6.042J - Variáveis Aleatórias)
  • MIT 6.042J - Expectation I (MIT 6.042J - Expectativa I)
  • MIT 6.042J - Expectation II (MIT 6.042J - Expectativa II)
  • MIT 6.042J - Large Deviations (MIT 6.042J - Grades Desvios)
  • MIT 6.042J - Random Walks (MIT 6.042J - Percursos Aleatórios)

• Simonson: Approximation Algorithms (video) (Simonson: Algoritmos de Aproximação - vídeo)

• Correspondência de String

  • Rabin-Karp (vídeos):
    • Rabin Karps Algorithm (Algoritmos de Rabin Karps)
    • Precomputing (Precomputação)
    • Optimization: Implementation and Analysis (Otimização: Implementação e Análise)
    • Table Doubling, Karp-Rabin (Duplicação de Tabela, Karp-Rabin)
    • Rolling Hashes, Amortized Analysis (Hashing Recursivo, Análise Amortizada)
  • Knuth-Morris-Pratt (KMP):
    • The Knuth-Morris-Pratt (KMP) String Matching Algorithm (O Algoritmo de Correspondência de String de Knuth-Morris-Pratt - KMP)
  • Algoritmo de busca de string de Boyer-Moore
    • Boyer-Moore String Search Algorithm (Algoritmo de Busca de String de Boyer-Moore)
    • Advanced String Searching Boyer-Moore-Horspool Algorithms (video) (Algoritmos Avançados de Busca de String de Boyer-Moore-Horspool - vídeo)
  • Coursera: Algorithms on Strings (Coursera: Algoritmos em Strings)
    • começa bem, mas depois que passa por KMP fica mais complicado do que precisa ser
    • boa explicação de tries
    • pode ser pulado

• Ordenação

  • Aulas de Stanford sobre ordenação:
    • Lecture 15 | Programming Abstractions (video) (Aula 15 | Abstrações de Programação - vídeo)
    • Lecture 16 | Programming Abstractions (video) (Aula 16 | Abstrações de Programação - vídeo)
  • Shai Simonson, Aduni.org:
    • Algorithms - Sorting - Lecture 2 (video) (Algoritmos - Ordenação - Aula 2 - vídeo)
    • Algorithms - Sorting II - Lecture 3 (video) (Algoritmos - Ordenação II - Aula 3 - vídeo)
  • Aulas de Steven Skiena sobre ordenação:
    • aula começa aos 26:46 (vídeo)
    • aula começa aos 27:40 (vídeo)
    • aula começa aos 35:00 (vídeo)
    • aula começa aos 23:50 (vídeo)

Séries de Vídeos

Sente-se e aproveite. "Netflix e habilidade" :P

• Lista de problemas individuais de Programação Dinâmica (cada um é curto)

• Arquitetura x86, Assemply, Aplicativos (11 vídeos)

• MIT 18.06 Linear Algebra, Spring 2005 (35 videos) (MIT 18.06 Álgebra Linear, Primavera de 2005 - 35 vídeos)

• Excelente - MIT Calculus Revisited: Single Variable Calculus (Cálculo de MIT Revisto: Cálculo de Variável Única)

• Computer Science 70, 001 - Spring 2015 - Discrete Mathematics and Probability Theory (Ciência da Computação 70, 001 - Primavera de 2005 - Matemática Discreta e Teoria de Probabilidade)

• Discrete Mathematics by Shai Simonson (19 videos) (Matemática Discreta por Shai Simonson - 19 vídeos)

• Discrete Mathematics Part 1 by Sarada Herke (5 videos) (Matemática Discreta Parte 1 por Sarada Herke - 5 vídeos)

• CSE373 - Análise de Algoritmos (25 vídeos)

  • Skiena lectures from Algorithm Design Manual (Aulas de Skiena do Manual de Design de Algoritmo)

• UC Berkeley 61B (Spring 2014): Data Structures (25 videos) (Universidade da Califórnia em Berkeley 61B (Primavera de 2014): Estrutura de Dados - 25 vídeos)

• UC Berkeley 61B (Fall 2006): Data Structures (39 videos) (Universidade da Califórnia em Berkeley 61B (Outono de 2006): Estrutura de Dados - 39 vídeos)

• UC Berkeley 61C: Machine Structures (26 videos) (Universidade da Califórnia em Berkeley 61C: Estruturas de Máquina - 26 vídeos)

• OOSE: Software Dev Using UML and Java (21 videos) (OOSE (Engenharia de Software Orientada a Objetos): Desenvolvimento de Software Usando UML e Java - 21 vídeos)

• UC Berkeley CS 152: Computer Architecture and Engineering (20 videos) (Universidade da Califórnia em Berkeley CS 152: Arquitetura e Engenharia de Computador - 20 vídeos)

• MIT 6.004: Computation Structures (49 videos) (MIT 6.004: Estruturas de Computação - 49 vídeos)

• Carnegie Mellon - Computer Architecture Lectures (39 videos) (Carnegie Mellon - Aulas de Arquitetura de Computador - 39 vídeos)

• MIT 6.006: Intro to Algorithms (47 videos) (MIT 6.006: Introdução a Algoritmos - 47 vídeos)

• MIT 6.033: Computer System Engineering (22 videos) (MIT 6.033: Engenharia de Sistema de Computador - 22 vídeos)

• MIT 6.034 Artificial Intelligence, Fall 2010 (30 videos) (MIT 6.034 Inteligência Artificial, Outono de 2010 - 30 vídeos)

• MIT 6.042J: Mathematics for Computer Science, Fall 2010 (25 videos) (MIT 6.042J: Matemática para Ciência da Computação, Outono de 2010 - 25 vídeos)

• MIT 6.046: Design and Analysis of Algorithms (34 videos) (MIT 6.046: Design e Análise de Algoritmos - 34 vídeos)

• MIT 6.050J: Information and Entropy, Spring 2008 (19 videos) (MIT 6.050J: Informação e Entropia, Primavera de 2008 - 19 vídeos)

• MIT 6.851: Advanced Data Structures (22 videos) (MIT 6.851: Estrutura de Dados Avançadas - 22 vídeos)

• MIT 6.854: Advanced Algorithms, Spring 2016 (24 videos) (MIT 6.854: Algoritmos Avançados, Primavera de 2016 - 24 vídeos)

• Harvard COMPSCI 224: Advanced Algorithms (25 videos) (Harvard COMPSCI 224: Algoritmos Avançados - 25 vídeos)

• MIT 6.858 Computer Systems Security, Fall 2014 (MIT 6.858 Segurança de Sistemas de Computador, Outono de 2014)

• Stanford: Programming Paradigms (27 videos) (Stanford: Paradigmas de Programação - 27 vídeos)

• Introduction to Cryptography by Christof Paar (Introdução a Criptografia por Christof Paar)

  • Website de Curso junto com Slides e Conjuntos de Problemas

• Mining Massive Datasets - Stanford University (94 videos) (Minerando Conjuntos de Dados Massivos - Universidade de Stanford - 94 vídeos)

• Graph Theory by Sarada Herke (67 videos) (Teoria de Grafos por Sarada Herke - 67 vídeos)

Cursos de Ciência da Computação

• Diretório de Cursos Online de Ciência da Computação
• Diretório de Cursos Online de Ciência da Computação (muitos com aulas online)