Desafio de Código Zig 2 — Estruturas de Dados

9 min de leitura
entrevistas desafios estruturas-dados código

Desafio de Código Zig #2 — Estruturas de Dados

Implementar estruturas de dados do zero é um exercício fundamental em entrevistas. Em Zig, isso demonstra domínio de alocação manual de memória, ponteiros opcionais, generics via comptime e tratamento de erros. Estes desafios cobrem implementações essenciais.

Desafio 1: Fila com Duas Pilhas

Problema: Implemente uma fila (FIFO) usando duas pilhas.

const std = @import("std");

fn FilaDuasPilhas(comptime T: type) type {
    return struct {
        const Self = @This();

        entrada: std.ArrayList(T),  // Pilha de entrada
        saida: std.ArrayList(T),    // Pilha de saída

        pub fn init(allocator: std.mem.Allocator) Self {
            return .{
                .entrada = std.ArrayList(T).init(allocator),
                .saida = std.ArrayList(T).init(allocator),
            };
        }

        pub fn deinit(self: *Self) void {
            self.entrada.deinit();
            self.saida.deinit();
        }

        pub fn enfileirar(self: *Self, item: T) !void {
            try self.entrada.append(item);
        }

        pub fn desenfileirar(self: *Self) ?T {
            if (self.saida.items.len == 0) {
                // Transfere da entrada para a saída (inverte a ordem)
                while (self.entrada.items.len > 0) {
                    self.saida.append(self.entrada.pop()) catch return null;
                }
            }
            if (self.saida.items.len == 0) return null;
            return self.saida.pop();
        }

        pub fn espiar(self: *Self) ?T {
            if (self.saida.items.len == 0) {
                while (self.entrada.items.len > 0) {
                    self.saida.append(self.entrada.pop()) catch return null;
                }
            }
            if (self.saida.items.len == 0) return null;
            return self.saida.items[self.saida.items.len - 1];
        }

        pub fn tamanho(self: *const Self) usize {
            return self.entrada.items.len + self.saida.items.len;
        }
    };
}

test "fila com duas pilhas" {
    const testing = std.testing;
    var fila = FilaDuasPilhas(i32).init(testing.allocator);
    defer fila.deinit();

    try fila.enfileirar(1);
    try fila.enfileirar(2);
    try fila.enfileirar(3);

    try testing.expectEqual(@as(?i32, 1), fila.desenfileirar());
    try testing.expectEqual(@as(?i32, 2), fila.desenfileirar());

    try fila.enfileirar(4);
    try testing.expectEqual(@as(?i32, 3), fila.desenfileirar());
    try testing.expectEqual(@as(?i32, 4), fila.desenfileirar());
    try testing.expectEqual(@as(?i32, null), fila.desenfileirar());
}

Análise: Enfileirar O(1), desenfileirar O(1) amortizado. Cada elemento é movido entre pilhas no máximo uma vez.

Desafio 2: Encontrar o k-ésimo Maior Elemento

Problema: Dado um array, encontre o k-ésimo maior elemento eficientemente.

const std = @import("std");

/// Usa min-heap de tamanho k.
fn kesimoMaior(allocator: std.mem.Allocator, nums: []const i32, k: usize) !i32 {
    // Min-heap via PriorityQueue
    var heap = std.PriorityQueue(i32, void, struct {
        fn lessThan(_: void, a: i32, b: i32) std.math.Order {
            return std.math.order(a, b);
        }
    }.lessThan).init(allocator, {});
    defer heap.deinit();

    for (nums) |num| {
        try heap.add(num);
        if (heap.count() > k) {
            _ = heap.remove();
        }
    }

    return heap.peek().?;
}

/// Solução alternativa com particionamento (Quickselect).
fn kesimoMaiorQuickselect(nums: []i32, k: usize) i32 {
    const alvo = nums.len - k;
    var esq: usize = 0;
    var dir: usize = nums.len - 1;

    while (esq < dir) {
        const pivo = particionar(nums, esq, dir);
        if (pivo == alvo) return nums[pivo]
        else if (pivo < alvo) esq = pivo + 1
        else dir = pivo - 1;
    }
    return nums[esq];
}

