Desafio de Código Zig 1 — Manipulação de Strings

7 min de leitura
entrevistas desafios strings código

Desafio de Código Zig #1 — Manipulação de Strings

Problemas de manipulação de strings são clássicos em entrevistas de programação. Em Zig, strings são []const u8 (slices de bytes), o que torna o trabalho explícito e eficiente, sem abstrações ocultas. Estes desafios testam sua compreensão de slices, alocação de memória e algoritmos em Zig.

Desafio 1: Comprimir String (Run-Length Encoding)

Problema: Dado “aaabbbccdd”, retorne “a3b3c2d2”. Se a compressão não reduz o tamanho, retorne a original.

const std = @import("std");

fn comprimirString(allocator: std.mem.Allocator, entrada: []const u8) ![]u8 {
    if (entrada.len == 0) {
        const vazio = try allocator.alloc(u8, 0);
        return vazio;
    }

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

    var i: usize = 0;
    while (i < entrada.len) {
        const char = entrada[i];
        var contagem: usize = 1;

        while (i + contagem < entrada.len and entrada[i + contagem] == char) {
            contagem += 1;
        }

        try resultado.append(char);
        if (contagem > 1) {
            // Converte número para string
            var num_buf: [20]u8 = undefined;
            const num_str = std.fmt.bufPrint(&num_buf, "{d}", .{contagem}) catch unreachable;
            try resultado.appendSlice(num_str);
        }

        i += contagem;
    }

    // Se a compressão não reduziu, retorna a original
    if (resultado.items.len >= entrada.len) {
        resultado.deinit();
        const copia = try allocator.alloc(u8, entrada.len);
        @memcpy(copia, entrada);
        return copia;
    }

    return try resultado.toOwnedSlice();
}

test "comprimir string" {
    const testing = std.testing;
    const allocator = testing.allocator;

    const r1 = try comprimirString(allocator, "aaabbbccdd");
    defer allocator.free(r1);
    try testing.expectEqualStrings("a3b3c2d2", r1);

    const r2 = try comprimirString(allocator, "abcd");
    defer allocator.free(r2);
    try testing.expectEqualStrings("abcd", r2); // Não comprimiu
}

Desafio 2: Verificar Anagramas

Problema: Verifique se duas strings são anagramas (mesmas letras, ordem diferente).

const std = @import("std");

fn saoAnagramas(a: []const u8, b: []const u8) bool {
    if (a.len != b.len) return false;

    // Conta frequência de cada caractere
    var freq: [256]i32 = [_]i32{0} ** 256;

    for (a) |c| freq[c] += 1;
    for (b) |c| freq[c] -= 1;

    for (freq) |f| {
        if (f != 0) return false;
    }
    return true;
}

fn saoAnagramasIgnorandoCaso(a: []const u8, b: []const u8) bool {
    var freq: [26]i32 = [_]i32{0} ** 26;
    var contagem_a: usize = 0;
    var contagem_b: usize = 0;

    for (a) |c| {
        const lower = if (c >= 'A' and c <= 'Z') c + 32 else c;
        if (lower >= 'a' and lower <= 'z') {
            freq[lower - 'a'] += 1;
            contagem_a += 1;
        }
    }

    for (b) |c| {
        const lower = if (c >= 'A' and c <= 'Z') c + 32 else c;
        if (lower >= 'a' and lower <= 'z') {
            freq[lower - 'a'] -= 1;
            contagem_b += 1;
        }
    }

    if (contagem_a != contagem_b) return false;
    for (freq) |f| {
        if (f != 0) return false;
    }
    return true;
}

test "anagramas" {
    const testing = std.testing;

    try testing.expect(saoAnagramas("listen", "silent"));
    try testing.expect(saoAnagramas("abc", "cba"));
    try testing.expect(!saoAnagramas("hello", "world"));
    try testing.expect(!saoAnagramas("ab", "abc"));

    try testing.expect(saoAnagramasIgnorandoCaso("Listen", "Silent"));
}

Desafio 3: Maior Substring sem Repetição

Problema: Encontre o comprimento da maior substring sem caracteres repetidos.

const std = @import("std");

