Artigo original: How to Rock the Coding Interview – Tips That Helped Me Land Job Offers from Google, Airbnb, and Dropbox

Em 2017, passei por algumas entrevistas de programação e recebi ofertas de várias grandes empresas de tecnologia. Foi naquele momento que decidi compartilhar o que tinha aprendido neste artigo.

Acabo de atualizá-lo para este ano para que seja superútil e relevante se você estiver procurando emprego agora.

Apesar de ter notas decentes tanto na minha disciplina básica de algoritmos, quanto na minha disciplina de estruturas de dados no curso de Ciência da Computação na universidade, estremeço ao pensar em passar por uma entrevista de programação que se concentre em algoritmos.

Assim, passei os últimos três meses descobrindo como melhorar minhas habilidades em programação para entrevistas e, no fim, recebi ofertas de grandes empresas de tecnologia, como Google, Facebook, Airbnb, Lyft, Dropbox e muitas outras.

Neste artigo, compartilharei as ideias e dicas que recebi ao longo do caminho. Candidatos experientes também podem esperar perguntas sobre design de sistemas, mas isso está fora do escopo deste artigo.

Muitos dos conceitos algorítmicos testados em entrevistas de programação não são aquilo que costumo usar no trabalho, onde sou um engenheiro de front-end (web). Naturalmente, me esqueci um pouco desses algoritmos e estruturas de dados, que aprendi principalmente durante o primeiro e o segundo anos da minha faculdade.

É estressante ter que produzir código (funcional) em uma entrevista enquanto alguém examina cada toque no teclado que você faz. O pior é que, como entrevistado, você é encorajado a comunicar seu processo de pensamento em voz alta ao entrevistador.

Eu costumava pensar que ser capaz de pensar, programar e comunicar simultaneamente era um feito impossível, até que percebi que a maioria das pessoas simplesmente não é boa em entrevistas de programação quando começam. Ser entrevistado é uma habilidade em que se pode melhorar estudando, preparando-se e praticando para isso.

Minha busca de emprego recente me levou a uma jornada para melhorar minhas habilidades para as entrevistas de programação. Os engenheiros de front-end gostam de se queixar de como o atual processo de contratação é ruim, pois as entrevistas técnicas podem incluir habilidades não relacionadas ao desenvolvimento de front-end. Por exemplo, escrever um algoritmo de resolução de labirintos e mesclar duas listas ordenadas de números. Como engenheiro de front-end, eu entendo bem o motivo da reclamação.

O front-end é um domínio especializado, onde os engenheiros têm que se preocupar com muitas questões relacionadas às compatibilidades do navegador, o Modelo de Objeto do Documento (DOM - Document Object Model), desempenho do JavaScript, layouts do CSS e assim por diante. É incomum para os engenheiros de front-end implementar alguns dos complexos algoritmos testados em entrevistas.

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

Infelizmente, as regras são estabelecidas pelas empresas, não pelos candidatos. Há uma grande ênfase nos conceitos gerais da informática, como algoritmos, padrões de design e estruturas de dados – habilidades essenciais que um bom engenheiro de software deve possuir. Se você quer o trabalho, você tem que jogar de acordo com as regras estabelecidas pelos mestres do jogo – e melhorar suas habilidades para as entrevistas de programação!

Este artigo está estruturado nas duas seções seguintes. Sinta-se à vontade para pular para a seção que interessa a você.

  • O formato das entrevistas de programação e como se preparar para elas.
  • Dicas úteis para cada tópico de algoritmos (arrays, árvores, programação dinâmica etc.), juntamente com perguntas práticas recomendadas pelo LeetCode para rever os conceitos centrais e melhorar nesses tópicos.

O conteúdo deste artigo pode ser encontrado aqui (em inglês). Lá, farei atualizações quando necessário.

Se você está interessado no conteúdo de front-end, confira meu manual de entrevistas para front-end aqui (em inglês).

Escolhendo uma linguagem de programação

Antes de mais nada, você precisa escolher uma linguagem de programação para sua entrevista de programação algorítmica.

A maioria das empresas permitirá que você programe na linguagem de sua escolha. A única exceção que eu conheço é o Google. Lá, é permitido que seus candidatos escolham apenas entre Java, C++, Python, Go ou JavaScript.

Na maioria das vezes, recomendo o uso de uma linguagem com a qual você esteja extremamente familiarizado, em vez de uma linguagem que é nova para você, mas que a empresa utiliza amplamente.

Há algumas linguagens que são mais adequadas do que outras para as entrevistas de programação. Também há algumas outras que você vai querer evitar, com certeza.

A partir da minha experiência como entrevistador, a maioria dos candidatos escolhe Python ou Java. Outras linguagens comumente selecionadas incluem JavaScript, Ruby e C++. Eu evitaria absolutamente linguagens de mais baixo nível, como o C ou o Go, simplesmente porque elas não possuem funções de biblioteca padrão e estruturas de dados.

Pessoalmente, o Python é normalmente a minha escolha para os algoritmos de programação durante as entrevistas. Ele é sucinto e tem uma enorme biblioteca de funções e estruturas de dados.