fn particionar(nums: []i32, esq: usize, dir: usize) usize {
    const pivo = nums[dir];
    var i: usize = esq;
    for (esq..dir) |j| {
        if (nums[j] <= pivo) {
            const tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i += 1;
        }
    }
    const tmp = nums[i];
    nums[i] = nums[dir];
    nums[dir] = tmp;
    return i;
}

test "k-ésimo maior" {
    const testing = std.testing;
    const allocator = testing.allocator;

    const nums = [_]i32{ 3, 2, 1, 5, 6, 4 };
    try testing.expectEqual(@as(i32, 5), try kesimoMaior(allocator, &nums, 2));

    var nums2 = [_]i32{ 3, 2, 3, 1, 2, 4, 5, 5, 6 };
    try testing.expectEqual(@as(i32, 4), kesimoMaiorQuickselect(&nums2, 4));
}

Desafio 3: Serializar e Deserializar Árvore Binária

Problema: Converta uma árvore binária para string e reconstrua-a.

const std = @import("std");
const Allocator = std.mem.Allocator;

fn ArvoreBin(comptime T: type) type {
    return struct {
        const Self = @This();
        const No = struct {
            valor: T,
            esq: ?*No,
            dir: ?*No,
        };

        raiz: ?*No,
        allocator: Allocator,

        pub fn init(allocator: Allocator) Self {
            return .{ .raiz = null, .allocator = allocator };
        }

        pub fn criarNo(self: *Self, valor: T) !*No {
            const no = try self.allocator.create(No);
            no.* = .{ .valor = valor, .esq = null, .dir = null };
            return no;
        }

        /// Serializa via pré-ordem: "1,2,#,#,3,4,#,#,5,#,#"
        pub fn serializar(self: *const Self, allocator: Allocator) ![]u8 {
            var resultado = std.ArrayList(u8).init(allocator);
            try serializarNo(self.raiz, &resultado);
            return try resultado.toOwnedSlice();
        }

        fn serializarNo(no: ?*No, resultado: *std.ArrayList(u8)) !void {
            if (no == null) {
                try resultado.appendSlice("#,");
                return;
            }
            const n = no.?;
            var buf: [20]u8 = undefined;
            const num_str = std.fmt.bufPrint(&buf, "{d},", .{n.valor}) catch unreachable;
            try resultado.appendSlice(num_str);
            try serializarNo(n.esq, resultado);
            try serializarNo(n.dir, resultado);
        }

        /// Deserializa a partir da string serializada.
        pub fn deserializar(self: *Self, dados: []const u8) !void {
            var iter = std.mem.splitScalar(u8, dados, ',');
            self.raiz = try self.deserializarNo(&iter);
        }

        fn deserializarNo(self: *Self, iter: *std.mem.SplitIterator(u8, .scalar)) !?*No {
            const token = iter.next() orelse return null;
            if (token.len == 0) return null;
            if (std.mem.eql(u8, token, "#")) return null;

            const valor = std.fmt.parseInt(T, token, 10) catch return null;
            const no = try self.criarNo(valor);
            no.esq = try self.deserializarNo(iter);
            no.dir = try self.deserializarNo(iter);
            return no;
        }

        pub fn deinit(self: *Self) void {
            liberarNo(self.allocator, self.raiz);
        }

        fn liberarNo(allocator: Allocator, no: ?*No) void {
            if (no) |n| {
                liberarNo(allocator, n.esq);
                liberarNo(allocator, n.dir);
                allocator.destroy(n);
            }
        }
    };
}

test "serializar e deserializar árvore" {
    const testing = std.testing;
    const allocator = testing.allocator;

    var arvore = ArvoreBin(i32).init(allocator);
    defer arvore.deinit();

    // Constrói: 1 -> (2, 3 -> (4, 5))
    arvore.raiz = try arvore.criarNo(1);
    arvore.raiz.?.esq = try arvore.criarNo(2);
    arvore.raiz.?.dir = try arvore.criarNo(3);
    arvore.raiz.?.dir.?.esq = try arvore.criarNo(4);
    arvore.raiz.?.dir.?.dir = try arvore.criarNo(5);

    const serializado = try arvore.serializar(allocator);
    defer allocator.free(serializado);

    // Deserializa em nova árvore
    var arvore2 = ArvoreBin(i32).init(allocator);
    defer arvore2.deinit();
    try arvore2.deserializar(serializado);

    // Verifica estrutura
    try testing.expectEqual(@as(i32, 1), arvore2.raiz.?.valor);
    try testing.expectEqual(@as(i32, 2), arvore2.raiz.?.esq.?.valor);
    try testing.expectEqual(@as(i32, 3), arvore2.raiz.?.dir.?.valor);
}

