Tag Archives: complejidad temporal

Cómo optimizar recorrido de arrays

Recorrer un array en forma eficiente es uno de los principales problemas de fondo en ejercicios de competencias de programación o en entrevistas laborales.

Este es un ejemplo práctico paso a paso que parte de la solución más obvia hasta llegar a la más óptima. Para eso tomamos un problema presentado en HackerRank como FunnyStrings.

El enunciado dice que nuestro programa recibirá una cadena de texto y deberá determinar si es Funny creando una copia invertida, restando a cada caracter el caracter siguiente (en la cadena original y en la invertida) usando sus valores ASCII y tomando el resultado en valor absoluto. Si la secuencia de resultados de restas es la misma en ambos casos es “Funny” y si no es “Not Funny”.

Si recibe la cadena “lmnop” su cadena invertida será “ponml” y los valores ASCII de la original serán [108, 109, 110, 111, 112] y de la invertida [112, 111, 110, 109, 108]. La resta en valores absolutos para la primera será [1, 1, 1, 1] y para la segunda [1, 1, 1, 1]. Por lo tanto el algoritmo deberá retornar Funny. En cambio si la cadena de entrada es “bcxz” (la invertida será “zxcb“) los valores ASCII de la primera [98, 99, 120, 122] y de la invertida [122, 120, 99, 98]. Y las respectivas restas darán [1, 21, 2] y [2, 21, 1]. Por ser distintas esta cadena resultará en “Not Funny”.

Continue reading Cómo optimizar recorrido de arrays