TheWhiteCode

Te pediré que resuelvas algunos problemas de programación usando Python y que me des el código, que debe ser lo suficientemente comprensible y el algoritmo debe ser eficiente y considerar todos los posibles casos especiales y manejar entradas grandes de manera eficiente. Cuentas con 10 minutos como tiempo maximo para realizar cada tarea ¿Está bien?

Si no has visto la primera parte donde te explico como proceder, aca te dejo el link!
https://thewhitecode.com/blog/2567

Ejercicio #2: Entero positivo menor

Escribe una solución de función que dada una matriz de N enteros devuelve el entero positivo más pequeño mayor que 0 que no ocurre en A

por ejemplo dado a= 1,3,6,4,1,2 la función debería devolver 5.

dado a = 1,2,3 devuelve 4

dado a= -1, -3 devuelve -1

Escriba un algoritmo eficiente para las siguientes suposiciones:

• N es un número entero dentro del rango [1...100000]

• y cada elemento de la matriz a es un número entero dentro del rango [-1000000...1000000]

Una posible solución a este problema es crear primero un conjunto de todos los enteros positivos que están presentes en la matriz de entrada. Luego podemos iterar a través de los enteros positivos comenzando desde 1 y verificar si están presentes en el conjunto. El primer entero positivo que no está presente en el conjunto es la respuesta.

Aquí está la implementación de la solución en Python:

1
2
3
4
5
6
7
8

def solution(A):
    # Create a set of all the positive integers in A
    positive_integers = set([x for x in A if x > 0])

    # Check each positive integer starting from 1
    for i in range(1, len(positive_integers) + 2):
        if i not in positive_integers:
            return i

En este código, definimos una función llamada solución que toma una matriz A como entrada y devuelve el entero positivo más pequeño mayor que 0 que no ocurre en A. La función primero crea un conjunto de enteros_positivos de todos los enteros positivos presentes en A. Luego comprueba cada entero positivo a partir de 1 y devuelve el primer entero que no está presente en el conjunto.

La complejidad temporal de este algoritmo es O(n), donde n es la longitud del arreglo de entrada A. Esto se debe a que necesitamos iterar sobre el arreglo de entrada para crear el conjunto de enteros positivos, y luego necesitamos iterar sobre el enteros positivos comenzando desde 1 hasta encontrar el primer entero que no está presente en el conjunto.

La complejidad del espacio también es O(n), ya que necesitamos almacenar el conjunto de enteros positivos. Sin embargo, dado que el rango de enteros posibles está limitado a [-1000000...1000000], el tamaño real del conjunto también está limitado, lo que hace que el algoritmo sea eficiente para el rango dado de valores de entrada.

Te quedas con la primera solución?

Podemos usar una tabla hash (diccionario de Python) para resolver esta tarea de manera más eficiente. En lugar de iterar sobre la matriz de entrada y agregar todos los enteros positivos a un conjunto, podemos iterar sobre la matriz e insertar cada entero positivo en un diccionario con el entero como clave y un valor de True. Luego podemos iterar sobre los enteros positivos a partir de 1 y verificar si existen en el diccionario. El primer entero positivo que no está en el diccionario es la respuesta.

Aquí está la implementación de la solución mejorada:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def solution(A):
    # Create a dictionary of all the positive integers in A
    positive_integers = {}
    for x in A:
        if x > 0:
            positive_integers[x] = True

    # Check each positive integer starting from 1
    for i in range(1, len(positive_integers) + 2):
        if i not in positive_integers:
            return i

En este código, primero inicializamos un diccionario vacío números_positivos. Luego iteramos sobre la matriz de entrada A, y para cada entero positivo, lo agregamos como una clave (Key) al diccionario con un valor de True.

Luego iteramos sobre los enteros positivos a partir de 1 y verificamos si existen en el diccionario. Si encontramos un entero positivo que no está en el diccionario, lo devolvemos como respuesta.

La complejidad temporal de este algoritmo es O(n), donde n es la longitud del arreglo de entrada A. La complejidad espacial también es O(n), ya que necesitamos almacenar un diccionario con todos los enteros positivos en A. Sin embargo, dado que el rango de enteros posibles está limitado a [-1000000...1000000], el tamaño real del diccionario también está limitado, lo que hace que el algoritmo sea eficiente para el rango dado de valores de entrada. Además, usar un diccionario nos permite realizar búsquedas en tiempo constante, lo que hace que el algoritmo sea más rápido que usar un set para tamaños de entrada más grandes.

El Manual de los algoritmos y las estructuras de datos.

  ¿Quieres estar preparado para cualquier entrevista de trabajo en programación? El Manual es la guía esencial que todo programador debe tener. Con explicaciones detalladas y ejemplos prácticos, aprenderás los algoritmos más usados y complejos que necesitas conocer para destacar en cualquier entrevista. ¡No pierdas la oportunidad de obtener esta herramienta invaluable para tu carrera!  

Descarga el manual directamente desde este enlace

https://leanpub.com/elmanualdelosalgoritmosylasestructurasdedatosfondoblanco

No te pierdas la segunda parte con otro ejemplo de ejercicio en una oferta de trabajo!

¿Te ha gustado?, quisieras acceder a más contenido?

Dejame saber tu opinion en los comentarios!