Available inSpanishEnglishFrenchGermanHindiPortugueseRussian
Patrones para entrevistas de código (Blind 75)
Lee un problema de Blind 75 que no habías visto, nombra la técnica que pide y el invariante que la hace correcta, antes de escribir una sola línea de código. Para quien ya ha resuelto setenta o más problemas de LeetCode y aun así se bloquea ante un enunciado nuevo; se da por hecho el dominio de Big-O, no se enseña sintaxis. Sesenta y cuatro tarjetas conectan diez familias de técnicas con los problemas que las necesitan.
Un array ordenado, dos elementos que sumen un objetivo y solo O(1) de espacio extra. Nombra la técnica que pide esa frase.
Two pointers, convergiendo desde los dos extremos
— Que llegue ordenado hace el trabajo que haría un hash map.
Source
Se juntan tres señales: la entrada llega ordenada, la respuesta es un par y la cota de espacio descarta el hash map. Pon un índice en cada extremo; si la suma se pasa, mueve el derecho hacia dentro, y si se queda corta, mueve el izquierdo. Cada paso retira un índice para siempre, así que el barrido es O(n) y no gasta memoria. En el enunciado inglés la señal viene como «sorted array» y el problema se llama «two sum». Se confunde con: el hash map de una pasada, que es lo correcto cuando el array no está ordenado y el espacio es libre, porque ordenar costaría un O(n log n) que allí no hace falta.