Troque memória por velocidade com hash maps
Use dicionários e sets para substituir laços aninhados por buscas.
- Reconhecer problemas que um hash map acelera.
- Resolver o Two Sum numa única passada.
- Contar frequências com um dicionário.
O hash map (um dict do Python) é a estrutura de dados mais útil nas entrevistas de programação. Ele responde “já vi isto antes?” e “onde?” em tempo O(1) em média. Sempre que a sua força bruta percorre a entrada de novo dentro de um laço, pergunte se um dicionário poderia lembrar o que o laço interno está procurando.
Padrões que usam hashing
- Busca do complemento: para cada valor, verifique se o valor de que você precisa (
target - num) já foi visto. Isso é o Two Sum. - Contagem de frequência:
collections.Counteroudict.get(key, 0) + 1para anagramas, elemento majoritário e “primeiro caractere único”. - Agrupamento: mapeie uma chave canônica para uma lista, como letras ordenadas → palavras, para agrupar anagramas.
- Set de vistos: detecte duplicatas ou ciclos.
1def two_sum(nums, target):
2 seen = {} # value -> index
3 for i, num in enumerate(nums):
4 if target - num in seen:
5 return [seen[target - num], i]
6 seen[num] = i
7 return None
8
9print(two_sum([2, 7, 11, 15], 9))
10print(two_sum([3, 2, 4], 6))[0, 1] [1, 2]
A força bruta testa todos os pares: tempo O(n²), espaço O(1). A versão com dicionário faz uma passada: tempo O(n), espaço O(n). Repare na ordem - verifique o complemento antes de guardar o número atual, para que um número nunca forme par consigo mesmo.
Principais conclusões
Use um dict ou um set quando um laço interno está procurando alguma coisa.
Verifique o complemento antes de guardar o item atual.
O hashing troca O(n) de memória por buscas O(1) em média.
Quiz da aula
5 perguntas · aprovação com 4 acertos · até 50 XP
Ao passar, você conclui a aula e mantém sua sequência. As perguntas erradas voltarão em sessões de revisão.
Pratique: resolva problemas de entrevistas técnicas
Resolva um problema clássico de entrevista em Python e execute-o com casos de teste. Busque a complexidade ideal e depois confira os casos extremos. Os exercícios rodam localmente no navegador.
Resolva o Two Sum
Leia uma linha de inteiros e depois um alvo. Exatamente um par de posições diferentes soma o alvo. Imprima os índices delas, o menor primeiro, separados por um espaço. Use um dicionário para uma solução O(n).
- Exemplo clássico
- Não é o primeiro elemento
- Valores duplicados
O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.
Dúvidas sobre esta lição
Travou em algum ponto? Pergunte. Descobriu algo? Compartilhe. Explicar também é uma ótima forma de aprender.
Carregando publicações…