Uma das principais razões que me faz recomendar o Python é o fato de ele usar APIs consistentes, que operam em diferentes estruturas de dados, tais como len(), for ... in ... e notação de corte (do inglês, slicing) em sequências (strings, listas e tuplas). Obter o último elemento em uma sequência é arr[-1] e revertê-lo é simplesmente arr[::-1]. Você pode conseguir muito com pouca sintaxe em Python.

O Java também é uma escolha decente. Como, no entanto, você terá que declarar constantemente os tipos em seu código, isso significa digitar mais. Isso diminuirá a velocidade na qual você programa e digita. Essa questão fica mais aparente quando você tiver que escrever em um quadro branco durante entrevistas no local.

As razões para escolher ou não escolher C++ são similares às de Java. No fim, Python, Java, e C++ são escolhas decentes. Se você está usando Java há algum tempo e não tem tempo para se familiarizar com outra linguagem, recomendo que se mantenha fiel ao Java em vez de pegar o Python do zero. Isto o ajudará a evitar de ter que usar uma linguagem para o trabalho e outra para entrevistas. A maior parte do tempo, o que trava é o pensamento, não a escrita.

Uma exceção à convenção de permitir que o candidato "escolha a linguagem de programação que quiser" é quando a entrevista é para um cargo específico de domínio, como funções de engenheiro de front-end, iOS ou Android. Você precisa estar familiarizado com algoritmos de programação em JavaScript, Objective-C, Swift e Java, respectivamente.

Se você precisar usar uma estrutura de dados que a linguagem não suporte, como uma fila ou pilha em JavaScript, pergunte ao entrevistador se você pode assumir que tem uma estrutura de dados que implementa certos métodos com complexidades de tempo especificadas. Se a implementação dessa estrutura de dados não for crucial para a solução do problema, o entrevistador normalmente a permitirá.

Na realidade, estar ciente das estruturas de dados existentes e selecionar as estruturas apropriadas para resolver o problema em questão é mais importante do que conhecer os intrincados detalhes de implementação.

Revise sua Ciência da Computação básica

Se você estiver fora da faculdade há algum tempo, é altamente aconselhável rever os fundamentos de computação. Eu prefiro revisar enquanto pratico. Eu revejo minhas anotações da faculdade e reviso os vários algoritmos enquanto trabalho nos problemas de algoritmos do LeetCode e do Cracking the Coding Interview.

Se você estiver interessado em como as estruturas de dados são implementadas, confira Lago, um repositório do GitHub contendo estruturas de dados e exemplos de Algoritmos em JavaScript.

lago
GitHub - yangshun/lago: 📕 Biblioteca de Algoritmos e Estruturas de Dados em TypeScript

Domínio através da prática

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

Pratique e resolva questões de algoritmos na linguagem de sua escolha. Embora o Cracking the Coding Interview seja um bom recurso, prefiro resolver problemas digitando o código, deixando-o rodar e obtendo feedback instantâneo.

Há vários juízes on-line, tais como o LeetCode, o HackerRank e o CodeForces para você praticar perguntas on-line e se acostumar a linguagem. Pela minha experiência, as perguntas do LeetCode são mais parecidas com as perguntas feitas em entrevistas. As perguntas do HackerRank e do CodeForces são mais parecidas com as perguntas da programação competitiva.

Se você praticar perguntas suficientes do LeetCode, há uma boa chance de que você veja ou complete uma das suas perguntas reais de entrevista (ou alguma variante dela).

Aprenda e compreenda as complexidades de tempo e de espaço das operações comuns na sua linguagem escolhida. Para Python, esta página virá a calhar. Aprenda também sobre o algoritmo de ordenação subjacente a ser usado na função sort() da linguagem e as suas complexidades de tempo e de espaço (em Python é o TimSort, que é um híbrido).

Depois de completar uma pergunta do LeetCode, normalmente acrescento as complexidades de tempo e espaço do código escrito como comentários acima do corpo da função. Utilizo os comentários para me lembrar de comunicar a análise do algoritmo após ter completado a implementação.

Leia sobre o estilo de programação recomendado para a sua linguagem e mantenha-se fiel a ele. Se escolher Python, consulte o Guia de Estilo PEP 8 (em inglês). Se escolher Java, consulte o Guia de Estilo de Java do Google (em inglês).

Aprenda e esteja familiarizado com as armadilhas e problemas comuns da linguagem. Se os apontar durante a entrevista e se evitar cair neles, ganhará pontos a mais e impressionará o entrevistador, independentemente de o entrevistador estar familiarizado com a linguagem ou não.

Obtenha uma ampla exposição a questões de vários tópicos. Na segunda metade do artigo, menciono tópicos de algoritmos e as questões úteis para a prática de cada tópico. Faça cerca de 100 a 200 perguntas do LeetCode e você deverá se sair bem.

