Prueba de Codility: guía en español para practicar corrección y complejidad

Una solución puede devolver la respuesta correcta en casos pequeños y crecer demasiado al aumentar los datos. Otra puede recorrer la entrada rápidamente y devolver un resultado equivocado. Puedes empezar la preparación de Codility con dos evidencias: por qué el algoritmo cumple el contrato y cuánto trabajo realiza cuando crece la entrada.

Esta guía en español utiliza un problema clásico, implementaciones propias y un laboratorio descargable. Compara una búsqueda repetida, una optimización defectuosa y una versión corregida con contadores. Puedes trasladar después el método a las preguntas de Software Engineer de PracHub, sin convertir una lista de práctica en una predicción de tu examen.

Hechos oficiales: los enlaces de Codility describen la evaluación y sus materiales públicos. Reportes de candidatos: los registros de PracHub aportan preguntas para practicar, sin confirmar el contenido de tu invitación. Análisis y ejercicios: las implementaciones, los contadores y los tests de esta guía son nuestros. El concepto de menor positivo ausente no es una invención del artículo.

Qué verificar antes de practicar una evaluación concreta

Oficial: la introducción para candidatos explica que una evaluación puede pedir escribir o modificar código y responder preguntas técnicas. Ese alcance no permite deducir cuántos ejercicios, lenguajes o minutos tendrá tu invitación.

Busca el formato anunciado, la ventana de acceso, el tiempo disponible después de comenzar y las herramientas permitidas. Anota una duda concreta si falta información. Una recomendación de preparación local no cambia las reglas del intento recibido; confirma el uso de documentación, IDE externo o IA con las instrucciones aplicables.

Oficial: Codility explica en cómo se evalúan las soluciones que el código debe compilar y que se ejecutan varios casos para comprobar corrección y escalabilidad. Utiliza esa distinción para revisar tu preparación. Los ejemplos y nuestros contadores sirven para revisar el código; no establecen una nota de corte ni un resultado de la plataforma.

El trabajo aquí se ejecutó localmente con CPython 3.12.14. No abrimos una evaluación privada ni enviamos las implementaciones a Codility. Si tu prueba utiliza otro lenguaje, tendrás que comprobar sus tipos, límites y firma: el razonamiento puede transferirse, pero el programa no se vuelve compatible por cambiarle el nombre.

Define el menor código positivo que falta

Oficial y público: Codility publica una demostración llamada MissingInteger sobre el menor entero positivo ausente. Nuestro laboratorio trabaja ese concepto clásico con otros datos, un caso vacío adicional y contadores propios. No reproduce una invitación de selección ni promete que ese ejercicio aparecerá en ella.

Imagina una lista de códigos enteros, con repeticiones y valores que no son positivos. Queremos el menor código mayor que cero que no aparece. Para [2, 1, 2, 5, -4], la respuesta es 3: uno y dos existen, mientras que tres no. El resultado no es el número de códigos distintos ni el máximo más uno.

Antes de programar, decide qué asunciones pertenecen al contrato. En nuestro laboratorio una lista vacía devuelve uno, y la función conserva la entrada. La demostración pública tiene sus propios límites; este caso vacío es una ampliación para estudiar la inicialización. En una evaluación, prueba primero los casos válidos del enunciado recibido.

Si la lista tiene n posiciones, la respuesta está entre uno y n+1. Para que faltase un valor mayor, tendrían que estar presentes todos los n+1 positivos anteriores, algo imposible con solo n elementos. Esta cota permite ignorar números muy grandes al diseñar una estructura indexada por los posibles resultados.

Conserva una solución correcta que puedas explicar

Una estrategia sencilla prueba los candidatos 1, 2, 3… y busca cada uno recorriendo la lista. Devuelve el primero que no encuentra. El límite anterior garantiza que la búsqueda termina como máximo en n+1. Esta versión constituye una referencia útil porque su conexión con el contrato es directa.

En [2, 1, 2, 5, -4], encuentra uno en la segunda posición, dos en la primera y recorre toda la lista buscando tres. Su lentitud depende de cuántos candidatos debe buscar y de cuánto tarda cada búsqueda. Para analizar esos dos bucles, cuenta cuántas comparaciones hacen cuando los primeros n positivos están presentes.

Tomemos [1, 2, …, n]. Encontrar uno requiere una comparación, encontrar dos requiere dos, y así hasta n. Para comprobar que n+1 falta, vuelve a examinar los n elementos. El total es 1+2+…+n+n, es decir, n(n+3)/2 comparaciones de igualdad. Este crecimiento es cuadrático, aunque la respuesta sea correcta.

La misma implementación usa poca memoria auxiliar y no altera los datos. Eso no la convierte automáticamente en una elección adecuada para un tamaño grande. Guarda su resultado como referencia para casos pequeños: podrás detectar si una optimización cambia la respuesta; evita ejecutar una versión deliberadamente cuadrática sobre una entrada enorme solo para observar que tarda.

Detecta una optimización que cambia la pregunta

Oficial: Python define un set como una colección de elementos distintos. Eliminar duplicados puede ayudar a comprobar pertenencia; el tamaño de ese conjunto no demuestra que sus valores formen una secuencia sin huecos.

Una versión defectuosa filtra los positivos, crea el conjunto y retorna su tamaño más uno. Con [1, 4, 4], conserva {1, 4} y devuelve tres. La respuesta correcta es dos. Esta función puede completar su trabajo con rapidez y seguir incumpliendo el contrato: confundió cantidad de valores distintos con continuidad desde uno.

