Estruturas de Dados e Algoritmos
Hash tables, instrumentação, pilhas, filas e análise de custo
Este teste não é "mais uma lista de exercícios". Ele é um teste de maturidade: tira você do território confortável de "escrevi um código e funcionou" e coloca você no território profissional de "eu sei justificar, medir, escolher estrutura, prever comportamento e provar que está certo". Aqui, o que vale não é só chegar ao resultado; é conseguir explicar por que chegou e quanto custa chegar.
Os desafios que aparecem ao longo das questões são bem específicos. Você vai encarar problemas em que a solução ingênua funciona, mas é cara demais, e vai ter que reescrever com uma estratégia linear usando hash tables. Vai precisar escolher regras de interpretação, por exemplo, "maior número" versus "maior número único", e entender o que isso muda no algoritmo. Vai ter que construir interseções, detectar duplicatas e encontrar "primeiros" elementos sob restrições de ordem, que é justamente o tipo de detalhe que costuma quebrar solução bonita e errada.
Você também vai entrar no mundo de estruturas com estado interno: implementar pilha e fila com capacidade fixa, lidar com overflow e underflow, e provar que FIFO e LIFO estão sendo respeitados. E, como se não bastasse, ainda vai olhar para funções hash e discutir distribuição e colisão sem se esconder atrás de "O(1)". Se você consegue resolver tudo com rigor, passa a dominar competências que são exatamente o núcleo da disciplina.
Isso significa pensamento algorítmico com trade-off explícito, fluência real com hash tables, preservação de ordem e semântica, implementação de estruturas com invariantes e estado, e trabalho com evidência por meio de instrumentação e validação. Em termos práticos: você deixa de apenas codar e passa a raciocinar, provar e validar. E isso prepara diretamente o que vem adiante no curso.
Leitura do enunciado
O enunciado não pede apenas o maior número do array. Ele pede o maior número que aparece exatamente uma vez. Essa diferença muda a estrutura do algoritmo, porque precisamos rastrear a frequência, não só o máximo.
Ideia central
A versão ingênua conta repetições com dois laços e paga custo quadrático. A versão boa faz duas passagens: primeiro conta frequências em uma hash table, depois escolhe o maior elemento com frequência 1. O ganho vem da troca tempo versus espaço.
Implementação correta
import random
def greatest_unique_quadratic(arr):
comparisons = 0
best = None
n = len(arr)
for i in range(n):
count = 0
for j in range(n):
comparisons += 1
if arr[j] == arr[i]:
count += 1
if count == 1 and (best is None or arr[i] > best):
best = arr[i]
return best, comparisons
def greatest_unique_linear(arr):
accesses = 0
freq = {}
for x in arr:
accesses += 1
current = freq.get(x, 0)
accesses += 1
freq[x] = current + 1
best = None
for x in arr:
accesses += 1
if freq[x] == 1 and (best is None or x > best):
best = x
return best, accesses
def run_experiment(sizes=(10, 100, 1000, 5000), seed=42):
random.seed(seed)
linhas = []
for n in sizes:
arr = [random.randint(0, n // 2) for _ in range(n)]
arr.append(10 ** 9 + n)
best1, comp = greatest_unique_quadratic(arr)
best2, acc = greatest_unique_linear(arr)
linhas.append(
f"N={len(arr)} | quadratico: best={best1}, comparacoes={comp} | "
f"linear: best={best2}, acessos={acc}"
)
return linhas
print(greatest_unique_quadratic([5, 1, 5, 9, 7, 9, 8]))
print(greatest_unique_linear([5, 1, 5, 9, 7, 9, 8]))
for linha in run_experiment():
print(linha)Análise de complexidade
A primeira versão custa O(N^2) no tempo e O(1) de memória extra. A segunda custa O(N) esperado no tempo e O(N) de memória, porque usa dicionário para frequências. O contador de comparações e o contador de acessos deixam isso observável, não apenas teórico.
Teste ou evidência
Os testes pequenos devem devolver o mesmo valor nas duas funções. Já o experimento com tamanhos crescentes mostra a explosão do contador quadrático versus o crescimento quase linear do contador baseado em hash.
set e perder a
informação de frequência. O contrato correto é "maior valor que
ocorre exatamente uma vez".
Leitura do enunciado
Interseção pode significar mais de uma coisa. Aqui a resposta adota uma semântica explícita: devolver elementos em comum sem repetição e preservando a ordem do segundo array. Isso evita ambiguidade e torna a implementação verificável.
Ideia central
Guardamos os elementos do primeiro array em uma hash table para consulta O(1) esperada. Depois percorremos o segundo array, adicionando ao resultado apenas o que estiver presente e ainda não tiver sido emitido.
Implementação correta
def intersection_linear(a, b):
present = {}
emitted = {}
out = []
for x in a:
present[x] = True
for y in b:
if y in present and y not in emitted:
out.append(y)
emitted[y] = True
return out
print(intersection_linear([1, 2, 2, 3, 5], [5, 2, 2, 8, 1, 1]))
def big_test():
a = list(range(200000))
b = list(range(150000, 350000))
out = intersection_linear(a, b)
print(len(out), out[0], out[-1])
big_test()Análise de complexidade
O custo esperado é O(len(a) + len(b)) no tempo e O(len(a)) no espaço, mais O(k) para os elementos realmente emitidos. O ponto central é que a busca repetida deixa de ser linear dentro de outro laço.
Teste ou evidência
No teste pequeno, a saída deve ser [5, 2, 1],
preservando a ordem do segundo array sem repetir elementos. No
teste grande, o tamanho esperado é 50000 e as extremidades
devem ser 150000 e 199999.
Leitura do enunciado
"Primeiro duplicado" não significa menor valor repetido. Significa o primeiro elemento que reaparece durante a leitura sequencial. A ordem de leitura faz parte do contrato.
Ideia central
Basta registrar em uma hash table tudo o que já foi visto. No primeiro elemento que aparecer de novo, retornamos imediatamente. A segunda ocorrência é o sinal decisivo.
Implementação correta
def first_duplicate(strings):
seen = {}
for s in strings:
if s in seen:
return s
seen[s] = True
return None
print(first_duplicate(["a", "b", "c", "b", "a"]))
print(first_duplicate(["x", "y", "z", "z"]))
print(first_duplicate(["u", "v", "w"]))Análise de complexidade
O tempo esperado é O(N) porque cada elemento é processado uma vez, com consulta e inserção esperadas O(1) na hash table. O espaço é O(N) no pior caso, quando nada repete antes do fim.
Teste ou evidência
Os resultados esperados são "b",
"z" e None. Isso cobre caso com
duplicado cedo, duplicado no fim e ausência total de
repetição.
Leitura do enunciado
O problema pede para ignorar ruído, considerar apenas letras
de a a z e encontrar a letra
faltante. Isso exige normalização e filtragem antes da etapa
de decisão.
Ideia central
Usamos um vetor de 26 posições booleanas, uma para cada letra. Ao percorrer a string normalizada, marcamos as letras presentes. Depois fazemos uma varredura fixa de 26 posições e devolvemos a que permaneceu falsa.
Implementação correta
def missing_letter(s):
present = [False] * 26
for ch in s.lower():
if "a" <= ch <= "z":
present[ord(ch) - ord("a")] = True
for i in range(26):
if not present[i]:
return chr(ord("a") + i)
return None
print(missing_letter("Th quck brown fox jumps over the lazy dog!! 123"))
print(missing_letter("abcdefghijklmnopqrstuvwxyz"))Análise de complexidade
O tempo é O(N), onde N é o tamanho da string de entrada, porque fazemos uma passagem principal sobre os caracteres e uma passagem final fixa de 26 posições. O espaço extra é O(1), já que 26 não cresce com a entrada.
Teste ou evidência
No primeiro teste, a letra faltante deve ser "e".
No segundo, todas as letras aparecem, então a função retorna
None.
Leitura do enunciado
A pergunta correta não é "qual caractere aparece uma vez?". É "qual caractere aparece uma vez e surge antes dos demais com essa propriedade?". Frequência e ordem atuam juntas.
Ideia central
A primeira passagem conta frequências. A segunda usa a ordem original da string para encontrar o primeiro caractere com frequência 1. Separar contagem de decisão deixa a solução clara e correta.
Implementação correta
def first_non_repeated_char(s):
freq = {}
for ch in s:
freq[ch] = freq.get(ch, 0) + 1
for ch in s:
if freq[ch] == 1:
return ch
return None
print(first_non_repeated_char("aabccdeff"))
print(first_non_repeated_char("aabbcc"))Análise de complexidade
O tempo esperado é O(N), com duas passagens lineares e operações esperadas O(1) na hash table. O espaço é O(N) no pior caso, limitado pela quantidade de caracteres distintos.
Teste ou evidência
Em "aabccdeff", a resposta correta é
"b". Em "aabbcc", não existe não
repetido, então o retorno correto é None.
Leitura do enunciado
O exercício não quer apenas ordenar. Ele quer observação interna do algoritmo. Isso significa que comparações e trocas devem ser contadas explicitamente, não inferidas depois.
Ideia central
Para cada posição i, buscamos o menor elemento do
trecho restante e fazemos uma troca ao final, se necessário. O
contador de comparações cresce sempre de forma quadrática; o
de trocas varia conforme a entrada.
Implementação correta
def selection_sort_instrumented(a):
a = a[:]
n = len(a)
comparisons = 0
swaps = 0
for i in range(n):
min_idx = i
for j in range(i + 1, n):
comparisons += 1
if a[j] < a[min_idx]:
min_idx = j
if min_idx != i:
a[i], a[min_idx] = a[min_idx], a[i]
swaps += 1
return a, comparisons, swaps
cases = {
"ordenada": [1, 2, 3, 4, 5],
"invertida": [5, 4, 3, 2, 1],
"aleatoria": [3, 1, 4, 1, 5, 9, 2],
}
for name, arr in cases.items():
sorted_arr, comp, swp = selection_sort_instrumented(arr)
print(name, sorted_arr, comp, swp)Análise de complexidade
Selection Sort faz O(N^2) comparações no melhor, médio e pior caso. O espaço extra é O(1), desconsiderando a cópia para preservar a entrada original no teste. O número de trocas é, no máximo, O(N).
Teste ou evidência
Os três casos devem terminar ordenados. A evidência importante é que o contador de comparações não cai para linear nem quando a entrada já está ordenada.
Leitura do enunciado
Aqui o foco já não é apenas ordenar, mas mostrar como o comportamento muda conforme o estado inicial do array. O exercício exige evidências de comparações e deslocamentos.
Ideia central
Insertion Sort mantém um prefixo ordenado e insere o próximo elemento no lugar correto. Quando o array está quase ordenado, há pouco trabalho. Quando está invertido, o número de deslocamentos explode.
Implementação correta
def insertion_sort_instrumented(a):
a = a[:]
comparisons = 0
shifts = 0
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0:
comparisons += 1
if a[j] > key:
a[j + 1] = a[j]
shifts += 1
j -= 1
else:
break
a[j + 1] = key
return a, comparisons, shifts
almost = [1, 2, 3, 5, 4, 6, 7, 8]
reversed_arr = [8, 7, 6, 5, 4, 3, 2, 1]
for arr in (almost, reversed_arr):
sorted_arr, comp, sh = insertion_sort_instrumented(arr)
print(arr, "->", sorted_arr, comp, sh)Análise de complexidade
No melhor caso, quando o array já está ordenado, o custo cai para O(N). No pior caso, quando está invertido, o custo sobe para O(N^2). O espaço extra é O(1), fora a cópia usada para teste.
Teste ou evidência
O caso quase ordenado deve mostrar poucos deslocamentos. O caso invertido deve mostrar muito mais comparações e deslocamentos, tornando visível a sensibilidade do algoritmo ao estado inicial.
Leitura do enunciado
O requisito do sistema é atender na ordem de chegada. Isso determina a estrutura. Não é uma questão de gosto; é uma questão de modelo operacional.
Ideia central
Fila implementa FIFO: quem entra primeiro sai primeiro. Pilha implementa LIFO: quem entra por último sai primeiro. Portanto, para preservar a ordem temporal, a resposta correta é fila.
Implementação correta
Não há código complexo exigido aqui; o essencial é a justificativa operacional correta:
enqueue(x)insere no fim.dequeue()remove do início.-
peek()observa quem será atendido primeiro.
Análise de complexidade
Em uma implementação adequada de fila, enqueue,
dequeue e peek podem operar em O(1).
O ponto do exercício, porém, é menos o custo e mais a
aderência ao contrato FIFO.
Teste ou evidência
Se as requisições chegarem na ordem A, B, C, a fila atende A, depois B, depois C. A pilha faria C, depois B, depois A. Esse contraexemplo basta para invalidar a pilha.
Leitura do enunciado
O exercício sai do nível de funções isoladas e entra no nível de estrutura com estado persistente. A pilha precisa guardar dados, topo, capacidade e reagir corretamente a erros de contrato.
Ideia central
Usamos um array fixo e um ponteiro top para a
próxima posição livre. push escreve e avança;
pop recua e devolve o elemento. Overflow e
underflow precisam ser tratados explicitamente.
Implementação correta
class StackOverflow(Exception):
pass
class StackUnderflow(Exception):
pass
class Stack:
def __init__(self, capacity):
self._data = [None] * capacity
self._top = 0
def push(self, x):
if self._top == len(self._data):
raise StackOverflow("overflow: pilha cheia")
self._data[self._top] = x
self._top += 1
def pop(self):
if self._top == 0:
raise StackUnderflow("underflow: pilha vazia")
self._top -= 1
x = self._data[self._top]
self._data[self._top] = None
return x
def state(self):
return {
"data": self._data[:],
"top": self._top,
"size": self._top,
"capacity": len(self._data),
}
s = Stack(3)
print(s.state())
s.push(10); print(s.state())
s.push(20); print(s.state())
s.push(30); print(s.state())
try:
s.push(40)
except StackOverflow as e:
print("ERRO:", e)
print("pop:", s.pop()); print(s.state())
print("pop:", s.pop()); print(s.state())
print("pop:", s.pop()); print(s.state())
try:
s.pop()
except StackUnderflow as e:
print("ERRO:", e)Análise de complexidade
push, pop e
state operam em O(1), exceto pela cópia rasa do
array dentro de state, que custa O(capacidade)
por decisão de diagnóstico. O armazenamento total é
O(capacidade).
Teste ou evidência
Os estados impressos mostram explicitamente os atributos internos depois de cada operação. Esse rastreio torna visível o contrato LIFO e deixa overflow e underflow testados, não apenas declarados.
Leitura do enunciado
A fila precisa manter estado interno consistente ao longo do
tempo. Isso exige mais que um array: exige head,
tail, size e circularidade para
reaproveitar espaço.
Ideia central
head aponta para o próximo elemento a sair,
tail aponta para a próxima posição livre, e
size distingue fila cheia de fila vazia. O uso de
módulo evita desperdício de espaço.
Implementação correta
class QueueOverflow(Exception):
pass
class QueueUnderflow(Exception):
pass
class Queue:
def __init__(self, capacity):
self._data = [None] * capacity
self._head = 0
self._tail = 0
self._size = 0
def enqueue(self, x):
if self._size == len(self._data):
raise QueueOverflow("overflow: fila cheia")
self._data[self._tail] = x
self._tail = (self._tail + 1) % len(self._data)
self._size += 1
def dequeue(self):
if self._size == 0:
raise QueueUnderflow("underflow: fila vazia")
x = self._data[self._head]
self._data[self._head] = None
self._head = (self._head + 1) % len(self._data)
self._size -= 1
return x
def state(self):
return {
"data": self._data[:],
"head": self._head,
"tail": self._tail,
"size": self._size,
"capacity": len(self._data),
}
q = Queue(4)
print(q.state())
q.enqueue("A"); print(q.state())
q.enqueue("B"); print(q.state())
q.enqueue("C"); print(q.state())
print("deq:", q.dequeue()); print(q.state())
q.enqueue("D"); print(q.state())
q.enqueue("E"); print(q.state())
print("deq:", q.dequeue()); print(q.state())
print("deq:", q.dequeue()); print(q.state())
print("deq:", q.dequeue()); print(q.state())Análise de complexidade
enqueue e dequeue operam em O(1). O
espaço total é O(capacidade). A circularidade preserva esse
custo sem deslocar elementos a cada remoção.
Teste ou evidência
As remoções devem ocorrer em ordem A, depois B, depois C,
depois D/E conforme a sequência de operações. Os estados
internos mostram head, tail e o
array circular evoluindo de forma consistente.
head == tail. Sem
size ou outra convenção extra, esse estado fica
ambíguo.
Leitura do enunciado
O pedido não é montar uma lista de caracteres. O pedido é inverter a string usando a semântica de pilha, sem usar atalhos prontos como slicing reverso.
Ideia central
Empilhamos cada caractere e depois desempilhamos ate esvaziar. O comportamento LIFO faz a ordem sair invertida de forma natural.
Implementação correta
def reverse_with_stack(s):
stack = []
for ch in s:
stack.append(ch)
out = []
while stack:
out.append(stack.pop())
return "".join(out)
print(reverse_with_stack("abcd"))
print(reverse_with_stack("acai"))
print(reverse_with_stack(""))Análise de complexidade
O tempo é O(N), com uma passagem para empilhar e outra para desempilhar. O espaço extra também é O(N), porque a pilha armazena todos os caracteres da string.
Teste ou evidência
As saídas esperadas são "dcba",
"iaca" e "". Isso cobre caso
simples, palavra curta e string vazia.
Leitura do enunciado
O foco não é construir a tabela inteira, e sim comparar a qualidade das funções hash. Isso significa observar resíduos gerados, baldes efetivamente usados e risco de colisão sob conjuntos típicos de chaves.
Ideia central
Com M = 10, as funções baseadas em módulo devem ser analisadas pelos resíduos de 0 a 9. A pergunta técnica correta não é "a fórmula funciona?", e sim "como ela distribui chaves e quantas colisões tende a produzir?".
Implementação correta
A resposta adequada aqui é analítica, em Markdown:
## Comparação técnica para M = 10
Funções:
- `h1(k) = k mod 10`
- `h2(k) = (k * 7) mod 10`
- `h3(k) = (k^2) mod 10`
### Caso A: chaves sequenciais 0..19
| Função | Comportamento | Impacto |
| --- | --- | --- |
| `h1` | distribui pelos resíduos 0..9 conforme o último dígito | boa distribuição para essa família de chaves |
| `h2` | como 7 é coprimo com 10, multiplica e permuta resíduos | também tende a cobrir bem os 10 baldes |
| `h3` | quadrados mod 10 caem apenas em {0, 1, 4, 5, 6, 9} | usa menos baldes e produz mais colisões |
### Caso B: chaves múltiplas de 10
Para `0, 10, 20, 30, ...`:
- `h1(k) = 0`
- `h2(k) = 0`
- `h3(k) = 0`
Conclusão: quando o padrão das chaves já está alinhado com o módulo, nenhuma das três salva a distribuição.
### Observação sobre colisão
- `h1` e `h2` costumam ter comportamento melhor para chaves sequenciais.
- `h3` tem maior risco de colisão sistemática, porque não cobre todos os resíduos possíveis.
- "Boa função hash" não é uma propriedade mística; depende do padrão das chaves e da tabela escolhida.Análise de complexidade
Como o exercício é analítico, a "complexidade" relevante é do raciocínio: comparar resíduos para um conjunto de chaves e observar concentração. O ponto técnico principal é o efeito das colisões sobre o desempenho esperado de consultas e inserções.
Teste ou evidência
A evidência é matemática: para k = 0..9,
k^2 mod 10 gera apenas os resíduos 0, 1, 4, 5, 6
e 9. Isso prova que h3 concentra chaves em menos
baldes e aumenta a colisão.