Patrones Rust para Entrevista

Patrones de Rust para Entrevista

HashMap para Conteos

let mut counts = std::collections::HashMap::new();

for value in values {
    *counts.entry(value).or_insert(0) += 1;
}

Aplicaciones:

• Anagramas.
• Top K frecuente.
• Conteo de caracteres o números.

HashMap para Complementos

let mut seen = std::collections::HashMap::new();

for (index, value) in nums.into_iter().enumerate() {
    let complement = target - value;

    if let Some(&previous_index) = seen.get(&complement) {
        return Some((previous_index, index));
    }

    seen.insert(value, index);
}

Aplicaciones:

• Two Sum.
• Pares con target.
• Detección de relaciones valor-índice.

HashSet para Pertenencia

let values: std::collections::HashSet<i32> = nums.into_iter().collect();

for &value in &values {
    if values.contains(&(value - 1)) {
        continue;
    }
}

Aplicaciones:

• Duplicados.
• Secuencias consecutivas.
• Visitados en grafos.

Suma de Prefijos con HashMap

let mut prefix_counts = std::collections::HashMap::from([(0, 1)]);
let mut prefix_sum = 0;
let mut matches = 0;

for value in nums {
    prefix_sum += value;
    let needed_prefix = prefix_sum - target;

    if let Some(count) = prefix_counts.get(&needed_prefix) {
        matches += count;
    }

    *prefix_counts.entry(prefix_sum).or_insert(0) += 1;
}

Aplicaciones:

• Contar subarreglos contiguos con una suma objetivo.
• Detectar rangos con suma específica.
• Trabajar con números negativos cuando sliding window ya no aplica.

Option para Resultados Ausentes

pub fn find_value(nums: Vec<i32>, target: i32) -> Option<usize> {
    for (index, value) in nums.into_iter().enumerate() {
        if value == target {
            return Some(index);
        }
    }

    None
}

Usar Option cuando una respuesta puede no existir. Es más idiomático que devolver -1.

Tests Estables con HashMap

Los mapas no garantizan orden de iteración. Si una función regresa grupos, ordenar antes de comparar:

for group in &mut result {
    group.sort();
}
result.sort();

Two Pointers

let mut left = 0;
let mut right = values.len() - 1;

while left < right {
    if should_move_left(values[left], values[right]) {
        left += 1;
    } else {
        right -= 1;
    }
}

Aplicaciones:

• Palíndromos.
• Pares o tripletas en arreglos ordenados.
• Contenedores o áreas donde los límites importan.

Sliding Window

let mut left = 0;

for right in 0..values.len() {
    add(values[right]);

    while window_is_invalid() {
        remove(values[left]);
        left += 1;
    }
}

Aplicaciones:

• Subcadenas sin repetidos.
• Ventanas mínimas con conteos.
• Mejor subarreglo contiguo bajo una condición.

Stack Monotónico

let mut stack: Vec<usize> = Vec::new();

for (index, value) in values.iter().enumerate() {
    while let Some(&previous_index) = stack.last() {
        if values[previous_index] >= *value {
            break;
        }

        stack.pop();
        resolve(previous_index, index);
    }

    stack.push(index);
}

Aplicaciones:

• Siguiente mayor o menor elemento.
• Temperaturas diarias.
• Rectángulos en histogramas.

Búsqueda Binaria Exacta

let mut left = 0;
let mut right = values.len();

while left < right {
    let mid = left + (right - left) / 2;

    if values[mid] == target {
        return Some(mid);
    }

    if values[mid] < target {
        left = mid + 1;
    } else {
        right = mid;
    }
}

Aplicaciones:

• Encontrar un índice exacto.
• Buscar posición de inserción.
• Implementar lower bound.

Búsqueda Binaria Sobre Respuesta

let mut left = minimum_possible_answer;
let mut right = maximum_possible_answer;

while left < right {
    let mid = left + (right - left) / 2;

    if works(mid) {
        right = mid;
    } else {
        left = mid + 1;
    }
}

Aplicaciones:

• Encontrar la mínima velocidad que cumple un límite.
• Encontrar la mínima capacidad que cumple una fecha límite.
• Optimizar una respuesta cuando la condición es monótona.

Backtracking

fn backtrack(state: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    if is_complete(state) {
        result.push(state.clone());
        return;
    }

    for choice in choices() {
        state.push(choice);
        backtrack(state, result);
        state.pop();
    }
}

Aplicaciones:

• Subconjuntos.
• Permutaciones.
• Combinaciones.
• Generación de paréntesis.
• Búsqueda DFS con restauración de estado.

Linked Lists con Option<Box>

let mut previous = None;

while let Some(mut node) = head {
    head = node.next.take();
    node.next = previous;
    previous = Some(node);
}

Aplicaciones:

• Revertir listas enlazadas.
• Fusionar listas ordenadas.
• Reordenar listas.
• Practicar ownership explícito en Rust.