Wie teste ich Python-Programmierkenntnisse? Aufgaben von Yandex


Hackathon an der School of Backend Development

2019 mussten wir automatisch die Fähigkeit testen, Python-Code mit Hunderten von Entwicklern zu schreiben. Deshalb haben wir zukünftige Schüler für die Backend Development School ausgewählt. Dies ist nicht dasselbe wie das Angebot, ein Problem auf einem Blatt Papier zu lösen, wie in einem Interview. Andererseits konnten wir auch die bereits für unsere Programmierwettbewerbe vorbereiteten Aufgabenbedingungen nicht wiederverwenden. Tatsache ist, dass der Wettbewerb um die Besten der Besten eine Sache ist und die Auswahl von Spezialisten mit wenig Erfahrung in der Schule eine andere. Wir brauchten Aufgaben, bei deren Lösung klar wäre, ob der Entwickler über die grundlegenden Fähigkeiten zum Schreiben von Code und die Fähigkeit verfügt, Speicher und Zeit korrekt zu nutzen. Dies sind die Bedingungen, die wir uns ausgedacht haben.

Häufiger Artikel

Lösungsautor: Mikhail Shushpanov Missgeschick. Das Problem wurde von 50% der Teilnehmer gelöst.

Bei einem Array a von n ganzen Zahlen. Schreiben Sie ein Programm, das die Nummer findet, die am häufigsten im Array gefunden wird. Zeitlimit: 2 s, Speicherlimit: 256 MB.

Eingabeformat
Die erste Eingabezeile enthält die Zahl n (1 ≤ n ≤ 300.000).
Die zweite Zeile enthält n ganze Zahlen a i (0 ≤ a i ≤ 1 000 000 000).

Ausgabeformat
Gibt die einzige Zahl x aus, die größte der Zahlen, die im Array a am häufigsten vorkommt.

Entscheidung
Eine einfache Aufgabe, die sowohl mit einem regulären Wörterbuch als auch mit der Zählerstruktur aus dem Sammlungsmodul gelöst werden kann.

Zuerst können Sie berechnen, wie oft jedes Element vorkommt, und dann die größte auswählen, die am häufigsten vorkommt. Die Lösung benötigt O (n) Zeit und O (n) zusätzlichen Speicher.

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) 

Sequenzelementwerte

Verfasser: Mikhail Shushpanov. Das Problem wurde von 20% der Teilnehmer gelöst.

Die Folge f 0 , f 1 , f 2 , ... ist gegeben durch die Wiederholungsrelationen f 0 = 0, f 1 = 1, f 2 = 2, f k = f k - 1 + f k - 3 .

Schreiben Sie ein Programm, das n Elemente dieser Sequenz mit den Zahlen k 1 , k 2 , ..., k n berechnet. Zeitlimit: 1 s, Speicherlimit: 10 MB.

Eingabeformat
Die erste Eingabezeile enthält eine Ganzzahl n (1 ≤ n ≤ 1000).
Die zweite Zeile enthält n nicht negative ganze Zahlen (0 ≤ ki ≤ 16000), durch Leerzeichen getrennt.

Ausgabeformat Durch
Leerzeichen getrennte Ausgabewerte f k 1 , f k 2 , ..., f k n .

Entscheidung
, . .

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

Implementieren Sie JOIN

Gepostet von: Dmitry Terrov schrecklich. Die Aufgabe wurde von 6% der Teilnehmer gelöst.

Zwei Tabellen T1 und T2 sind angegeben. Jede Tabelle wird durch zwei numerische Felder dargestellt. Tabelle T1 enthält die Felder a und b. Tabelle T2 enthält die Felder a und c.

Es ist notwendig, eine vereinfachte Variation des SQL JOIN von zwei Tabellen im Feld a und in der Formtabelle T3 zu implementieren.

Die Werte von Feld a in der Tabelle können dupliziert werden, aber die Anzahl der Duplikate jedes Felds überschreitet nicht 5. Zeitlimit: 1 s, Speicherlimit: 64 MB.

Eingabeformat
Die erste Zeile der Eingabe enthält eine Ganzzahl n1 (1 ≤ n1 ≤ 15000) - die Anzahl der Zeilen in Tabelle T1. Als nächstes werden in n1 Zeilen zwei durch Leerzeichen getrennte ganze Zahlen geschrieben - die Werte der Felder ai und bi (1 ≤ ai, bi ≤ 1000) der Tabelle T1. Die nächste Zeile enthält eine Ganzzahl n2 (1 ≤ n2 ≤ 10000) - die Anzahl der Zeilen in Tabelle T2. Als nächstes werden in n2 Zeilen zwei ganze Zahlen mit einem Leerzeichen geschrieben - die Werte der Felder aj und cj (1 ≤ aj, cj ≤ 1000) der Tabelle T2. Die letzte Zeile ist der Name der Operation (INNER, LEFT, RIGHT, FULL).

Ausgabeformat Geben Sie
in der ersten Zeile die Nummer n3 ein - die Anzahl der Zeilen in Tabelle T3. In den nächsten n3 Zeilen werden die Leerzeichenwerte ak, bk und ck der Tabelle T3 durch ein Leerzeichen gedruckt. Wenn beim Verknüpfen von Tabellen der Wert eines Felds fehlt, drucken Sie NULL anstelle dieses Felds. Die Ausgabereihenfolge der Zeilen in Tabelle T3 ist nicht wichtig.

