Get best of the week

Comment tester les compétences de programmation Python? Tâches de Yandex


Hackathon à la School of Backend Development

En 2019, nous devions tester automatiquement la capacité d'écrire du code Python avec des centaines de développeurs. Nous avons donc sélectionné les futurs étudiants de la Backend Development School. Ce n'est pas la même chose que de proposer de résoudre un problème sur une feuille de papier, comme dans une interview. D'autre part, nous n'avons pas non plus pu réutiliser les conditions de tâches déjà préparées pour nos compétitions de programmation. Le fait est que la compétition pour déterminer le meilleur des meilleurs est une chose, et la sélection de spécialistes ayant peu d'expérience à l'école en est une autre. Nous avions besoin de tâches, par la solution desquelles il serait clair si le développeur avait les compétences de base d'écriture de code et la capacité d'utiliser correctement la mémoire et le temps. Ce sont les conditions que nous avons établies.

Article fréquent

Auteur de la solution: Mikhail Shushpanov mishush. Le problème a été résolu par 50% des participants, étant

donné un tableau a de n entiers. Écrivez un programme qui trouve le nombre le plus souvent trouvé dans le tableau. Limite de temps: 2 s, limite de mémoire: 256 Mo.

Format d'entrée
La première ligne d'entrée contient le nombre n (1 ≤ n ≤ 300 000).
La deuxième ligne contient n entiers a i (0 ≤ a i ≤ 1 000 000 000).

Format de sortie
Imprimez le seul nombre x, le plus grand des nombres que l'on trouve le plus souvent dans le tableau a.

Décision
Une tâche simple qui peut être résolue à la fois à l'aide d'un dictionnaire standard et à l'aide de la structure Compteur du module collections.

Tout d'abord, vous pouvez calculer le nombre de fois que chaque élément se produit, puis sélectionner le plus grand de ceux qui se produisent le plus grand nombre de fois. La solution nécessite O (n) de temps et O (n) de mémoire supplémentaire.

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)

Valeurs des éléments de séquence

Auteur: Mikhail Shushpanov. Le problème a été résolu par 20% des participants.

La séquence f 0 , f 1 , f 2 , ... est donnée par les relations de récurrence f 0 = 0, f 1 = 1, f 2 = 2, f k = f k - 1 + f k - 3 .

Écrivez un programme qui calcule n éléments de cette séquence avec les nombres k 1 , k 2 , ..., k n . Limite de temps: 1 s, limite de mémoire: 10 Mo.

Format d'entrée
La première ligne d'entrée contient un entier n (1 ≤ n ≤ 1000).
La deuxième ligne contient n entiers non négatifs (0 ≤ ki ≤ 16000), séparés par des espaces.

Format de
sortie Valeurs séparées par un espace de sortie f k 1 , f k 2 , ..., f k n .

Décision
, . .

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

Implémenter JOIN

Publié par: Dmitry Terrov terrmit. La tâche a été résolue par 6% des participants,

deux tableaux T1 et T2 sont fournis. Chaque table est représentée par deux champs numériques. Le tableau T1 contient les champs a et b. Le tableau T2 contient les champs a et c.

Il est nécessaire d'implémenter une variation simplifiée du SQL JOIN de deux tables dans le champ a et la table de formulaire T3.

Les valeurs du champ a dans le tableau peuvent être dupliquées, mais le nombre de duplications de chaque champ ne dépasse pas 5. Limite de temps: 1 s, limite de mémoire: 64 Mo.

Format d'entrée
La première ligne de l'entrée contient un entier n1 (1 ≤ n1 ≤ 15000) –– le nombre de lignes du tableau T1. Ensuite, en n1 lignes, deux entiers sont écrits séparés par des espaces - les valeurs des champs ai et bi (1 ≤ ai, bi ≤ 1000) du tableau T1. La ligne suivante contient un entier n2 (1 ≤ n2 ≤ 10000) –– le nombre de lignes dans le tableau T2. Ensuite, en n2 lignes, deux entiers sont écrits avec un espace - les valeurs des champs aj et cj (1 ≤ aj, cj ≤ 1000) du tableau T2. La dernière ligne est le nom de l'opération (INNER, LEFT, RIGHT, FULL).

