Este guia abrange uma variedade de tópicos comumente encontrados em entrevistas técnicas, focando em estruturas de dados, algoritmos, padrões de projeto e cenários de programação.
Preparação Essencial
Revisão de Problemas Clássicos: É altamente recomendável resolver e revisitar os problemas do LeetCode Hot 100 e do "Cracking the Coding Interview" (ou "Entrevista com o Código") pelo menos duas vezes. Uma grande porcentagem das questões de algoritmos em entrevistas são derviadas dessas coleções.
Padrões de Projeto
Padrões Fundamentais: Esteja familiarizado com padrões de projeto comuns, como o Singleton e o Factory. O padrão Singleotn, em particular, é frequentemente solicitado em sua forma thread-safe.
Implementação de Singleton (Thread-Safe)
A seguir, um exemplo de implementação de Singleton thread-safe em C++:
class Singleton {
private:
static Singleton* instance;
// Construtor privado para evitar instanciação externa
Singleton() {
// Inicialização de membros, se necessário
}
// Previne cópia e atribuição
Singleton(const Singleton&) = delete;
Singleton& operator=(const Singleton&) = delete;
public:
static Singleton* getInstance() {
// Implementação thread-safe (pode variar dependendo do padrão de inicialização)
// Exemplo básico com mutex (simplificado para ilustração):
static std::once_flag flag;
std::call_once([&]() {
if (instance == nullptr) {
instance = new Singleton();
}
});
return instance;
}
// Método para limpeza, se necessário (geralmente via smart pointers ou RAII)
static void destroyInstance() {
// Lógica de destruição segura
}
};
Singleton* Singleton::instance = nullptr; // Inicialização estática
Problemas de Concorrência
Impressão Alternada de Caracteres por Múltiplos Threads
Um cenário comum é ter múltiplos threads imprimindo caracteres em uma ordem específica (por exemplo, A, B, C, A, B, C...). Isso geralmente é resolvido usando mutexes e variáveis de condição para sincronização.
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <vector>
std::mutex mtx;
std::condition_variable cv;
int turn = 0; // 0 para A, 1 para B, 2 para C
void printChar(int threadId, char charToPrint, int& currentTurn, int maxCount) {
for (int i = 0; i < maxCount; ++i) {
std::unique_lock<:mutex> lock(mtx);
cv.wait(lock, [&] { return turn == threadId; });
std::cout << "Thread " << threadId + 1 << ": " << charToPrint << std::endl;
turn = (turn + 1) % 3; // Avança para o próximo thread
cv.notify_all();
}
}
int main() {
const int printCount = 10;
std::thread tA(printChar, 0, 'A', std::ref(turn), printCount);
std::thread tB(printChar, 1, 'B', std::ref(turn), printCount);
std::thread tC(printChar, 2, 'C', std::ref(turn), printCount);
tA.join();
tB.join();
tC.join();
std::cout << "Main thread finished." << std::endl;
return 0;
}
</:mutex></vector></condition_variable></mutex></thread></iostream>
Algoritmos e Estruturas de Dados
Login via QR Code
Descrever o fluxo de um sistema de login que utiliza QR codes envolve a comunicação entre o cliente (app escaneando o código) e o servidor, validação do código e confirmação do login.
Troca de Variáveis Sem Temporário
É possível trocar os valores de duas variáveis inteiras sem usar uma variável temporária, utilizando operações bitwise XOR.
void swapXOR(int& a, int& b) {
if (&a == &b) return; // Evita auto-troca se os endereços forem os mesmos
a = a ^ b;
b = a ^ b; // b agora tem o valor original de a
a = a ^ b; // a agora tem o valor original de b
}
Implementação de strcpy / memcpy (Considerando Sobrescrita de Memória)
A implementação de funções como strcpy e memcpy deve considerar o caso em que as regiões de memória de origem e destino podem se sobrepor. Para isso, memmove é geralmente a função mais segura, pois lida corretamente com sobreposições.
QuickSort
O QuickSort é um algoritmo de ordenação eficiente. A escolha do pivô é crucial para o desempenho.
#include <vector>
#include <algorithm> // Para std::swap
// Função auxiliar para trocar elementos em um vetor
void swapElements(std::vector<int>& vec, int i, int j) {
std::swap(vec[i], vec[j]);
}
// Função de particionamento (estratégia comum: usar o último elemento como pivô)
int partition(std::vector<int>& vec, int low, int high) {
int pivot = vec[high];
int i = (low - 1);
for (int j = low; j <= high - 1; ++j) {
if (vec[j] < pivot) {
i++;
swapElements(vec, i, j);
}
}
swapElements(vec, i + 1, high);
return (i + 1);
}
// Função principal do QuickSort
void quickSort(std::vector<int>& vec, int low, int high) {
if (low < high) {
int pi = partition(vec, low, high);
quickSort(vec, low, pi - 1);
quickSort(vec, pi + 1, high);
}
}
</int></int></int></algorithm></vector>
HeapSort
O HeapSort utiliza a estrutura de dados heap (geralmente um max-heap para ordenação crescente) para ordenar os elementos.
#include <vector>
#include <algorithm> // Para std::swap
// Função para reconstruir o heap (max-heap)
void heapify(std::vector<int>& arr, int n, int i) {
int largest = i; // Inicializa largest como raiz
int left = 2 * i + 1; // Filho esquerdo
int right = 2 * i + 2; // Filho direito
// Se o filho esquerdo for maior que a raiz
if (left < n && arr[left] > arr[largest])
largest = left;
// Se o filho direito for maior que o maior até agora
if (right < n && arr[right] > arr[largest])
largest = right;
// Se o maior não for a raiz
if (largest != i) {
std::swap(arr[i], arr[largest]);
// Recursivamente heapify o sub-árvore afetado
heapify(arr, n, largest);
}
}
// Função principal do HeapSort
void heapSort(std::vector<int>& arr) {
int n = arr.size();
// Constrói um max-heap.
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Pega o elemento máximo da heap e o coloca no final
// Reduz o tamanho da heap a cada iteração
for (int i = n - 1; i > 0; i--) {
std::swap(arr[0], arr[i]); // Move o atual root para o final
heapify(arr, i, 0); // chama max heapify on the reduced heap
}
}
</int></int></algorithm></vector>
Insertion Sort
O Insertion Sort constrói a lista ordenada um item de cada vez.
#include <vector>
void insertionSort(std::vector<int>& nums) {
int n = nums.size();
for (int i = 1; i < n; ++i) {
int key = nums[i];
int j = i - 1;
// Move os elementos de nums[0..i-1], que são maiores que key,
// para uma posição à frente de sua posição atual
while (j >= 0 && nums[j] > key) {
nums[j + 1] = nums[j];
j = j - 1;
}
nums[j + 1] = key;
}
}
</int></vector>
Otimizações do QuickSort
O QuickSort pode ter problemas de desempenho em certos casos (como arrays já ordenados ou quase ordenados). Otimizações incluem:
- Seleção de Pivô: Usar a mediana de três (primeiro, meio, último elemento) ou um pivô aleatório.
- Otimização para Pequenos Subarrays: Alternar para Insertion Sort quando o tamanho do subarray for pequeno.
- Agrupamento de Elementos Iguais: Lidar com elementos iguais ao pivô de forma eficiente.
- Otimização de Recursão: Usar loops para a recursão mais profunda.
- Paralelização: Utilizar múltiplos threads para processar subarrays.
Reversão de Lista Ligada
Reverter uma lista ligada pode ser feito iterativamente ou recursivamente.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
ListNode* nextTemp = nullptr;
while (current != nullptr) {
nextTemp = current->next; // Guarda o próximo nó
current->next = prev; // Inverte o ponteiro 'next'
prev = current; // Move 'prev' para frente
current = nextTemp; // Move 'current' para frente
}
return prev; // 'prev' será o novo head
}
Problemas "Top K"
Encontrar os K maiores (ou menores) elementos, ou o K-ésimo maior (ou menor) elemento em um conjunto de dados. Várias abordagens são possíveis:
- Heaps (Min-Heap/Max-Heap): Use um min-heap para encontrar os K maiores elementos e um max-heap para os K menores. A complexidade é O(N log K).
- QuickSelect: Um algoritmo derivado do QuickSort que foca em apenas uma partição a cada passo. Complexidade média O(N), pior caso O(N^2).
- Ordenação Completa: Ordenar o array inteiro e pegar os K primeiros/últimos elementos. Complexidade O(N log N).
- Seleção Parcial: Iterativamente encontrar o maior/menor K vezes. Complexidade O(N*K).
- Divisão e Conquista: Dividir os dados em M grupos, encontrar Top K em cada grupo e depois combinar os resultados.
Exemplo com Min-Heap (para Top K maiores)
Ao processar N elementos, mantenha um min-heap de tamanho K. Se um novo elemento for maior que o topo do heap, remova o topo e insira o novo elemento. A complexidade de inserção em um heap é O(log K).
Exemplo com QuickSelect (para K-ésimo Maior)
QuickSelect particiona o array em torno de um pivô. Se o pivô estiver na posição K, encontramos o elemento. Caso contrário, recursivamente aplicamos QuickSelect na partição correta (esquerda se K for menor, direita se K for maior).
// Implementação em Java para ilustração
public class TopK {
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, k, 0, nums.length - 1);
}
private int quickSelect(int[] arr, int k, int left, int right) {
if (left == right) {
return arr[right];
}
// Escolha um pivô (ex: aleatório, mediana de três)
int pivotIndex = partition(arr, left, right);
// O número de elementos à esquerda do pivô + o próprio pivô
int elementsCount = pivotIndex - left + 1;
if (elementsCount == k) {
return arr[pivotIndex];
} else if (elementsCount > k) {
// O k-ésimo maior está na partição esquerda
return quickSelect(arr, k, left, pivotIndex - 1);
} else {
// O k-ésimo maior está na partição direita
// Ajustamos k para procurar o (k - elementsCount)-ésimo maior na sublista direita
return quickSelect(arr, k - elementsCount, pivotIndex + 1, right);
}
}
// Função de particionamento similar ao QuickSort
private int partition(int[] arr, int left, int right) {
// Estratégia simples: usar o último elemento como pivô
int pivotValue = arr[right];
int storeIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] < pivotValue) { // Para k-ésimo maior, particionamos com base em '<'
swap(arr, storeIndex, i);
storeIndex++;
}
}
swap(arr, storeIndex, right); // Coloca o pivô em sua posição final
return storeIndex;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Ordenação Externa
Ordenando Grandes Volumes de Dados (Ordem de Magnitude de Gigabytes)
Para dados que não cabem na memória RAM, utiliza-se a Ordenação Externa. O processo envolve:
- Divisão: Dividir o arquivo grande em múltiplos arquivos menores, cada um cabendo na memória.
- Ordenação Interna: Ordenar cada arquivo menor usando um algoritmo eficiente como QuickSort ou HeapSort.
- Fusão (Merge): Realizar uma fusão de M-vias (onde M é o número de arquivos ordenados) para combinar os arquivos ordenados em um único arquivo final ordenado. Isso é semelhante ao MergeSort, mas com múltiplos "streams" de entrada.
Árvores e Tabelas Hash
Construção de Árvore Binária a partir de Pré-ordem com Marcadores Nulos
É possível reconstruir uma árvore binária a partir de sua representação em pré-ordem, onde "null" é usado para indicar nós ausentes. Isso é útil para serializar e desserializar árvores.
#include <vector>
#include <string>
#include <queue>
struct TreeNode {
std::string val;
TreeNode *left;
TreeNode *right;
TreeNode(std::string x) : val(x), left(nulptr), right(nullptr) {}
};
// Função para construir a árvore a partir do vetor (pré-ordem com null)
TreeNode* buildTreeFromPreorder(const std::vector<:string>& nodes, int& index) {
if (index >= nodes.size() || nodes[index] == "null") {
index++;
return nullptr;
}
TreeNode* root = new TreeNode(nodes[index]);
index++;
root->left = buildTreeFromPreorder(nodes, index);
root->right = buildTreeFromPreorder(nodes, index);
return root;
}
// Função auxiliar para serializar a árvore para um vetor (pré-ordem com null)
void serializePreorder(TreeNode* root, std::vector<:string>& result) {
if (!root) {
result.push_back("null");
return;
}
result.push_back(root->val);
serializePreorder(root->left, result);
serializePreorder(root->right, result);
}
// Exemplo de uso
// std::vector<:string> preorder = {"1", "2", "null", "null", "3", "4", "null", "null", "5", "null", "null"};
// int index = 0;
// TreeNode* root = buildTreeFromPreorder(preorder, index);
// std::vector<:string> serialized;
// serializePreorder(root, serialized); // Reconstrui o vetor original (ou similar)
</:string></:string></:string></:string></queue></string></vector>
Árvores B e B+
Árvore B: Uma árvore de busca balanceada multi-vias, otimizada para sistemas que leem e escrevem grandes blocos de dados. Usada em sistemas de arquivos. Complexidade de busca O(log N).
Árvore B+: Uma variação da Árvore B onde todos os dados são armazenados nos nós folha, e as folhas são ligadas sequencialmente. Predominantemente usada para indexação em bancos de dados, pois otimiza varreduras (scans).
Árvores Rubro-Negras (Red-Black Trees)
São árvores de busca binária balanceadas que garantem que o caminho mais longo da raiz a uma folha não seja mais que o dobro do caminho mais curto. Propriedades mantêm o balanceamento. Usadas em implementações de map e set em STL (C++). Complexidade O(log N) para inserção, deleção e busca.
Consultas SQL
Para selecionar as primeiras 1000 linhas de uma tabela, a sintaxe SQL padrão é:
SELECT *
FROM sua_tabela
LIMIT 1000;
(A sintaxe exata pode variar ligeiramente entre SGBDs, como TOP 1000 no SQL Server).
Probabilidade e Estatística
Probabilidade da Soma de N Dados
Calcular a probabilidade de obter uma soma específica 'm' ao lançar 'N' dados envolve combinatória e, possivelmente, programação dinâmica para calcular o número de maneiras de alcançar a soma.
Gerenciamento de Grandes Volumes de Dados
Bitmap
Princípio: Um Bitmap usa um bit para representar a presença ou ausência de um elemento. É eficiente em termos de espaço para conjuntos de inteiros densos dentro de um intervalo razoável.
Uso: Ordenação e compressão de dados. Para um inteiro N, o bit na posição N % tamanho\_do\_bloco (geralmente 32 ou 64) em um array de inteiros é definido.
Vantagens: Alta eficiência de operação e baixo uso de memória para dados densos.
Desvantagens: Não lida bem com dados esparsos ou repetidos (embora variações como 2-bit bitmaps possam tratar contagens).
Cálculos de Indexação: Para um array bitmap\[\] de inteiros de 32 bits:
- Índice do array:
N >> 5(equivalente aN / 32) - Posição do bit dentro do inteiro:
N & 0x1F(equivalente aN % 32) - Para marcar N como presente:
bitmap\[N >> 5\] |= (1 << (N & 0x1F));
Filtro de Bloom
Princípio: Uma estrutura de dados probabilística que verifica eficientemente se um elemento *pode* estar em um conjunto. É um vetor de bits e múltiplos (k) funções de hash.
Operação: Para inserir um item, aplique as k funções de hash e defina os bits correspondentes no vetor. Para verificar, aplique as k funções e veja se *todos* os bits estão definidos. Se algum bit não estiver definido, o elemento definitivamente não está no conjunto. Se todos estiverem definidos, ele *provavelmente* está (risco de falsos positivos).
Vantagens: Extremamente eficiente em espaço e tempo (inserção/verificação O(k)).
Desvantagens: Não suporta remoção (a menos que variações com contadores sejam usadas), e há uma probabilidade de falsos positivos.
Persistência: Para grandes volumes e limites de memória, filtros de Bloom podem ser armazenados em disco e carregados em partes conforme necessário.
Algoritmos de Grafos
Dijkstra
Algoritmo para encontrar os caminhos mais curtos de um único vértice de origem para todos os outros vértices em um grafo com pesos de aresta não negativos.
Árvore Geradora Mínima (MST)
Algoritmos como Prim e Kruskal encontram um subconjunto de arestas que conecta todos os vértices com o menor peso total possível.
Estruturas de Dados Dinâmicas
Array Dinâmico (Similar a std::vector)
A implementação de um array dinâmico envolve um array subjacente de tamanho fixo. Quando o array enche, um novo array maior é alocado, os elementos são copiados, e o array antigo é desalocado. A estratégia de redimensionamento (geralmente dobrar o tamanho) garante complexidade amortizada O(1) para inserções.
Fila Thread-Safe
Uma fila que pode ser acessada de múltiplos threads simultaneamente requer sincronização (mutexes e variáveis de condição) para operações de enfileirar (enqueue) e desenfileirar (dequeue), garantindo que as operações sejam atômicas e que os threads esperem corretamente quando a fila estiver cheia ou vazia.
#include <vector>
#include <mutex>
#include <condition_variable>
#include <queue> // Pode ser usada como base ou implementada manualmente
template <typename capacity="" size_t="" t="">
class ThreadSafeQueue {
private:
std::vector<t> buffer;
size_t head = 0;
size_t tail = 0;
size_t count = 0;
std::mutex mtx;
std::condition_variable not_full_cv;
std::condition_variable not_empty_cv;
public:
ThreadSafeQueue() : buffer(Capacity) {}
bool enqueue(const T& value) {
std::unique_lock<:mutex> lock(mtx);
not_full_cv.wait(lock, [this] { return count < Capacity; }); // Espera se a fila estiver cheia
buffer[tail] = value;
tail = (tail + 1) % Capacity;
count++;
not_empty_cv.notify_one(); // Notifica um consumidor que há um item
return true;
}
T dequeue() {
std::unique_lock<:mutex> lock(mtx);
not_empty_cv.wait(lock, [this] { return count > 0; }); // Espera se a fila estiver vazia
T value = buffer[head];
head = (head + 1) % Capacity;
count--;
not_full_cv.notify_one(); // Notifica um produtor que há espaço
return value;
}
bool isEmpty() const {
std::lock_guard<:mutex> lock(mtx);
return count == 0;
}
bool isFull() const {
std::lock_guard<:mutex> lock(mtx);
return count == Capacity;
}
};
</:mutex></:mutex></:mutex></:mutex></t></typename></queue></condition_variable></mutex></vector>
Cenários de Uso: Buffers de comunicação entre produtores e consumidores, gerenciamento de tarefas em sistemas multi-threaded, processamento assíncrono.
Outros Tópicos
- Hash Trees / Merkle Trees: Usadas para verificar a integridade de dados de forma eficiente.
- Consistent Hashing: Técnica usada em sistemas distribuídos para mapear chaves a servidores de forma que a adição ou remoção de servidores cause o mínimo de remapeamento de chaves.
- Shell Sort: Uma melhoria do Insertion Sort que compara elementos distantes entre si.
- B-Tree vs. B+ Tree vs. Red-Black Tree: Entender as diferenças, vantagens e cenários de aplicação de cada um.