Entscheidung
, 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. , . , .

Löschen von Nullwerten

Verfasser: Mikhail Shushpanov. 7% der Teilnehmer haben das Problem gelöst.

Schreiben Sie ein Programm, das Werte aus der JSON-Struktur entfernt, bei denen es sich um leere Wörterbücher ({}) oder leere Listen ([]) handelt, sofern solche Werte vorhanden sind. Wenn der Wert im Wörterbuch gelöscht wird, wird auch der entsprechende Schlüssel gelöscht. Zeitlimit: 0,2 s, Speicherlimit: 6 MB.

Eingabeformat
Eine einzelne Eingabezeile enthält eine Zeichenfolge mit der Länge n (1 ≤ n ≤ 1000). Es wird garantiert, dass diese Zeichenfolge eine gültige JSON-Zeichenfolge ist.

Ausgabeformat:
Geben Sie über ein Leerzeichen die Anzahl der gelöschten leeren Wörterbücher und die Anzahl der gelöschten leeren Listen aus.

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

Hohe Belastung

Lösungsautor: Dmitry Terrov. Das Problem wurde von 14% der Teilnehmer gelöst.

Sie erhalten eine Historie von Sitzungen zu einem fiktiven Dienst. Jede Sitzung ist durch die Start- und Endzeiten si und fi gekennzeichnet. Der Einfachheit halber sind alle diese Werte unterschiedlich.

Finden Sie den Zeitpunkt t, zu dem die größte Anzahl von Sitzungen aktiv war. Wenn es mehrere solcher Momente gibt, drucken Sie den frühesten aus. Zeitlimit: 1 s, Speicherlimit: 256 MB.

Eingabeformat
Die erste Eingabezeile enthält eine Ganzzahl n (1 ≤ n ≤ 1000). Dann werden in n Zeilen zwei ganze Zahlen si und fi (0 ≤ si <fi ≤ 1 000 000 000) mit einem Leerzeichen geschrieben.

Ausgabeformat
Drucken Sie die gewĂĽnschte Zeit t.

Entscheidung
, — , . — 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)

Serienlängencodierung

Der Autor der Entscheidung: Mikhail Shushpanov. Das Problem wurde von 33% der Teilnehmer gelöst.

Series Length Coding (RLE) - ein Datenkomprimierungsalgorithmus, der wiederholte Zeichen durch ein Zeichen und die Anzahl der Iterationen ersetzt. Eine Serie ist eine Sequenz, die aus mehreren identischen Zeichen (mehr als einem) besteht. Beim Codieren wird eine Zeichenfolge identischer Zeichen, aus denen eine Reihe besteht, durch eine Zeichenfolge ersetzt, die das sich wiederholende Zeichen selbst und die Anzahl seiner Wiederholungen enthält.

Beispielsweise wird die Zeichenfolge AAAABBB auf die Zeichenfolge A4B3 und die Zeichenfolge AAAAAAAAAAAAAAAAAAAAAA auf die Zeichenfolge A15BA5 komprimiert.

Wenn Sie eine komprimierte Zeichenfolge erhalten, ermitteln Sie die Länge der ursprünglichen Zeichenfolge. Die Länge der Quellzeichenfolge überschreitet nicht 1000 Zeichen. Alle Zeichen der Quellzeichenfolge sind Großbuchstaben des lateinischen Alphabets. Zeitlimit: 2 s, Speicherlimit: 264 MB.

Eingabeformat
Eine einzelne Eingabezeile enthält eine nicht leere Zeile. Es ist garantiert, dass diese Zeichenfolge das Ergebnis der korrekten RLE-Komprimierung einer Zeichenfolge ist.

Ausgabeformat
Gibt die Länge der Quellzeichenfolge aus.

Entscheidung
.

, . , . — . — . , .

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)

DDoS-Detektor

Verfasser: Sergey Demurin kakty3. Das Problem wurde von 7% der Teilnehmer gelöst. Eine

Liste mit N IP-Adressen wurde angegeben. Wir nennen eine IP-Adresse "schlecht", wenn es M aufeinanderfolgende Zeilen gibt, in denen diese IP-Adresse mindestens K-mal vorkommt. Zeitlimit: 10 s, Speicherlimit: 10 MB.

Eingabeformat
Die erste Zeile enthält die Nummer N (1 ≤ N ≤ 10 6 ).
Die zweite Zeile enthält die Zahl M (1 ≤ M ≤ 10 3 ).
Die dritte Zeile enthält die Zahl K (1 ≤ K ≤ M).
Die nächsten N Zeilen enthalten IP-Adressen, eine pro Zeile.

Ausgabeformat Listet
die fehlerhaften IP-Adressen in lexikografischer Reihenfolge auf.

Entscheidung
: , 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()

Diese Aufgaben waren der erste Teil der Einführungsaufgabe an die Backend Development School. Den zweiten Teil (Cloud Service) werden wir in den kommenden Wochen veröffentlichen und analysieren.

Wenn Sie an Wettbewerben fĂĽr Backder interessiert sind, lesen Sie die Analyse der Backend-Tracks der ersten und zweiten Programmiermeisterschaft.

All Articles