O guia de 30 minutos para balançar sua próxima entrevista de codificação

Estátuas de Android no Google Mountain View campus

Apesar de ter notas decentes em minha classe de Algoritmo CS101 e na minha classe de Estruturas de Dados na universidade, tremo com o pensamento de passar por uma entrevista de codificação que se concentra em algoritmos.

Por isso, passei os últimos três meses descobrindo como melhorar minhas habilidades de entrevista de codificação e, eventualmente, receberam ofertas das grandes empresas de tecnologia. Nesta publicação, vou compartilhar as idéias e dicas que ganhei ao longo do caminho. Os candidatos experientes também podem esperar questões de design do sistema, mas isso está fora do escopo desta postagem.

Muitos dos conceitos algorítmicos testados em entrevistas de codificação não são o que eu costumo usar no trabalho, onde sou engenheiro web de front-end. Naturalmente, eu esqueci um pouco sobre esses algoritmos e estruturas de dados, que eu aprendi principalmente durante meus alunos de segundo ano e segundo ano da faculdade.

É estressante ter que produzir código (trabalhando) em uma entrevista, enquanto alguém examina cada pressionamento de tecla que você faz. O que é pior é que, como entrevistado, você é encorajado a comunicar seu processo de pensamento em voz alta para o entrevistador.

Eu costumava pensar que ser capaz de pensar, codificar e comunicar simultaneamente era uma façanha impossível, até que eu percebi que a maioria das pessoas simplesmente não era boa em entrevistas de codificação quando começaram. Entrevistar é uma habilidade em que você pode melhorar ao estudar, preparar e praticar para isso.

Minha pesquisa de emprego recente me levou a uma jornada para melhorar minhas habilidades de entrevista de codificação. Os engenheiros de front-end gostam de discutir sobre como o processo de contratação atual está quebrado porque as entrevistas técnicas podem incluir habilidades não relacionadas ao desenvolvimento de front-end. Por exemplo, escrevendo um algoritmo de resolução de labirinto e mesclando duas listas de números ordenados . Como engenheiro de frente, eu posso simpatizar com eles.

O front end é um domínio especializado onde os engenheiros precisam se preocupar com muitas questões relacionadas às compatibilidades do navegador, o modelo de objeto de documento, desempenho de JavaScript, layouts de CSS e assim por diante. É incomum para engenheiros front-end implementar alguns dos algoritmos complexos testados em entrevistas.

Em empresas como o Facebook e o Google, as pessoas são engenheiros de software em primeiro lugar, especialistas em domínio em segundo lugar.

Infelizmente, as regras são definidas pelas empresas, não pelos candidatos. Existe uma grande ênfase em conceitos gerais de ciência da computação, como algoritmos, padrões de design, estruturas de dados; habilidades básicas que um bom engenheiro de software deve possuir. Se você quer o trabalho, você deve jogar de acordo com as regras estabelecidas pelos mestres do jogo – melhore suas habilidades de entrevista de codificação!

Esta publicação está estruturada nas duas seções a seguir. Sinta-se à vontade para avançar para a seção que lhe interessa.

  • A quebra de entrevistas de codificação e como se preparar para elas.
  • Dicas e sugestões úteis para cada tópico de algoritmo (arrays, árvores, programação dinâmica, etc.), juntamente com as perguntas recomendadas da LeetCode para revisar conceitos básicos e melhorar esses tópicos.

O conteúdo desta postagem pode ser encontrado no meu repositório do Tech Interview Handbook no GitHub . As atualizações serão feitas lá. Os pedidos de sugestões e correções são bem-vindos!

yangshun / tech-interview-handbook
tech-interview-handbook – ? Algoritmos, front-end e conteúdo comportamental para balançar sua entrevista de codificação. github.com

Escolhendo uma linguagem de programação

Antes de mais, você precisa escolher uma linguagem de programação para sua entrevista de codificação algorítmica. A maioria das empresas permitirá que você codifique no idioma escolhido. A única exceção que conheço é o Google. Eles permitem que seus candidatos escolham apenas de Java, C ++, Python, Go ou JavaScript. Para a maior parte, recomendo usar um idioma com o qual você esteja extremamente familiarizado, em vez de um que é novo para você, mas que a empresa usa amplamente.

Existem algumas linguas que são mais adequadas do que outras para codificação de entrevistas. Depois, há alguns que você deseja absolutamente evitar. Da minha experiência como entrevistador, a maioria dos candidatos escolhe Python ou Java. Outros idiomas comumente selecionados incluem JavaScript, Ruby e C ++. Eu absolutamente evitaria linguagens de nível inferior como C ou Go, simplesmente porque não possuem funções de biblioteca padrão e estruturas de dados.

Pessoalmente, Python é minha escolha de fato para algoritmos de codificação durante as entrevistas. É sucinto e tem uma enorme biblioteca de funções e estruturas de dados. Uma das principais razões que eu recomendo Python é que ele usa APIs consistentes que operam em diferentes estruturas de dados, como len() , for ... in ... e cortando notação em seqüências (strings, listas e tuplas). Obter o último elemento em uma seqüência é arr[-1] , e reverter é simplesmente arr[::-1] . Você pode conseguir muito com sintaxe mínima em Python.

Java também é uma escolha decente. Mas porque você terá que declarar constantemente os tipos em seu código, significa entrar em teclas extras. Isso diminuirá a velocidade na qual você codifica e escreve. Esta questão será mais evidente quando você precisa escrever em um quadro branco durante entrevistas no local.

