¿Cómo probar las habilidades de programación de Python? Tareas de Yandex


Hackathon en la Escuela de Desarrollo de Backend

En 2019, necesitábamos probar automáticamente la capacidad de escribir código Python con cientos de desarrolladores. Así que seleccionamos futuros estudiantes para la Escuela de Desarrollo de Backend. Esto no es lo mismo que ofrecer resolver un problema en una hoja de papel, como en una entrevista. Por otro lado, tampoco pudimos reutilizar las condiciones de la tarea ya preparadas para nuestras competencias de programación. El hecho es que la competencia para determinar lo mejor de lo mejor es una cosa, y la selección de especialistas con poca experiencia en la escuela es otra. Necesitábamos tareas, cuya solución sería claro si el desarrollador tenía las habilidades básicas de escribir código y la capacidad de usar correctamente la memoria y el tiempo. Estas son las condiciones que inventamos.

Artículo frecuente

Autor de la solución: Mikhail Shushpanov mishush. El problema fue resuelto por el 50% de los participantes,

dada una matriz de n enteros. Escriba un programa que encuentre el número que se encuentra con mayor frecuencia en la matriz. Límite de tiempo: 2 s, límite de memoria: 256 MB.

Formato de entrada
La primera línea de entrada contiene el número n (1 ≤ n ≤ 300,000).
La segunda línea contiene n enteros a i (0 ≤ a i ≤ 1 000 000 000).

Formato de salida
Imprima el único número x, el mayor de los números que se encuentra con mayor frecuencia en la matriz a.

Decisión
Una tarea simple que se puede resolver usando un diccionario regular y usando la estructura Counter del módulo de colecciones.

Primero, puede calcular cuántas veces ocurre cada elemento, luego seleccione la mayor de las que ocurran la mayor cantidad de veces. La solución requiere O (n) tiempo y O (n) memoria adicional.

from collections import Counter

n = int(input()) 
a = [int(i) for i in input().split()] 

counter = Counter(a)

result = a[0]
max_count = counter[result]
for number, count in counter.items():
    if count > max_count or (count == max_count and number > result):
        result = number
        max_count = count

print(result) 

Valores del elemento de secuencia

Autor: Mikhail Shushpanov. El problema fue resuelto por el 20% de los participantes.

La secuencia f 0 , f 1 , f 2 , ... viene dada por las relaciones de recurrencia f 0 = 0, f 1 = 1, f 2 = 2, f k = f k - 1 + f k - 3 .

Escriba un programa que calcule n elementos de esta secuencia con los números k 1 , k 2 , ..., k n . Límite de tiempo: 1 s, límite de memoria: 10 MB.

Formato de entrada
La primera línea de entrada contiene un número entero n (1 ≤ n ≤ 1000).
La segunda línea contiene n enteros no negativos (0 ≤ ki ≤ 16000), separados por espacios.

Formato de
salida Valores separados por espacios de salida f k 1 , f k 2 , ..., f k n .

Decisión
, . .

, fk f0, f1, ..., fk–1. fk, k = max(k1, k2, ..., kn). , fk–1 fk–3, , , .

O(max(k, n)) O(n) .

n = int(input())
indices = [int(i) for i in input().split()]
results = {i: i if i < 3 else None for i in indices}
k = max(indices)
a, b, c = 0, 1, 2
for i in range(3, k + 1):
    a, b, c = b, c, a + c
    if i in results:
        results[i] = c
print(" ".join(str(results[i]) for i in indices)) 

Implementar ÚNASE

Publicado por: Dmitry Terrov terror. La tarea fue resuelta por el 6% de los participantes,

se dan dos tablas T1 y T2. Cada tabla está representada por dos campos numéricos. La tabla T1 contiene los campos ay b. La tabla T2 contiene los campos ayc.

Es necesario implementar una variación simplificada de SQL JOIN de dos tablas en el campo ay la tabla de formulario T3.

Los valores del campo a en la tabla pueden duplicarse, pero el número de duplicaciones de cada campo no excede 5. Límite de tiempo: 1 s, límite de memoria: 64 MB.