Desafio 4: Mediana em Stream de Dados

Problema: Implemente uma estrutura que calcula a mediana à medida que números são adicionados.

const std = @import("std");

/// Usa dois heaps: max-heap para metade inferior, min-heap para superior.
const MedianaStream = struct {
    const Self = @This();

    // Max-heap (metade inferior) — armazena os menores valores
    inferior: std.PriorityQueue(i32, void, struct {
        fn cmp(_: void, a: i32, b: i32) std.math.Order {
            return std.math.order(b, a); // Invertido para max-heap
        }
    }.cmp),

    // Min-heap (metade superior) — armazena os maiores valores
    superior: std.PriorityQueue(i32, void, struct {
        fn cmp(_: void, a: i32, b: i32) std.math.Order {
            return std.math.order(a, b);
        }
    }.cmp),

    pub fn init(allocator: std.mem.Allocator) Self {
        return .{
            .inferior = @TypeOf(@as(Self, undefined).inferior).init(allocator, {}),
            .superior = @TypeOf(@as(Self, undefined).superior).init(allocator, {}),
        };
    }

    pub fn deinit(self: *Self) void {
        self.inferior.deinit();
        self.superior.deinit();
    }

    pub fn adicionar(self: *Self, num: i32) !void {
        // Sempre adiciona na metade inferior primeiro
        try self.inferior.add(num);

        // Garante que topo da inferior <= topo da superior
        if (self.superior.count() > 0 and self.inferior.peek().? > self.superior.peek().?) {
            try self.superior.add(self.inferior.remove());
        }

        // Balanceia tamanhos (diferença máxima de 1)
        if (self.inferior.count() > self.superior.count() + 1) {
            try self.superior.add(self.inferior.remove());
        } else if (self.superior.count() > self.inferior.count()) {
            try self.inferior.add(self.superior.remove());
        }
    }

    pub fn mediana(self: *Self) f64 {
        if (self.inferior.count() > self.superior.count()) {
            return @floatFromInt(self.inferior.peek().?);
        }
        const a: f64 = @floatFromInt(self.inferior.peek().?);
        const b: f64 = @floatFromInt(self.superior.peek().?);
        return (a + b) / 2.0;
    }
};

test "mediana em stream" {
    const testing = std.testing;

    var ms = MedianaStream.init(testing.allocator);
    defer ms.deinit();

    try ms.adicionar(1);
    try testing.expectEqual(@as(f64, 1.0), ms.mediana());

    try ms.adicionar(2);
    try testing.expectEqual(@as(f64, 1.5), ms.mediana());

    try ms.adicionar(3);
    try testing.expectEqual(@as(f64, 2.0), ms.mediana());
}

Desafio 5: Detectar Ciclo em Lista Encadeada

Problema: Determine se uma lista encadeada possui ciclo (algoritmo de Floyd).

const std = @import("std");

fn ListaEncadeada(comptime T: type) type {
    return struct {
        const Self = @This();
        const No = struct {
            valor: T,
            proximo: ?*No,
        };

        head: ?*No,
        allocator: std.mem.Allocator,

        pub fn init(allocator: std.mem.Allocator) Self {
            return .{ .head = null, .allocator = allocator };
        }

        pub fn adicionar(self: *Self, valor: T) !*No {
            const no = try self.allocator.create(No);
            no.* = .{ .valor = valor, .proximo = self.head };
            self.head = no;
            return no;
        }

        /// Floyd's Cycle Detection — O(n) tempo, O(1) espaço.
        pub fn temCiclo(self: *const Self) bool {
            var lento = self.head;
            var rapido = self.head;

            while (rapido != null and rapido.?.proximo != null) {
                lento = lento.?.proximo;
                rapido = rapido.?.proximo.?.proximo;
                if (lento == rapido) return true;
            }
            return false;
        }

        /// Encontra o início do ciclo (se existir).
        pub fn inicioCiclo(self: *const Self) ?*No {
            var lento = self.head;
            var rapido = self.head;

            // Fase 1: Detecta ciclo
            while (rapido != null and rapido.?.proximo != null) {
                lento = lento.?.proximo;
                rapido = rapido.?.proximo.?.proximo;
                if (lento == rapido) break;
            }

            if (rapido == null or rapido.?.proximo == null) return null;

            // Fase 2: Encontra início do ciclo
            lento = self.head;
            while (lento != rapido) {
                lento = lento.?.proximo;
                rapido = rapido.?.proximo;
            }
            return lento;
        }
    };
}