Se preferir cursos onde a aprendizagem seja mais estruturada, aqui ficam algumas recomendações. De modo algum é obrigatório fazer cursos on-line para passar em entrevistas.

  • O AlgoMonster visa ajudá-lo a passar na entrevista técnica no mais curto espaço de tempo possível. Criado por engenheiros do Google, o AlgoMonster utiliza uma abordagem baseada em dados para ensinar os padrões de perguntas-chave mais úteis e tem conteúdos para ajudar a rever rapidamente algoritmos e estruturas de dados básicos. O melhor de tudo é que o AlgoMonster não é baseado em assinaturas – pague uma taxa única e obtenha acesso vitalício.
  • Grokking the Coding Interview: Patterns for Coding Questions, da Educative, expande as questões práticas recomendadas neste artigo, mas aborda a prática a partir de uma perspectiva de padrão de perguntas, que é uma abordagem com a qual também concordo para a aprendizagem e com a qual me habituei pessoalmente a melhorar na programação de entrevistas. O curso permite praticar perguntas selecionadas em Java, Python, C++, JavaScript e também fornece exemplos de soluções nessas linguagens. Aprenda e compreenda os padrões em vez de memorizar as respostas.

Logicamente, pratique, pratique e pratique um pouco mais!

Fases de uma entrevista de programação

Parabéns! Você está pronto para pôr as suas capacidades em prática! Em uma entrevista de programação, será feita uma pergunta técnica pelo entrevistador. Você escreverá o código em tempo real, em um editor colaborativo (tela do telefone) ou em um quadro branco (no local) e terá 30 a 45 minutos para resolver o problema. É aqui que a verdadeira diversão começa!

O seu entrevistador procurará ver se você preenche os requisitos para o cargo. Cabe a você mostrar para ele que possui as competências necessárias. Inicialmente, pode parecer estranho falar enquanto programa, já que a maioria dos programadores não tem o hábito de explicar em voz alta os seus pensamentos enquanto escrevem o código.

No entanto, é difícil para o entrevistador saber o que você está pensando simplesmente olhando para o seu código. Se comunicar a sua abordagem ao entrevistador mesmo antes de começar a programar, pode validar a sua abordagem com eles. Dessa forma, os dois podem chegar a acordo sobre uma abordagem aceitável.

Preparação para uma entrevista remota

Para telas de telefones e entrevistas remotas, tenha à disposição um papel e uma caneta ou lápis para fazer anotações ou diagramas. Se for feita uma pergunta sobre árvores e gráficos, geralmente ajuda desenhar exemplos da estrutura de dados.

Use fones de ouvido. Certifique-se de que se encontra em um ambiente calmo. Não queira segurar o telefone com uma mão e escrever com a outra. Tente evitar o uso de alto-falantes. Se o feedback for ruim, a comunicação fica mais difícil. Ter que repetir apenas resultará em perda de tempo valioso.

O que fazer quando você receber a pergunta

Muitos candidatos começam a programar assim que ouvem a pergunta. Isso geralmente é um grande erro. Primeiro, reserve um momento e repita a pergunta para o entrevistador para ter certeza de que você entendeu a pergunta. Se você tiver entendido mal a pergunta, o entrevistador poderá esclarecê-la.

Sempre busque esclarecimento sobre a questão ao ouvi-la, mesmo que você ache que é clara. Você pode descobrir que escapou alguma coisa. Isso também permite ao entrevistador saber que você está atento aos detalhes.

Considere fazer as seguintes perguntas:

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

Depois de ter esclarecido suficientemente o escopo e a intenção do problema, explique ao entrevistador sua abordagem de alto nível, mesmo que seja uma solução ingênua. Se você estiver preso, considere várias abordagens e explique em voz alta porque elas podem ou não funcionar. Às vezes, seu entrevistador pode deixar passar dicas que o levarão no caminho certo.

Comece com uma abordagem de força bruta. Comunique-a ao entrevistador. Explique as complexidades de tempo e espaço e esclareça o motivo de tentar a força bruta é ruim. É improvável que a abordagem de força bruta seja aquela que você utilizará em programação. Neste ponto, o entrevistador normalmente fará a temida pergunta "Podemos fazer melhor?". Isso significa que estão procurando por uma abordagem mais otimizada.

Essa é geralmente a parte mais difícil da entrevista. Em geral, procure por trabalhos repetidos e tente otimizá-los, potencialmente armazenando o resultado calculado em algum lugar. Consulte-o mais tarde, em vez de calculá-lo novamente. A seguir, forneço algumas dicas para abordar detalhadamente questões específicas do tópico.

Só comece a programar depois que você e seu entrevistador tiverem concordado em uma abordagem e que você tenha recebido um sinal positivo para seguir em frente.

Começando a programar

Use um bom estilo para escrever seu código. Ler código escrito por outros geralmente não é uma tarefa agradável. Ler código horrivelmente formatado escrito por outros é ainda pior. Seu objetivo é fazer seu entrevistador entender seu código para que possa avaliar rapidamente se seu código faz o que se supõe que faça e se resolve um determinado problema.

Use nomes de variáveis claros e evite nomes que sejam letras únicas, a menos que sejam para a iteração. Entretanto, se você estiver programando em um quadro branco, evite usar nomes extensos 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, textualmente, para o entrevistador o código que você está produzindo. Fale sobre a seção do código que você está implementando atualmente em nível superior. Explique por que ele é escrito assim e o que está tentando alcançar.

