De programación competitiva a LeetCode y entrevistas

Existe un solapamiento del 80–90% entre los algoritmos evaluados en entrevistas técnicas de las empresas tecnológicas líderes (Google, Meta, Amazon, Microsoft, Apple, Uber) y las primeras tres etapas de este compendio (Fundamentos, Bronce y Plata, junto con elementos seleccionados de Oro).

Sin embargo, la forma de abordar los problemas y los criterios de evaluación son sustancialmente distintos. En este documento aprenderás a transferir tu intuición algorítmica al formato de entrevistas y a navegar los patrones más frecuentes de LeetCode.

Programación Competitiva vs Entrevistas Técnicas

Mapeo de Patrones de LeetCode contra el Currículum

Casi cualquier problema de las listas célebres (como Blind 75, Grind 75 o NeetCode 150) se clasifica en uno de los siguientes patrones algorítmicos cubiertos en este sitio:

┌───────────────────────────────────────────────┬───────────────────────────────┐
│ Patrón de Entrevista / LeetCode               │ Sección del Curso             │
├───────────────────────────────────────────────┼───────────────────────────────┤
│ Two Pointers & Sliding Window                 │ Plata (Sumas / Dos Punteros)  │
│ Fast & Slow Pointers (Floyd Cycle Finding)    │ Fundamentos / Plata           │
│ Binary Search (valores y sobre la respuesta) │ Plata (Búsqueda Binaria)      │
│ Prefix Sums & Difference Arrays               │ Plata (Sumas de Prefijos)     │
│ BFS & DFS en Grids / Matrices                 │ Plata (Grafos / Flood Fill)   │
│ Árboles Binarios (LCA, DFS, Traversals)       │ Plata & Oro (Árboles)         │
│ Monotonic Stack & Monotonic Queue             │ Plata / Oro                   │
│ Backtracking (Subconjuntos y Permutaciones)  │ Bronce (Búsqueda Completa)    │
│ Heaps / Priority Queue (Top K Elements)       │ Plata (Estructuras STL)       │
│ Interval Scheduling & Merge Intervals         │ Plata (Ordenamiento y Greedy) │
│ Dynamic Programming (1D, 2D, Mochila)         │ Oro (Programación Dinámica)   │
│ Union-Find / Disjoint Set Union (DSU)         │ Oro (Estructuras de Datos)    │
│ Trie / Árbol de Prefijos                      │ Oro / Avanzado (Cadenas)      │
│ Topological Sort (Kahn / DFS)                 │ Oro (Grafos)                  │
└───────────────────────────────────────────────┴───────────────────────────────┘

Ejemplo Práctico de Conversión: Del Estilo CP al Estilo Entrevista

Veamos cómo cambia la implementación del clásico problema Two Sum (encontrar dos índices cuyos valores sumen un valor objetivo $K$).

Versión en Estilo Competitivo (CP)

// Rápido de escribir en un concurso, pero inaceptable en una entrevista
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, k;
    if (!(cin >> n >> k)) return 0;
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        if (mp.count(k - x)) {
            cout << mp[k - x] << " " << i << "\n";
            return 0;
        }
        mp[x] = i;
    }
    return 0;
}

Versión Optimizada para Entrevista (LeetCode)

#include <vector>
#include <unordered_map>
 
class Solution {
public:
    /**
     * Encuentra los índices de dos números que sumen target.
     * Complejidad Temporal: O(N) promedio mediante hash table.
     * Complejidad Espacial: O(N) para almacenar hasta N elementos.
     */
    std::vector<int> twoSum(const std::vector<int>& nums, int target) {
        // Usamos unordered_map para O(1) tiempo promedio de búsqueda
        std::unordered_map<int, int> seenValueToIndex;
        seenValueToIndex.reserve(nums.size()); // Optimización de reserva de cubetas
 
        for (int currentIndex = 0; currentIndex < static_cast<int>(nums.size()); ++currentIndex) {
            int complement = target - nums[currentIndex];
            
            auto it = seenValueToIndex.find(complement);
            if (it != seenValueToIndex.end()) {
                return {it->second, currentIndex};
            }
            
            seenValueToIndex[nums[currentIndex]] = currentIndex;
        }
 
        // Si el problema garantiza una solución única, esta línea no se alcanza
        return {};
    }
};