fn maiorSubstringSemRepeticao(s: []const u8) usize {
    if (s.len == 0) return 0;

    // Sliding window com mapa de último índice
    var ultima_posicao: [256]i64 = undefined;
    @memset(&ultima_posicao, -1);

    var max_len: usize = 0;
    var inicio: usize = 0;

    for (s, 0..) |c, i| {
        const ultima = ultima_posicao[c];
        if (ultima >= @as(i64, @intCast(inicio))) {
            inicio = @intCast(ultima + 1);
        }
        ultima_posicao[c] = @intCast(i);

        const len_atual = i - inicio + 1;
        if (len_atual > max_len) max_len = len_atual;
    }

    return max_len;
}

test "maior substring sem repetição" {
    const testing = std.testing;

    try testing.expectEqual(@as(usize, 3), maiorSubstringSemRepeticao("abcabcbb"));
    try testing.expectEqual(@as(usize, 1), maiorSubstringSemRepeticao("bbbbb"));
    try testing.expectEqual(@as(usize, 3), maiorSubstringSemRepeticao("pwwkew"));
    try testing.expectEqual(@as(usize, 0), maiorSubstringSemRepeticao(""));
    try testing.expectEqual(@as(usize, 5), maiorSubstringSemRepeticao("abcde"));
}

Desafio 4: Palíndromo mais Longo

Problema: Encontre a maior substring palindrômica em uma string.

const std = @import("std");

fn palindromoMaisLongo(s: []const u8) []const u8 {
    if (s.len <= 1) return s;

    var melhor_inicio: usize = 0;
    var melhor_len: usize = 1;

    // Expande a partir de cada centro possível
    for (0..s.len) |centro| {
        // Palindromos de tamanho ímpar
        expandirDoCentro(s, centro, centro, &melhor_inicio, &melhor_len);
        // Palindromos de tamanho par
        if (centro + 1 < s.len) {
            expandirDoCentro(s, centro, centro + 1, &melhor_inicio, &melhor_len);
        }
    }

    return s[melhor_inicio .. melhor_inicio + melhor_len];
}

fn expandirDoCentro(s: []const u8, esq_init: usize, dir_init: usize, melhor_inicio: *usize, melhor_len: *usize) void {
    var esq: i64 = @intCast(esq_init);
    var dir: usize = dir_init;

    while (esq >= 0 and dir < s.len and s[@intCast(esq)] == s[dir]) {
        const len = dir - @as(usize, @intCast(esq)) + 1;
        if (len > melhor_len.*) {
            melhor_inicio.* = @intCast(esq);
            melhor_len.* = len;
        }
        esq -= 1;
        dir += 1;
    }
}

test "palindromo mais longo" {
    const testing = std.testing;

    try testing.expectEqualStrings("bab", palindromoMaisLongo("babad"));
    try testing.expectEqualStrings("bb", palindromoMaisLongo("cbbd"));
    try testing.expectEqualStrings("a", palindromoMaisLongo("a"));
    try testing.expectEqualStrings("aba", palindromoMaisLongo("aba"));
}

Desafio 5: Agrupar Anagramas

Problema: Dado um array de strings, agrupe os anagramas juntos.

const std = @import("std");

fn agruparAnagramas(allocator: std.mem.Allocator, palavras: []const []const u8) ![][]const []const u8 {
    // Usa a versão ordenada como chave
    var mapa = std.StringHashMap(std.ArrayList([]const u8)).init(allocator);
    defer {
        var iter = mapa.iterator();
        while (iter.next()) |entry| {
            allocator.free(entry.key_ptr.*);
            entry.value_ptr.deinit();
        }
        mapa.deinit();
    }

    for (palavras) |palavra| {
        // Cria chave ordenada
        var chave = try allocator.alloc(u8, palavra.len);
        @memcpy(chave, palavra);
        std.mem.sort(u8, chave, {}, std.sort.asc(u8));

        if (mapa.getPtr(chave)) |lista| {
            try lista.append(palavra);
            allocator.free(chave); // Chave já existe
        } else {
            var lista = std.ArrayList([]const u8).init(allocator);
            try lista.append(palavra);
            try mapa.put(chave, lista);
        }
    }

    // Converte mapa para array de arrays
    var resultado = std.ArrayList([]const []const u8).init(allocator);
    var iter = mapa.iterator();
    while (iter.next()) |entry| {
        const grupo = try entry.value_ptr.toOwnedSlice();
        try resultado.append(grupo);
    }

    return try resultado.toOwnedSlice();
}

