Os Blocos Fundamentais: Arrays, Strings e Hash Tables
Domine o trio de ferro de toda entrevista: Arrays, Strings e o superpoder dos Hash Tables para otimizar suas soluções de O(n²) para O(n).
Vou te contar uma história real, de um projeto React/TypeScript que me deu uma dor de cabeça danada. A gente tinha uma feature que precisava encontrar uma informação específica dentro de um array com mais de 45.000 itens. Para cada interação do usuário, o código rodava um .find() nesse array gigante. O resultado? A interface engasgava, a performance era péssima, e a experiência do usuário era horrível.
A primeira reação foi pensar "precisamos de mais poder de processamento!". Mas a solução era muito mais elegante e estava bem debaixo do meu nariz, na matéria desta aula. A virada de chave foi quando eu parei de tratar os dados como um Array e os transformei em um objeto JSON (que no fundo, é a implementação de um Hash Table em JavaScript). Em vez de um .find() com complexidade O(n), a busca se tornou um acesso direto à propriedade (meuObjeto[chave]), com complexidade O(1).
A diferença foi da água para o vinho. A feature ficou instantânea. Naquele dia, eu não só resolvi um problema de performance, mas entendi na prática que dominar estruturas de dados não é teoria de entrevista, é uma ferramenta essencial para construir software de qualidade. Esta aula é sobre te dar essa mesma virada de chave.
1. O Trio de Ferro das Entrevistas
Se você só pudesse estudar três estruturas de dados para uma entrevista, seriam estas. Praticamente todo problema de code challenge pode ser resolvido ou otimizado com um profundo conhecimento de:
2. Arrays e Strings: A Base de Tudo
Arrays e Strings são coleções de elementos armazenados em sequência na memória. Por causa disso, eles têm características de performance muito específicas que você precisa saber de cor.
| Operação | Complexidade de Tempo | Por quê? |
|---|---|---|
Acesso (arr[i]) | O(1) | Acesso direto via índice na memória. É instantâneo. |
Busca (arr.find()) | O(n) | No pior caso, você precisa olhar cada elemento para encontrar o que procura. |
| Inserção/Deleção no Final | O(1) (amortizado) | Geralmente rápido, mas pode ser O(n) se o array precisar ser realocado na memória. |
| Inserção/Deleção no Início/Meio | O(n) | Você precisa "empurrar" ou "puxar" todos os outros elementos para abrir ou fechar espaço. |
3. Hash Tables: O Superpoder Secreto 🧙♂️
Hash Tables (conhecidos como Map em JavaScript, dict em Python, ou HashMap em Java) são a sua arma mais poderosa. Eles armazenam pares de chave-valor.
A Mágica: Em um Hash Table, as operações de inserção, busca e remoção têm uma complexidade de tempo média de O(1) - tempo constante!
Como a Mágica Funciona (Simplificado)?
4. O "Pulo do Gato": Resolvendo Problemas com Hash Tables
Vamos ver o poder do Hash Table em ação com um dos problemas mais clássicos de entrevistas: o "Two Sum".
O Problema: Dado um array de números e um número alvo (target), retorne dois números do array que somam o alvo.
Abordagem 1: Força Bruta (O(n²))
A primeira ideia é usar dois loops: pegar um número e verificar se a soma dele com todos os outros números do array resulta no alvo.
function twoSum_BruteForce(arr, target) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] === target) {
return [arr[i], arr[j]];
}
}
}
return null; // Nenhum par encontrado
}
// Complexidade de Tempo: O(n²) - dois loops aninhados.
// Complexidade de Espaço: O(1) - não usamos memória extra.Abordagem 2: Otimizada com Hash Table (O(n))
E se, ao percorrer a lista uma única vez, pudéssemos saber instantaneamente se já vimos o número complementar que precisamos? É isso que o Hash Table nos dá!
function twoSum_HashTable(arr, target) {
const seenNumbers = new Set(); // Ou um Map/Object
for (let i = 0; i < arr.length; i++) {
const currentNum = arr[i];
const complement = target - currentNum;
// Eu já vi o número que preciso para completar a soma?
if (seenNumbers.has(complement)) {
return [complement, currentNum];
}
// Se não, adiciono o número atual ao meu conjunto de números vistos.
seenNumbers.add(currentNum);
}
return null; // Nenhum par encontrado
}
// Complexidade de Tempo: O(n) - um único loop.
// Complexidade de Espaço: O(n) - no pior caso, guardamos todos os números no Set.Percebe a diferença? Trocamos um loop aninhado por um único loop e uma consulta O(1) a cada passo. É uma melhoria de performance brutal!
5. A Troca Justa: Tempo vs. Espaço
Note que na solução otimizada, nós usamos memória extra para criar o seenNumbers. Este é um dos trade-offs mais comuns e importantes em algoritmos:
O Trade-off Clássico ⚖️
Muitas vezes, podemos gastar mais memória (complexidade de espaço) para obter uma solução com menor tempo de execução (complexidade de tempo). Em uma entrevista, ser capaz de discutir esse trade-off é um sinal de grande maturidade.
💊 Pílula Devly
Arrays e Strings são seus blocos de construção. Hash Tables são sua ferramenta de demolição para complexidades quadráticas. Na dúvida em uma entrevista, pare por um segundo e se pergunte: "Um Hash Table (ou Map, ou Set) resolve isso mais rápido?". Em 50% das vezes, a resposta é um sonoro "sim!".