Os motivos para escolher ou não escolher C ++ são semelhantes a Java. Em última análise, Python, Java e C ++ são escolhas decentes. Se você estiver usando o Java por um tempo e não tem tempo para se familiarizar com outro idioma, eu recomendo manter o Java em vez de pegar o Python a partir do zero. Isso ajuda você a evitar ter que usar um idioma para o trabalho e outro para entrevistas. Na maioria das vezes, o gargalo está no pensamento e não na escrita.

Uma exceção à convenção de permitir que o candidato “escolha qualquer linguagem de programação que eles desejem” é quando a entrevista é para uma posição específica do domínio, como funções de engenheiro front-end, iOS ou Android. Você precisa estar familiarizado com os algoritmos de codificação em JavaScript, Objective-C, Swift e Java, respectivamente.

Se você precisar usar uma estrutura de dados que o idioma não suporte, como uma fila ou heap em JavaScript, pergunte ao entrevistador se você pode assumir que você possui uma estrutura de dados que implementa determinados métodos com complexidades de tempo especificadas. Se a implementação dessa estrutura de dados não for crucial para resolver o problema, o entrevistador geralmente o permitirá. Na realidade, estar ciente das estruturas de dados existentes e selecionar os apropriados para abordar o problema em questão é mais importante do que conhecer os intrincados detalhes de implementação.

Revise seu CS101

Se você estiver fora da faculdade há algum tempo, é altamente recomendável rever os fundamentos do CS. Eu prefiro analisá-lo como eu pratico. Examino minhas notas da faculdade e reviso os vários algoritmos à medida que trabalho nos problemas de algoritmo do LeetCode e Cracking the Coding Interview.

Este repositório de entrevistas de Kevin Naughton Jr. serviu como uma atualização rápida para mim.

O Medium Basecs de publicação de Vaidehi Joshi também é um recurso grande e leve para recapitular as várias estruturas de dados e algoritmos.

Se você está interessado em como as estruturas de dados são implementadas, confira o Lago , uma biblioteca de Estrutura de Dados e Algoritmos para JavaScript. É ainda muito WIP, mas pretendo entrar numa biblioteca capaz de ser usada na produção e também um recurso de referência para aprender Estruturas de Dados e Algoritmos.

yangshun / lago
lago – Biblioteca de Estruturas de Dados e Algoritmos para JavaScript. github.com

Maestria pela prática

Em seguida, obtenha familiaridade e domínio dos algoritmos e estruturas de dados na sua linguagem de programação escolhida.

Pratique e resolva questões de algoritmo no idioma escolhido. Enquanto Cracking the Coding Interview é um bom recurso, eu prefiro resolver problemas digitando código, deixando-o funcionar e recebendo feedback instantâneo. Existem vários juízes on-line, como LeetCode , HackerRank e CodeForces para que você possa fazer perguntas on-line e se acostumar com a linguagem. Da minha experiência, as perguntas do LeetCode são mais parecidas com as perguntas feitas nas entrevistas. As perguntas do HackerRank e do CodeForces são mais semelhantes às questões em programação competitiva. Se você praticar perguntas LeetCode suficientes, há uma boa chance de que você veja ou complete uma das suas perguntas reais sobre a entrevista (ou alguma variante dela).

Aprenda e compreenda as complexidades de tempo e espaço das operações comuns no seu idioma escolhido. Para Python, esta página será útil. Além disso, saiba mais sobre o algoritmo de classificação subjacente utilizado na função sort() do idioma e suas complexidades de tempo e espaço (em Python é Timsort, que é um híbrido). Depois de concluir uma pergunta no LeetCode, geralmente adiciono as complexidades de tempo e espaço do código escrito como comentários acima do corpo da função. Eu uso os comentários para me lembrar de comunicar a análise do algoritmo depois de concluir a implementação.

Leia o estilo de codificação recomendado para o seu idioma e fique com ele. Se você escolher Python, consulte o Guia de Estilo PEP 8 . Se você escolher Java, consulte o Guia de Estilo Java do Google .

Conheça e conheça as armadilhas e as advertências comuns da língua. Se você os apontar durante a entrevista e evite cair neles, você ganhará pontos de bônus e impressionará o entrevistador, independentemente de o entrevistador estar familiarizado com o idioma ou não.

Obtenha ampla exposição a perguntas de vários tópicos. Na segunda metade do artigo, menciono tópicos de algoritmos e as perguntas úteis para cada tópico a praticar. Faça aproximadamente 100 a 200 perguntas de LeetCode, e você deve estar bem.

Prática, prática e mais prática!

Fases de uma entrevista de codificação

Parabéns, você está pronto para colocar suas habilidades para a prática! Em uma entrevista de codificação, você receberá uma pergunta técnica pelo entrevistador. Você escreverá o código em um editor colaborativo em tempo real (tela do telefone) ou em um quadro branco (no local) e terá de 30 a 45 minutos para resolver o problema. Aqui é onde a verdadeira diversão começa!

Seu entrevistador procurará ver que você atende aos requisitos do papel. Depende de você mostrar-lhes que você tem as habilidades. Inicialmente, pode parecer estranho falar enquanto você codifica, já que a maioria dos programadores não faz o hábito de explicar em voz alta seus pensamentos enquanto estão escrevendo código.

No entanto, é difícil para o entrevistador saber o que você está pensando apenas olhando seu código. Se você comunicar sua abordagem ao entrevistador mesmo antes de começar a codificar, você pode validar sua abordagem com eles. Desta forma, vocês dois podem concordar com uma abordagem aceitável.

