Curso
Python intermediário
4 h
1.4M
Aprenda Python do zero
Domine o Python para a ciência de dados e adquira habilidades que estão em alta.
Perguntas básicas sobre estruturas de dados
Para demonstrar seu entendimento, é importante ter segurança nas estruturas centrais e suas implementações. As perguntas a seguir testam sua habilidade de explicar esses conceitos e mostrar seu conhecimento.
Quais são os diferentes tipos de estruturas de dados?
As estruturas de dados são classificadas da seguinte forma:
- Estruturas lineares: Uma estrutura é considerada linear quando todos os elementos estão dispostos em sequência. Os itens são armazenados de forma não hierárquica, em que cada um tem um predecessor e um sucessor, exceto o primeiro e o último.
- Estruturas não lineares: Não formam uma sequência; cada item se conecta a dois ou mais outros itens em um arranjo não linear. Os elementos não são organizados de forma sequencial.
Explique a diferença entre array e lista ligada (linked list).
Arrays e listas ligadas armazenam grupos de itens, mas funcionam de maneiras diferentes. Veja as principais diferenças:
- Arrays: funcionam como uma fileira de caixas na memória, permitindo acesso rápido por índice, com complexidade de tempo O(1). Porém, inserir ou remover itens no meio é trabalhoso, pois exige deslocar outros elementos.
- Listas ligadas: são compostas por nós, em que cada nó guarda um item e aponta para o próximo. Isso facilita inserir ou excluir sem afetar toda a lista, mas encontrar um item é mais lento, com complexidade O(n).
O que é uma pilha (stack)?
Uma pilha é uma lista ordenada na qual você adiciona e remove itens por uma única extremidade, chamada topo. Segue o princípio LIFO (last-in, first-out): o último elemento que entrou é o primeiro a sair.
Pilhas são usadas em várias aplicações, como avaliação de expressões, backtracking, gerenciamento de memória e chamadas/retornos de funções.
Como implementar uma pilha usando um array?
Em Python, uma lista funciona como pilha nativamente: append() é o push, e pop() remove o topo.
my_stack = []
item = 1
my_stack.append(item)
my_stack.pop()Mantendo o índice do topo, você torna essas operações rápidas e eficientes.
Explique o conceito de fila (queue) e suas implementações comuns em Python.
Uma fila segue o princípio FIFO (first-in, first-out) — como a fila de um caixa, em que as pessoas entram atrás e saem pela frente.
Em Python, você pode implementar uma fila de diferentes maneiras:
Usando uma lista e aproveitando os métodos append() e pop():
my_queue = []
item = 1
# Enfileirar (enqueue)
my_queue.append(item)
# Desenfileirar (dequeue)
my_queue.pop(0)Usando deque() da biblioteca collections, que executa append() e pop() mais rápido que listas:
from collections import deque
my_queue = deque()
item = 1
# Enfileirar
my_queue.append(item)
# Desenfileirar
my_queue.popleft()Usando o módulo interno queue.Queue:
from queue import Queue
my_queue = Queue(maxsize = 3)
# Enfileirar
my_queue.put(item)
# Desenfileirar
my_queue.get()O que é uma árvore de busca binária (BST) e como ela funciona?
Uma árvore binária é uma estrutura em que cada nó tem no máximo dois filhos: esquerdo e direito. Já a árvore de busca binária (BST) é um tipo específico de árvore binária com propriedades de ordenação: para todo nó, todas as chaves na subárvore esquerda são menores, todas as chaves na subárvore direita são maiores, e ambas as subárvores também são BSTs.
Essas propriedades permitem operações eficientes de busca, inserção e remoção, normalmente com complexidade O(log n) em árvores balanceadas.
Árvore de busca binária. Imagem do autor.
Explique o conceito de hashing e suas aplicações.
Hashing é uma técnica que transforma dados de qualquer tamanho em um valor de tamanho fixo chamado hash, usando uma função de hash.
Um uso comum é em tabelas hash, associando chaves a posições específicas em um array, o que facilita localizar e recuperar dados rapidamente. Hashing também é aplicado em criptografia (armazenamento seguro de senhas) e em deduplicação para organizar dados.
O que é um heap e para que ele é usado?
Heap é uma estrutura em forma de árvore que segue regras específicas.
Em um max-heap, todo pai é maior ou igual aos filhos; em um min-heap, todo pai é menor ou igual aos filhos.
Heaps são muito usados para criar filas de prioridade, classificando itens por importância. Também são a base do heap sort, um método eficiente de ordenação.
Em um min-heap, todos os nós pai são menores que os filhos — imagem do autor.
Perguntas intermediárias sobre estruturas de dados
Depois dos fundamentos, vamos a perguntas de nível intermediário que exploram sua proficiência técnica em implementar e usar esses conceitos.
Como você balancearia uma árvore de busca binária?
Uma BST balanceada mantém alturas semelhantes entre as subárvores esquerda e direita. Balancear é crucial para preservar a eficiência de busca, inserção e remoção.
Técnicas como árvores AVL e árvores rubro-negras são usadas para auto-balanceamento. AVL mantém diferença de altura de no máximo 1 entre as subárvores; árvores rubro-negras têm restrições de balanceamento mais rígidas.
Como você implementaria um min-heap em Python?
Um min-heap normalmente é suportado por uma lista. As duas operações-chave são insert (adiciona um elemento e faz o bubble-up para restaurar a propriedade do heap) e extract_min (remove a raiz e faz o sift-down para reordenar):
class MinHeap:
def __init__(self):
self.heap = []
def __len__(self): # Tamanho do heap
return len(self.heap)
def __parent(self, i): # Índice do pai
return (i - 1) // 2
def __left(self, i): # Índice do filho esquerdo
return 2 * i + 1
def __right(self, i): # Índice do filho direito
return 2 * i + 2
def __swap(self, i, j): # Troca dois elementos
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def __heapify_up(self, i): # Restaura a propriedade de min-heap após inserção
while i > 0 and self.heap[i] < self.heap[self.__parent(i)]:
self.__swap(i, self.__parent(i))
i = self.__parent(i)
def __heapify_down(self, i): # Restaura a propriedade de min-heap após extração
while True:
smallest = i
left = self.__left(i)
right = self.__right(i)
if left < len(self) and self.heap[left] < self.heap[smallest]:
smallest = left
if right < len(self) and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != i:
self.__swap(i, smallest)
i = smallest
else:
break
def insert(self, val): # Insere um valor no heap
self.heap.append(val)
self.__heapify_up(len(self) - 1)
def extract_min(self): # Extrai o menor valor do heap
if not self.heap:
return None
min_val = self.heap[0]
self.heap[0] = self.heap[-1]
self.heap.pop()
self.__heapify_down(0)
return min_valExplique o conceito de trie e suas aplicações.
Uma trie, também chamada de árvore de prefixos, é uma estrutura em árvore projetada para busca eficiente de strings e correspondência de prefixos.
Em uma trie, cada nó representa um caractere, e os caminhos da raiz até os nós formam strings completas. Tries são comuns em autocomplete, corretores ortográficos e implementação de dicionários.
Uma trie, em que cada nó representa um caractere que se conecta para formar uma string. Imagem do autor.
Como você implementaria uma tabela hash com resolução de colisões?
Colisão ocorre quando duas chaves diferentes geram o mesmo índice.
Há vários métodos para resolver colisões, incluindo encadeamento (chaining), em que os elementos colidentes são armazenados em uma lista ligada no índice correspondente, e endereçamento aberto (open addressing), que busca o próximo espaço disponível por técnicas de sondagem como linear, quadrática ou double hashing.
Explique o conceito de grafo e suas diferentes representações.
Um grafo é uma estrutura composta por um conjunto de vértices (nós) interconectados por arestas. Ele é útil para representar relações e conexões entre entidades.
- Matriz de adjacência: representação do grafo por uma matriz bidimensional. Cada elemento da matriz indica se há aresta entre dois vértices. Na linha do vértice i e coluna do vértice j, o valor indica a conexão: zero significa ausência de aresta; um número positivo mostra o peso.
- Lista de adjacência. Aqui, usamos uma lista de listas. Cada índice da lista principal representa um vértice; as listas internas mostram seus vizinhos diretos. Essa abordagem é mais econômica em memória para grafos esparsos, pois armazena apenas conexões reais.
Como executar busca em profundidade (DFS) e busca em largura (BFS) em um grafo?
Depth-first search (DFS) explora um grafo/árvore mergulhando ao máximo em cada ramo antes de retroceder. Pode ser implementada com uma pilha explícita ou recursão. A complexidade é O(V + E), em que V é o número de vértices e E o de arestas.
Breadth-first search (BFS) explora sistematicamente todos os nós do nível atual antes de ir para o próximo. É eficaz para achar o caminho mais curto em grafos não ponderados e costuma ser implementada com uma fila. Assim como DFS, tem complexidade O(V + E).
Descreva os trade-offs entre diferentes algoritmos de ordenação.
Algoritmos de ordenação são fundamentais para processamento eficiente de dados — possibilitam buscas mais rápidas, melhor análise e visualização. Ao escolher, considere alguns trade-offs:
- Bubble sort é simples de implementar, mas lento para entradas grandes, com complexidade O(n²). É mais útil para fins didáticos.
- Merge sort roda em O(n log n) independentemente da entrada, mas precisa de espaço extra, pois cria arrays temporários na etapa de merge.
- Quick sort também tem média O(n log n) e geralmente é mais rápido na prática por ordenar in-place. O porém é que um pivô ruim pode degradar para O(n²) no pior caso.
Veja implementações limpas em Python:
# Bubble sort — ordena in-place
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Quick sort — ordena in-place
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
# Merge sort — retorna uma nova lista ordenada
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
return merge(left_half, right_half)nums = [3, 1, 4, 1, 5, 9, 2, 6]
bubble_sort(nums) # ordena nums in-place
quick_sort(nums, 0, len(nums) - 1) # também in-place
sorted_nums = merge_sort(nums) # retorna nova listaEm uma entrevista, o conteúdo acima é suficiente. Para se destacar, mencione que sorted() e list.sort() do Python usam o Timsort, um híbrido de merge sort e insertion sort. Por isso, quase nunca vale escrever um sort do zero em produção.
Como encontrar o caminho mais curto entre dois nós em um grafo?
Há vários algoritmos para encontrar caminhos mínimos em grafos.
Para grafos não ponderados, a busca em largura explora os nós por camadas. Em grafos ponderados com arestas não negativas, o algoritmo de Dijkstra encontra o caminho mais curto examinando primeiro o vértice mais próximo.
O algoritmo A* melhora a eficiência usando heurísticas para estimar o custo restante. A escolha depende das características do grafo e dos requisitos do problema.
Perguntas avançadas sobre estruturas de dados
Agora, algumas perguntas avançadas para quem busca posições sênior ou quer demonstrar domínio de estruturas especializadas e complexas.
Explique o conceito de programação dinâmica e como aplicá-la a problemas com estruturas de dados.
Programação dinâmica resolve problemas complexos dividindo-os em subproblemas menores e sobrepostos. Em vez de recalcular tudo do zero, guardamos soluções parciais para evitar trabalho repetido.
Ela é muito útil para encontrar a maior subsequência comum entre duas strings ou o custo mínimo para chegar a um ponto em uma grade.
Explique o conceito de B-tree e suas vantagens sobre árvores de busca binária.
B-trees são árvores balanceadas projetadas para acesso eficiente a disco. Algumas características:
- Todas as folhas têm a mesma profundidade.
- Cada nó armazena um número variável de chaves dentro de um intervalo definido.
- Nós internos funcionam como índices que direcionam a busca para a subárvore correta.
Vantagens sobre árvores de busca binária:
- Menos I/O de disco: várias chaves por nó reduzem o número de leituras necessárias para localizar uma chave.
- Melhor desempenho: em grandes volumes de dados, mais chaves por nó implicam menos níveis e buscas mais rápidas.
Descreva o conceito de ordenação topológica e suas aplicações.
Ordenação topológica organiza os vértices de um grafo acíclico direcionado (DAG) de forma que, se existir uma aresta do vértice u para o vértice v, então u aparece antes de v na ordem. É usada em agendamento de tarefas — definindo a ordem de execução respeitando dependências —, além de sistemas de build, gerenciadores de pacotes e planejamento de pré-requisitos de cursos.
Descreva a diferença entre min-heap e fila de prioridade.
Um min-heap é uma implementação específica de fila de prioridade e é uma árvore binária completa em que o valor de cada nó é menor ou igual ao de seus filhos, permitindo encontrar e extrair o mínimo com eficiência.
Já a fila de prioridade é uma estrutura abstrata que permite inserir elementos com uma prioridade associada, e a remoção ocorre em ordem de prioridade. Min-heaps são uma forma comum de implementá-la por gerenciarem essas operações com eficiência.
Explique o conceito de conjunto disjunto (disjoint-set) e suas aplicações.
Um conjunto disjunto, também chamado de union-find, mantém uma coleção de conjuntos que não se intersectam. Essa estrutura dá suporte a duas operações principais:
- Find: determina a qual conjunto um elemento pertence.
- Union: mescla dois conjuntos em um único.
Há muitas aplicações, com destaque para o algoritmo de Kruskal (encontrar a árvore geradora mínima) e o problema de fluxo em redes para determinar componentes conectados.
Explique o conceito de segment tree e suas aplicações.
Segment tree é uma estrutura projetada para consultas e atualizações eficientes em intervalos de um array. É especialmente útil quando precisamos, repetidamente, somar, encontrar mínimo/máximo ou o MDC em um intervalo específico.
Ela é construída como uma árvore binária, em que cada nó representa um segmento do array. As folhas correspondem a elementos individuais; nós internos agregam valores dos filhos conforme a operação. Tanto atualizações quanto consultas alcançam O(log n).
Como você implementaria uma árvore de sufixos (suffix tree)?
Uma árvore de sufixos armazena todos os sufixos de uma string para responder a consultas de padrão em tempo proporcional ao tamanho do padrão, não do texto. Uma árvore verdadeira usa compressão de arestas para obter O(n) de espaço e geralmente é construída com o algoritmo de Ukkonen — complexo demais para implementar do zero em uma entrevista curta.
Um meio-termo comum é a trie de sufixos, que armazena um caractere por nó. Usa O(n²) de espaço, mas é bem mais simples de escrever e explicar. Em entrevista, vale explicitar esse trade-off.
Aqui vai uma implementação limpa em Python:
class SuffixTrieNode:
def __init__(self):
self.children = {} # Mapa caractere -> nó filho
self.indices = [] # Posições iniciais dos sufixos que passam por este nó
class SuffixTrie:
def __init__(self, text):
self.root = SuffixTrieNode()
self.text = text + "$" # Anexa um terminador único
self._build()
def _build(self):
"""Insere todos os sufixos do texto na trie."""
for i in range(len(self.text)):
self._insert_suffix(i)
def _insert_suffix(self, index):
node = self.root
for i in range(index, len(self.text)):
c = self.text[i]
if c not in node.children:
node.children[c] = SuffixTrieNode()
node = node.children[c]
node.indices.append(index)
def search(self, pattern):
"""Retorna todas as posições iniciais onde `pattern` aparece no texto."""
node = self.root
for c in pattern:
if c not in node.children:
return []
node = node.children[c]
return node.indicesO que são quadtrees e quais suas aplicações mais comuns?
Quadtrees são estruturas hierárquicas que subdividem recursivamente um espaço 2D em quatro quadrantes iguais. Essa técnica de particionamento espacial é muito eficaz em processamento de imagens, detecção de colisão em jogos e sistemas de informações geográficas para armazenamento e consulta espacial eficientes.
Perguntas de entrevista baseadas em cenários
Mostrar que você conhece as estruturas de dados é importante, mas saber quando usá-las do jeito certo faz você se destacar na entrevista. Nesta seção, veremos como aplicar esse conhecimento em situações práticas.
Você está projetando um sistema de caronas. Qual estrutura de dados pode casar motoristas e passageiros?
Por ser um problema em tempo real, você vai precisar de estruturas eficientes.
Eu usaria quadtrees para dados geográficos, filas de prioridade para ranquear os matches por distância e urgência, e tabelas hash para buscas rápidas das localizações de motoristas e passageiros.
Que estrutura de dados usar para recomendar produtos a usuários com base no histórico?
Podemos combinar várias estruturas para recomendar produtos de forma eficaz.
Uma matriz esparsa usuário–item armazena interações; tabelas hash mapeiam usuários e itens com eficiência; filas de prioridade ranqueiam recomendações; e grafos modelam relações usuário–item para análises mais sofisticadas, como detecção de comunidades.
Você trabalha em uma rede social. Que estrutura de dados ajuda a detectar e remover contas de spam?
Um grafo é muito eficaz para detectar e remover spam. Representando usuários como nós e conexões como arestas, é possível analisar a topologia: clusters muito densos, nós isolados e picos súbitos de atividade ajudam a sinalizar contas suspeitas.
Quais estruturas você usaria para entregar mensagens aos destinatários corretos em um chat em tempo real?
Eu usaria uma combinação de estruturas.
Tabelas hash para mapear IDs de usuários às suas conexões, permitindo lookups rápidos. Filas para cada usuário, mantendo a ordem das mensagens. Além disso, árvores (como AVL) para armazenar e consultar status online/offline com atualizações em tempo real.
Você está construindo um corretor ortográfico. Que estruturas usar para armazenar e buscar palavras do dicionário com eficiência?
Para um corretor, a busca eficiente é crucial. A trie é ideal: cada nó representa uma letra e os caminhos formam palavras. Isso permite buscas rápidas por prefixo e sugestões ágeis para correções.
Qual estrutura você usaria em um jogo de estratégia em tempo real para consultar áreas com estruturas e atualizar novas construções?
Nesse cenário, segment trees se destacam. Elas lidam muito bem com consultas por intervalo e atualizações. Podemos representar o mapa do jogo como um array 1D, em que cada posição é uma célula da grade que indica presença ou ausência de uma estrutura.
Dicas para se preparar para uma entrevista sobre estruturas de dados
Eu sei que se preparar para esse tipo de entrevista pode ser desafiador, mas uma abordagem estruturada deixa tudo mais leve!
Foque em dominar os conceitos fundamentais: arrays, listas ligadas, pilhas, filas, árvores, grafos e tabelas hash. Entenda seus princípios, como gerenciam dados e as complexidades de tempo de operações como inserção, remoção e busca.
Conhecer os conceitos é ótimo, mas não basta. Você deve saber implementar essas estruturas do zero. Para isso, aproveite os cursos da DataCamp e os desafios de código que vão afiar sua resolução de problemas.
Entender os trade-offs é chave. Por exemplo, arrays oferecem acesso rápido, mas inserções e exclusões podem ser custosas; listas ligadas facilitam modificações, mas exigem percursos para acesso. Esteja pronto para discutir essas trocas na entrevista.
Lembre-se: comunicação é tão importante quanto código. Entrevistadores buscam quem adapta a explicação ao público. Como discutido no podcast DataFramed sobre o futuro das carreiras em dados:
Você precisa ser capaz de entregar qualquer insight de um jeito que uma criança de seis anos entenda e também de um jeito que satisfaça a mim ou alguém ainda mais técnico. Se você realmente domina o assunto, consegue simplificar bastante, mas também tornar tão complexo que, honestamente, só quem está lá no topo em expertise técnica vai acompanhar.
Mo Chen, Data & Analytics Manager at NatWest Group
Torne-se certificado em ciência de dados
Melhore sua carreira como cientista de dados profissional.
Author
Maria Eugenia Inzaugarat
Tópicos
