Get best of the week

Bagaimana cara menguji keterampilan pemrograman Python? Tugas dari Yandex


Hackathon di School of Backend Development

Pada tahun 2019, kami perlu secara otomatis menguji kemampuan untuk menulis kode Python dengan ratusan pengembang. Jadi kami memilih siswa yang akan datang untuk Backend Development School. Ini tidak sama dengan menawarkan untuk menyelesaikan masalah pada selembar kertas, seperti dalam sebuah wawancara. Di sisi lain, kami juga tidak dapat menggunakan kembali kondisi tugas yang sudah disiapkan untuk kompetisi pemrograman kami. Faktanya adalah bahwa kompetisi untuk menentukan yang terbaik dari yang terbaik adalah satu hal, dan pemilihan spesialis dengan sedikit pengalaman di sekolah adalah hal lain. Kami membutuhkan tugas, dengan solusi yang akan jelas apakah pengembang memiliki keterampilan dasar menulis kode dan kemampuan untuk menggunakan memori dan waktu dengan benar. Ini adalah kondisi yang kami buat.

Barang yang sering

Penulis solusi: Mikhail Shushpanov mishush. Masalahnya dipecahkan oleh 50% dari peserta.

Diberikan array dari bilangan bulat. Tulis program yang menemukan nomor yang paling sering ditemukan dalam array. Batas waktu: 2 dtk, batas memori: 256 MB.

Format input
Baris input pertama berisi angka n (1 ≤ n ≤ 300.000).
Baris kedua berisi n bilangan bulat a i (0 ≤ a i ≤ 1 000 000 000).

Format Output
Cetak satu-satunya angka x, angka terbesar yang paling sering ditemukan dalam array a.

Keputusan
Tugas sederhana yang dapat diselesaikan menggunakan kamus reguler dan menggunakan struktur Penghitung dari modul koleksi.

Pertama, Anda dapat menghitung berapa kali setiap elemen terjadi, lalu pilih yang terbesar dari yang terjadi dalam jumlah terbesar. Solusinya memerlukan O (n) waktu dan O (n) memori tambahan.

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)

Nilai Elemen Urutan

Penulis: Mikhail Shushpanov. Masalahnya diselesaikan oleh 20% dari peserta.

Urutan f 0 , f 1 , f 2 , ... diberikan oleh hubungan perulangan f 0 = 0, f 1 = 1, f 2 = 2, f k = f k - 1 + f k - 3 .

Tulis program yang menghitung n elemen dari urutan ini dengan angka k 1 , k 2 , ..., k n . Batas waktu: 1 detik, batas memori: 10 MB.

Format input
Baris input pertama berisi bilangan bulat n (1 ≤ n ≤ 1000).
Baris kedua berisi n bilangan bulat non-negatif (0 ≤ ki ≤ 16000), dipisahkan oleh spasi.

Format
Keluaran Keluaran yang dipisahkan nilai ruang fk 1 , f k 2 , ..., f k n .

Keputusan
, . .

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

Laksanakan BERGABUNG

Dikirim oleh: Dmitry Terrov terrmit. Tugas diselesaikan oleh 6% dari peserta.

Dua tabel T1 dan T2 diberikan. Setiap tabel diwakili oleh dua bidang angka. Tabel T1 berisi bidang a dan b. Tabel T2 berisi bidang a dan c.

Hal ini diperlukan untuk mengimplementasikan variasi yang disederhanakan dari SQL JOIN dari dua tabel di bidang a dan bentuk tabel T3.

Nilai-nilai bidang a dalam tabel dapat diduplikasi, tetapi jumlah duplikasi dari masing-masing bidang tidak melebihi 5. Batas waktu: 1 detik, batas memori: 64 MB.

Masukkan format
Baris pertama input berisi bilangan bulat n1 (1 ≤ n1 ≤ 15000) –– jumlah baris pada tabel T1. Kemudian, dalam baris n1, dua bilangan bulat ditulis dipisahkan oleh spasi - nilai bidang ai dan bi (1 ≤ ai, bi ≤ 1000) dari tabel T1. Baris berikutnya berisi bilangan bulat n2 (1 ≤ n2 ≤ 10000) –– jumlah baris dalam tabel T2. Kemudian, dalam baris n2, dua bilangan bulat ditulis dengan spasi - nilai bidang aj dan cj (1 ≤ aj, cj ≤ 1000) dari tabel T2. Baris terakhir adalah nama operasi (INNER, LEFT, RIGHT, FULL).

