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;
}
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.
Pratique com desafios de código e revise perguntas básicas. Construa implementações para seu portfólio e estude tutoriais para mais exemplos.