如何测试Python编程技能?Yandex的任务


后端开发学院的Hackathon

在2019年,我们需要自动测试与数百名开发人员一起编写Python代码的能力。因此,我们选择了后端开发学院的未来学生。这与面试中提供解决问题的方法不同。另一方面,我们也无法重用已经为编程比赛准备的任务条件。事实是,确定最好的最好的竞争是一回事,而选择在学校中经验很少的专家则是另一回事。我们需要执行任务,通过解决方案,可以明确开发人员是否具有编写代码的基本技能以及正确使用内存和时间的能力。这些是我们创造的条件。

常用物品

解决方案作者:Mikhail Shushpanov 米舒什

给定一个由n个整数组成的数组,有 50%的参与者解决了这个问题编写一个程序,查找在数组中最常见的数字。时间限制:2秒,内存限制:256 MB。

输入格式输入
的第一行包含数字n(1≤n≤300,000)。
第二行包含n个整数一个(0≤一个 ≤1 000 000 000)。

输出格式
仅打印数字x,这是数组a中最常出现的最大数字。

决断
一个简单的任务既可以使用常规词典也可以使用collections模块中的Counter结构来解决。

首先,您可以计算每个元素出现的次数,然后选择出现次数最多的元素中的最大元素。该解决方案需要O(n)时间和O(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) 

序列元素值

作者:Mikhail Shushpanov。 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 MB。

输入格式输入
的第一行包含一个整数n(1≤n≤1000)。
第二行包含n个非负整数(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)) 

实施加入

发言者:德米特里·特罗夫(Dmitry Terrov) 可怕的6%的参与者解决了该任务,并给出了

两个表T1和T2。每个表由两个数字字段表示。表T1包含字段a和b。表T2包含字段a和c。

必须在字段a和表单表T3中实现两个表的SQL JOIN的简化变体。

表中字段a的值可以重复,但每个字段的重复次数不超过5个。时间限制:1秒,内存限制:64 MB。

输入格式
输入的第一行包含一个整数n1(1≤n1≤15000)–表T1中的行数。然后,在n1行中,用空格分隔写入两个整数-表T1的字段ai和bi(1≤ai,bi≤1000)的值。下一行包含一个整数n2(1≤n2≤10000)–表T2中的行数。然后,在n2行中,用空格写两个整数-表T2的字段aj和cj(1≤aj,cj≤1000)的值。最后一行是操作的名称(INNER,LEFT,RIGHT,FULL)。

输出格式
在第一行中,打印数字n3-表T3中的行数。在接下来的n3行中,通过空格打印表T3的空格值ak,bk和ck。如果由于联接表而导致缺少字段的值,请打印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. , . , .

删除空值

作者:Mikhail Shushpanov。7%的参与者解决了这个问题。

编写一个程序从JSON结构中删除空字典({})或空列表([])的值,只要有这样的值即可。如果字典中的值被删除,相应的键也将被删除。时间限制:0.2秒,内存限制:6 MB。

输入格式
单个输入行包含一个长度为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 MB。

输入格式输入
的第一行包含一个整数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)

系列长度编码

决定的作者:米哈伊尔·舒什帕诺夫(Mikhail Shushpanov)。有33%的参与者解决了该问题。

系列长度编码(RLE)-一种数据压缩算法,用一个字符和迭代次数替换重复的字符。系列是由几个相同的字符(一个以上)组成的序列。编码时,组成一系列的相同字符的字符串将被包含重复字符本身及其重复次数的字符串替换。

例如,字符串AAAABBB将被压缩为字符串A4B3,字符串AAAAAAAAAAAAAAAABAAAAA被压缩为字符串A15BA5。

给您一个压缩的字符串,找到原始字符串的长度。源字符串的长度不超过1000个字符,源字符串的所有字符均为拉丁字母的大写字母。时间限制:2秒,内存限制:264 MB。

输入格式
单行输入包含非空行。确保该字符串是某些字符串正确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检测器

作者:Sergey Demurin kakty37%的参与者解决了该问题,并

列出了N个IP地址。如果有M条连续的行,其中该IP地址出现至少K次,我们称该IP地址为“坏”。时间限制:10秒,内存限制:10 MB。

输入格式
第一行包含数字N(1≤N≤10 6)。
第二行包含数字M(1≤M≤10 3)。
第三行包含数字K(1≤K≤M)。
接下来的N行包含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()

这些任务是后端开发学校入门作业的第一部分。第二部分(云服务)将在未来几周内发布和分析。

如果您对支持者竞赛感兴趣,请阅读第一第二届编程锦标赛的后端轨迹分析

All Articles