Archivo de la etiqueta: algoritmos

#DailyCodingProblem: El producto de todos los elementos en el arreglo menos el elemento actual

https://www.dailycodingproblem.com/

Good morning! Here’s your coding interview problem for today.

This problem was asked by Uber.

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can’t use division?

Si ignoramos la restricción este problema es muy sencillo de resolver.

  • Iteramos el arreglo y calculamos el producto total de todos los elementos: 1 x 2 x 3 x 4 x 5 = 120
  • Iteramos nuevamente dividiendo el total entre cada uno de los elementos y guardamos esos resultados en nuevo arreglo: 120/1, 120/2, 120/3, 120/4, 120/5

La complejidad de esta solución seria O(2n) o simplemente O(n), pero debido a que el problema dice que no podemos usar la división las cosas se complican un poco mas.

Solución cuadrática

Sin usar la división la solución mas obvia es una solución cuadrática, iteramos el arreglo y por cada elemento vamos a ir acumulando el producto de esos valores menos el elemento i actual.

    int[] calculateProduct(int[] numbers) {
        int[] result = new int[numbers.length];
        // ...
        // ... logica para inicializar todos los valores de result en 1
        // ...
        for (int i = 0; i < numbers.length; i += 1) {
            for (int j = 0; j < numbers.length; j += 1) {
                if (i != j) {
                    result[j] *= numbers[i];
                }
            }
        }
        return result;
    }

Esta solución es muy fácil de entender pero no es para nada eficiente, O(n2), en la publicación anterior ya analizábamos otra solución cuadrática y veíamos que era un problema con inputs de datos muy grandes, por ejemplo un arreglo de 1000 elementos (1 millón de operaciones).

Solución en tiempo lineal con programación dinámica

Después de pensar un rato en este problema, haciendo algunas anotaciones y viendo la relación entre los indices y el producto parcial de cada uno de ellos llegue a la siguiente solución.

La primera fila son los valores del arreglo, después como si estuviéramos iterando, el valor actual es marcado en color amarillo, si pudiéramos obtener el producto acumulado de izquierda y derecha de cada uno de los elementos entonces podríamos resolver el problema multiplicándolos entre si 🙂

Ejemplo: para el obtener el resultado del 3 tendríamos que multiplicar sus valores de la izquierda que son 2 y sus valores de la derecha que son 20 dando como resultado 40.

Vamos a recorrer el arreglo por la izquierda y por la derecha guardando el producto de sus elementos, para eso necesitaremos 2 arreglos mas, left y right, podemos hacer esos recorridos en una sola iteración, después iteramos nuevamente multiplicando los valores de izquierdo y derecho de result[i].

    public static int[] calculateProduct(int[] numbers) {
        int[] result = new int[numbers.length];
        int[] left = new int[numbers.length];
        int[] right = new int[numbers.length];
        int totalLeft = 1;
        int totalRight = 1;
        int size = numbers.length - 1;
        for (int i = 0; i <= size; i += 1) {
            totalLeft *= numbers[i];
            totalRight *= numbers[size - i];
            left[i] = totalLeft;
            right[size - i] = totalRight;

        }
        for (int i = 0; i < numbers.length; i += 1) {
            if (i == 0) {
                result[i] = right[i + 1];
            } else if (i == numbers.length - 1) {
                result[i] = left[i - 1];
            } else {
                result[i] = left[i - 1] * right[i + 1];
            }
        }
        return result;
    }

La complejidad en tiempo de esta solución es O(2n) o O(n).
La complejidad en espacio de esta solución es O(3n) o O(n), (tomando en cuenta solamente los 3 nuevos arreglos que necesitamos, todas las demás variables son espacio constante).

Happy hacking 🙂

StringTransformer: the transformation tool

st

Hola lectores, en esta ocasión me gustaría compartir con ustedes una herramienta opensource que he publicado en mi repositorio de github, se trata de StringTransformer, un script desarrollado en python cuya finalidad es tomar una cadena de texto y transformarla a distintas representaciones equivalentes de la misma, por ejemplo binario, hexadecimal, octal, md5, sha256, etc. Las funciones de transformación son clases separadas del script principal por lo que la herramienta es modular, esto significa que es bastante fácil para cualquier programador (que sepa python) crear sus propias transformaciones y extender la funcionalidad de la herramienta.

Esta herramienta les puede ser útil cuando están jugando Capture the flags y necesitan una forma rápida de analizar cadenas de texto (o al menos esa es su finalidad), la herramienta sigue en desarrollo, corrigiendo bugs e implementando nuevas funcionalidades.