El contraejemplo revela qué hay que reparar. No necesitas añadir una excepción que devuelva dos cuando encuentre exactamente esa lista; debes comprobar los candidatos en orden hasta el primer ausente. El caso [1, 4, 4] conserva dos positivos distintos y deja el hueco dos: comprueba directamente la continuidad que la versión defectuosa daba por hecha.

Puedes construir una solución basada en pertenencia a un conjunto. Su análisis debe reconocer el comportamiento de la estructura elegida. Nuestro ejemplo corregido usa marcas indexadas para que el argumento de crecimiento dependa de la cota n+1, y para poder contar accesos explícitos sin presentar una búsqueda hash como una garantía universal del lenguaje.

Corrige con una tabla de presencia acotada

Crea una tabla de n+1 posiciones booleanas, de cero a n. La posición cero queda sin usar. Para cada valor x entre uno y n, marca seen[x]. Después busca la primera posición sin marcar entre uno y n; si todas están marcadas, devuelve n+1 sin acceder a esa posición adicional.

def solution(values):
    n = len(values)
    seen = [False] * (n + 1)
    for x in values:
        if 1 <= x <= n:
            seen[x] = True
    for candidate in range(1, n + 1):
        if not seen[candidate]:
            return candidate
    return n + 1

La condición de rango importa. Un negativo no debe utilizarse como índice de la tabla: Python permite índices negativos, pero aquí no representan códigos positivos. Un valor superior a n tampoco necesita una casilla, porque no cambia cuál de los primeros n+1 candidatos falta.

La primera pasada conserva este invariante: cada marca verdadera corresponde a un candidato que ha aparecido. Los duplicados vuelven a marcar la misma posición. La segunda pasada revisa los candidatos de menor a mayor, por lo que el primer falso es la respuesta mínima. Si no aparece ninguno, la cota justifica el retorno final.

Inicializar la tabla, recorrer la entrada y revisar las marcas requiere O(n) trabajo bajo el modelo usual de acceso a listas. La memoria auxiliar es O(n). Hemos elegido ese coste para conservar los datos; una técnica que reutilice la propia lista tendría otros riesgos de modificación y otra explicación de corrección.

Cuenta operaciones antes de hablar de velocidad

El laboratorio instrumenta las dos versiones correctas sobre la misma familia [1, 2, …, n]. La lenta cuenta comparaciones de igualdad. La corregida registra visitas a valores y lecturas de marcas por separado:

Al duplicar n, las comparaciones se acercan a multiplicarse por cuatro, mientras las visitas y lecturas se duplican. Estas cantidades son unidades distintas. No permiten afirmar que una versión tarda cierto múltiplo de segundos menos: tampoco incluyen del mismo modo cada instrucción, la inicialización o el coste del intérprete.

El archivo results.json conserva las mediciones realizadas, el resultado y los contadores. No usamos cronómetro ni registramos un benchmark. Para n=100.000, la fórmula de la versión lenta predice 5.000.150.000 comparaciones sobre esa familia; ese número es una derivación, no una ejecución realizada. La versión corregida sí se comprobó con los primeros 100.000 positivos y devolvió 100.001.

Oficial: las lecciones de complejidad temporal ofrecen ejercicios para practicar este análisis. Nuestra recomendación es acompañar la notación O(n) u O(n²) con una entrada que explique el crecimiento. Esa evidencia ayuda a localizar el trabajo repetido que necesita una estructura diferente.

Usa una matriz que distinga los defectos

La siguiente matriz pertenece al laboratorio. Cada caso cuestiona una decisión concreta de implementación:

El recibo results.json registra 17 comprobaciones ejecutadas con CPython 3.12.14. Incluye preservación de la entrada, invariancia al reordenar, valores irrelevantes y las tres mediciones de contadores. También documenta el resultado incorrecto deliberado de la versión rápida; no interpreta esa observación como un test fallido de la solución corregida.

Un oráculo distinto ordena los positivos únicos y detecta el primer hueco. La búsqueda lenta y la tabla de marcas coinciden con él en 9.331 listas de longitud cero a cinco, formadas por -2, 0, 1, 2, 3, 7. Es evidencia acotada sobre nuestras implementaciones, no una cobertura de los casos ocultos de Codility.

Para reproducirlo, descomprime el ZIP y ejecuta python3 missing_code_lab.py desde su carpeta. El paquete incluye el código, el README y los recibos JSON y CSV. Es una práctica local con biblioteca estándar, sin credenciales ni acceso a un examen; no verifica permisos, red ni condiciones de una evaluación real. Comprueba después que tu versión final mantiene el tipo de retorno y la firma exigidos por la pregunta real.

Continúa con una propiedad diferente

Reportes de candidatos en PracHub: estas preguntas registradas sirven para practicar variaciones. Su presencia no confirma que una empresa las utilice en Codility ni anuncia tu evaluación.

Elige una de las preguntas de Software Engineer y prepara un argumento de corrección, un contraejemplo y una entrada adversaria de tamaño creciente. Vuelve luego a tu invitación para confirmar el entorno y la entrega. Así relacionas cada decisión del código con una evidencia que puedes explicar y reproducir.

Sources and Further Reading

• Codility: I got an invitation to complete a Codility assessment
• Codility: How will my solutions be assessed?
• Codility: MissingInteger public demo
• Codility: Time Complexity lesson
• Python: set and frozenset