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:
-
Nes 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:
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:
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!
isabella.conti
SRE aquí, y lo que más me gustó es que el enunciado declare explícitamente los límites: N ≤ 100000 y el rango de los elementos. Esas suposiciones son lo que hace el problema acotado y verificable — exactamente lo que me molesta cuando falta en un ticket de producción. Por eso mismo me quedo con la duda del caso todo-negativo: un comportamiento no especificado es un bug esperando pasar a producción.
marcus.thompson
Desde el lado de los backends en producción: en Go la misma solución sería un map[int]struct{} que actúa de set, igual de O(n). Lo que noto es que la segunda solución con diccionario se presenta como 'más eficiente', pero en realidad agrega memoria sin ganar tiempo — en una entrevista yo le preguntaría al candidato exactamente eso: '¿qué ganamos con este cambio?'. Las respuestas a las preguntas de tradeoffs separan a los juniors de los seniors.
sofia.codes
¡Qué buena serie! Ya estaba practicando con la parte 1 y este ejercicio me encantó. Hice la solución con set en menos de 10 minutos, pero se me fue el tiempo intentando entender el caso donde la matriz solo tiene negativos: la spec dice que devuelve -1, y yo lo tendría devolviendo 1. ¿Eso es intencional o es un detalle que el entrevistador espera que preguntes?
omarhaddad
Como team lead lo leo con ojos de code review: la primera solución es limpia y el nombre positive_integers comunica bien. Pero la 'mejora' con diccionario me haría una sola pregunta en la review: ¿por qué mantenemos el diccionario y no el set, si la complejidad es idéntica? Me gusta la serie porque enseña a escribir el código, pero en las entrevistas reales el candidato también tiene que justificar cada estructura que elige.
danielweber
Curiosidad técnica: la 'mejora' con el diccionario no cambia la complejidad respecto al set — un set ya ES una tabla hash, así que son O(n) en tiempo y espacio ambas. En C++ lo escribiría con std::unordered_set y directamente buscaría el primer hueco. Lo que sí me hubiera encantado ver como tercera opción: la solución in-place en O(1) de espacio extra, colocando cada valor en su índice (o marcándolo con negativo) y luego escaneando. Ahí es donde el entrevistador nota si sabes lo que haces.
emilybuilds
Como matemática, me detiene un detalle de la especificación: el ejemplo a = -1, -3 devuelve -1, pero el enunciado pide 'el entero positivo más pequeño' — y -1 no es positivo. En la versión clásica de este problema (Codility) ese caso devuelve 1. Mi recomendación en una entrevista real: señalar la ambigüedad y confirmar con el entrevistador ANTES de programar. Preguntar buenas preguntas puntúa más que el código perfecto.
lucasdev
Llevo una semana resolviendo este formato de ejercicios para un proceso de selección y el límite de 10 minutos es realista: en mi última prueba me dieron 12 para un problema casi igual. Me ayudó mucho empezar por la parte 1 y seguir el método de anotar los requisitos mientras el 'locutor' habla. Gracias por la serie, es de lo poco que está en español con este nivel.
yuki.tanaka
Uso estos ejercicios como calentamiento entre experimentos de modelos (es bueno para no perder el tacto con el código puro). El enfoque con set transfiere directo a los problemas de deduplicación que uno ve en pipelines de tokenización. Una duda: ¿considerarían hacer una parte con problemas de strings, tipo los de detección de tokens duplicados? Me gustaría ver cómo se manejan los rangos de entrada grandes también ahí.
anna.data
Vengo del lado de los data pipelines y este problema lo veo todos los días como hash join: los enteros presentes son la tabla de lookup y escanear de 1 en adelante es el scan de la tabla izquierda. En SQL se resolvería generando una secuencia de 1..N+1 y haciendo un LEFT JOIN + WHERE IS NULL contra los valores de la matriz. Curiosamente en Spark la solución 'idiomática' sería un set() en una UDF para el lookup. Buen ejercicio, muy transferible.
henrik.security
Perspectiva de seguridad: este problema es un ejemplo perfecto de input no confiable. Los negativos, los duplicados y el rango [-1000000, 1000000] son la frontera de confianza que hay que validar antes de tocar el algoritmo. Mi regla es 'trust, but verify': nunca asumo que la entrada respeta la spec, y eso en una entrevista lo menciono explícitamente al candidato. Ojalá la serie tenga una parte sobre manejo de errores y validación, es donde la mayoría de los candidatos se rompe.