Instalación

Su instalación es bastante sencilla, primero deben de clonar el repositorio usando git

$ git clone https://github.com/Alevsk/stringTransformer.git

Una vez descargado el repositorio acceden a la carpeta del proyecto, dan los permisos de ejecución necesarios y lanzan el script:

$ cd stringTransformer
$ chmod +x stringTransformer.py
$ ./stringTransformer.py
                  
              _______         
       _____ |   _   |  ____  
      |    |  \  V  /  |    | 
      |   \ \  \_ _/  / /   | 
      \  \ \ \   '   / / /  / 
       \  \   | 'V' |   /  /  
     |\ \_____| \ / |_____/ /|
     | \        | |        / |
     |  |    ,/|| ||\,    |  |
     |   `| '  || ||  ' |`   |
     |    | |  || ||  | |    |
     \    | |  || ||  | |    /
      \.  | |  ||_||  | |  ./ 
       \  | |  |___|  | |  /  
         \' ,  _____  , '/    
             \/ ___ \/        
               /___\          
                           

stringTransformer v0.1 (https://github.com/alevsk/stringTransformer/)

Usage: stringTransformer.py -i INPUT_STRING | --input INPUT_STRING | --load FILE

stringTransformer.py: error: Required argument is missing. Use '-h' for help.

Con el comando -h o –help podran ver el menu de ayuda:

Options:
  -h/--help             show this help message and exit
  -i/--input=INPUT      set the input string to test with
  -l/--load=LOAD_FILE   load list of input strings (one per line)
  -x/--exclude=EXCLUDE  exclude this representations
  -o/--only=ONLY        transform input only to this representations
  -O/--output=OUTPUT    generate an output file
  -p/--params=PARAMS    use custom parameters on transformation functions
  --list                list available input representations
  --update              update from the official git repository

Examples:
./stringTransformer.py -i [STRING]
./stringTransformer.py -i [STRING] --exclude "hexa, octal"
./stringTransformer.py -i [STRING] --only "hexa, octal"
./stringTransformer.py -i [STRING] --params "rot.cipher=13,rot.encoding=utf-8"
./stringTransformer.py --load list.txt
./stringTransformer.py --list

Para ver las funciones de transformación actualmente disponibles pueden utilizar –list:

stringTransformer v0.1 (https://github.com/alevsk/stringTransformer/)

- sha1
- octal
- binary
- sha256
- html_entities_decode
- html_entities_encode
- md5
- base64_encode
- base64_decode
- ascii
- slug
- rot_encode
- hexa
- urlencode

Puedes ayudar a crear más funciones de transformación para la herramienta, para eso sugiero lean la documentación en la página principal del repositorio (o en el archivo README.md) https://github.com/Alevsk/stringTransformer

Ejemplos de uso

Queremos aplicar una transformación hexadecimal, rot 13 encode y ascii a la cadena de texto “The transformation tool”

$ ./stringTransformer.py -i "The transformation tool" -o "hexa,rot_encode,ascii"

Obtenemos como resultado:

stringTransformer v0.1 (https://github.com/alevsk/stringTransformer/)

[i] Loaded 3 representations to apply.
[i] Starting tests at: "23:54:04"

The transformation tool

[i] applying transformation...

ascii:

84 104 101 32 116 114 97 110 115 102 111 114 109 97 116 105 111 110 32 116 111 111 108

rot_encode:

Gur genafsbezngvba gbby

hexa:

54 0x68 0x65 0x20 0x74 0x72 0x61 0x6e 0x73 0x66 0x6f 0x72 0x6d 0x61 0x74 0x69 0x6f 0x6e 0x20 0x74 0x6f 0x6f 0x6c 

==================================

Incluso podemos pasar parámetros a las funciones de transformación que lo soporten, rot_encode por defecto utilizar 13 posiciones de desplazamiento pero aquí indicamos que use 51

$ ./stringTransformer.py -i "The transformation tool" -o "rot_encode" --params="rot_encode.cipher=51"

stringTransformer v0.1 (https://github.com/alevsk/stringTransformer/)

[i] Loaded 1 representations to apply.
[i] Starting tests at: "23:58:11"

The transformation tool

[i] applying transformation...

rot_encode:

Sgd sqzmrenqlzshnm snnk

==================================

La herramienta cuenta con muchísimos otros parámetros que los invito a explorar.
saludos