Preparando-se para uma entrevista remota

Para telas de telefone e entrevistas remotas, tenha um papel e uma caneta ou um lápis para anotar notas ou diagramas. Se você tiver uma pergunta sobre árvores e gráficos, geralmente ajuda se você desenhar exemplos da estrutura de dados.

Use fones de ouvido. Certifique-se de estar num ambiente calmo. Você não quer manter um telefone em uma mão e digitar com o outro. Tente evitar o uso de alto-falantes. Se o feedback for ruim, a comunicação é mais difícil. Ter que repetir-se apenas resultará na perda de tempo valioso.

O que fazer quando você faz a pergunta

Muitos candidatos começam a codificar assim que ouvem a questão. Isso geralmente é um grande erro. Primeiro, tome um momento e repita a pergunta ao entrevistador para se certificar de que compreende a questão. Se você entender mal a questão, o entrevistador pode esclarecer.

Sempre procure esclarecimentos sobre a questão ao ouvir isso, mesmo se você achar que está claro. Você pode descobrir que você perdeu alguma coisa. Ele também permite que o entrevistador saiba que você está atento aos detalhes.

Considere fazer as seguintes perguntas.

  • Quão grande é o tamanho da entrada?
  • Quão grande é a gama de valores?
  • Que tipos de valores existem? Existem números negativos? Pontos flutuantes? Haverá entradas vazias?
  • Existem duplicatas dentro da entrada?
  • Quais são alguns dos casos extremos da entrada?
  • Como é armazenada a entrada? Se você receber um dicionário de palavras, é uma lista de strings ou trie?

Depois de ter esclarecido suficientemente o alcance e a intenção do problema, explique sua abordagem de alto nível ao entrevistador, mesmo que seja uma solução ingênua. Se você está preso, considere várias abordagens e explique em voz alta por que pode ou não funcionar. Às vezes, seu entrevistador pode deixar dicas e levá-lo para o caminho certo.

Comece com uma abordagem de força bruta. Comunique-se ao entrevistador. Explique as complexidades do tempo e do espaço e esclarece por que é ruim. É improvável que a abordagem da força bruta seja a que você codificará. Neste ponto, o entrevistador geralmente apresentará a pergunta temida “Podemos fazer melhor?”. Isso significa que eles estão buscando uma abordagem mais ótima.

Esta é geralmente a parte mais difícil da entrevista. Em geral, procure trabalhos repetidos e tente otimizá-los, potencialmente armazenando em cache o resultado calculado em algum lugar. Faça referência mais tarde, em vez de informá-lo novamente. Eu forneço algumas dicas para abordar as questões específicas do tópico em detalhes abaixo.

Apenas comece a codificar depois de você e seu entrevistador concordou em uma abordagem e você recebeu luz verde.

Começando a codificar

Use um bom estilo para escrever seu código. O código de leitura escrito por outros geralmente não é uma tarefa agradável. Ler o código horrivelmente formatado escrito por outros é ainda pior. Seu objetivo é fazer com que seu entrevistador compreenda seu código para que eles possam avaliar rapidamente se seu código faz o que é supor e se ele resolve um determinado problema. Use nomes de variáveis ​​claros e evite nomes que sejam letras únicas, a menos que sejam para iteração. No entanto, se você estiver codificando em um quadro branco, evite usar nomes detalhados de variáveis. Isso reduz a quantidade de escrita que você terá que fazer.

Sempre explique ao entrevistador o que você está escrevendo ou digitando. Não se trata de ler, literalmente, ao entrevistador o código que você está produzindo. Fale sobre a seção do código que você está implementando atualmente em um nível superior. Explique por que está escrito como tal e o que está tentando alcançar.

Quando você copia e cola no código, considere se é necessário. Às vezes é, às vezes não é. Se você se encontra copiando e colando um grande pedaço de código que abrange várias linhas, provavelmente é um indicador de que você pode reestruturar o código extraindo essas linhas em uma função. Se é apenas uma única linha que você copiou, geralmente está bem. No entanto, lembre-se de alterar as respectivas variáveis ​​na sua linha de código copiada quando relevante. Copiar e colar erros são uma fonte comum de erros, mesmo na codificação do dia-a-dia!

Após a codificação

Depois de terminar a codificação, não anuncie imediatamente ao entrevistador que você terminou. Na maioria dos casos, seu código geralmente não é perfeito. Pode conter erros ou erros de sintaxe. O que você precisa fazer é rever seu código.

Primeiro, veja seu código do início ao fim. Olhe como se fosse escrito por outra pessoa, e você está vendo pela primeira vez e tentando detectar erros nela. É exatamente isso que o entrevistador estará fazendo. Revise e corrija quaisquer problemas que você possa encontrar.

Em seguida, venha com pequenos casos de teste e passe pelo código (e não o seu algoritmo) com a amostra. Os entrevistadores gostam quando você lê suas mentes. O que eles costumam fazer depois de terminar a codificação é fazer com que você escreva testes. É uma grande vantagem se você escrever testes para seu código mesmo antes de solicitar que você o faça. Você deve emular um depurador ao passar pelo seu código. Anote ou diga-lhes os valores de certas variáveis ​​enquanto você anda pelo entrevistador através das linhas de código.

Se houver grandes pedaços duplicados de código na sua solução, reestruture o código para mostrar ao entrevistador que você valoriza a codificação de qualidade. Além disso, procure lugares onde você pode fazer uma avaliação de curto-circuito .