Formato de entrada
La primera línea de la entrada contiene un número entero n1 (1 ≤ n1 ≤ 15000) –– el número de filas en la tabla T1. A continuación, en n1 líneas, dos enteros se escriben separados por espacios: los valores de los campos ai y bi (1 ≤ ai, bi ≤ 1000) de la tabla T1. La siguiente línea contiene un número entero n2 (1 ≤ n2 ≤ 10000), el número de filas en la tabla T2. A continuación, en n2 líneas, se escriben dos enteros con un espacio: los valores de los campos aj y cj (1 ≤ aj, cj ≤ 1000) de la tabla T2. La última línea es el nombre de la operación (INTERIOR, IZQUIERDA, DERECHA, COMPLETA).

Formato de salida
En la primera línea imprima el número n3, el número de filas en la tabla T3. En las siguientes líneas n3 imprime los valores de espacio ak, bk y ck de la tabla T3 a través de un espacio. Si como resultado de unir tablas falta el valor de un campo, imprima NULL en lugar de este campo. El orden de salida de las filas en la tabla T3 no es importante.

Decisión
, a . — :

for a1, b in t1:
    for a2, c in t2:
        if a1 == a2:
            t3.append((a1, b, c))

. a. -:

for row in t1:
    t1_map[row[0]] = row

LEFT. , , . — (a, b, c), — (a, b, NULL).

for a, b in t1_map.items():
     if a in t2_map:
         t3.append((a, b, t2[a]))
     else:
         t3.append((a, b, 'NULL'))

RIGHT .

FULL , , :

for a, c in t2_map.items():
    if a not in t1_map:
        t3.append((a, 'NULL', c))

a , hash-map , a. Python itertools.product.

, a , — N x N. , . , .

Eliminar valores nulos

Autor: Mikhail Shushpanov. El 7% de los participantes resolvió el problema.

Escriba un programa que elimine los valores de la estructura JSON que son diccionarios vacíos ({}) o listas vacías ([]), siempre que existan dichos valores. Si se elimina el valor en el diccionario, también se elimina la clave correspondiente. Límite de tiempo: 0.2 s, límite de memoria: 6 MB.

Formato de entrada
Una sola línea de entrada contiene una cadena de longitud n (1 ≤ n ≤ 1000). Se garantiza que esta cadena es una cadena JSON válida.

Formato de salida:
genera, a través de un espacio, la cantidad de diccionarios vacíos eliminados y la cantidad de listas vacías eliminadas.

Decisión
. , -, , JSON. json, isinstance, , Python. JSON {}, [], : , ''{}, []'' .

— , .

import json
dict_counter, list_counter = 0, 0
def clean_struct(struct):
    global dict_counter, list_counter
    if isinstance(struct, dict):
        for key, value in struct.copy().items():
            cleaned_struct = clean_struct(value)
            if cleaned_struct is None:
                del struct[key]
            else:
                struct[key] = cleaned_struct
        if len(struct) == 0:
            dict_counter += 1
            return None
    if isinstance(struct, list):
        i = 0
        while i < len(struct):
            cleaned_struct = clean_struct(struct[i])
            if cleaned_struct is None:
                del struct[i]
            else:
                struct[i] = cleaned_struct
                i += 1
        if len(struct) == 0:
            list_counter += 1
            return None
    return struct
struct = json.loads(input())
clean_struct(struct)
print(dict_counter, list_counter) 

Alta carga

Autor de la solución: Dmitry Terrov. El problema fue resuelto por el 14% de los participantes.

Se le da un historial de sesiones en algún servicio ficticio. Cada sesión se caracteriza por los tiempos de inicio y finalización si y fi, por conveniencia, todos estos valores son diferentes.

Encuentre el momento t cuando la mayor cantidad de sesiones estuvo activa. Si hay varios de esos momentos, imprima el primero de ellos. Límite de tiempo: 1 s, límite de memoria: 256 MB.

Formato de entrada
La primera línea de entrada contiene un número entero n (1 ≤ n ≤ 1000). Luego, n líneas contienen dos enteros separados por espacios si y fi (0 ≤ si <fi ≤ 1,000,000,000).

Formato de salida
Imprima el tiempo deseado t.

Decisión
, — , . — O(N x N).

. — . . , , , — , — . — O(N x log N).

n = int(input())
sessions = []
for _ in range(n):
    x, y = map(int, input().split())
    sessions.append((x, y))

events = []
for start, end in sessions:
    events.append((start, 1))
    events.append((end, -1))
events.sort()