Diferencias que los entrevistadores observan:

1. Elección de estructura: std::unordered_map ($\mathcal{O}(1)$ promedio) en vez de std::map ($\mathcal{O}(\log N)$ basado en árbol rojinegro).
2. Paso por referencia constante: const std::vector<int>& nums evita copias costosas de memoria en cada llamada.
3. Manejo de nombres: Nombres que documentan la intención (complement, seenValueToIndex).
4. Reserva de capacidad: reserve() demuestra conocimiento de cómo funcionan las tablas hash a bajo nivel.

La Metodología UMPIRE para Entrevistas

Durante una entrevista de 45 minutos, seguí el framework UMPIRE para asegurar una estructura impecable:

[ U ] Understand   ──> Aclarar restricciones, tipos, casos extremos (3-5 min)
[ M ] Match        ──> Identificar el patrón (Two Pointers, DP, BFS...) (2 min)
[ P ] Plan         ──> Pseudocódigo en alto nivel y соглашение con el entrevistador (5 min)
[ I ] Implement    ──> Escribir código limpio y modularizado (15-20 min)
[ R ] Review       ──> Testear línea por línea con un ejemplo en seco (5 min)
[ E ] Evaluate     ──> Concluir con Complejidad Temporal y Espacial Big-O (2 min)

1. Understand (Entender)

• Hacé preguntas aclaratorias: “¿Los números pueden ser negativos?”, “¿El arreglo cabe en memoria RAM?”, “¿Puede haber duplicados?”.
• Proponé un caso de prueba mínimo y confirmá la salida esperada.

2. Match (Emparejar el Patrón)

• Si el arreglo está ordenado $\implies$ Búsqueda Binaria o Dos Punteros.
• Si pide encontrar el subarreglo continuo óptimo $\implies$ Ventana Deslizante o Sumas de Prefijos.
• Si pide el camino más corto en un grafo no ponderado $\implies$ BFS.
• Si pide todas las combinaciones o permutaciones posibles $\implies$ Backtracking.
• Si hay subproblemas solapados y elección de decisiones $\implies$ Programación Dinámica.

3. Plan (Planificar antes de codear)

• Explicá la idea en voz alta: “Primero podemos ordenar el arreglo y luego utilizar dos punteros en los extremos…”.
• Pedí confirmación al entrevistador: “¿Tiene sentido este enfoque antes de empezar a implementarlo?”.

4. Implement (Implementar)

• Escribí código limpio y legible, manteniendo la calma. Si una función secundaria es larga, podés dejar un stub provisional (// TODO: helper) y completarla luego.

5. Review (Revisar en seco)

• Nunca digas “Listo” sin probar tu código. Elegí un caso de prueba pequeño y trazá el valor de cada variable paso a paso en una tabla manual.

6. Evaluate (Evaluar)

• Declará explícitamente: “La complejidad temporal es $\mathcal{O}(N \log N)$ debido al ordenamiento inicial, y la complejidad espacial es $\mathcal{O}(1)$ de memoria auxiliar ya que ordenamos in-place”.

Plan de Estudio Recomendado para Entrevistas

Si tenés entre 1 y 3 meses para preparar entrevistas técnicas:

1. Semanas 1 y 2: Módulos de Fundamentos (I/O, Tipos, Complejidad y Fórmulas) + Calentamiento.
2. Semanas 3 a 5: Todo el contenido de Bronce (Búsqueda exhaustiva, conjuntos, simulaciones) y los primeros módulos de Plata (Sumas de Prefijos, Dos Punteros, Búsqueda Binaria).
3. Semanas 6 a 8: Completar Plata (Grafos, BFS, DFS, Árboles) e iniciar temas clave de Oro (Programación Dinámica clásica y DSU).
4. Semanas 9 en adelante: Resolver las listas Grind 75 o NeetCode 150 simulando entrevistas reales con límite de tiempo de 30 minutos y explicando cada paso en voz alta.

¡Dominar las bases algorítmicas de este sitio te dará una ventaja técnica contundente frente a cualquier desafío de entrevista!