Por fim, dê as complexidades de tempo e espaço do seu código, e explique por que é assim. Você pode anotar pedaços de seu código com suas várias complexidades de tempo e espaço para demonstrar sua compreensão do código. Você pode até fornecer as APIs da sua linguagem de programação escolhida. Explique quaisquer trade-offs em sua abordagem atual versus abordagens alternativas, possivelmente em termos de tempo e espaço.

Se o seu entrevistador estiver feliz com a solução, a entrevista geralmente termina aqui. Também é comum que o entrevistador lhe pergunte questões de extensão, como a forma como você lida com o problema se a entrada inteira for muito grande para caber na memória ou se a entrada chegar como um fluxo. Esta é uma questão de acompanhamento comum no Google, onde eles se preocupam muito com a escala. A resposta é geralmente uma abordagem de divisão e conquista – execute o processamento distribuído dos dados e leia apenas alguns troços da entrada do disco na memória, escreva a saída de volta para o disco e combine-os mais tarde.

Prática com entrevistas falsas

Os passos mencionados acima podem ser ensaiados uma e outra vez até que você os tenha internalizado completamente e eles se tornem uma segunda natureza para você. Uma boa maneira de praticar é parceria com um amigo e se revezando para entrevistar uns aos outros.

Um ótimo recurso para se preparar para entrevistas de codificação é entrevistar . Esta plataforma oferece entrevistas de prática gratuitas e anônimas com engenheiros do Google e do Facebook, que podem levar a empregos e estágios reais. Em virtude de ser anônimo durante a entrevista, o processo de entrevista inclusiva é imparcial e de baixo risco. No final da entrevista, tanto o entrevistador quanto o entrevistado podem fornecer feedback mútuo com o objetivo de ajudar uns aos outros a melhorar.

Fazer bem em entrevistas simuladas irá desbloquear a página de emprego para os candidatos e permitir que eles entrem em entrevistas (também anonimamente) com empresas de alto nível como Uber, Lyft, Quora, Asana e muito mais. Para aqueles que são novos nas entrevistas de codificação, uma entrevista de demonstração pode ser vista neste site . Observe que este site exige que os usuários façam login.

Eu usei entrevistas.io, tanto como entrevistador quanto como entrevistado. A experiência foi ótima. Aline Lerner , CEO e co-fundadora da interviewing.io , e sua equipe são apaixonadas por revolucionar o processo de codificação de entrevistas e ajudar os candidatos a melhorar suas habilidades de entrevista. Ela também publicou uma série de artigos de codificação relacionados à entrevista no blog interviewing.io . Eu recomendo inscrever o mais cedo possível com interviewing.io, mesmo que esteja em versão beta, para aumentar a probabilidade de receber um convite.

Prática de entrevista anonimamente com engenheiros de empresas de topo!

Outra plataforma que permite a prática de entrevistas de codificação é Pramp . Onde entrevistas.io coincide com possíveis candidatos a emprego com entrevistadores de codificação experientes, a Pramp adota uma abordagem diferente. Pramp combina você com outro parceiro que também é um candidato a emprego. Os dois se revezam assumindo os papéis de entrevistador e entrevistado. A Pramp também prepara perguntas e fornece soluções e instruções para orientar o entrevistado.

Pessoalmente, não adoro a abordagem de Pramp. Porque quando faço entrevistas, faço perguntas que me são familiares. Além disso, muitos usuários não têm a experiência de serem entrevistadores e isso pode resultar em uma experiência de entrevista horrível. Em um caso, o meu par correspondente assumiu o papel do entrevistador, mas ele não teve a compreensão correta da questão e tentou me levar pelo caminho errado para resolver a questão. No entanto, isso é mais um problema do candidato do que a plataforma.

Sai e conquiste

Depois de fazer uma boa quantidade de perguntas sobre o LeetCode e ter bastante prática fazendo entrevistas falsas, avance e coloque suas novas habilidades de entrevista encontradas para a prova. Candidate-se às suas empresas favoritas ou, melhor ainda, obtenha referências de seus amigos trabalhando para essas empresas. As referências tendem a ser notadas anteriormente e têm uma taxa de resposta mais rápida do que a aplicação sem uma referência. Boa sorte!

Dicas práticas para codificar perguntas

Esta seção mergulha profundamente em dicas práticas para tópicos específicos de algoritmos e estruturas de dados, que aparecem frequentemente em questões de codificação. Muitas questões de algoritmo envolvem técnicas que podem ser aplicadas a questões de natureza similar.

Quanto mais técnicas você tiver em seu arsenal, maiores serão suas chances de passar a entrevista. Para cada tópico, há também uma lista de perguntas recomendadas, que é valiosa para dominar os conceitos básicos. Algumas das perguntas só estão disponíveis com uma assinatura paga para o LeetCode, o que, na minha opinião, vale absolutamente o dinheiro se ele forçá-lo a trabalhar.

Dicas gerais

Valide sempre a entrada primeiro. Verifique se há entradas inválidas, vazias, negativas ou diferentes. Nunca assuma que você tenha os parâmetros válidos. Alternativamente, esclareça com o entrevistador se você pode assumir a entrada válida (geralmente sim), o que pode poupar tempo de escrever o código que faz a validação de entrada.

Existem requisitos ou restrições de complexidade de tempo e espaço?

Verifique se há erros off-by-one.

Em idiomas onde não há coerção de tipo automático, verifique se a concatenação de valores é do mesmo tipo: int , str e list .

Depois de terminar seu código, use algumas entradas de exemplo para testar sua solução.

