Desafió semana 2

Esta semana el desafió es:

Crear un algoritmo que muestre los diferentes elementos de una lista que sumen un numero k.

Tiempo: 20 Min

En esta clase de ejercicios que parecen simples, en verdad tiene un desafió «oculto» el cual busca que determines el mejor algoritmo para resolver la tarea.

import numpy as np
arr = [2, 4, 6, 1, 5, 3, 5]
k = 8

Una forma de resolverlo es usando numpy u otra biblioteca, el cual con el comando where nos permite recorrer todo el arreglo. Sin embargo, si lo haces así, estarías fallando la pregunta, es usual que en algún apartado diga «no ocupar una función que permita bla bla bla» y de no decirlo te podrían castigar, ya que el objetivo del problema es encontrar el mejor algoritmo.

Primero empezamos a crear el esqueleto del algoritmo

for valorA in arr:
    for valorB in arr:
        if ((valorA + valorB) == k):
            print("{} - {}".format(valorA, valorB))

Ahora empezamos a hacemos la pregunta que probablemente un entrevistador nos realizara ¿Se puede mejorar? Respuesta 1: Si, hasta ahora podríamos sumar el mismo arreglo para obtener la suma que diera el valor k, pero tenemos que buscar los diferentes elementos, pero ademas, en este punto te pueden pedir que si es el mismo numero del arreglo, no los agregues

for valorA in arr:
    for valorB in arr:
        if ((valorA + valorB) == k) and (valorA != valorB):
            print("{} - {}".format(valorA, valorB))

¿Se puede mejorar? Si, hasta ahora, al usar los dos loops (for), recorremos completamente el interior antes que de el siguiente paso del loop exterior.

arreglo = np.sort(arr)
out = []
for valorA in range(len(arreglo)):
    for valorB in range(valorA+1, len(arreglo)):
        if ((arreglo[valorA] + arreglo[valorB]) == k) and (valorA != valorB):
            print("{} - {}".format(valorA, valorB))

Bien, ahora el loop interior ahora empieza desde el indice mayor al valor numérico del loop exterior, pero para hacer esto, debemos ordenar el arreglo o podrían haber problemas de omitir números, ademas resolvimos el problema de la duplicación donde solo invertían la posición. entonces ¿se puede seguir mejorando? bien…la verdad es que aun queda un poco que podemos hacer

arreglo = np.sort(arr)
out = []
tamanio = len(arreglo)
for valorA in range(tamanio):
    for valorB in range(valorA+1, tamanio):
        if ((arreglo[valorA] + arreglo[valorB]) == k) and (valorA != valorB):
            print("{} - {}".format(valorA, valorB))

Al guardar en variable el largo del arreglo, evitamos que vuelva a consultar el tamaño cada vez que intente iterar en el loop interior. Ahora si, ¿se puede seguir mejorando?…bueno…si y no… se puede mejorar para considerar algunos casos como si el numero es mayor a la combinación buscada no vale la pena recorrer dicho numero, aun que aumentara la complejidad máxima, disminuirá la mínima, por lo que se podría considerar bueno implementarlo indicando esas indicaciones. No se dejo en igualdad por que en ningún lugar aseguramos que un numero en el arreglo no pudiese ser cero.

arreglo = np.sort(arr)
out = []
tamanio = len(arreglo)
for valorA in range(tamanio):
    if arreglo[valorA]>k:
      continue
    for valorB in range(valorA+1, tamanio):
        if arreglo[valorB]>k:
          continue
        if ((arreglo[valorA] + arreglo[valorB]) == k) and (valorA != valorB):
            print("{} - {}".format(valorA, valorB))

Allí si creo que estaría completo, si quieren dejen sus comentarios sobre como mejorar este algoritmo o si les interesa que resuelva algún problema de sus entrevistas de trabajo pueden dejarlo también y los realizare cuando termine la lista que ya tengo (no sean cheaters)

Deja un comentario