Como testar as habilidades de programação Python? Tarefas do Yandex


Hackathon na School of Backend Development

Em 2019, precisávamos testar automaticamente a capacidade de escrever código Python com centenas de desenvolvedores. Por isso, selecionamos futuros alunos para a Backend Development School. Isso não é o mesmo que se oferecer para resolver um problema em um pedaço de papel, como em uma entrevista. Por outro lado, também não foi possível reutilizar as condições da tarefa já preparadas para nossas competições de programação. O fato é que a competição para determinar o melhor dos melhores é uma coisa, e a seleção de especialistas com pouca experiência na escola é outra. Precisávamos de tarefas, cuja solução seria clara se o desenvolvedor tinha as habilidades básicas de escrever código e a capacidade de usar corretamente a memória e o tempo. Essas são as condições que criamos.

Item frequente

Autor da solução: Mikhail Shushpanov mishush. O problema foi resolvido por 50% dos participantes, considerando

um conjunto de n números inteiros. Escreva um programa que encontre o número mais frequentemente encontrado na matriz. Limite de tempo: 2 s, limite de memória: 256 MB.

Formato de entrada
A primeira linha de entrada contém o número n (1 ≤ n ≤ 300.000).
A segunda linha contém n números inteiros a i (0 ≤ a i ≤ 1 000 000 000).

Formato de saída
Imprima o único número x, o maior dos números encontrados com mais freqüência na matriz a.

Decisão
Uma tarefa simples que pode ser resolvida usando um dicionário comum e usando a estrutura Counter no módulo de coleções.

Primeiro, você pode calcular quantas vezes cada elemento ocorre e, em seguida, selecionar a maior daquelas que ocorrerem o maior número de vezes. A solução requer O (n) tempo e O (n) memória 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 do elemento de sequência

Autor: Mikhail Shushpanov. O problema foi resolvido por 20% dos participantes.A

sequência f 0 , f 1 , f 2 , ... é dada pelas relações de recorrência f 0 = 0, f 1 = 1, f 2 = 2, f k = f k - 1 + f k - 3 .

Escreva um programa que calcule n elementos dessa sequência com os números k 1 , k 2 , ..., k n . Limite de tempo: 1 s, limite de memória: 10 MB.

Formato de entrada
A primeira linha de entrada contém um número inteiro n (1 ≤ n ≤ 1000).
A segunda linha contém n números inteiros não negativos (0 ≤ ki ≤ 16000), separados por espaços.

Formato de
saída Valores de saída separados por espaço f k 1 , f k 2 , ..., f k n .

Decisão
, . .

, 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 JOIN

Publicado por: Dmitry Terrov terrmit. A tarefa foi resolvida por 6% dos participantes, sendo apresentadas

duas tabelas T1 e T2. Cada tabela é representada por dois campos numéricos. A tabela T1 contém os campos a e b. A tabela T2 contém os campos a e c.

É necessário implementar uma variação simplificada do SQL JOIN de duas tabelas no campo a e formar a tabela T3.

Os valores do campo a na tabela podem ser duplicados, mas o número de duplicações de cada campo não excede 5. Limite de tempo: 1 s, limite de memória: 64 MB.

Formato de entrada
A primeira linha da entrada contém um número inteiro n1 (1 ≤ n1 ≤ 15000) - o número de linhas na tabela T1. Em seguida, em n1 linhas, dois números inteiros são escritos separados por espaços - os valores dos campos ai e bi (1 ≤ ai, bi ≤ 1000) da tabela T1. A próxima linha contém um número inteiro n2 (1 ≤ n2 ≤ 10000) - o número de linhas na tabela T2. Então, em n2 linhas, dois números inteiros são escritos com um espaço - os valores dos campos aj e cj (1 ≤ aj, cj ≤ 1000) da tabela T2. A última linha é o nome da operação (INTERNO, ESQUERDO, DIREITO, CHEIO).