O algoritmo deve ser executado várias vezes, talvez em um servidor web? Se sim, a entrada provavelmente pode ser pré-processada para melhorar a eficiência em cada chamada de API.

Use uma combinação de paradigmas de programação funcional e imperativa:

  • Escreva as funções puras o mais rápido possível.
  • Use funções puras porque são mais fáceis de argumentar e podem ajudar a reduzir os erros na sua implementação.
  • Evite mutar os parâmetros passados ​​em sua função, especialmente se eles são passados ​​por referência, a menos que você tenha certeza do que está fazendo.
  • Obtenha um equilíbrio entre precisão e eficiência. Use a quantidade certa de código funcional e imperativo onde apropriado. A programação funcional geralmente é cara em termos de complexidade espacial devido à não mutação e à alocação repetida de novos objetos. Por outro lado, o código imperativo é mais rápido porque você opera em objetos existentes.
  • Evite confiar em variáveis ​​variáveis ​​globais. As variáveis ​​globais introduzem o estado.
  • Certifique-se de que você não muda acidentalmente variáveis ​​globais, especialmente se você tiver que confiar nelas.

Geralmente, para melhorar a velocidade de um programa, podemos optar por usar uma estrutura ou algoritmo de dados apropriado, ou para usar mais memória. É um intercâmbio clássico de espaço e tempo.

As estruturas de dados são suas armas. Escolher a arma certa para a batalha certa é a chave para a vitória. Conheça os pontos fortes de cada estrutura de dados e a complexidade do tempo para suas várias operações.

As estruturas de dados podem ser aumentadas para alcançar uma complexidade de tempo eficiente em diferentes operações. Por exemplo, um HashMap pode ser usado junto com uma lista duplamente vinculada para alcançar a complexidade do tempo O (1) tanto para a operação get e put em um cache LRU .

Os HashMaps são provavelmente a estrutura de dados mais comumente usada para questões de algoritmo. Se você está preso em uma questão, seu último recurso pode ser enumerar através das possíveis estruturas de dados (felizmente não há tantos) e considerar se cada um deles pode ser aplicado ao problema. Isso já funcionou para mim às vezes.

Se você estiver cortando cantos em seu código, indique isso em voz alta para seu entrevistador e explique-lhes o que você faria fora de uma configuração de entrevista (sem restrições de tempo). Por exemplo, explique que você escreva uma regex para analisar uma string ao invés de usar o split , que não cobre todos os casos.

Seqüência

Notas

Arrays e strings são considerados sequências (uma string é uma seqüência de caracteres). Há dicas para lidar com arrays e strings, que serão abordados aqui.

Existem valores duplicados na seqüência? Eles afetariam a resposta?

Verifique a seqüência fora dos limites.

Esteja atento sobre cortar ou concatenar seqüências em seu código. Normalmente, as sequências de fatiamento e concatenação requerem tempo de O (n). Use índices de início e fim para demarcar um subarray ou substring sempre que possível.

Às vezes você atravessa a seqüência do lado direito e não da esquerda.

Mestre a técnica da janela deslizante que se aplica a muitos substring ou problemas de subarray.

Quando você recebe duas seqüências para processar, é comum ter um índice por seqüência para percorrer. Por exemplo, usamos a mesma abordagem para fundir dois arrays ordenados.

Casos de canto

  • Sequência vazia
  • Sequência com 1 ou 2 elementos
  • Sequência com elementos repetidos

Array

Notas

A matriz está ordenada ou parcialmente ordenada? Se for o caso, alguma forma de busca em binário deve ser possível. Isso geralmente significa que o entrevistador está procurando uma solução que seja mais rápida do que O (n).

Você pode classificar a matriz? Às vezes, ordenar a matriz primeiro pode simplificar significativamente o problema. Certifique-se de que a ordem dos elementos da matriz não precisa ser preservada antes de tentar classificá-la.

Para questões em que o somatório ou a multiplicação de um subarray esteja envolvido, a pré-computação usando hash ou um prefixo, uma soma de sufixo ou produto pode ser útil.

Se você receber uma seqüência e o entrevistador pede o espaço de O (1), pode ser possível usar a matriz em si como uma tabela de hash. Por exemplo, se a matriz tiver valores apenas de 1 a N, onde N é o comprimento da matriz, negar o valor nesse índice (menos um) para indicar a presença desse número.

Perguntas de prática

Binário

Links de estudo

Notas

As perguntas envolvendo representações binárias e operações bit-bit são feitas às vezes. Você deve saber como converter um número da forma decimal em forma binária, e vice-versa, na sua linguagem de programação escolhida.

Alguns fragmentos de utilidade úteis:

  • O bit de teste kth está definido: num & (1 << k) != 0
  • Set kth bit: num |= (1 << k)
  • Desligue o bit kth: num &= ~(1 << k)
  • Alternar o bit kth: num ^= (1 << k)
  • Para verificar se um número é uma potência de 2: num & num - 1 == 0 .

Casos de canto

  • Verifique o estouro / subida
  • Números negativos

Perguntas de prática

Programaçao dinamica

Links de estudo

Notas

A programação dinâmica (DP) geralmente é usada para resolver problemas de otimização. Alaina Kafkes escreveu uma publicação incrível sobre como lidar com problemas de DP. Você deveria lê-lo.

A única maneira de melhorar em DP é com a prática. É preciso muita prática para reconhecer que um problema pode ser resolvido pela DP.

