Hashmaps en entrevistas técnicas: 2 problemas leetcode paso a paso

Cuando empecé con LeetCode cada problema se sentía como empezar de cero. Me tomó un rato darme cuenta de que la mayoría se agrupan por estructura, y que cuando reconoces el patrón el problema se desarma solo. El hashmap fue de los primeros "trucos" que me cambió la forma de resolverlos.

¿LeetCode sigue importando con tanta IA? Las big tech todavía usan este tipo de problemas para evaluar candidatos, así que reconocer estos patrones sigue siendo útil. Hoy usamos esa base para desarmar dos problemas clásicos.

En el artículo anterior vimos cómo funciona un hashmap por debajo. Hoy usamos esa base para resolver los problemas.

Lo que vas a encontrar:Dos problemas resueltos paso a paso: Two Sum y Roman to IntegerCómo saber cuándo un problema te está pidiendo un hashmap (la señal que buscas)Dónde aparecen los hashmaps fuera de las entrevistas

Recordatorio rápido: qué hace un hashmap

Por si llegaste directo a este artículo, te dejo un resumen sencillo. Un hashmap guarda pares de clave y valor, y te deja buscar por la clave en tiempo casi constante. Le pides "dame el valor de esta clave" y te lo devuelve al instante, sin recorrer toda la estructura.

En JavaScript el hashmap se usa con Map. Le agregas pares con map.set(clave, valor), preguntas si una clave existe con map.has(clave) y recuperas su valor con map.get(clave). Cuando solo te interesa saber si algo está o no está, sin guardar un valor asociado, el Set hace ese trabajo.

Con eso basta para los problemas. Vamos.

Problema 1: Two Sum (easy)

"Two Sum" de LeetCode.

Problema: dado un array de enteros nums y un entero target, devuelve los índices de los dos números que sumados dan target. Cada input tiene exactamente una solución y no puedes usar el mismo elemento dos veces.

Input:  nums = [2,7,11,15], target = 9   → [0,1]   (porque 2 + 7 == 9)
Input:  nums = [3,2,4],     target = 6   → [1,2]
Input:  nums = [3,3],       target = 6   → [0,1]

¿Cómo lo pensamos?

La forma obvia es comparar cada número contra todos los demás con dos loops anidados. Funciona, pero es O(n²) y se pone lento rápido.

Aquí está la señal: "para cada número necesito encontrar su complemento". Si estoy parado en el 2 y mi target es 9, lo que busco es el 7. Ese target - num es el complemento. La pregunta entonces se vuelve "¿ya vi antes el número que me falta?", y responder eso rápido es justo lo que un hashmap hace bien.

La idea: recorremos el array una sola vez. En cada paso calculamos el complemento y preguntamos si ya lo guardamos. Si sí, encontramos la pareja. Si no, guardamos el número actual con su índice y seguimos.

Solución

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const map = new Map();

  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    const complemento = target - num;

    if (map.has(complemento)) {
      return [i, map.get(complemento)];
    }

    map.set(num, i);
  }
};

Lo importante:

1. El Map guarda cada número que ya vimos como clave, y su índice como valor.
2. Antes de guardar el número actual, preguntamos si su complemento ya está en el Map.
3. Si está, devolvemos los dos índices y terminamos.
4. Guardamos primero y preguntamos después no funciona aquí: por eso preguntamos antes de hacer set, así no nos emparejamos con nosotros mismos.

Complejidad: O(n) tiempo y O(n) espacio. Una sola pasada, y en el peor caso el Map guarda los n números.

Problema 2: Roman to Integer (easy)

"Roman to Integer" de LeetCode.

Problema: los números romanos usan siete símbolos (I, V, X, L, C, D, M), cada uno con un valor. Dado un número romano como string, conviértelo a entero.

Casi siempre se escriben de mayor a menor, de izquierda a derecha, y los valores se suman. La excepción es la notación sustractiva: cuando un símbolo menor va antes de uno mayor, se resta. Por eso IV es 4 (no IIII) y IX es 9.

Input:  s = "III"      → 3      (III = 3)
Input:  s = "LVIII"    → 58     (L=50, V=5, III=3)
Input:  s = "MCMXCIV"  → 1994   (M=1000, CM=900, XC=90, IV=4)

¿Cómo lo pensamos?

Aquí el hashmap cambia de papel. En Two Sum lo usamos para recordar lo que ya vimos. En este problema lo usamos como tabla de equivalencias: símbolo a número.

La señal: "tengo una tabla fija de equivalencias". Cada símbolo romano siempre vale lo mismo, así que un Map que traduzca de símbolo a valor es perfecto.

Falta el truco de la resta. Recorremos el string de izquierda a derecha y comparamos cada símbolo con el siguiente. Si el actual es menor que el que sigue, estamos ante una pareja sustractiva (como IV o IX), así que lo restamos. Si no, lo sumamos.

Solución

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function (s) {
  const values = new Map([
    ["I", 1],
    ["V", 5],
    ["X", 10],
    ["L", 50],
    ["C", 100],
    ["D", 500],
    ["M", 1000],
  ]);

  let result = 0;

  for (let i = 0; i < s.length; i++) {
    const actual = values.get(s[i]);
    const siguiente = i + 1 < s.length ? values.get(s[i + 1]) : 0;

    if (actual < siguiente) {
      result -= actual;
    } else {
      result += actual;
    }
  }

  return result;
};

Lo importante:

1. El Map values es la tabla de equivalencias: traduce cada símbolo a su número.
2. En cada posición miramos el valor actual y el siguiente.
3. Si el actual es menor que el siguiente, lo restamos (notación sustractiva). Si no, lo sumamos.
4. Cuando estamos en el último símbolo, no hay siguiente, así que usamos 0 para que siempre entre al caso de suma.

El patrón detrás de los dos

Si lees los dos problemas seguidos vas a notar que el hashmap aparece de dos formas distintas.

• Two Sum: "¿ya vi este valor o su complemento?". El hashmap es un lookup rápido de lo que ya pasó.
• Roman to Integer: "traduce este símbolo a su valor". El hashmap es una tabla de equivalencias fija.

Esos son los dos usos que más vas a repetir. Cuando un problema te pide recordar lo que ya viste, o traducir algo a un valor fijo, piensa en hashmap.

¿Cuándo uso un hashmap? (las señales)

Estas son las frases que suelen aparecer en los enunciados y lo que casi siempre te están pidiendo:

• "cuenta cuántas veces aparece cada..." → contador de frecuencias con un Map.
• "para cada X encuentra su par o complemento" → guarda lo que ya viste en un Map.
• "agrupa por..." → la clave es el criterio de agrupación.
• "traduce / mapea A a B" → tabla de equivalencias.

Como ves, casi todas se reducen a lo mismo: necesitas buscar algo rápido por una clave. Esa es la pista.

Uso de hashmaps en aplicaciones reales

Los hashmaps no solamente nos sirven para resolver problemas de entrevistas. El patrón de "buscar rápido por clave" está por todos lados:

• Un cache que guarda resultados por su clave para no recalcularlos.
• Contar palabras o eventos en un log.
• Los headers HTTP, que son pares clave y valor.

Para seguir practicando

Te dejo la lista de problemas de hashmap en LeetCode ordenada para que la trabajes por dificultad.