Pares K-Complementarios con JavaScript
Recientemente tuve la oportunidad de aceptar un desafío de código para una empresa que realmente admiro y con la que me gustaría trabajar un día. Estaba agradecida, emocionada y aún más ansiosa porque había muchas incógnitas en el desafío del código. La realidad es que no hay mucho que puedas hacer para prepararte:
- Construir proyectos
- Estudiar algoritmos
- Problemas de Grind: LeetCode, HackerRank, CodeSignal
Sin embargo, la única manera de averiguar si está listo o no es saltar al extremo profundo para ver si puede flotar. Así que lo hice, y aprendí mucho más de lo que había aprendido antes, y por eso quería compartirlo.
Al inicio de la tarea me enfrenté a tres tareas que completar. Me centraré en solo 1 de estos en este blog — K-Pares complementarios.
El Objetivo
- Se le da un Entero de destino y una Matriz llena de enteros positivos
- Necesita encontrar y localizar el complemento del Entero de Destino — lo que significa que el valor de un índice y otro índice DEBE ser igual al Objetivo
- Devolver el recuento de los pares al final
Bandeja de números + bandeja de números = 7
Lo anterior sería un par válido ya que estos dos valores son iguales al objetivo.
Primer acercamiento
Cuando abordé por primera vez este problema, lo perseguí de una manera de fuerza bruta. Pensé que podría usar bucles anidados para verificar los pares complementarios, ¡y bueno, tenía razón! Realmente trabajado:
¿Cómo funciona?
- Se realiza un bucle sobre los elementos de la matriz inicial.
- Luego lo recorres al unísono para verificar si es igual o no al Objetivo en cada pasada.
- Si el Objetivo coincide, el recuento se incrementa.
Si bien funciona, y recibí un recuento preciso de los pares complementarios dados a un objetivo, no era ideal. La realidad es que los bucles anidados son lentos, y pueden crecer exponencialmente con matrices de elementos más grandes. La complejidad temporal es O (N2).
Segundo enfoque — Optimización
Así que volví al tablero de dibujo. Después de un poco de investigación y consideración, descubrí que podía almacenar los valores en un objeto — {clave: valor}.
Esto seguía siendo muy complicado, especialmente porque nunca antes había escrito algo tan complejo. Yo estaba pisando a un nuevo territorio, pero estaba emocionado porque yo estaba realmente capaz de optimizar mi ex algoritmo de O(N):
Entonces, ¿cómo funciona?
- Vet ese número de raya o la Longitud existe.
- Primero ejecutamos la barra numberArray para crear pares clave / valor en el objeto located_pairs. A lo largo de este proceso, comprobará la singularidad y los duplicados.
- Luego ejecutamos las teclas del objeto ubicado y verificamos si se realiza o no con el objetivo. Si lo hace, el número de pares se incrementa.