Ao copiar e colar em código, considere se é necessário. Às vezes, é; às vezes, não é. Se você se encontrar copiando e colando um grande pedaço de código abrangendo várias linhas, provavelmente é um indicador de que você pode reestruturar o código, extraindo essas linhas em uma função. Se for apenas uma única linha que você copiou, geralmente está bem.

Entretanto, lembre-se de alterar as respectivas variáveis em sua linha de código copiada, onde for relevante. Erros de cópia e colagem são uma fonte comum de bugs, mesmo na programação do dia a dia!

Após a programação

Depois de terminar de programar, não anuncie imediatamente ao entrevistador que você está pronto. Na maioria dos casos, seu código geralmente não está perfeito. Ele pode conter bugs ou erros de sintaxe. O que você precisa fazer é revisar seu código.

Primeiro, olhe seu código do início ao fim. Olhe para ele como se fosse escrito por outra pessoa, como se você o estivesse vendo pela primeira vez e tentando detectar erros nele. Isso é exatamente o que seu entrevistador estará fazendo. Revise e corrija quaisquer problemas que você possa encontrar.

Em seguida, apresente pequenos casos de teste e execute o código passo a passo (não seu algoritmo) com essas amostras de entrada.

Os entrevistadores gostam quando você lê suas mentes. O que eles costumam fazer depois que você termina de programar é fazer você escrever testes. É uma grande vantagem se você escrever testes para seu código antes mesmo que eles o peçam para fazer isso. Você deve estar emulando um depurador ao passar por seu código. Anote ou diga a eles os valores de certas variáveis enquanto você percorre com o entrevistador as 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 programação de qualidade. Além disso, procure lugares onde você possa fazer uma avaliação de curto-circuito.

Por fim, forneça as complexidades de tempo e espaço de seu código e explique por que ele é assim. Você pode fazer anotações em partes do seu código com suas várias complexidades de tempo e espaço para demonstrar sua compreensão do código. Você pode até mesmo fornecer as APIs de sua linguagem de programação escolhida. Explique quaisquer trade-offs na sua abordagem atual em comparação com abordagens alternativas, possivelmente em termos de tempo e espaço.

Se seu entrevistador estiver satisfeito com a solução, a entrevista geralmente termina aqui. Também é comum que o entrevistador faça perguntas de extensão, como, por exemplo, sobre como você lidaria com o problema se toda a entrada for muito grande para caber na memória, ou se a entrada chegar como uma stream. Essa é uma pergunta posterior comum no Google, onde eles se preocupam muito com a escala.

A resposta é geralmente uma abordagem de dividir e conquistar – realizar o processamento distribuído dos dados e somente ler certas partes da entrada do disco para a memória, gravar a saída de volta para o disco e combiná-los mais tarde.

Prática com entrevistas simuladas

Os passos mencionados acima podem ser repetidamente ensaiados até que você os tenha interiorizado completamente e eles se tornem normais para você. Uma boa maneira de praticar é fazer uma parceria com um amigo e revezar nas entrevistas um com o outro.

Um grande recurso para a preparação de entrevistas de programação é o interview.io. Essa plataforma oferece entrevistas práticas 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 dar feedback um ao outro com o objetivo de ajudar um ao outro a melhorar.

Sair-se bem nas entrevistas simuladas desbloqueará a página de empregos para os candidatos e permitirá que eles marquem entrevistas (também anônimas) com empresas de ponta, como Uber, Lyft, Quora, Asana, entre outras. Para aqueles que são novatos nas entrevistas de programação, uma entrevista demonstrativa pode ser visualizada neste site. Observe que o site exige que os usuários façam o registro.

Já usei a interviewing.io, tanto como entrevistador quanto como entrevistado. A experiência foi ótima. Aline Lerner, a CEO e cofundadora do interviewing.io, e sua equipe são apaixonados por revolucionar o processo de entrevistas de programação e por ajudar os candidatos a melhorar suas habilidades de entrevista.

Ela também publicou uma série de artigos relacionados às entrevistas de programação no blog interviewing.io. Recomendo inscrever-se o mais cedo possível no interviewing.io, mesmo que ele esteja em estágio beta, para aumentar a probabilidade de receber um convite.

image-58

Outra plataforma que permite praticar entrevistas de programação é a Pramp. Enquanto a interview.io combina potenciais candidatos a empregos com entrevistadores experientes em programação, a Pramp adota uma abordagem diferente. A Pramp combina você com outro colega que também é um candidato a emprego. Os dois se revezam assumindo as funções de entrevistador e entrevistado. A Pramp também prepara perguntas e fornece soluções e dicas para orientar o entrevistado.

Vá em frente e conquiste

Depois de fazer uma quantidade razoável de perguntas no LeetCode e de ter prática suficiente em entrevistas simuladas, vá em frente e ponha à prova suas novas habilidades de entrevista.

Inscreva-se em suas empresas favoritas ou, melhor ainda, obtenha indicações de seus amigos que trabalham para essas empresas. As indicações tendem a ser notadas mais cedo e a ter uma taxa de resposta mais rápida do que se você se candidatar sem uma indicação. Boa sorte!