Format Output
Pada baris pertama cetak angka n3 - jumlah baris pada tabel T3. Pada baris n3 berikutnya cetak nilai spasi ak, bk dan ck dari tabel T3 melalui spasi. Jika akibat menggabungkan tabel nilai bidang tidak ada, cetak NULL sebagai ganti bidang ini. Urutan output dari baris dalam tabel T3 tidak penting.

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

Menghapus Nilai Null

Penulis: Mikhail Shushpanov. 7% dari peserta menyelesaikan masalah.

Tulis program yang menghapus nilai dari struktur JSON yang merupakan kamus kosong ({}) atau daftar kosong ([]), selama ada nilai-nilai tersebut. Jika nilai dalam kamus dihapus, kunci yang sesuai juga dihapus. Batas waktu: 0,2 s, batas memori: 6 MB.

Format
input Baris input tunggal berisi string dengan panjang n (1 ≤ n ≤ 1000). Dijamin bahwa string ini adalah string JSON yang valid.

Format keluaran:
Keluaran, melalui spasi, jumlah kamus kosong yang dihapus dan jumlah daftar kosong yang dihapus.

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

Beban tinggi

Penulis solusi: Dmitry Terrov. Masalahnya dipecahkan oleh 14% dari peserta.

Anda diberi sejarah sesi pada beberapa layanan fiktif. Setiap sesi ditandai oleh waktu mulai dan berakhir si dan fi, untuk kenyamanan, semua nilai ini berbeda.

Temukan titik waktu t ketika jumlah sesi terbesar aktif. Jika ada beberapa momen seperti itu, maka cetaklah yang paling awal. Batas waktu: 1 detik, batas memori: 256 MB.

Format input
Baris input pertama berisi bilangan bulat n (1 ≤ n ≤ 1000). Kemudian, dalam n baris, dua bilangan bulat si dan fi (0 ≤ si <fi ≤ 1 000 000 000) ditulis dengan spasi.

Format keluaran
Cetak waktu yang diinginkan t.

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

Pengodean Panjang Seri

Penulis keputusan: Mikhail Shushpanov. Masalahnya dipecahkan oleh 33% peserta

Series Length Coding (RLE) - sebuah algoritma kompresi data yang menggantikan karakter yang diulang dengan satu karakter dan jumlah iterasi. Serial adalah urutan yang terdiri dari beberapa karakter identik (lebih dari satu). Saat menyandikan, serangkaian karakter identik yang membentuk suatu seri digantikan oleh string yang berisi karakter berulang itu sendiri dan jumlah pengulangannya.

Sebagai contoh, string AAAABBB akan dikompresi menjadi string A4B3, dan string AAAAAAAAAAAAAAAABAAAAAA ke string A15BA5.

Anda diberi string terkompresi, temukan panjang string asli. Panjang string sumber tidak melebihi 1000 karakter, semua karakter string sumber adalah huruf kapital dari alfabet Latin. Batas waktu: 2 dtk, batas memori: 264 MB.

Masukkan format
Satu baris input berisi baris yang tidak kosong. Dijamin bahwa string ini adalah hasil dari kompresi RLE yang benar dari beberapa string.

Format Output.
Cetak panjang string sumber.

Keputusan
.

, . , . — . — . , .

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)

Detektor DDoS

Penulis: Sergey Demurin kakty3. Masalahnya diselesaikan oleh 7% dari peserta.

Daftar alamat IP N diberikan. Kami menyebut alamat IP "buruk" jika ada M baris berturut-turut di mana alamat IP ini muncul setidaknya K kali. Batas waktu: 10 detik, batas memori: 10 MB.

Format input
Baris pertama berisi angka N (1 ≤ N ≤ 10 6 ).
Baris kedua berisi angka M (1 ≤ M ≤ 10 3 ).
Baris ketiga berisi angka K (1 ≤ K ≤ M).
Baris N berikutnya berisi alamat IP, satu per baris.

Format Output.
Daftar alamat IP yang buruk dalam urutan leksikografis.

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

Tugas-tugas ini adalah bagian pertama dari tugas pengantar ke Backend Development School. Bagian kedua (layanan cloud) akan kami publikasikan dan analisis dalam beberapa minggu mendatang.

Jika Anda tertarik pada kompetisi untuk backders, baca analisis trek backend dari kejuaraan pemrograman pertama dan kedua .

More articles:


All Articles