test "agrupar anagramas" {
    const testing = std.testing;
    const allocator = testing.allocator;

    const palavras = [_][]const u8{ "eat", "tea", "tan", "ate", "nat", "bat" };
    const grupos = try agruparAnagramas(allocator, &palavras);
    defer {
        for (grupos) |g| allocator.free(g);
        allocator.free(grupos);
    }

    // Verifica que temos 3 grupos
    try testing.expectEqual(@as(usize, 3), grupos.len);
}

Desafio 6: Parser de CSV Simples

Problema: Implemente um parser de CSV que lida com campos entre aspas.

const std = @import("std");

fn parseCsvLinha(allocator: std.mem.Allocator, linha: []const u8) ![][]const u8 {
    var campos = std.ArrayList([]const u8).init(allocator);

    var i: usize = 0;
    while (i <= linha.len) {
        if (i == linha.len) {
            try campos.append("");
            break;
        }

        if (linha[i] == '"') {
            // Campo entre aspas
            i += 1; // Pula aspa de abertura
            const inicio = i;
            while (i < linha.len and linha[i] != '"') {
                i += 1;
            }
            try campos.append(linha[inicio..i]);
            if (i < linha.len) i += 1; // Pula aspa de fechamento
            if (i < linha.len and linha[i] == ',') i += 1; // Pula vírgula
        } else {
            // Campo normal
            const inicio = i;
            while (i < linha.len and linha[i] != ',') {
                i += 1;
            }
            try campos.append(linha[inicio..i]);
            if (i < linha.len) i += 1; // Pula vírgula
            else break;
        }
    }

    return try campos.toOwnedSlice();
}

test "parser CSV" {
    const testing = std.testing;
    const allocator = testing.allocator;

    const campos = try parseCsvLinha(allocator, "nome,\"cidade grande\",idade");
    defer allocator.free(campos);

    try testing.expectEqual(@as(usize, 3), campos.len);
    try testing.expectEqualStrings("nome", campos[0]);
    try testing.expectEqualStrings("cidade grande", campos[1]);
    try testing.expectEqualStrings("idade", campos[2]);
}

Desafio 7: Validar Parênteses Balanceados

Problema: Verifique se uma string tem parênteses/colchetes/chaves balanceados.

const std = @import("std");

fn parentesesBalanceados(s: []const u8) bool {
    var pilha: [256]u8 = undefined;
    var topo: usize = 0;

    for (s) |c| {
        switch (c) {
            '(', '[', '{' => {
                if (topo >= pilha.len) return false;
                pilha[topo] = c;
                topo += 1;
            },
            ')' => {
                if (topo == 0 or pilha[topo - 1] != '(') return false;
                topo -= 1;
            },
            ']' => {
                if (topo == 0 or pilha[topo - 1] != '[') return false;
                topo -= 1;
            },
            '}' => {
                if (topo == 0 or pilha[topo - 1] != '{') return false;
                topo -= 1;
            },
            else => {},
        }
    }

    return topo == 0;
}

test "parênteses balanceados" {
    const testing = std.testing;

    try testing.expect(parentesesBalanceados("()"));
    try testing.expect(parentesesBalanceados("()[]{}"));
    try testing.expect(parentesesBalanceados("{[()]}"));
    try testing.expect(parentesesBalanceados(""));
    try testing.expect(!parentesesBalanceados("(]"));
    try testing.expect(!parentesesBalanceados("([)]"));
    try testing.expect(!parentesesBalanceados("(("));
}

Dicas para Entrevistas

  1. Strings em Zig são []const u8 — não há tipo string separado
  2. Cuidado com UTF-8 — um caractere pode ter mais de 1 byte
  3. Use std.mem e std.fmt para operações comuns
  4. Sempre considere alocação — use testing.allocator em testes
  5. Sliding window é padrão para substrings

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