Dicas práticas para questões de programação

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 programação. Muitas questões de algoritmos 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 na entrevista. Para cada tópico, há também uma lista de perguntas recomendadas, que é valiosa para dominar os conceitos centrais. Algumas das perguntas só estão disponíveis com uma assinatura paga do LeetCode, que, na minha opinião, vale o dinheiro se você conseguir um emprego.

Dicas gerais

Valide sempre a entrada em primeiro lugar. Verifique se as entradas são inválidas, vazias, negativas ou diferentes. Nunca assuma que são dados parâmetros válidos. Como alternativa, esclareça com o entrevistador se você pode assumir que a entrada é válida (geralmente, sim), o que pode poupar seu tempo de escrever o código que faz a validação da entrada.

Há algum requerimento de complexidade de tempo e espaço ou restrições?

Verificar a existência de erros off-by-one (texto em inglês).

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

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

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

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

  • Escreva funções puras com a maior frequência possível.
  • Use funções puras porque são mais fáceis de pensar a respeito e podem ajudar a reduzir erros em sua implementação.
  • Evite a alteração dos parâmetros passados para sua função, especialmente se eles forem passados por referência, a menos que você esteja seguro do que está fazendo.
  • Atinja um equilíbrio entre precisão e eficiência. Use a quantidade certa de código funcional e imperativo, quando apropriado. A programação funcional é normalmente 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 com objetos existentes.
  • Evite confiar em variáveis globais mutáveis. As variáveis globais introduzem o estado.
  • Certifique-se de que você não mudará acidentalmente as variáveis globais, especialmente se você tiver que confiar nelas.

Geralmente, para melhorar a velocidade de um programa, podemos escolher entre usar uma estrutura de dados ou um algoritmo apropriado ou usar mais memória. É uma troca clássica 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 de tempo para suas várias operações.

As estruturas de dados podem ser aumentadas para alcançar uma complexidade de tempo eficiente através de diferentes operações. Por exemplo, um HashMap pode ser usado juntamente com uma lista duplamente vinculada para alcançar a complexidade de tempo O(1) tanto para a operação de get como para a de put em um cache LRU (em inglês, onde LRU significa "menos recentemente usado").

Os HashMaps são provavelmente a estrutura de dados mais comumente usada para questões de algoritmos. Se você estiver preso a uma pergunta, seu último recurso pode ser enumerar através das possíveis estruturas de dados (felizmente não existem tantas) e considerar se cada uma delas pode ser aplicada ao problema. Isto tem funcionado para mim às vezes.

Se você estiver fazendo coisas apressadamente em seu código, declare isso em voz alta ao seu entrevistador e explique a ele o que você faria fora de um ambiente de entrevista (sem restrições de tempo). Por exemplo, explique que você escreveria uma regex para fazer o parsing de uma string em vez de usar split, que não cobre todos os casos.

Sequência

Observações

Arrays e strings são considerados sequenciais (uma string é uma sequência de caracteres). Há dicas para lidar tanto com arrays quanto com strings que serão abordadas aqui.

Há valores duplicados na sequência? Eles afetariam a resposta?

Verifique a sequência fora dos limites.

Esteja atento ao fatiamento (do inglês, slicing) ou à concatenação de sequências em seu código. Tipicamente, o fatiamento e as sequências concatenadas requerem tempo O(n). Use índices de início e fim para demarcar um subarray ou uma substring sempre que possível.

Às vezes, você percorre a sequência a partir do lado direito em vez do lado esquerdo.

Dominar a técnica de janela deslizante (texto em inglês) que se aplica a muitos problemas de substring ou subarray.

Quando são dadas duas sequências para processar, é comum ter um índice por sequência a ser percorrida. Por exemplo, usamos a mesma abordagem para unir dois arrays ordenados.

Casos limítrofes

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

Array

Observações

O array é ordenado ou parcialmente ordenado? Se for, alguma forma de busca binária deve ser possível. Isto geralmente significa que o entrevistador está procurando uma solução que seja mais rápida do que o O(n).

Você pode ordenar o array? Às vezes, ordenar o array primeiro pode simplificar significativamente o problema. Certifique-se de que a ordem dos elementos do array não precisa ser preservada antes de tentar ordená-lo.

Para perguntas onde a soma ou a multiplicação de um subarray está envolvida, a pré-computação usando hashing ou um prefixo, soma de sufixos ou produto pode ser útil.

Se você receber uma sequência e o entrevistador pedir espaço O(1), talvez seja possível usar o próprio array como uma tabela de hash. Por exemplo, se o array tiver valores apenas de 1 a N, onde N é o comprimento do array, deixe negativo o valor naquele índice (menos um) para indicar a presença daquele número.

Perguntas práticas (exemplos em inglês do LeetCode)

Binário

Observações

Às vezes, são feitas perguntas que envolvem representações binárias e operações bitwise. Você deve saber como converter um número de decimal para binário e vice-versa em sua linguagem de programação escolhida.

Alguns trechos úteis:

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