Para otimizar o espaço, às vezes você não precisa armazenar toda a tabela DP na memória. Os dois últimos valores ou as últimas duas linhas da matriz serão suficientes.

Perguntas de prática

Geometria

Notas

Ao comparar a distância euclidiana entre dois pares de pontos, o uso de dx² + dy² é suficiente. É desnecessário criar o valor do root.

Para descobrir se dois círculos se sobrepõem, verifique se a distância entre os dois centros dos círculos é menor do que a soma de seus raios.

Gráfico

Links de estudo

Notas

Esteja familiarizado com as várias representações gráficas e algoritmos de pesquisa de gráficos, e com suas complexidades de tempo e espaço.

Você pode receber uma lista de bordas e encarregado de criar seu próprio gráfico a partir das bordas para realizar uma travessia. As representações de gráfico comuns são

  • Matriz de adjacência
  • Lista de adjacências
  • HashMap de HashMaps

Algumas insumos parecem ser árvores, mas são realmente gráficos. Esclarecer isso com o entrevistador. Nesse caso, você terá que lidar com ciclos e manter um conjunto de nós visitados ao percorrer.

Algoritmos de pesquisa em grafos

  • Comum: Breadth first search (BFS), Depth first search (DFS)
  • Pouco frequentes: tipo topológico, algoritmo de Dijkstra
  • Raro: algoritmo Bellman-Ford, algoritmo de Floyd-Warshall, algoritmo de Prim e algoritmo de Kruskal

Na codificação de entrevistas, os gráficos são comumente representados como matrizes 2-D, onde as células são os nós e cada célula pode atravessar as células adjacentes (para cima, para baixo, para a esquerda e para a direita). Por isso, é importante estar familiarizado com a passagem de uma matriz 2-D. Ao percorrer recursivamente a matriz, sempre assegure-se de que sua próxima posição esteja dentro do limite da matriz. Mais dicas para fazer DFS em uma matriz podem ser encontradas aqui . Um modelo simples para fazer DFS em uma matriz aparece algo assim:

 def traverse (matriz): 
 linhas, cols = len (matriz), len (matriz [0]) 
 visitado = conjunto () 
 direções = ((0, 1), (0, -1), (1, 0), (-1, 0)) 
 def dfs (i, j): 
 se (i, j) em visitado: 
 Retorna 
 visitado.add ((i, j)) 
 # Traverse vizinhos 
 para direção em direções: 
 next_i, next_j = i + direção [0], j + direção [1] 
 se 0 <= next_i <linhas e 0 <= next_j <cols: # Check boundary 
 # Adicione qualquer outra verificação aqui ^ 
 dfs (next_i, next_j)
 para o intervalo i (linhas): 
 para j no alcance (cols): 
 dfs (i, j)

Casos de canto

  • Gráfico vazio
  • Gráfico com um ou dois nós
  • Gráficos disjuntos
  • Gráfico com ciclos

Perguntas de prática

Intervalo

Notas

Perguntas de intervalo são questões que dão uma matriz de arrays de dois elementos (um intervalo). Os dois valores representam um valor inicial e final. As perguntas de intervalo são consideradas parte da família da matriz, mas envolvem algumas técnicas comuns. Portanto, eles têm sua própria seção especial.

Um exemplo de uma matriz de intervalo: [[1, 2], [4, 7]] .

As perguntas de intervalo podem ser complicadas para aqueles que não têm experiência com eles. Isso é devido ao grande número de casos a serem considerados quando os arrays de intervalos se sobrepõem.

Esclarecer com o entrevistador se [1, 2] e [2, 3] são considerados intervalos sobrepostos, porque afeta a forma como você irá escrever suas verificações de igualdade.

Uma rotina comum para questões de intervalo é classificar a matriz de intervalos pelo valor de início de cada intervalo.

Esteja familiarizado com o código de escrita para verificar se dois intervalos se sobrepõem e mesclar dois intervalos sobrepostos:

 def is_overlap (a, b): 
 retornar um [0] <b [1] e b [0] <a [1]
 def merge_overlapping_intervals (a, b): 
 retornar [min (a [0], b [0]), max (a [1], b [1])]

Casos de canto

  • Intervalo único
  • Intervalos sem sobreposição
  • Um intervalo totalmente consumido dentro de outro intervalo
  • Intervalos duplicados

Perguntas de prática

Lista vinculada

Notas

Como arrays, as listas ligadas são usadas para representar dados seqüenciais. O benefício das listas vinculadas é que a inserção e exclusão de código de qualquer lugar na lista é O (1), enquanto que em matrizes, os elementos devem ser deslocados.

Adicionar um nó fofo na cabeça e / ou na cauda pode ajudar a lidar com muitos casos de borda em que as operações devem ser realizadas na cabeça ou na cauda. A presença de nós falsos garante que as operações nunca serão executadas na cabeça ou na cauda. Os nodos Dummy removem a dor de cabeça da escrita de verificações condicionais para lidar com ponteiros nulos. Certifique-se de removê-los no final da operação.

Às vezes, o problema das listas vinculadas pode ser resolvido sem armazenamento adicional. Tente pedir emprestado ideias do para reverter um problema de lista vinculada.

Para exclusão em listas vinculadas, você pode modificar os valores do nó ou alterar os ponteiros do nó. Talvez seja necessário manter uma referência ao elemento anterior.

Para particionar listas vinculadas, crie duas listas vinculadas separadas e junte-as novamente.

Os problemas das listas vinculadas compartilham semelhanças com problemas de matrizes. Pense sobre como você resolveria um problema de matriz e aplicá-lo-á a uma lista vinculada.

