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.

Listas Enlazadas 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.

Árboles con Rc<RefCell>

type TreeLink = Option<Rc<RefCell<TreeNode>>>;

Aplicaciones:

• Recorrer árboles con DFS o BFS.
• Mutar hijos en problemas como invertir árbol.
• Clonar enlaces Rc para pasar subárboles a funciones recursivas.

DFS con Retorno en Árboles

fn height(root: TreeLink) -> i32 {
    match root {
        None => 0,
        Some(node) => {
            let node = node.borrow();
            1 + height(node.left.clone()).max(height(node.right.clone()))
        }
    }
}

Aplicaciones:

• Profundidad máxima.
• Balance de árbol.
• Diámetro de árbol.

BFS por Niveles

while !queue.is_empty() {
    let level_len = queue.len();
    let mut level = Vec::new();

    for _ in 0..level_len {
        let node = queue.pop_front().unwrap();
        level.push(node.borrow().val);
    }
}

Aplicaciones:

• Level order traversal.
• Distancias por capas.
• Procesamiento por profundidad.

Validación de BST con Límites

fn validate(root: TreeLink, lower: Option<i32>, upper: Option<i32>) -> bool {
    match root {
        None => true,
        Some(node) => {
            let node = node.borrow();

            if lower.is_some_and(|limit| node.val <= limit)
                || upper.is_some_and(|limit| node.val >= limit)
            {
                return false;
            }

            validate(node.left.clone(), lower, Some(node.val))
                && validate(node.right.clone(), Some(node.val), upper)
        }
    }
}

Aplicaciones:

• Validar BST.
• Mantener restricciones heredadas por ancestros.
• Evitar falsos positivos al comparar solo contra el padre.

DFS en Matriz

fn dfs(grid: &[Vec<i32>], visited: &mut [Vec<bool>], row: usize, col: usize) {
    if visited[row][col] || grid[row][col] == 0 {
        return;
    }

    visited[row][col] = true;

    for (next_row, next_col) in neighbors(row, col, grid.len(), grid[0].len()) {
        dfs(grid, visited, next_row, next_col);
    }
}

Aplicaciones:

• Islas.
• Componentes conectados en una matriz.
• Áreas máximas.

BFS Multisource

let mut queue = VecDeque::new();

for row in 0..rows {
    for col in 0..cols {
        if is_source(row, col) {
            queue.push_back((row, col, 0));
        }
    }
}

while let Some((row, col, distance)) = queue.pop_front() {
    for (next_row, next_col) in neighbors(row, col, rows, cols) {
        if can_visit(next_row, next_col) {
            queue.push_back((next_row, next_col, distance + 1));
        }
    }
}

Aplicaciones:

• Distancias mínimas en matriz sin pesos.
• Propagación simultánea.
• Problemas con varias fuentes iniciales.

Ordenamiento Topológico

let mut queue = VecDeque::new();

for (node, &indegree) in indegrees.iter().enumerate() {
    if indegree == 0 {
        queue.push_back(node);
    }
}

while let Some(node) = queue.pop_front() {
    order.push(node);

    for &neighbor in &graph[node] {
        indegrees[neighbor] -= 1;
        if indegrees[neighbor] == 0 {
            queue.push_back(neighbor);
        }
    }
}

Aplicaciones:

• Prerequisitos.
• Detección de ciclos en grafos dirigidos.
• Ordenar tareas con dependencias.

Union Find

fn find(parent: &mut Vec<usize>, value: usize) -> usize {
    if parent[value] != value {
        parent[value] = find(parent, parent[value]);
    }

    parent[value]
}

Aplicaciones:

• Componentes conectados dinámicos.
• Detección de ciclos en grafos no dirigidos.
• Agrupar elementos equivalentes.

Montículo Mínimo con Reverse

let mut heap = BinaryHeap::new();

for value in values {
    heap.push(Reverse(value));

    if heap.len() > k {
        heap.pop();
    }
}

Aplicaciones:

• Kth largest.
• Mantener solo los mejores k candidatos.
• Modelar prioridades mínimas con BinaryHeap.

Dos Montículos para Mediana

let mut lower = BinaryHeap::new();
let mut upper = BinaryHeap::new();

lower.push(value);

if lower.len() > upper.len() + 1 {
    upper.push(Reverse(lower.pop().unwrap()));
}

Aplicaciones:

• Median stream.
• Mantener dos mitades balanceadas.
• Consultar mediana en O(1).

Fusionar Intervalos

intervals.sort_unstable_by_key(|&(start, end)| (start, end));

for (start, end) in intervals {
    match merged.last_mut() {
        Some((_, previous_end)) if start <= *previous_end => {
            *previous_end = (*previous_end).max(end);
        }
        _ => merged.push((start, end)),
    }
}

Aplicaciones:

• Merge intervals.
• Insert interval.
• Normalizar rangos antes de analizarlos.

Greedy por Fin Más Temprano

intervals.sort_unstable_by_key(|&(start, end)| (end, start));

let mut last_end = intervals[0].1;

for (start, end) in intervals.into_iter().skip(1) {
    if start >= last_end {
        last_end = end;
    }
}

Aplicaciones:

• Intervalos no solapados.
• Selección máxima de eventos compatibles.
• Minimizar remociones.

DP 1D con Compresión

let mut two_back = base_two_back;
let mut one_back = base_one_back;

for item in items {
    let current = transition(two_back, one_back, item);
    two_back = one_back;
    one_back = current;
}

Aplicaciones:

• Escaleras.
• Robo de casas.
• Decodificación.

DP de Minimización

let unreachable = target + 1;
let mut dp = vec![unreachable; target + 1];
dp[0] = 0;

for amount in 1..=target {
    for coin in &coins {
        if *coin <= amount {
            dp[amount] = dp[amount].min(dp[amount - *coin] + 1);
        }
    }
}

Aplicaciones:

• Coin Change.
• Costos mínimos.
• Caminos mínimos sin pesos negativos.

Knapsack 0/1

let mut dp = vec![false; target + 1];
dp[0] = true;

for value in values {
    for current in (value..=target).rev() {
        dp[current] = dp[current] || dp[current - value];
    }
}

Aplicaciones:

• Partition Equal Subset Sum.
• Subset sum.
• Decisiones donde cada elemento se usa una vez.

DP 2D con Fila Comprimida

let mut previous = vec![0; cols + 1];

for row in rows {
    let mut current = vec![0; cols + 1];

    for col in 0..cols {
        current[col + 1] = transition(&previous, &current, row, col);
    }

    previous = current;
}

Aplicaciones:

• Longest Common Subsequence.
• Problemas de grid.
• Comparación de dos secuencias.