Casos limítrofes

  • Verificação de sobrefluxo/baixo fluxo
  • Números negativos

Perguntas práticas (exemplos em inglês do LeetCode)

Programação dinâmica

Observações

A Programação Dinâmica (DP) é normalmente usada para resolver problemas de otimização. Alaina Kafkes escreveu um artigo fantástico sobre a solução de problemas de DP. Você deve lê-lo.

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

Para otimizar o espaço, às vezes não é necessário armazenar a tabela de DP inteira na memória. Os dois últimos valores ou as duas últimas filas da matriz serão suficientes.

Perguntas práticas (exemplos em inglês do LeetCode)

Geometria

Observações

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

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.

Grafos

Links de estudo (textos em inglês)

Observações

Esteja familiarizado com as várias representações de grafos e algoritmos de pesquisa de grafos, bem como com suas complexidades de tempo e espaço.

Você pode receber uma lista de arestas e ser encarregado de construir seu próprio grafo a partir das arestas para realizar uma travessia. As representações de grafos comuns são:

  • Matriz adjacente
  • Lista adjacente
  • HashMap dos HashMaps

Algumas entradas parecem ser árvores, mas, na verdade, são grafos. Esclareça isto com seu entrevistador. Nesse caso, você terá que lidar com ciclos e manter um conjunto de nós visitados quando estiver percorrendo os grafos.

Algoritmos de busca de grafos

  • Comum: busca primeiramente em largura (BFS), busca primeiramente em profundidade (DFS)
  • Incomum: ordenação topológica, o algoritmo de Dijkstra
  • Raro: algoritmo Bellman-Ford, algoritmo Floyd-Warshall, algoritmo Prim e algoritmo Kruskal

Nas entrevistas de programação, os grafos são comumente representados como matrizes 2D, onde as células são os nós e cada célula pode percorrer até suas células adjacentes (para cima, para baixo, para a esquerda e para a direita). Portanto, é importante estar familiarizado com a travessia de uma matriz 2-D.

Ao atravessar recursivamente a matriz, certifique-se sempre de que sua próxima posição esteja dentro dos limites da matriz. Mais dicas para fazer a DFS em uma matriz podem ser encontradas aqui (em inglês). Um modelo simples para fazer a DFS em uma matriz é algo parecido com isto:

def traverse(matrix):
  rows, cols = len(matrix), len(matrix[0])
  visited = set()
  directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
  def dfs(i, j):
    if (i, j) in visited:
      return
    visited.add((i, j))
    # Traverse neighbors
    for direction in directions:
      next_i, next_j = i + direction[0], j + direction[1]
      if 0 <= next_i < rows and 0 <= next_j < cols: # Check boundary
        # Add any other checking here ^
        dfs(next_i, next_j)
  for i in range(rows):
    for j in range(cols):
      dfs(i, j)

Casos limítrofes

  • Grafo vazio
  • Grafo com um ou dois nós
  • Grafos desconjuntados
  • Grafos com ciclos

Perguntas práticas (exemplos em inglês do LeetCode)

Intervalo

Observações

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

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

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

Esclareça com o entrevistador se [1, 2] e [2, 3] são considerados intervalos sobrepostos, pois isso afeta a forma como você vai escrever suas verificações de igualdade.

Uma rotina comum para perguntas de intervalo é ordenar o conjunto de intervalos pelo valor inicial de cada intervalo.

Esteja familiarizado com escrever código para verificar se dois intervalos se sobrepõem e para unir dois intervalos sobrepostos:

def is_overlap(a, b):
  return a[0] < b[1] and b[0] < a[1]
  
def merge_overlapping_intervals(a, b):
  return [min(a[0], b[0]), max(a[1], b[1])]

Casos limítrofes

  • Intervalo único
  • Intervalos não sobrepostos
  • Um intervalo totalmente consumido dentro de outro intervalo
  • Intervalos em duplicata

Perguntas práticas (exemplos em inglês do LeetCode)

Lista vinculada

Observações

Como os arrays, listas vinculadas são usadas para representar dados sequenciais. O benefício das listas vinculadas é que a inserção e exclusão de código de qualquer parte da lista é O(1), enquanto, nos arrays, os elementos têm que ser mudados.

Adicionar um nó fictício na cabeça e/ou na cauda pode ajudar a lidar com muitos casos limítrofes onde as operações têm que ser realizadas na cabeça ou na cauda. A presença de nós fictícios garante que as operações nunca terão sido executadas na cabeça ou na cauda. Os nós fictícios removem a dor de cabeça de escrever verificações condicionais para lidar com indicações nulas. Certifique-se de removê-los ao final da operação.

Às vezes, os problemas de listas vinculadas podem ser resolvidos sem armazenamento adicional. Tente pegar ideias emprestadas para reverter um problema de lista vinculada.

Para exclusão em listas vinculadas, você pode modificar os valores dos nós ou alterar os ponteiros dos nós. Você pode precisar manter uma referência ao elemento anterior.

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

