كيف تختبر مهارات برمجة Python؟ المهام من Yandex


Hackathon في مدرسة Backend Development

في عام 2019 ، كنا بحاجة إلى اختبار القدرة تلقائيًا على كتابة رمز Python مع مئات المطورين. لذلك اخترنا طلاب المستقبل لمدرسة Backend Development School. هذا ليس مثل عرض حل مشكلة على قطعة من الورق ، كما هو الحال في المقابلة. من ناحية أخرى ، لم نتمكن أيضًا من إعادة استخدام شروط المهمة التي تم إعدادها بالفعل لمسابقات البرمجة لدينا. والحقيقة هي أن المنافسة لتحديد الأفضل هي شيء ، واختيار المتخصصين ذوي الخبرة القليلة في المدرسة شيء آخر. كنا بحاجة إلى المهام ، والتي سيتضح من خلالها الحل ما إذا كان المطور لديه مهارات كتابة التعليمات البرمجية الأساسية والقدرة على استخدام الذاكرة والوقت بشكل صحيح. هذه هي الشروط التي وضعناها.

عنصر متكرر

مؤلف الحل: ميخائيل شوشبانوف mishush. تم حل المشكلة من قبل 50٪ من المشاركين ، مع

إعطاء مصفوفة من الأعداد الصحيحة. اكتب برنامجًا يعثر على الرقم الذي يوجد غالبًا في المصفوفة. الحد الزمني: 2 ثانية ، حد الذاكرة: 256 ميجابايت.

تنسيق
الإدخال يحتوي السطر الأول من الإدخال على الرقم n (1 ≤ n ≤ 300،000).
يحتوي السطر الثاني على n أعداد صحيحة a i (0 ≤ a i ≤ 1 0000000 000).

تنسيق الإخراج
اطبع الرقم x فقط ، وهو أكبر عدد من الأرقام التي توجد غالبًا في المصفوفة a.

القرار
مهمة بسيطة يمكن حلها باستخدام قاموس عادي واستخدام بنية العداد من وحدة المجموعات.

أولاً ، يمكنك حساب عدد المرات التي يحدث فيها كل عنصر ، ثم تحديد أكبر تلك التي تحدث أكبر عدد من المرات. يتطلب الحل وقتًا (n) وذاكرة إضافية (n).

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) 

قيم عنصر التسلسل

المؤلف: ميخائيل شوشبانوف. تم حل المشكلة بواسطة 20٪ من المشاركين.

التسلسل f 0 ، f 1 ، f 2 ، ... يعبر عن علاقات التكرار f 0 = 0، f 1 = 1، f 2 = 2، f k = f k - 1 + f k - 3 .

اكتب برنامجًا يحسب n عناصر هذا التسلسل بالأرقام k 1 ، k 2 ، ...، k n . الحد الزمني: 1 ثانية ، حد الذاكرة: 10 ميجابايت.

تنسيق
الإدخال يحتوي السطر الأول من الإدخال على عدد صحيح n (1 ≤ n ≤ 1000).
يحتوي السطر الثاني على عدد صحيح غير سالب (0 ≤ kط ≤ 16000) ، مفصولة بمسافات.

تنسيق
الإخراج إخراج قيم مفصولة بمسافة الإخراج f k 1 ، f k 2 ، ...، f k 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)) 

تنفيذ JOIN

تم النشر بواسطة: ديمتري تروف إرميت. تم حل المهمة بواسطة 6٪ من المشاركين ،

وتم تقديم جدولين T1 و T2. يتم تمثيل كل جدول بحقلين رقميين. يحتوي الجدول T1 على الحقلين a و b. يحتوي الجدول T2 على الحقلين a و c.

من الضروري تنفيذ اختلاف مبسط لـ SQL JOIN لجدولين في الحقل a وجدول النموذج T3.

يمكن تكرار قيم الحقل a في الجدول ، ولكن لا يتجاوز عدد التكرارات لكل حقل 5. المهلة الزمنية: ثانية واحدة ، حد الذاكرة: 64 ميغابايت.

نمط الإدخال
يحتوي السطر الأول من الإدخال على عدد صحيح n1 (1 ≤ n1 ≤ 15000) - عدد الصفوف في الجدول T1. بعد ذلك ، في الأسطر n1 ، يتم كتابة عددين صحيحين مفصولين بمسافات - قيم الحقول ai و bi (1 ≤ ai ، bi ≤ 1000) من الجدول T1. يحتوي السطر التالي على عدد صحيح n2 (1 ≤ n2 ≤ 10000) –– عدد الصفوف في الجدول T2. بعد ذلك ، في أسطر n2 ، يتم كتابة رقمين صحيحين بمسافة - قيم الحقول aj و cj (1 ≤ aj، cj ≤ 1000) من الجدول T2. السطر الأخير هو اسم العملية (INNER ، LEFT ، RIGHT ، FULL).