Formato de saída
Na primeira linha, imprima o número n3 - o número de linhas na tabela T3. Nas próximas linhas n3, imprima os valores de espaço ak, bk e ck da tabela T3 através de um espaço. Se, como resultado da junção de tabelas, o valor de um campo estiver ausente, imprima NULL em vez deste campo. A ordem de saída das linhas na tabela T3 não é importante.

Decisão
, 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. , . , .

Excluindo valores nulos

Autor: Mikhail Shushpanov. 7% dos participantes resolveram o problema:

escreva um programa que remova valores da estrutura JSON que são dicionários vazios ({}) ou listas vazias ([]), desde que existam esses valores. Se o valor no dicionário for excluído, a chave correspondente também será excluída. Limite de tempo: 0,2 s, limite de memória: 6 MB.

Formato de entrada
Uma única linha de entrada contém uma sequência de comprimento n (1 ≤ n ≤ 1000). É garantido que essa sequência seja uma sequência JSON válida.

Formato de saída:
gera, através de um espaço, o número de dicionários vazios excluídos e o número de listas vazias excluídas.

Decisão
. , -, , 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) 

Carga elevada

Autor da solução: Dmitry Terrov. O problema foi resolvido por 14% dos participantes.Você

tem um histórico de sessões em algum serviço fictício. Cada sessão é caracterizada pelos horários de início e término si e fi, por conveniência, todos esses valores são diferentes.

Encontre o ponto no tempo t em que o maior número de sessões estava ativo. Se houver vários desses momentos, imprima o primeiro deles. Limite de tempo: 1 s, limite de memória: 256 MB.

Formato de entrada
A primeira linha de entrada contém um número inteiro n (1 ≤ n ≤ 1000). Em seguida, n linhas contêm dois números inteiros separados por espaço si e fi (0 ≤ si <fi ≤ 1.000.000.000).

Formato de saída
Imprima a hora desejada t.

Decisão
, — , . — 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)

Codificação de comprimento de série

O autor da decisão: Mikhail Shushpanov. O problema foi resolvido por 33% dos participantes,

Series Length Coding (RLE) - um algoritmo de compactação de dados que substitui caracteres repetidos por um caractere e o número de iterações. Uma série é uma sequência que consiste em vários caracteres idênticos (mais de um). Ao codificar, uma sequência de caracteres idênticos que compõem uma série é substituída por uma sequência que contém o próprio caractere de repetição e o número de repetições.

Por exemplo, a string AAAABBB será compactada na string A4B3 e a string AAAAAAAAAAAAAAAABAAAAA na string A15BA5.

Você recebe uma sequência compactada, encontre o comprimento da sequência original. O comprimento da cadeia de origem não excede 1000 caracteres, todos os caracteres da cadeia de origem são letras maiúsculas do alfabeto latino. Limite de tempo: 2 s, limite de memória: 264 MB.

Formato de entrada
Uma única linha de entrada contém uma linha não vazia. É garantido que essa sequência seja o resultado da compactação RLE correta de alguma sequência.

Formato de saída
Imprima o comprimento da string de origem.

Decisão
.

, . , . — . — . , .

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. O problema foi resolvido por 7% dos participantes e uma

lista de N endereços IP foi fornecida. Chamamos um endereço IP de "ruim" se houver M linhas consecutivas nas quais esse endereço IP ocorrerá pelo menos K vezes. Limite de tempo: 10 s, limite de memória: 10 MB.

Formato de entrada
A primeira linha contém o número N (1 ≤ N ≤ 10 6 ).
A segunda linha contém o número M (1 ≤ M ≤ 10 3 ).
A terceira linha contém o número K (1 ≤ K ≤ M).
As próximas N linhas contêm endereços IP, um por linha.

Formato de saída
Liste os endereços IP inválidos em ordem lexicográfica.

Decisão
: , 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()

Essas tarefas foram a primeira parte da tarefa introdutória da Backend Development School. A segunda parte (serviço em nuvem) publicaremos e analisaremos nas próximas semanas.

Se você estiver interessado em competições para backders, leia a análise das trilhas de back-end do primeiro e do segundo campeonato de programação.

All Articles