Os problemas de listas vinculadas compartilham semelhanças com problemas de array. Pense em como você resolveria um problema de array e o aplicaria a uma lista vinculada.

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

  • Obtendo o k-ésimo nó a partir do último nó: use dois ponteiros, onde um está k nós à frente do outro. Quando o nó à frente chega ao fim, o outro nó está k nós atrás.
  • Detectando ciclos: use dois ponteiros, onde um ponteiro aumenta duas vezes mais do que o outro. Se os dois ponteiros se encontrarem, significa que há um ciclo.
  • Obtendo o nó do meio: use dois ponteiros. Um ponteiro incrementa duas vezes mais que o outro. Quando o nó mais rápido chegar ao final da lista, o mais lento estará no meio.

Esteja familiarizado com as seguintes rotinas, pois muitas perguntas da lista vinculada fazem uso de uma ou mais destas rotinas em sua solução.

  • Contar o número de nós na lista vinculada
  • Reverter uma lista vinculada no local
  • Encontre o nó central da lista vinculada usando ponteiros rápidos ou lentos
  • Fazer a fusão (do inglês, merge) de duas listas juntas

Casos limítrofes

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

Perguntas práticas (exemplos em inglês do LeetCode)

Matemática

Observações

Se o código envolver divisão ou módulo, lembre-se de verificar a divisão ou o módulo em função do caso com 0 (zero).

Quando uma pergunta envolve "um múltiplo de um número", o módulo pode ser útil.

Verifique e administre overflow e underflow se estiver usando uma linguagem tipada como Java e C++. No mínimo, mencione que o overflow ou que o underflow é possível e pergunte se você precisa lidar com ele.

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 for para implementar um operador como potência, raiz quadrada ou divisão, e se for para ser mais rápido que O(n), a busca binária é geralmente a abordagem.

Algumas fórmulas comuns

  • Soma de 1 para N = (n+1) * n/2
  • Soma de progressões geométricas = 2⁰ + 2¹ + 2² + 2³ + … 2^n = 2^(n+1)-1
  • Permutações de N = N! / (N-K)!
  • Combinações de N = N! / (K! * (N-K)!)

Casos limítrofes

  • Divisão por 0
  • Overflow e underflow de números inteiros

Perguntas práticas (exemplos em inglês do LeetCode)

Matriz

Notas

Uma matriz é um array bidimensional. As questões envolvendo matrizes estão geralmente relacionadas à programação dinâmica ou à travessia do grafo.

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

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)
  • Muitos jogos baseados em grade podem ser modelados como uma matriz, como, por exemplo, o Jogo da Velha, Sudoku, palavras cruzadas, Ligue 4 e Batalha Naval. Não é raro ser solicitada a verificação da condição de vencedor do jogo. Para jogos como o Jogo da Velha, o Ligue 4 e as Palavras Cruzadas, a verificação tem que ser feita vertical e horizontalmente. Um truque é escrever o código para verificar a matriz para as células horizontais. Em seguida, transpor a matriz, reutilizando a lógica usada para verificação horizontal para verificar as células originalmente verticais (que agora são horizontais).
  • A transposição de uma matriz em Python é simples:
transposed_matrix = zip(*matrix)

Casos limítrofes

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

Perguntas práticas (exemplos em inglês do LeetCode)

Recursão

Observações

A recursividade é útil para a permutação, pois gera todas as combinações e perguntas baseadas em árvores. Você deve saber como gerar todas as permutações de uma sequência, bem como lidar com as duplicatas.

Lembre-se sempre de definir um caso base para que sua recorrência termine.

A recorrência utiliza implicitamente uma pilha. Assim, todas as abordagens recursivas podem ser reescritas iterativamente usando uma pilha.

Cuidado com os casos em que o nível de recorrência vai muito fundo e causa um transbordamento de pilha (o limite padrão em Python é 1000). Você pode receber pontos de bônus por apontar isso para o entrevistador.

A recursividade nunca terá complexidade espacial O(1) porque uma pilha está envolvida, a menos que haja uma otimização da chamada de cauda (TCO). Descubra se a linguagem escolhida dá suporte à TCO.

Perguntas práticas (exemplos em inglês do LeetCode)

String

Observações

Leia as dicas acima sobre sequências. Elas também se aplicam às strings.

Pergunte sobre o conjunto de caracteres de entrada e a distinção entre maiúsculas e minúsculas. Normalmente, os caracteres são limitados a caracteres latinos em letras minúsculas – por exemplo, de a até z.

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

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

As estruturas de dados comuns para a busca eficiente de strings são:

Algoritmos de strings comuns são:

  • Rabin Karp, que realiza buscas eficientes de substrings, utilizando um hash "rolante"
  • KMP, que realiza buscas eficientes de substrings

Caracteres não repetentes

Use uma máscara de 26 bits para indicar quais caracteres latinos em letras minúsculas estão dentro da string.

mask = 0
for c in set(word):
  mask |= (1 << (ord(c) - ord('a')))

Para determinar se duas strings têm caracteres em comum, execute & nas duas máscaras de bits. Se o resultado não for zero, mascara_a & mascara_b > 0 , então as duas strings têm caracteres em comum.

Anagrama

Um anagrama é um trocador 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. Em entrevistas, normalmente só nos preocupamos com palavras sem espaços nelas.

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

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

