Boas-vindas ao curso de Code Interview (entrevista de código). Meu nome é Jefferson Silva e vou te acompanhar durante este curso.
Audiodescrição: Eu sou um homem branco, com barba e cabelos escuros; uso óculos e estou usando uma camiseta preta com o nome da Alura.
A primeira informação que queremos apresentar é para quem este curso se destina. Este curso de Code Interview é para qualquer pessoa que esteja planejando se candidatar a vagas na área de tecnologia.
Sabemos que muitos processos seletivos envolvem uma etapa de entrevista de código, que conheceremos em profundidade ao longo deste curso.
Nosso objetivo é explicar como funciona esse tipo de entrevista, quais estratégias você pode utilizar para enfrentar os problemas que surgem, como criar um repertório de soluções e estruturas que podem ser empregadas para encontrar possíveis respostas e dialogar com a pessoa entrevistadora.
Ao longo do curso, apresentaremos tudo de forma visual, para que você veja, na prática, como os problemas são resolvidos e como essas estruturas e técnicas ajudam nesse processo.
O que você precisa saber para acompanhar este curso? A ideia principal é que você conheça uma linguagem de programação.
Não é necessário conhecimento aprofundado em framework (estrutura) ou similares, pois os problemas que resolveremos são fundamentais do ponto de vista dos recursos da linguagem. Se você já conhece o básico de Python, JavaScript, Java ou qualquer outra linguagem, tudo o que ensinarmos aqui continuará válido.
Neste curso, utilizaremos a linguagem Python, mas, se você conhece qualquer outra linguagem, ficará claro o que pode ser utilizado para substituir, por exemplo, uma estrutura que estamos empregando, alguma instrução específica ou a própria sintaxe. Isso se torna ainda mais evidente para quem já possui familiaridade com a linguagem que utiliza no dia a dia.
Outra informação importante: o curso foi estruturado em etapas. Começaremos com um panorama do repertório de ferramentas e técnicas e, na parte final do curso, traremos simulações de entrevistas de código. Nós vamos resolver vários problemas, simulando um ambiente próximo ao que encontramos em entrevistas reais.
Essa etapa será muito proveitosa. Mesmo que você nunca tenha participado de uma entrevista desse tipo, terá uma ideia de como funciona e do que esperar. Incluiremos momentos com obstáculos e situações que não saem como planejamos, e veremos como lidar com isso na prática.
Dito isso, vamos partir para nossa primeira aula e começar a aprender mais sobre entrevistas de código.
Neste curso, vamos entender o que é uma entrevista de código e em que contexto ela ocorre.
Geralmente, a entrevista de código aparece como parte do processo seletivo. Ao aplicarmos para uma vaga em uma empresa de desenvolvimento de software, é comum que uma das etapas envolva avaliar como resolvemos problemas envolvendo código.
O que a pessoa entrevistadora busca nesse tipo de processo? A ideia é apresentar um problema, geralmente bem definido, porém com algumas possíveis lacunas — isto é, alguns pontos em aberto que precisamos explorar em conversa. O objetivo principal é observar nosso processo de resolução de problemas: como exploramos o enunciado, como verificamos casos de teste, como consideramos diferentes soluções de acordo com as restrições fornecidas no momento, como justificamos a correção do algoritmo, como validamos o resultado final e como respondemos a imprevistos. Pode ocorrer um bug (erro) no meio do caminho, ou a pessoa entrevistadora pode trazer novas informações ou restrições que mudam o rumo do que estamos fazendo.
De modo geral, a entrevista segue um processo que podemos simplificar em quatro etapas:
Vamos explorar o que deve constar em cada uma dessas etapas para conduzirmos uma entrevista bem-sucedida.
Já estamos com este slide (apresentação) preparado, no qual vemos um processo simplificado em quatro etapas.
Agora, vamos detalhar cada um desses passos e entender o que há em cada um deles.
O objetivo é confirmar que vamos resolver o que está sendo pedido. Geralmente, há um enunciado, e sabemos que enunciados podem ser confusos, dependendo de como foram escritos.
A primeira ação é ler o enunciado e reformulá-lo com nossas próprias palavras. É uma boa prática: após lermos o problema, dizemos algo como “Estamos entendendo que o que precisamos fazer é isso; confere?”. A pessoa entrevistadora confirmará se estamos no caminho certo.
Também precisamos distinguir o que é requisito e o que é restrição:
Além disso, antes de começarmos a elaborar a solução, é útil pensar em alguns exemplos. No caso de somar números de uma lista, por exemplo, podemos montar um conjunto de entrada na ferramenta utilizada, somar os números e observar estratégias possíveis para obter a resposta esperada. Esse passo é essencial para começarmos a visualizar que tipos de solução podem funcionar.
No planejamento, já entendemos o problema e buscamos responder: que tipo de solução podemos implementar?
Aqui entram as escolhas de estruturas de dados, abordagens e técnicas, sempre em alto nível — ainda sem detalhar em código. A ideia é descrever, com poucas palavras, a estratégia a ser usada. Por exemplo: “Para resolver este problema, vamos ordenar a primeira lista de entrada e, em seguida, percorrer os índices de 2 em 2 realizando a operação X.”
Com esse plano em alto nível, já conseguimos estimar tempo e espaço. Quando formos falar de complexidade, isso ficará ainda mais claro. Mesmo assim, já é possível ter uma noção de quantas operações o algoritmo realiza, quanto de memória utiliza e se atende às restrições definidas. Isso é muito importante, especialmente porque já fizemos o trabalho de entendimento do que podemos ou não fazer.
Também é valioso identificar de imediato possíveis gargalos. Por exemplo: “Esta solução é a mais simples no momento e é a que tentaremos implementar, mas percebemos que ela é quadrática; talvez não seja a melhor opção, pois repete determinado trabalho.” Uma resposta assim mostra que estamos olhando à frente e tomando decisões conscientes, alinhadas com as informações disponíveis — algo muito positivo em uma entrevista de código.
Chegamos à etapa de implementação, que pode causar certo receio. Em entrevistas de código, geralmente trabalhamos em um ambiente diferente do habitual, possivelmente da própria empresa ou de uma plataforma padronizada fornecida por outra organização, com poucos recursos: sem bibliotecas externas, sem preenchimento automático (autocomplete) em muitos casos. Mesmo quando esse recurso existe, não devemos depender dele.
Essa limitação gera pressão, que podemos mitigar com treino. É importante nos prepararmos previamente para que a falta de recursos não prejudique nosso desempenho durante a entrevista.
O que acontece no momento da implementação?
Em geral, podemos escolher entre algumas linguagens. Devemos optar por aquela com a qual temos mais familiaridade, o que ajuda bastante. O objetivo é transformar o plano de alto nível em código.
Ao digitar o código, não precisamos narrar cada instrução para a pessoa entrevistadora (por exemplo: “declarando uma variável”, “incrementando i”, “decrementando j”), pois isso não agrega. É mais relevante explicitar as decisões e o raciocínio: por exemplo, “utilizamos um dicionário para armazenar as frequências dos caracteres desta palavra”. Mesmo que estejamos escrevendo poucas linhas, devemos comunicar a finalidade delas e o objetivo que buscamos alcançar. Isso é mais importante do que narrar o código, pois o foco é a nossa linha de pensamento.
Se identificarmos um problema não previsto durante a implementação em relação ao que foi planejado, é adequado pausar e retomar o raciocínio em voz alta. Por exemplo, se a complexidade estimada muda de n para n ao quadrado, precisamos reavaliar essa parte do código. Esse procedimento traz a pessoa entrevistadora para a conversa. Podemos fazer e receber perguntas e utilizar informações adicionais. A entrevista é um diálogo; se não fosse, seria apenas uma plataforma automatizada em que digitamos, submetemos e recebemos um resultado.
Devemos aproveitar a presença da pessoa entrevistadora para exercitar comunicação, capacidade analítica e resolução de problemas, tornando explícito nosso processo. Não devemos nos assustar nem interromper o fluxo: é uma situação natural, comum no dia a dia, e uma oportunidade para evidenciar nossas competências.
Vamos em frente.
Última etapa: testes. Após finalizar o código, é provável que tenhamos apenas o caso de teste inicial planejado (às vezes fornecido pelo enunciado, às vezes o primeiro exemplo que idealizamos). Com o código pronto, torna-se mais simples gerar diversos casos de teste para validar todas as restrições definidas e verificar se o sistema atende aos requisitos. Para cada caso que conseguirmos elaborar e para o qual houver tempo, vale inserir o teste e verificar se o código continua funcionando.
O que é importante testar nesse momento?
Esses casos aparecem com frequência e podem ser reaproveitados em problemas diferentes. Eles nos dão um norte sobre que tipo de teste executar em entrevistas.
Outro cenário possível é rodarmos os testes e percebermos que alguns não passam. Isso é um bom sinal para a pessoa entrevistadora, pois evidencia um processo completo: começamos com a solução, fizemos o planejamento, implementamos e testamos. Ao chegar à etapa de testes, buscamos certificar que o que implementamos funciona. Pode ser que a ideia esteja correta, mas houve um deslize na implementação; ao testar, garantimos que o que estamos entregando realmente corresponde à solução planejada.
Com isso, concluímos a entrevista. A pessoa entrevistadora pode encerrar a etapa dizendo que está ótimo e seguir com o processo, ou pode propor um follow up (continuação) da entrevista. Por exemplo: “A solução funciona, mas agora vamos supor que exista uma restrição adicional de memória e de tempo. O que faríamos com a solução agora?” Nesse caso, retornamos ao início do ciclo: entender claramente as novas restrições, planejar novamente, avaliar se é preciso mudar a solução e o que é possível reaproveitar, verificar a complexidade do novo plano, implementar e testar outra vez. Repetimos quantas vezes forem necessárias até encerrar o processo.
Geralmente, essas entrevistas levam de 30 a 50 minutos, aproximadamente uma hora. É para ser um processo relativamente rápido. Como vimos, a ideia não é apenas digitar código, mas tornar claro o processo: se o raciocínio fica evidente rapidamente e a pessoa entrevistadora percebe nosso conhecimento, a capacidade de lidar com o problema, de explicitar decisões e de nos comunicarmos bem, a entrevista já será muito bem-sucedida.
Em muitos casos, o foco não é apenas saber programar, e sim resolver problemas: definir quais estruturas de dados e técnicas vamos utilizar. Não se trata de decorar problemas já resolvidos. Embora utilizemos exercícios comuns nesse tipo de entrevista, o objetivo não é memorizar soluções. Se chegarmos com uma solução pronta, isso não será bem visto nesse contexto. O objetivo é explicar como chegamos à solução: quais foram os fundamentos e o raciocínio que nos conduziram ao resultado final apresentado.
Concluímos o processo de como funciona uma entrevista de código. Agora, vamos discutir como justificar que um algoritmo está correto e como medir a complexidade de tempo e de espaço de uma solução.
Até mais.
Agora nós já entendemos o processo de entrevista de código e, nas etapas do processo de entrevista, vimos que existe a etapa de planejamento, na qual escolhemos a solução que vamos implementar e precisamos identificar qual é a mais adequada para o problema que estamos resolvendo.
Ao definir a solução mais adequada, precisamos nos atentar a três aspectos:
Vamos discutir esses pontos ao longo desta aula.
Para facilitar o processo, vamos utilizar uma ferramenta de visualização com uma lista de números: 3, 1, 2 e 5. A primeira tarefa é pensar em um algoritmo para somar todos os números dessa lista.
Para começar, vamos representar essa lista e inicializar o acumulador de soma:
nums = [3, 1, 2, 5]
soma = 0
Se pensarmos em um algoritmo simples, teremos um contador que vamos chamar de soma. Em seguida, teremos um laço que percorre todo o alcance desse array (vetor), isto é, dessa lista que temos. Vamos obter o comprimento da lista e iterar do índice 0 até o final da lista. Para cada elemento, vamos considerar o elemento atual, que é o número no índice i. Para cada um desses elementos, queremos pegar esse elemento atual e adicioná-lo ao contador soma.
Mantendo soma inicializado, adicionamos o laço que percorre todos os índices:
soma = 0
for i in range(len(nums)):
Vamos obter o comprimento da lista e iterar do índice 0 até o final da lista. Para cada elemento, vamos considerar o elemento atual, que é o número no índice i.
Dentro do laço, capturamos o elemento atual:
for i in range(len(nums)):
atual = nums[i]
Para cada um desses elementos, queremos pegar esse elemento atual e adicioná-lo ao contador soma.
Vamos atualizar soma = soma + elementoAtual.
Agora inserimos a atualização do acumulador dentro do laço:
for i in range(len(nums)):
atual = nums[i]
soma = soma + atual
Vamos observar o que acontece quando executamos esse raciocínio passo a passo.
Temos a lista inicial e a variável soma, que começa em 0. Vamos destacá-la. Iniciamos o laço com o contador i valendo 0. Vamos explicitar também o elemento atual que estamos observando, posicionando-o perto de soma, e manter um cursor apontando para a posição do array (vetor) que estamos olhando naquele momento.
Inicialmente, o valor observado é 3, na posição 0 (índice 0). Vamos somar esse valor ao acumulador soma.
Repetimos o procedimento: incrementamos o contador i e vamos para o índice 1. O elemento atual agora vale 1. Adicionamos esse valor à variável soma, que passa a ser 4.
Incrementamos i novamente, vamos para o índice 2, que aponta para o elemento 2. O elemento atual é 2 e somamos novamente ao nosso acumulador soma.
Passamos a ter soma igual a 6 e repetimos o último passo do algoritmo com o próximo elemento.
Ao final, obtemos o resultado 11.
Intuitivamente, sabemos que esse algoritmo funciona, mas como justificamos a sua correção para outra pessoa? Como afirmamos que o algoritmo é correto?
Uma justificativa possível é a seguinte: imaginemos que estamos olhando para a posição 0 desse array (vetor). Nesse momento, observamos que o elemento vale 3. Pegamos esse 3 e o adicionamos ao contador que guarda a soma. Essa soma inicialmente era 0 e, após o primeiro passo, sabemos que soma vale exatamente a soma de todos os elementos até a posição 0. Isso é verificável porque há um único elemento. Se o array (vetor) tivesse um único elemento, a soma seria exatamente o valor desse elemento. Até aqui, está correto.
Agora, realizamos o passo de indução. Adicionamos mais um elemento, que é o que ocorre quando incrementamos o contador i: avançamos um passo. Ao avançar um passo, temos a soma acumulada até aquele momento e um novo elemento que entra na solução. Pegamos esse novo elemento e somamos ao valor acumulado até então. Assim, garantimos que, da posição 0 até a 1, temos a soma de todos os elementos até aquela posição. Se conseguimos provar matematicamente que o passo inicial funciona e que o incremento (isto é, ao inserir um novo elemento) mantém a propriedade de que soma guarda a soma de todos os elementos até a posição atual, então temos uma prova válida. Consequentemente, ao chegarmos ao final do array (vetor), teremos passado por esse procedimento para todos os elementos e, portanto, a soma final está correta.
Trata-se de um processo matemático e também intuitivo: percorremos todos os elementos do array (vetor) e somamos seus valores em um acumulador. Conseguimos garantir que somamos todos os elementos e que passamos uma única vez por cada um deles. Podemos, então, afirmar que esse algoritmo é correto do ponto de vista de corretude.
Como avaliamos agora quantas operações realizamos para chegar a esse resultado?
Se olharmos novamente para a simulação, verificamos a posição 0 uma vez, a posição 1 uma vez, a posição 2 uma vez e a posição 3 uma vez. Fizemos quatro verificações e somamos os quatro números do array (vetor). Nesse caso, o número de operações depende do tamanho da lista, isto é, da quantidade de números que ela contém. Para quatro elementos, tivemos quatro operações; se o array (vetor) tivesse oito posições, teríamos oito operações, e assim por diante.
Quando falamos de complexidade em computação, utilizamos a notação chamada de Big O (Grande O), por meio da qual buscamos construir uma representação (como um gráfico) do comportamento do crescimento do número de operações do algoritmo em relação ao tamanho da entrada, representado por N.
Vamos tomar um exemplo para clareza. Consideremos um gráfico no qual traçamos uma reta que representa essa relação. No eixo x, colocamos o número de elementos do array (vetor), isto é, da entrada. No eixo y, colocamos o tempo ou o número de operações realizadas. Esse gráfico corresponde ao que observamos: quando temos quatro elementos, a curva (reta) indica quatro operações realizadas.
Este é o eixo y.
Ele é proporcional à quantidade de elementos.
Conforme aumentamos o número de elementos, o número de operações cresce proporcionalmente, de forma linear, como uma reta.
É esse o comportamento que observamos.
Doze elementos, doze operações.
Como representamos isso na anotação Big O (grande O)?
É justamente O(n) que colocamos no final.
Vamos posicionar essa anotação ao lado para ampliar a visualização.
Deslocamos um pouco para a lateral.
Escrevemos assim: O(n).
Para fixar a notação de tempo linear, adicionamos:
O(n)
É como se disséssemos que esse algoritmo, no pior caso, leva um tempo proporcional à quantidade de elementos que temos no nosso array (vetor).
Por que falamos em pior caso?
Haverá momentos em que o algoritmo, dependendo da entrada, fará mais ou menos operações.
Mas, quando falamos em notação de Big O (grande O), buscamos uma garantia.
Queremos saber, por exemplo, se não tivermos sorte — imaginemos que o algoritmo não tenha a sorte de encontrar a solução logo no início do array — qual deve ser a nossa expectativa?
Quantas operações, no máximo, esse algoritmo pode realizar?
Esse é o O(n).
Consideramos a pior expectativa possível.
Nesse caso, precisamos passar por todos os elementos do nosso array.
Isso determina qual é a ordem de crescimento em número de operações.
Vimos a primeira operação: percorrer um array passando uma vez por cada elemento.
A ideia aqui é guardar a intuição.
Não precisamos decorar as funções.
Veremos isso muitas vezes durante o curso.
Também veremos outras funções que entram na notação de Big O (grande O), comuns e recorrentes, para compararmos soluções diferentes.
Por exemplo, vamos considerar agora um array um pouco diferente: [1, 2, 1, 5].
Vamos utilizá-lo como novo tipo de lista.
Para acompanhar visualmente o novo cenário, podemos representar a lista:
nums = [1, 2, 1, 5]
A tarefa é a seguinte:
Precisamos saber quantos pares de elementos repetidos existem dentro desse array.
Por exemplo, o 1 aparece duas vezes; há um par de números 1.
Queremos contar quantos pares assim existem.
Será que existe um par 2, 2?
Um par 5, 5?
E assim por diante.
Precisamos bolar uma solução.
Uma solução direta e comum para esse tipo de problema é a seguinte:
Pegamos o primeiro elemento (índice 0) e comparamos com todos os outros.
Comparamos o índice 0 com os índices 1, 2 e 3, como se usássemos dois cursores.
Depois repetimos o processo, agora comparando o índice 1 com os demais elementos à frente: índice 1 com 2, índice 1 com 3, e assim por diante.
Até onde vamos?
Deslocamos o cursor principal; o i passa a apontar para o índice 2, e sobra apenas um último elemento para comparar, o índice 3.
Com isso, verificamos todos os pares.
Podemos perceber que não comparamos, por exemplo, o 1 com o 1 à esquerda.
Comparamos sempre com os elementos à direita.
Fazemos isso porque a ordem do par é irrelevante.
Qual é a intuição aqui?
Estamos olhando para todas as combinações de elementos 2 a 2 dentro do array.
Veremos essa conta mais adiante; ela resulta na soma de uma PA e leva a uma complexidade de ordem n².
É algo quadrático.
Registramos ao lado: O(n²).
Para destacar a ordem quadrática:
O(n)
O(n^2)
Vale lembrar:
O(n).O(n²).Conectando essas ideias com a notação usada em tela:
O(n) -> busca linear
O(n^2) -> todos pares
Nesse caso, fica claro o que estamos analisando: se formos verificar todos os pares dentro de um array, teremos algo quadrático.
Vamos ativar a curva quadrática no gráfico para visualizar.
Temos um comparativo dessas duas complexidades com as quais estamos trabalhando até agora.
O(n) cresce linearmente (com o número de elementos).
Já n² cresce de forma quadrática, ou exponencial em relação ao número de elementos.
Quando temos 4 elementos, olhando a curva quadrática, teremos 16 operações.
Se avançarmos para 8 elementos, teremos 64 operações.
E assim por diante.
Esse crescimento ocorre exponencialmente.
Vemos que essas duas curvas se distanciam muito rapidamente.
Algo viável para um algoritmo linear pode não ser viável para um quadrático.
Por exemplo, vamos aumentar o alcance do gráfico até o máximo de elementos, que é aproximadamente 1 milhão.
Com 1 milhão de elementos, olhando O(n), temos da ordem de 1 mil operações.
Parece aceitável.
E, no quadrático, quantas operações teríamos se o array tivesse 1 milhão de elementos?
Teríamos 1 milhão de operações realizadas.
Para esse caso, em que simplesmente comparamos dois números, pode não fazer diferença.
Se essa operação que estamos fazendo, por exemplo, uma validação entre contas dentro de um banco com 1 milhão de contas, não for trivial, teremos 1 milhão de verificações acontecendo. Nessa situação, a solução quadrática claramente deixa de ser viável.
Devemos guardar isso: soluções quadráticas podem ser inviáveis, embora às vezes sejam a única alternativa disponível para um problema.
Em alguns casos, ao resolver problemas, podemos partir de um array inicial — por exemplo, [3, 2, 1, 5] — que não está ordenado. Em diversas situações, ordenar os números da entrada fornece uma propriedade que permite resolver o problema com uma complexidade muito melhor do que a quadrática.
Sempre que falamos sobre ordenação — e a maioria das linguagens de programação fornece implementações eficientes — estamos nos referindo, em geral, a uma complexidade O(n log n). Vamos entender de onde vem esse n log n mais adiante; por ora, queremos construir a intuição sobre a velocidade de crescimento dessa curva.
Quando falamos de O(n log n), temos em mente operações como ordenação (nem sempre será esse o caso, mas é um exemplo válido). Ao plotarmos o gráfico comparativo, vemos uma curva abaixo da quadrática e acima da linear, isto é, mais eficiente do que O(n^2) e menos eficiente do que O(n). A diferença não é tão grande em entradas pequenas: com 12 elementos, uma solução linear realiza 12 operações; uma O(n log n) realiza 43; e a quadrática já realiza 144.
Para relacionar as categorias mais comuns, destacamos:
O(n) -> busca linear
O(n log n) -> ordenação
O(n^2) -> todos pares
Por que isso é útil? Às vezes, tínhamos uma solução quadrática porque a entrada vinha desordenada. Se ordenamos a entrada e, em seguida, conseguimos executar o restante do algoritmo em O(n log n) ou O(n), saímos de O(n^2) para O(n log n) simplesmente por ordenar a entrada. Fazemos um pré-processamento para manter tudo ordenado, e a propriedade de ordenação pode permitir resolver o problema de forma linear. Esse é um tipo de troca muito comum, que precisamos conhecer.
Outra operação bastante comum é a busca. Dependendo da propriedade do array — por exemplo, estar ordenado — conseguimos separá-lo em partes. Em uma busca binária, olhamos para uma posição do array: se o número for maior do que o que estamos procurando, analisamos uma parte; caso contrário, analisamos a outra parte, e assim por diante. Em cada passo, descartamos muitos elementos. Essa capacidade de descartar, com garantia de que não estamos eliminando a solução, leva a uma complexidade O(log n).
Como lembrete visual do raciocínio de descarte:
O(log n) -> descartar muitos elementos
No gráfico, a curva O(log n) cresce muito devagar, ficando abaixo da linear. A intuição é que não precisamos examinar todos os elementos de um array ordenado para encontrar um número específico. Mesmo com 4 elementos, bastam cerca de 2 verificações para termos certeza sobre a presença ou ausência do valor.
Há também casos em que o algoritmo não depende da quantidade de elementos na entrada. Nesse cenário, dizemos que ele é O(1), isto é, executa uma quantidade constante de operações. Por exemplo, obter o comprimento de uma lista quando a linguagem fornece essa informação diretamente é uma operação constante. Independentemente de haver 10, 100 ou 1000 elementos, continuamos com uma única operação. No gráfico, isso aparece como uma linha horizontal abaixo de todas as outras curvas; é a melhor complexidade possível.
Complementando com a notação usada na tela:
O(log n) -> descartar muitos elementos
O(1) -> constante
Vimos, então, os principais tipos de complexidade e como compará-los. Precisamos ser capazes de olhar para a solução, no planejamento, e estimar em qual dessas curvas o algoritmo se encaixa. Resta uma questão: como determinar a complexidade quando o código contém trechos com custos diferentes? Suponhamos que há uma parte inicial que identificamos como O(n) e, em seguida, outra parte também O(n). Como procederemos nessa análise é o que vamos discutir a seguir.
É como se percorrêssemos um array duas vezes. Nesse caso, teríamos algo do tipo O(N) + O(N), como se estivéssemos somando duas funções. No final, estaríamos realizando um trabalho linear proporcional à quantidade de elementos, e depois outro trabalho linear também proporcional à quantidade de elementos. Nessa soma, ficamos com 2N, ou seja, realizamos 2N operações. Esse fator constante 2 faz pouca diferença, pois, no gráfico, o crescimento continua sendo linear, representado por uma reta.
Visualmente, essa soma de custos lineares aparece assim:
# O(n) + O(n)
Nesse tipo de análise, o que sempre vamos fazer é observar qual termo domina a complexidade do algoritmo. Neste exemplo, ambos os termos são lineares; é o único comportamento presente. Portanto, a complexidade final do algoritmo é O(N).
Agora, e se tivéssemos algo do tipo: primeiro precisamos ordenar os números do array (O(N log N)), e depois percorremos todos os elementos do array com laços simples (O(N)). Nesse caso, ao lembrarmos das curvas, O(N log N) domina O(N), isto é, cresce mais rápido que o linear. Então, a complexidade que realmente conta é O(N log N). Apesar de haver uma parte linear, N log N cresce mais rapidamente e é o que determinará o número de operações do algoritmo.
Podemos anotar esses dois estágios de forma separada:
# O(n log n)
# O(n)
A mesma lógica vale se houver um trecho quadrático. Se, após uma ordenação, precisarmos realizar um trabalho quadrático, então N^2 domina N log N, e teremos, no final, um algoritmo O(N^2).
Registrando o caso dominante quadrático:
# O(n^2)
Nesta aula, a ideia não era resolver problemas específicos, e sim gerar intuição — algo que precisamos guardar e que vamos aproveitar bastante quando estivermos elaborando soluções para os problemas apresentados aqui. O que é importante reter: não é necessário decorar as funções, mas lembrar a intuição. Por exemplo, que tipo de complexidade ocorre quando olhamos para todos os pares de um array? Que tipo de complexidade ocorre quando precisamos ordenar uma palavra em uma solução? Tudo isso já nos indica qual é o indício que temos em relação à complexidade.
Um último detalhe: usamos a notação Big O também para medir o crescimento do uso de memória nas soluções. É sempre importante falar sobre o número de operações e sobre a quantidade de memória utilizada. Aplicamos o mesmo raciocínio: se a memória cresce de forma linear com a quantidade de elementos na entrada, então o consumo de espaço é O(N). Se for necessário gerar todas as combinações e armazená-las, estaremos falando de um espaço de memória quadrático, O(N^2).
A seguir, veremos uma resolução guiada. Vamos aplicar o processo de entrevista de código e aproveitar o que vimos sobre complexidade para entender como tudo se integra e como isso é executado na prática. Até mais.
O curso Coding Interview: aprenda técnicas para resolver problemas algorítmicos possui 309 minutos de vídeos, em um total de 55 atividades. Gostou? Conheça nossos outros cursos de Fundamentos de Programação em Back-end, ou leia nossos artigos de Back-end.
Matricule-se e comece a estudar com a gente hoje! Conheça outros tópicos abordados durante o curso:
O Plano Plus evoluiu: agora com Luri para impulsionar sua carreira com os melhores cursos e acesso à maior comunidade tech.
2 anos de Alura
Matricule-se no plano PLUS 24 e garanta:
Jornada de estudos progressiva que te guia desde os fundamentos até a atuação prática. Você acompanha sua evolução, entende os próximos passos e se aprofunda nos conteúdos com quem é referência no mercado.
Back-end, Dados, Front-end, DevOps, Mobile, Gestão & Negócios, UX & Design, Cibersegurança, Cloud, Inteligência Artificial
Formações com mais de 1500 cursos atualizados e novos lançamentos semanais, em Programação, Inteligência Artificial, Front-end, UX & Design, Data Science, Mobile, DevOps e Inovação & Gestão.
A cada curso ou formação concluído, um novo certificado para turbinar seu currículo e LinkedIn.
Acesso à inteligência artificial da Alura.
No Discord, você participa de eventos exclusivos, pode tirar dúvidas em estudos colaborativos e ainda conta com mentorias em grupo com especialistas de diversas áreas.
Catálogo de tecnologia para quem é da área de Marketing
Faça parte da maior comunidade Dev do país e crie conexões com mais de 120 mil pessoas no Discord.
Acesso ilimitado ao catálogo de Imersões da Alura para praticar conhecimentos em diferentes áreas.
Explore um universo de possibilidades na palma da sua mão. Baixe as aulas para assistir offline, onde e quando quiser.
20% de desconto na Pós Tech
Luri Vision chegou no Plano Pro: a IA da Alura que enxerga suas dúvidas, acelera seu aprendizado e conta também com o Alura Língua que prepara você para competir no mercado internacional.
2 anos de Alura
Todos os benefícios do PLUS 24 e mais vantagens exclusivas:
Acesso ao catálogo da Casa do Código e leitura dentro da plataforma
Modo entrevista - Pratique situações reais e evolua com feedback personalizado
Envie imagens para a Luri e ela te ajuda a solucionar problemas, identificar erros, esclarecer gráficos, analisar design e muito mais.
Aprenda um novo idioma e expanda seus horizontes profissionais. Cursos de Inglês, Espanhol e Inglês para Devs, 100% focado em tecnologia.
Para quem quer atingir seus objetivos mais rápido: Luri Vision ilimitado, vagas de emprego exclusivas e mentorias para acelerar cada etapa da jornada.
2 anos de Alura
Todos os benefícios do PRO 24 e mais vantagens exclusivas:
Envie imagens para a Luri e ela te ajuda a solucionar problemas, identificar erros, esclarecer gráficos, analisar design e muito mais de forma ilimitada.
Lives CareerUp: eventos exclusivos com foco em empregabilidade e carreira
Mentorias de carreira: 2 encontros individuais com mentores do Talent Lab
Conecte-se ao mercado com mentoria individual personalizada, vagas exclusivas e networking estratégico que impulsionam sua carreira tech para o próximo nível.