Duas abordagens de ponteiro também são comuns para listas vinculadas:

  • Obtendo o kth do último nó: tenha dois ponteiros, onde um é k nós a frente do outro. Quando o nó adiante alcança a extremidade, o outro nó é k nós atrás.
  • Ciclos de detecção: tenha dois ponteiros, onde um ponteiro incremente duas vezes mais do que o outro. Se os dois ponteiros se encontrarem, isso significa que há um ciclo.
  • Obtendo o nó do meio: tenha dois ponteiros. Um ponteiro aumenta duas vezes mais do que o outro. Quando o nó mais rápido atinge o final da lista, o nó mais lento estará no meio.

Esteja familiarizado com as seguintes rotinas porque muitas perguntas da lista vinculada utilizam uma ou mais dessas rotinas na sua solução.

  • Contar o número de nós na lista vinculada
  • Inverter uma lista vinculada no lugar
  • Encontre o nó do meio da lista vinculada usando ponteiros rápidos ou lentos
  • Junte duas listas juntas

Casos de canto

  • Nó único
  • Dois nós
  • A lista vinculada tem ciclo. Esclarecer com o entrevistador se pode haver um ciclo na lista. Normalmente, a resposta é não.

Perguntas de prática

Matemática

Notas

Se o código envolve divisão ou módulo, lembre-se de verificar divisão ou módulo por 0 caso.

Quando uma questão envolve “um múltiplo de um número”, o módulo pode ser útil.

Verifique e manipule o transbordamento e subfluxo se você estiver usando um idioma digitado como Java e C ++. No mínimo, mencione que o estouro ou subfluxo é possível e pergunte se você precisa lidar com isso.

Considere números negativos e números de ponto flutuante. Isso pode parecer óbvio, mas quando você está sob pressão em uma entrevista, muitos pontos óbvios passam despercebidos.

Se a pergunta solicitar a implementação de um operador, como poder, squareroot ou divisão, e deve ser mais rápido do que O (n), a pesquisa binária geralmente é a abordagem.

Algumas fórmulas comuns

  • Soma de 1 a N = (n + 1) * n / 2
  • Soma de GP = 2⁰ + 2¹ + 2² + 2³ + … 2 ^ n = 2 ^ (n + 1) -1
  • Permutações de N = N! / (NK)!
  • Combinações de N = N! / (K! * (NK)!)

Casos de canto

  • Divisão por 0
  • Sobretensão total e sub-fluxo

Perguntas de prática

Matriz

Notas

Uma matriz é uma matriz bidimensional. As questões que envolvem matrizes geralmente estão relacionadas a programação dinâmica ou cruzamento gráfico.