Palíndromo

Um palíndromo é uma palavra, frase, número ou outra sequência de caracteres que é lido do mesmo modo para trás e para frente, tais como "madam" ou "racecar".

Aqui estão maneiras de determinar se uma string é um palíndromo:

  • Reverta a string e ela deve ser igual a si mesma.
  • Ter 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 coincidir.

A ordem dos caracteres dentro da string importa, portanto, os HashMaps geralmente não são úteis.

Quando se trata de contar o número de palíndromos, um truque comum é ter dois ponteiros que se movem para fora e para longe do meio. Note que os palíndromos podem ter um comprimento par ou ímpar. Para cada posição de pivô central, é necessário verificá-la duas vezes: uma vez que inclua o caractere e outra sem o caractere.

  • Para as substrings, você pode terminar antecipadamente uma vez que não haja correspondência.
  • Para as subsequentes, use programação dinâmica, pois existem subproblemas sobrepostos. Confira esta pergunta (em inglês, no LeetCode).

Casos limítrofes

  • String vazia
  • String de um único caractere
  • Strings com apenas um caractere distinto

Perguntas práticas (exemplos em inglês do LeetCode)

Árvore

Links de estudo (em inglês)

Observações

Uma árvore é um grafo acíclico, não direcionado e conectado.

A recursividade é uma abordagem comum para as árvores. Quando você perceber que o problema da subárvore pode ser usado para resolver o problema inteiro, tente usar a recursividade.

Ao utilizar a recorrência, lembre-se sempre de verificar o caso base, geralmente onde o nó é nulo.

Quando você for solicitado a atravessar uma árvore por nível, use a busca em profundidade.

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

Se a questão envolver a soma dos 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 travessias de pré-ordem, dentro da ordem e pós-ordem recursivamente. Como extensão, desafie-se escrevendo-as iterativamente. Às vezes, os entrevistadores pedem aos candidatos a abordagem iterativa, especialmente se o candidato terminar de escrever a abordagem recursiva muito rapidamente.

Árvore binária

A travessia em ordem de uma árvore binária é insuficiente para serializar uma árvore de maneira única. Também é necessária a travessia pré-ordem ou pós-ordem.

Árvore de busca binária - Binary search tree (BST)

A travessia em ordem de uma BST dará a você todos os elementos em ordem.

Esteja muito familiarizado com as propriedades de uma BST. Valide se uma árvore binária é uma BST. Isso aparece com mais frequência do que o esperado.

Quando uma pergunta envolve uma BST, o entrevistador geralmente está procurando uma solução que funcione mais rápido que a O(n).

Casos limítrofes

  • Árvore vazia
  • Nó único
  • Dois nós
  • Árvore muito desbalanceada (como uma lista vinculada)

Perguntas práticas (exemplos em inglês do LeetCode)

Tries

Links de estudo (em inglês)

Observações

Tries são árvores especiais (árvores de prefixos) que tornam mais eficiente a busca e o armazenamento de strings. As tries têm muitas aplicações práticas, tais como a realização de buscas e o fornecimento de autocompletar. É útil conhecer essas aplicações comuns para que você possa identificar facilmente quando um problema pode ser resolvido de modo eficiente usando uma trie.

Às vezes, o pré-processamento de um dicionário de palavras (dado em uma lista) em uma trie melhorará a eficiência da busca por uma palavra de comprimento k, entre n palavras. A busca 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 add, remove e search.

Perguntas práticas (exemplos em inglês do LeetCode)

Heap

Links de estudo (em inglês)

Observações

Se você vir um k superior ou inferior mencionado na pergunta, geralmente, é um sinal de que uma heap pode ser usada para resolver o problema, como em K elementos mais frequentes.

Se você precisar dos k elementos superiores, use uma heap de tamanho k. Faça a iteração através de cada elemento, inserindo-o na heap. Sempre que o tamanho da heap exceder k, remova o elemento menor. Isso garantirá que você tenha os k elementos maiores.

Perguntas práticas (exemplos em inglês do LeetCode)

Conclusão

As entrevistas de programação são difíceis. Felizmente, no entanto, você pode melhorar para elas, estudando e praticando para elas e fazendo entrevistas simuladas.

Recapitulando: para se sair bem nas entrevistas de programação:

  1. Decida sobre uma linguagem de programação
  2. Estude fundamentos da Ciência da Computação
  3. Pratique a solução de questões de algoritmos
  4. Internalize o que se faz e o que não se faz nas entrevistas
  5. Pratique através de entrevistas técnicas simuladas
  6. Faça a entrevista com sucesso e consiga o emprego

Seguindo essas etapas, você melhorará suas habilidades em entrevistas de programação e estará um passo mais próximo (ou provavelmente mais) de conseguir o emprego dos seus sonhos.

Sucesso para você!

O conteúdo deste artigo também pode ser encontrado aqui. Atualizações futuras serão publicadas lá. Pedidos de sugestões e correções são bem-vindos.

Se você gostou deste artigo, compartilhe-o com seus amigos!

Você pode seguir o autor no GitHub e no Twitter.