Format de sortie
Sur la première ligne, imprimez le nombre n3 - le nombre de lignes du tableau T3. Dans les n3 lignes suivantes, imprimez les valeurs d'espace ak, bk et ck de la table T3 à travers un espace. Si, suite à la jointure de tables, la valeur d'un champ est manquante, imprimez NULL au lieu de ce champ. L'ordre de sortie des lignes du tableau T3 n'est pas important.

Décision
, 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. , . , .

Suppression de valeurs nulles

Auteur: Mikhail Shushpanov. 7% des participants ont résolu le problème.

Écrivez un programme qui supprime des valeurs de la structure JSON qui sont des dictionnaires vides ({}) ou des listes vides ([]), tant qu'il existe de telles valeurs. Si la valeur du dictionnaire est supprimée, la clé correspondante est également supprimée. Limite de temps: 0,2 s, limite de mémoire: 6 Mo.

Format d'entrée
Une seule ligne d'entrée contient une chaîne de longueur n (1 ≤ n ≤ 1000). Il est garanti que cette chaîne est une chaîne JSON valide.

Format de sortie:
affichez, à travers un espace, le nombre de dictionnaires vides supprimés et le nombre de listes vides supprimées.

Décision
. , -, , 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)

Charge élevée

Auteur de la solution: Dmitry Terrov. Le problème a été résolu par 14% des participants.

On vous donne un historique des séances sur un service fictif. Chaque session est caractérisée par les heures de début et de fin si et fi, pour plus de commodité, toutes ces valeurs sont différentes.

Trouvez le moment t où le plus grand nombre de sessions était actif. S'il y a plusieurs de ces moments, imprimez le plus tôt possible. Limite de temps: 1 s, limite de mémoire: 256 Mo.

Format d'entrée
La première ligne d'entrée contient un entier n (1 ≤ n ≤ 1000). Ensuite, n lignes contiennent deux entiers séparés par un espace si et fi (0 ≤ si <fi ≤ 1 000 000 000).

Format de sortie
Imprimez l'heure souhaitée t.

Décision
, — , . — 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)

Codage de longueur de série

L'auteur de la décision: Mikhail Shushpanov. Le problème a été résolu par 33% des participants

Series Length Coding (RLE) - un algorithme de compression de données qui remplace les caractères répétés par un caractère et le nombre d'itérations. Une série est une séquence composée de plusieurs personnages identiques (plus d'un). Lors de l'encodage, une chaîne de caractères identiques qui composent une série est remplacée par une chaîne contenant le caractère répétitif lui-même et le nombre de répétitions.

Par exemple, la chaîne AAAABBB sera compressée en chaîne A4B3 et la chaîne AAAAAAAAAAAAAAAABAAAAA en chaîne A15BA5.

On vous donne une chaîne compressée, trouvez la longueur de la chaîne d'origine. La longueur de la chaîne source ne dépasse pas 1000 caractères, tous les caractères de la chaîne source sont des majuscules de l'alphabet latin. Limite de temps: 2 s, limite de mémoire: 264 Mo.

Format d'entrée
Une seule ligne d'entrée contient une ligne non vide. Il est garanti que cette chaîne est le résultat de la compression RLE correcte d'une chaîne.

Format de sortie
Imprime la longueur de la chaîne source.

Décision
.

, . , . — . — . , .

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)

Détecteur DDoS

Auteur: Sergey Demurin kakty3. Le problème a été résolu par 7% des participants et une

liste de N adresses IP a été fournie. Nous appelons une adresse IP «mauvaise» s'il y a M lignes consécutives dans lesquelles cette adresse IP apparaît au moins K fois. Limite de temps: 10 s, limite de mémoire: 10 Mo.

Format d'entrée
La première ligne contient le nombre N (1 ≤ N ≤ 10 6 ).
La deuxième ligne contient le nombre M (1 ≤ M ≤ 10 3 ).
La troisième ligne contient le nombre K (1 ≤ K ≤ M).
Les N lignes suivantes contiennent des adresses IP, une par ligne.

Format de sortie
Liste les mauvaises adresses IP dans l'ordre lexicographique.

Décision
: , 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()

Ces tâches étaient la première partie de la mission d'introduction à la Backend Development School. La deuxième partie (service cloud) que nous publierons et analyserons dans les prochaines semaines.

Si vous êtes intéressé par les compétitions pour les backders, lisez l'analyse des pistes back-end des premier et deuxième championnats de programmation.

More articles:


All Articles