test "detecção de ciclo" {
    const testing = std.testing;
    const allocator = testing.allocator;

    var lista = ListaEncadeada(i32).init(allocator);

    const no3 = try lista.adicionar(3);
    _ = try lista.adicionar(2);
    const no1 = try lista.adicionar(1);

    // Sem ciclo
    try testing.expect(!lista.temCiclo());

    // Cria ciclo: 1 -> 2 -> 3 -> 1
    no3.proximo = no1;
    try testing.expect(lista.temCiclo());

    const inicio = lista.inicioCiclo();
    try testing.expect(inicio != null);
    try testing.expectEqual(@as(i32, 1), inicio.?.valor);

    // Limpa ciclo antes de liberar
    no3.proximo = null;
    allocator.destroy(no3);
    allocator.destroy(lista.head.?.proximo.?);
    allocator.destroy(lista.head.?);
}

Desafio 6: Merge de K Listas Ordenadas

Problema: Combine k listas ordenadas em uma única lista ordenada.

const std = @import("std");

fn mergeKListas(allocator: std.mem.Allocator, listas: []const []const i32) ![]i32 {
    const Entrada = struct {
        valor: i32,
        lista_idx: usize,
        elem_idx: usize,
    };

    var heap = std.PriorityQueue(Entrada, void, struct {
        fn cmp(_: void, a: Entrada, b: Entrada) std.math.Order {
            return std.math.order(a.valor, b.valor);
        }
    }.cmp).init(allocator, {});
    defer heap.deinit();

    // Inicializa com o primeiro elemento de cada lista
    for (listas, 0..) |lista, i| {
        if (lista.len > 0) {
            try heap.add(.{ .valor = lista[0], .lista_idx = i, .elem_idx = 0 });
        }
    }

    var resultado = std.ArrayList(i32).init(allocator);

    while (heap.count() > 0) {
        const menor = heap.remove();
        try resultado.append(menor.valor);

        // Avança na lista de onde veio o elemento
        const prox_idx = menor.elem_idx + 1;
        if (prox_idx < listas[menor.lista_idx].len) {
            try heap.add(.{
                .valor = listas[menor.lista_idx][prox_idx],
                .lista_idx = menor.lista_idx,
                .elem_idx = prox_idx,
            });
        }
    }

    return try resultado.toOwnedSlice();
}

test "merge k listas ordenadas" {
    const testing = std.testing;
    const allocator = testing.allocator;

    const listas = [_][]const i32{
        &.{ 1, 4, 7 },
        &.{ 2, 5, 8 },
        &.{ 3, 6, 9 },
    };

    const resultado = try mergeKListas(allocator, &listas);
    defer allocator.free(resultado);

    const esperado = [_]i32{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    try testing.expectEqualSlices(i32, &esperado, resultado);
}

Dicas para Entrevistas

  1. Sempre use defer para cleanup — demonstra disciplina de memória
  2. Escolha a estrutura certa — hash map para O(1), heap para mediana, etc.
  3. Use testing.allocator para verificar leaks nos testes
  4. Explique trade-offs — tempo vs. espaço, complexidade vs. simplicidade
  5. Teste edge cases — arrays vazios, um elemento, duplicatas

Recursos Relacionados

Explore Mais

🚀 Primeiros Passos 🔧 Build System 📋 Receitas Prontas 💼 Vagas e Carreira ❓ FAQ (50 Perguntas) 🔄 Migrar de Outra Linguagem

Artigos relacionados

Continue aprendendo Zig

Explore mais tutoriais e artigos em português para dominar a linguagem Zig.

📚 Ver Todos os Tutoriais 💬 Junte-se à Comunidade