Para questões que envolvam a passagem ou programação dinâmica, faça uma cópia da matriz com as mesmas dimensões que são inicializadas para valores vazios. Use esses valores para armazenar o estado visitado ou a tabela de programação dinâmica. Esteja familiarizado com esta rotina:

 linhas, cols = len (matriz), len (matriz [0]) 
 copy = [[0 para _ no intervalo (cols)] para _ no intervalo (linhas)
  • Muitos jogos baseados em grade podem ser modelados como uma matriz. Por exemplo, Tic-Tac-Toe, Sudoku, Crossword, Connect 4 e Battleship. Não é incomum que se peça verificar a condição vencedora do jogo. Para jogos como Tic-Tac-Toe, Connect 4 e Crosswords, a verificação deve ser feita verticalmente e horizontalmente. Um truque é escrever código para verificar a matriz para as células horizontais. Em seguida, transponha a matriz, reutilizando a lógica usada para verificação horizontal para verificar células originalmente verticais (que agora estão horizontais).
  • A transposição de uma matriz em Python é simplesmente:
 transposed_matrix = zip (* matrix)

Casos de canto

  • Matriz vazia. Verifique se nenhuma das matrizes tem 0 comprimento.
  • 1 x 1 matriz.
  • Matriz com apenas uma linha ou coluna.

Perguntas de prática

Recursão

Notas

A recursão é útil para permutação, pois gera todas as combinações e questões baseadas em árvore. Você deve saber como gerar todas as permutações de uma seqüência, bem como como lidar com duplicatas.

Lembre-se de sempre definir um caso base para que sua recursão termine.

A recursão usa implicitamente uma pilha. Portanto, todas as abordagens recursivas podem ser reescritas iterativamente usando uma pilha. Cuidado com os casos em que o nível de recursão é muito profundo e causa um estouro de pilha (o limite padrão em Python é 1000). Você pode obter pontos de bônus por apontar isso para o entrevistador. A recursão nunca será a complexidade do espaço O (1) porque uma pilha está envolvida, a menos que haja otimização da chamada traseira (TCO). Descubra se o seu idioma escolhido suporta TCO.

Perguntas de prática

Corda

Notas

Leia as dicas acima sobre a sequência . Eles também se aplicam às cordas.

Pergunte sobre o conjunto de caracteres de entrada e a sensibilidade do caso. Normalmente, os caracteres são limitados a caracteres latinos em minúsculas, por exemplo, a para z.

Quando você precisa comparar strings onde a ordem não é importante (como anagrama), você pode considerar usar um HashMap como um contador. Se o seu idioma tiver uma classe de Counter embutida como Python, peça para usar isso.

Se você precisa manter um contador de personagens, um erro comum é dizer que a complexidade espacial necessária para o contador é O (n). O espaço necessário para um contador é O (1) não O (n). Isso ocorre porque o limite superior é o intervalo de caracteres, que geralmente é uma constante fixa de 26. O conjunto de entrada é apenas caracteres latinos em minúsculas.

Estruturas de dados comuns para procurar cordas de forma eficiente são

Algoritmos comuns de cordas são

  • Rabin Karp , que conduz pesquisas eficientes de substrings, usando um hash de rolamento
  • KMP , que conduz pesquisas eficientes de substrings

Caracteres não repetitivos

Use uma máscara de bits de 26 bits para indicar quais os caracteres latinos em minúsculas estão dentro da seqüência de caracteres.

 máscara = 0 
 para c em conjunto (palavra): 
 máscara | = (1 << (ord (c) - ord ('a')))

Para determinar se duas cadeias têm caracteres comuns, execute & nas duas máscaras de bits. Se o resultado for diferente de zero, mask_a & mask_b > 0 , as duas cadeias têm caracteres comuns.

Anagrama

Um anagrama é conversão de palavras ou jogo de palavras. É o resultado de reorganizar as letras de uma palavra ou frase para produzir uma nova palavra ou frase, enquanto usa todas as letras originais apenas uma vez. Nas entrevistas, geralmente somos incomodados com palavras sem espaços neles.

Para determinar se duas cordas são anagramas, existem algumas abordagens plausíveis:

  • A triagem de ambas as cordas deve produzir a mesma string resultante. Isso leva O (nlgn) tempo e O (lgn) espaço.
  • Se nós mapeamos cada personagem para um número primo e multiplicamos cada número mapeado juntos, os anagramas devem ter o mesmo múltiplo (decomposição do fator principal). Isso leva O (n) tempo e O (1) espaço.
  • A contagem de frequência de caracteres ajudará a determinar se duas strings são anagramas. Isso também leva O (n) tempo e O (1) espaço.

Palindrome

Um palindrome é uma palavra, frase, número ou outra seqüência de caracteres que lê o mesmo para trás e para frente, como madam ou racecar .

Aqui estão maneiras de determinar se uma string é um palindrome:

  • Inverta a corda e deve ser igual a si mesmo.
  • Tenha dois ponteiros no início e no final da string. Mova os ponteiros para dentro até que eles se encontrem. Em qualquer momento, os caracteres em ambos os ponteiros devem corresponder.

A ordem dos caracteres dentro da cadeia é importante, portanto, HashMaps geralmente não são úteis.

Quando uma questão é sobre contar o número de palíndromes, um truque comum é ter dois ponteiros que se movem para fora, longe do meio. Observe que os palíndromes podem ser pares ou estranhos. Para cada posição de pivô do meio, você precisa verificar duas vezes: uma vez que inclui o personagem e uma vez sem o personagem.

  • Para substrings, você pode terminar cedo uma vez que não há correspondência.
  • Para subseqüências, use programação dinâmica, pois existem subproblemas sobrepostos. Confira esta questão .

Casos de canto

  • Cadeia de caracteres vazia
  • Cadeia de um único caracter
  • Cordas com apenas um caractere distinto

Perguntas de prática

Árvore

Links de estudo

Notas

Uma árvore é um gráfico acíclico não dirigido e conectado.

A recursão é uma abordagem comum para as árvores. Quando você percebe que o problema da subárvore pode ser usado para resolver todo o problema, tente usar a recursão.

Ao usar a recursão, lembre-se sempre de verificar o caso base, geralmente onde o nó é null .

Quando você é solicitado a percorrer uma árvore por nível, use a primeira pesquisa de profundidade.

Às vezes, é possível que sua função recursiva precise retornar dois valores.

Se a questão envolver soma de nós ao longo do caminho, certifique-se de verificar se os nós podem ser negativos.

Você deve estar muito familiarizado com a escrita de pré-ordem, pedido e passagem posterior da ordem de forma recursiva. Como uma extensão, desafie-se escrevendo iteratively. Às vezes, entrevistadores pedem candidatos para a abordagem iterativa, especialmente se o candidato terminar de escrever a abordagem recursiva com muita rapidez.

Árvore binária

A passagem de uma árvore binária em ordem é insuficiente para serializar uma árvore de forma exclusiva. O percurso pré-pedido ou pós-pedido também é necessário.

Árvore de pesquisa binária (BST)

As tentativas são árvores especiais (árvores de prefixo) que tornam a busca e o armazenamento de strings mais eficientes. Tries tem muitas aplicações práticas, como realizar buscas e fornecer autocompletar. É útil conhecer essas aplicações comuns para que você possa identificar facilmente quando um problema pode ser resolvido eficientemente usando um trie.

Às vezes, o pré-processamento de um dicionário de palavras (fornecido em uma lista) em um trie, irá melhorar a eficiência da busca de uma palavra de comprimento k, entre n palavras. A pesquisa torna-se O (k) em vez de O (n).

Esteja familiarizado com a implementação, a partir do zero, de uma classe Trie e seus métodos de add , remove e search .

Perguntas de prática

Heap

Links de estudo

Notas

Se você ver um k superior ou menor mencionado na pergunta, é geralmente um sinal de que uma pilha pode ser usado para resolver o problema, como no Top K Elementos freqüentes .

Se você precisar dos elementos k superiores, use um Min Heap de tamanho k . Iterate através de cada elemento, empurrando-o para o heap. Sempre que o tamanho do heap exceda k , remova o elemento mínimo. Isso garantirá que você tenha os k maiores elementos.

Perguntas de prática

Texto original em inglês.