max_number = min_time = cur_number = 0
for cur_time, operation in events:
    cur_number = cur_number + operation
    if cur_number > max_number:
        max_number = cur_number
        min_time = cur_time

print(min_time)

Codificación de longitud de serie

El autor de la decisión: Mikhail Shushpanov. El problema fue resuelto por el 33% de los participantes

. Codificación de longitud de serie (RLE): un algoritmo de compresión de datos que reemplaza los caracteres repetidos con un carácter y el número de iteraciones. Una serie es una secuencia que consta de varios caracteres idénticos (más de uno). Al codificar, una cadena de caracteres idénticos que forman una serie se reemplaza por una cadena que contiene el carácter que se repite y el número de sus repeticiones.

Por ejemplo, la cadena AAAABBB se comprimirá a la cadena A4B3 y la cadena AAAAAAAAAAAAAAAABAAAAA a la cadena A15BA5.

Se le da una cadena comprimida, encuentre la longitud de la cadena original. La longitud de la cadena de origen no supera los 1000 caracteres, todos los caracteres de la cadena de origen son letras mayúsculas del alfabeto latino. Límite de tiempo: 2 s, límite de memoria: 264 MB.

Formato de entrada
Una sola línea de entrada contiene una línea no vacía. Se garantiza que esta cadena es el resultado de la compresión RLE correcta de alguna cadena.

Formato de salida
Imprime la longitud de la cadena de origen.

Decisión
.

, . , . — . — . , .

O(n) O(1) (O(n) ).

first_symbol = True
result = 0
number = ''

for c in input():
    if c.isdigit():
        number += c
    elif c.isalpha() and not number:
        if first_symbol:
            first_symbol = False
        else:
            result += 1
    elif c.isalpha() and number:
        result += int(number)
        number = ''
	
if number:
    result += int(number)
else:
    result += 1
print(result)

Detector DDoS

Autor: Sergey Demurin kakty3. El problema fue resuelto por el 7% de los participantes y se proporcionó una

lista de N direcciones IP. Llamamos a una dirección IP "incorrecta" si hay M líneas consecutivas en las que esta dirección IP se produce al menos K veces. Límite de tiempo: 10 s, límite de memoria: 10 MB.

Formato de entrada
La primera línea contiene el número N (1 ≤ N ≤ 10 6 ).
La segunda línea contiene el número M (1 ≤ M ≤ 10 3 ).
La tercera línea contiene el número K (1 ≤ K ≤ M).
Las siguientes N líneas contienen direcciones IP, una por línea.

Formato de salida
Enumere las direcciones IP incorrectas en orden lexicográfico.

Decisión
: , M , K . , - .

: — M . M. , ≥ K. , , .

, — . :
— ,
— «» , K.

, IP- . 106. . , , . 103.

O(N) IP- O(M) .

# coding: utf-8
from collections import Counter, deque
import sys

def main():
    #   N, M  K
    n_of_lines = int(sys.stdin.readline().strip())
    window_size = int(sys.stdin.readline().strip())
    threshold = int(sys.stdin.readline().strip())

    #    «» ,
    #     
    #   
    bad_ips = set()
    last_ips = deque(maxlen=window_size)
    counter = Counter()

    for _ in range(n_of_lines):
        #  IP-
        current_ip = sys.stdin.readline().rstrip()

        # ,   
        if len(last_ips) == window_size:
            #      
            #      
            oldest_ip = last_ips.pop()
            counter[oldest_ip] -= 1

            #      —  
            if not counter[oldest_ip]:
                del counter[oldest_ip]

        #     
        last_ips.appendleft(current_ip)

        #        «»,
        #      
        if current_ip in bad_ips:
            continue

        #     
        counter[current_ip] += 1

        #      K,
        #      «»
        if counter[current_ip] >= threshold:
            bad_ips.add(current_ip)
            #  «»   ,
            #     
            del counter[current_ip]

    #  «»    
    print('\n'.join(current_ip for current_ip in sorted(bad_ips)))

if __name__ == "__main__":
    main()

Estas tareas fueron la primera parte de la asignación introductoria a la Escuela de Desarrollo de Backend. La segunda parte (servicio en la nube) la publicaremos y analizaremos en las próximas semanas.

Si está interesado en competiciones para patrocinadores, lea el análisis de las pistas de back-end del primer y segundo campeonato de programación.

All Articles