La mayoría de las preguntas de entrevista que piden hacerlo «en un solo recorrido» tienen la misma respuesta: guarda lo que ya has visto en un diccionario o un conjunto, con una clave que puedas buscar en un solo paso.
- Conjunto de elementos vistos: primera repetición, duplicados, «¿ya hemos visto este identificador?».
- Búsqueda del complemento: para dos valores que sumen un objetivo, guarda la posición de cada valor y, para cada valor nuevo, busca
target - value.
- Clave de agrupación: agrupa los elementos que van juntos bajo la misma clave, como los anagramas bajo sus letras ordenadas.
- Recuentos: un
Counter permite encontrar el «primer elemento que aparece una sola vez» en dos recorridos.
- Conjunto de todos los valores: permite iniciar una secuencia solo desde su primer valor (
x - 1 no está en el conjunto), de modo que encontrar la secuencia más larga de números consecutivos requiere O(n).
La habilidad está en elegir la clave. Pregúntate: ¿qué necesito encontrar al instante cuando llegue el siguiente elemento?
Salida: (1, 3). Cuando llega 9, su pareja 7 ya está en el diccionario.