تنسيق الإخراج
في السطر الأول طباعة الرقم n3 - عدد الصفوف في الجدول T3. في الأسطر n3 التالية ، اطبع قيم المسافة ak و bk و ck للجدول T3 من خلال مسافة. إذا كانت قيمة الحقل مفقودة نتيجة لربط الجداول ، اطبع NULL بدلاً من هذا الحقل. ترتيب إخراج الصفوف في الجدول T3 غير مهم.

القرار
, 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. , . , .

حذف القيم الخالية

المؤلف: ميخائيل شوشبانوف. قام 7٪ من المشاركين بحل المشكلة.

اكتب برنامجًا يزيل القيم من بنية JSON التي تكون قواميس فارغة ({}) أو قوائم فارغة ([]) ، طالما كانت هناك مثل هذه القيم. إذا تم حذف القيمة في القاموس ، فسيتم حذف المفتاح المقابل أيضًا. الحد الزمني: 0.2 ثانية ، حد الذاكرة: 6 ميغابايت.

تنسيق
الإدخال يحتوي خط الإدخال الواحد على سلسلة بطول n (1 ≤ n ≤ 1000). من المضمون أن هذه السلسلة هي سلسلة JSON صالحة.

تنسيق الإخراج:
الإخراج ، من خلال مسافة ، عدد القواميس الفارغة المحذوفة وعدد القوائم الفارغة المحذوفة.

القرار
. , -, , 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) 

حمل زائد

مؤلف الحل: Dmitry Terrov. تم حل المشكلة من قبل 14٪ من المشاركين ،

ويتم منحك تاريخًا من الجلسات حول بعض الخدمات الوهمية. تتميز كل جلسة بوقت البدء والانتهاء si و fi ، للراحة ، كل هذه القيم مختلفة.

حدد النقطة الزمنية t عندما كان أكبر عدد من الجلسات نشطًا. إذا كان هناك العديد من هذه اللحظات ، فقم بطباعتها مبكرًا. الحد الزمني: 1 ثانية ، حد الذاكرة: 256 ميجابايت.

تنسيق
الإدخال يحتوي السطر الأول من الإدخال على عدد صحيح n (1 ≤ n ≤ 1000). بعد ذلك ، تحتوي السطور n على عددين صحيحين مفصولين بمسافة si و fi (0 ≤ si <fi ≤ 1،000،000،000).

تنسيق الإخراج
طباعة الوقت المطلوب t.

القرار
, — , . — 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)

ترميز طول السلسلة

صاحب القرار: ميخائيل شوشبانوف. تم حل المشكلة عن طريق 33 ٪ من المشاركين

طول السلسلة (RLE) - خوارزمية ضغط البيانات التي تستبدل الأحرف المتكررة بحرف واحد وعدد التكرارات. السلسلة هي سلسلة تتكون من عدة أحرف متطابقة (أكثر من واحد). عند الترميز ، يتم استبدال سلسلة من الأحرف المتطابقة التي تتكون منها سلسلة بسلسلة تحتوي على الحرف المكرر نفسه وعدد مرات تكرارها.

على سبيل المثال ، سيتم ضغط السلسلة AAAABBB إلى السلسلة A4B3 ، والسلسلة AAAAAAAAAAAAAAAABAAAAA إلى السلسلة A15BA5.

يتم إعطاؤك سلسلة مضغوطة ، ابحث عن طول السلسلة الأصلية. لا يتجاوز طول السلسلة المصدر 1000 حرف ، وجميع أحرف السلسلة المصدر هي أحرف كبيرة من الأبجدية اللاتينية. الحد الزمني: 2 ثانية ، حد الذاكرة: 264 ميجابايت.

نمط الإدخال
يحتوي سطر إدخال واحد على سطر غير فارغ. من المضمون أن هذه السلسلة هي نتيجة ضغط RLE الصحيح لبعض السلسلة.

تنسيق الإخراج
طباعة طول سلسلة المصدر.

القرار
.

, . , . — . — . , .

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

المؤلف: سيرجي ديمورين kakty3. تم حل المشكلة من قبل 7٪ من المشاركين وتم تقديم

قائمة بعناوين IP N. نسمي عنوان IP بأنه "سيئ" إذا كانت هناك سطور متتالية M يحدث فيها عنوان IP هذا على الأقل K مرة. الحد الزمني: 10 ثانية ، حد الذاكرة: 10 ميغابايت.

تنسيق الإدخال
يحتوي السطر الأول على الرقم N (1 ≤ N ≤ 10 6 ).
يحتوي السطر الثاني على الرقم M (1 ≤ M ≤ 10 3 ).
يحتوي السطر الثالث على الرقم K (1 ≤ K ≤ M).
تحتوي السطور التالية على عناوين IP ، عنوان لكل سطر.

نسق الإخراج سرد
عناوين IP السيئة بترتيب معجمي.

القرار
: , 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()

كانت هذه المهام الجزء الأول من المهمة التمهيدية لمدرسة تطوير الخلفية. الجزء الثاني (الخدمة السحابية) الذي سننشره ونحلله في الأسابيع القادمة.

إذا كنت مهتما في منافسات backders، وقراءة تحليل مسارات الخلفية من الأولى و الثانية بطولة البرمجة.

All Articles