Perguntas de Entrevista sobre Algoritmos em Zig
Perguntas de algoritmos e estruturas de dados são universais em entrevistas de programação, independente da linguagem. Implementar algoritmos em Zig demonstra domínio da linguagem e compreensão de conceitos de baixo nível como gerenciamento de memória, ponteiros e performance. Este guia cobre implementações idiomáticas em Zig.
Estruturas de Dados
Implemente uma ArrayList genérica em Zig.
fn ArrayList(comptime T: type) type {
return struct {
items: []T,
capacity: usize,
allocator: std.mem.Allocator,
const Self = @This();
pub fn init(allocator: std.mem.Allocator) Self {
return .{ .items = &[_]T{}, .capacity = 0, .allocator = allocator };
}
pub fn append(self: *Self, item: T) !void {
if (self.items.len >= self.capacity) {
try self.grow();
}
self.items.len += 1;
self.items[self.items.len - 1] = item;
}
fn grow(self: *Self) !void {
const new_cap = if (self.capacity == 0) 8 else self.capacity * 2;
self.items = try self.allocator.realloc(self.items, new_cap);
self.capacity = new_cap;
}
pub fn deinit(self: *Self) void {
self.allocator.free(self.items.ptr[0..self.capacity]);
}
};
}
Note como o allocator é recebido como parâmetro (padrão idiomático Zig) e deinit libera a memória. Veja perguntas de memória.
Implemente uma HashMap simples.
Uma HashMap básica com chaining para resolução de colisões demonstra allocators, slices e optionals:
fn HashMap(comptime K: type, comptime V: type) type {
return struct {
buckets: []?*Node,
allocator: std.mem.Allocator,
const Node = struct { key: K, value: V, next: ?*Node };
const Self = @This();
pub fn get(self: Self, key: K) ?V {
const idx = hash(key) % self.buckets.len;
var node = self.buckets[idx];
while (node) |n| {
if (std.mem.eql(u8, n.key, key)) return n.value;
node = n.next;
}
return null;
}
};
}
Algoritmos de Ordenação
Implemente merge sort em Zig.
fn mergeSort(comptime T: type, items: []T, allocator: std.mem.Allocator) !void {
if (items.len <= 1) return;
const mid = items.len / 2;
const temp = try allocator.alloc(T, items.len);
defer allocator.free(temp);
try mergeSort(T, items[0..mid], allocator);
try mergeSort(T, items[mid..], allocator);
// Merge
var i: usize = 0;
var j: usize = mid;
var k: usize = 0;
while (i < mid and j < items.len) {
if (items[i] <= items[j]) {
temp[k] = items[i];
i += 1;
} else {
temp[k] = items[j];
j += 1;
}
k += 1;
}
@memcpy(temp[k..], items[i..mid]);
@memcpy(temp[k + mid - i..], items[j..]);
@memcpy(items, temp[0..items.len]);
}
Note que allocator é necessário para o buffer temporário — em Zig, alocações são sempre explícitas.
Algoritmos de Busca e Grafos
Implemente busca binária.
fn buscaBinaria(comptime T: type, items: []const T, alvo: T) ?usize {
var low: usize = 0;
var high: usize = items.len;
while (low < high) {
const mid = low + (high - low) / 2;
if (items[mid] == alvo) return mid;
if (items[mid] < alvo) {
low = mid + 1;
} else {
high = mid;
}
}
return null;
}
Implemente BFS (busca em largura).
fn bfs(grafo: []const []const usize, inicio: usize, allocator: std.mem.Allocator) ![]bool {
var visitado = try allocator.alloc(bool, grafo.len);
@memset(visitado, false);
var fila = std.ArrayList(usize).init(allocator);
defer fila.deinit();
visitado[inicio] = true;
try fila.append(inicio);
while (fila.items.len > 0) {
const atual = fila.orderedRemove(0);
for (grafo[atual]) |vizinho| {
if (!visitado[vizinho]) {
visitado[vizinho] = true;
try fila.append(vizinho);
}
}
}
return visitado;
}
Programação Dinâmica
Explique a diferença entre memoização e tabulação com um exemplo em Zig.
Memoização é top-down: resolve o problema recursivamente, armazenando resultados em cache para evitar recomputação. Tabulação é bottom-up: preenche uma tabela iterativamente na ordem correta.
// Memoização — top-down para Fibonacci
fn fibMemo(n: u64, cache: []?u64) u64 {
if (n <= 1) return n;
if (cache[n]) |v| return v;
const resultado = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
cache[n] = resultado;
return resultado;
}
// Tabulação — bottom-up para Fibonacci
fn fibTabela(n: u64, tabela: []u64) u64 {
tabela[0] = 0;
tabela[1] = 1;
var i: usize = 2;
while (i <= n) : (i += 1) tabela[i] = tabela[i-1] + tabela[i-2];
return tabela[n];
}
Em entrevistas, demonstre que você entende as trocas: memoização é mais natural de escrever, mas tabulação é mais eficiente em cache de CPU por ter acesso sequencial à memória.
Como implementar quicksort in-place em Zig?
fn quicksort(comptime T: type, items: []T) void {
if (items.len <= 1) return;
const pivo = items[items.len / 2];
var esq: usize = 0;
var dir: usize = items.len - 1;
while (esq <= dir) {
while (items[esq] < pivo) esq += 1;
while (items[dir] > pivo) dir -= 1;
if (esq <= dir) {
std.mem.swap(T, &items[esq], &items[dir]);
esq += 1;
if (dir > 0) dir -= 1;
}
}
quicksort(T, items[0..dir + 1]);
quicksort(T, items[esq..]);
}
Note que quicksort in-place não precisa de allocator — opera diretamente no slice passado. A complexidade é O(n log n) em média e O(n²) no pior caso.
Dicas para Entrevistas
- Sempre considere o allocator: Em Zig, qualquer estrutura que aloca memória precisa de um allocator.
- Use
deferpara cleanup: Mesmo em algoritmos, garanta liberação de memória temporária. - Comptime para generic: Use
comptime T: typepara algoritmos genéricos. - Error handling: Funções que alocam devem retornar
!Te usartry. - Slices são seus amigos: Use slicing (
arr[low..high]) para subproblemas. - Complexidade explícita: Sempre mencione a complexidade de tempo e espaço da sua solução.
- Safety checks: Em modo Debug, Zig verifica bounds de arrays automaticamente — mencione isso como vantagem.
Pratique com desafios de código e revise perguntas básicas. Construa implementações para seu portfólio e estude tutoriais para mais exemplos.