Как проверить навыки программирования на Python? Задачи от Яндекса / forpes.ru

Главная
Как проверить навыки программирования на Python? Задачи от Яндекса

Как проверить навыки программирования на Python? Задачи от Яндекса +16

18.02.2020 08:59

Leono 22 20100 Источник

^{_{Хакатон в Школе бэкенд-разработки}}

В 2019 году нам потребовалось автоматизированно проверить умение писать Python-код у сотен разработчиков. Так мы отбирали будущих студентов для Школы бэкенд-разработки. Это не то же самое, что предложить решить задачу на листе бумаги, как на собеседовании. С другой стороны, мы также не могли переиспользовать условия задач, уже подготовленные для наших соревнований по программированию. Дело в том, что соревнования с целью определить лучших из лучших — это одно, а отбор специалистов с небольшим опытом в школу — совсем другое. Нам требовались задачи, по решению которых было бы видно, обладает ли разработчик базовыми навыками написания кода и умением грамотно использовать память и время. Вот какие условия мы составили.

Частый элемент

^{Автор решения: Михаил Шушпанов mishush. Задачу решили 50% участников}

Дан массив a из n целых чисел. Напишите программу, которая найдет число, которое чаще других встречается в массиве. Ограничение времени: 2 с, ограничение памяти: 256 МБ.

Формат ввода
В первой строке входных данных записано число n (1 ? n ? 300?000).
Во второй строке записаны n целых чисел a_i (0 ? a_i ? 1?000?000?000).

Формат вывода
Выведите единственное число x, наибольшее из чисел, которое чаще других встречается в массиве a.

Решение

Простая задача, которую можно решить как с использованием обычного словаря, так и с использованием структуры Counter из модуля collections.

Сначала можно посчитать, сколько раз встречается каждый элемент, затем выбрать наибольший из тех, которые встречаются наибольшее число раз. Решение требует 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)

Значения элементов последовательности

^{Автор: Михаил Шушпанов. Задачу решили 20% участников}

Последовательность f₀, f₁, f₂,… задана рекуррентными соотношениями f₀ = 0, f₁ = 1, f₂ = 2, f_k = f_k–1 + f_k–3.

Напишите программу, которая вычисляет n элементов этой последовательности c номерами k₁, k₂, ..., k_n. Ограничение времени: 1 с, ограничение памяти: 10 МБ.

Формат ввода
В первой строке входных данных записано целое число n (1 ? n ? 1000).
Во второй строке записаны n целых неотрицательных чисел (0 ? k_i ? 16000), разделенных пробелами.

Формат вывода
Выведите через пробел значения f_k₁, f_k₂, ..., f_{k_n}.

Решение

В задаче нужно было не только подобрать оптимальный по времени алгоритм, но и использовать как можно меньше дополнительной памяти. Большинство присланных решений не уложились в ограничения по времени или по памяти.

Заметим, что для вычисления f_k необходимо вычислить f₀, f₁, ..., f_k–1. Поэтому достаточно вычислить f_k, где k = max(k₁, k₂, ..., k_n). Кроме того, для вычисления нужны лишь и f_k–1 и f_k–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

^{Автор: Дмитрий Терров terrmit. Задачу решили 6% участников}

Даны две таблицы T1 и T2. Каждая таблица представлена двумя числовыми полями. Таблица T1 содержит поля a и b. Таблица T2 содержит поля a и с.

Необходимо реализовать упрощенную вариацию SQL JOIN двух таблиц по полю a и сформировать таблицу T3.

Значения поля a в таблице могут дублироваться, но количество дублирований каждого поля не превышает 5. Ограничение времени: 1 с, ограничение памяти: 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)

Высокая нагрузка

^{Автор решения: Дмитрий Терров. Задачу решили 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, а строка AAAAAAAAAAAAAAABAAAAA — в строку 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% участников}

Дан список из N IP-адресов. Назовем IP-адрес «плохим», если существует M подряд идущих строк, в которых этот IP-адрес встречается хотя бы K раз. Ограничение времени: 10 с, ограничение памяти: 10 МБ.

Формат ввода
Первая строка содержит число N (1 ? N ? 10⁶).
Вторая строка содержит число M (1 ? M ? 10³).
Третья строка содержит число K (1 ? K ? M).
В следующих N строках записаны IP-адреса, по одному на строку.

Формат вывода
Выведите список «плохих» IP-адресов в лексикографическом порядке.

Решение

Наивное решение: сохранить все адреса в список, а потом пройтись по нему окном длиной M и найти адреса, которых в этом окне больше K штук. Такое решение сработает на первых простых тестах, но дальше не пройдет из-за лимитов по памяти и по времени.

Улучшение: на самом деле нам не нужен список всех адресов — достаточно иметь список M последних адресов. Его удобно хранить с помощью дека длины M. В деке можно искать адреса, количество которых ? K. Это более удачное решение, но поскольку на каждом шаге мы будем подсчитывать адреса в деке, то все равно не уложимся в лимит по времени.

Чтобы на каждом шаге не пересчитывать адреса заново, будем для каждого адреса хранить счетчик — сколько раз он встречается в списке последних М адресов. При чтении нового адреса будем:
— уменьшать счетчик на единицу для самого старого адреса и увеличивать на единицу для нового,
— а затем добавлять в список «плохих» адресов новый адрес, если счетчик для него достиг K.

Но это решение не уложится в лимит по памяти, если все IP-адреса уникальные. Тогда количество счетчиков достигнет 10⁶. Однако для большинства адресов счетчик будет содержать ноль. Другими словами, если счетчик адреса при уменьшении достиг нуля, то достаточно удалить этот счетчик из памяти. Тогда количество счетчиков не привысит 10³.

Финальное решение требует 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()

Перечисленные задачи были первой частью вступительного задания в Школу бэкенд-разработки. Вторую часть (облачный сервис) мы опубликуем и разберём в ближайшие недели.

Если вам интересны соревнования для бэкендеров, почитайте разборы бэкенд-треков первого и второго чемпионата по программированию.

Комментарии (22)

GCU
18.02.2020 15:03
#21291882
Режим зануды:
В последнем примере кода если адрес уже есть в списке плохих, то от него остаётся счётчик, который уйдёт в отрицательные числа, и тогда при некоторых условиях число счётчиков превысит 1000.
```
print('\n'.join(current_ip for current_ip in sorted(bad_ips)))
```
Зачем так, можно же
```
print('\n'.join(sorted(bad_ips)))
```
1. kakty3
  19.02.2020 18:58
  #21298410
  В последнем примере кода если адрес уже есть в списке плохих, то от него остаётся счётчик, который уйдёт в отрицательные числа, и тогда при некоторых условиях число счётчиков превысит 1000.
  
  Не понял момент про отрицательное значение счетчика. Когда адрес добавляется в список плохих, то его счетчик удаляется. Если этот адрес встречается дальше, ты мы его просто пропускаем.
  1. GCU
    19.02.2020 23:00
    #21299438
    Всё верно, после добавления ip в список плохих счётчик удаляется и далее пропускается, счётчик ip не увеличивается.
    Однако ip попадает в очередь и позже удаляется из очереди, при этом счётчик ip всегда уменьшается (при уменьшении счётчик для ip тоже создаётся), дополнительной проверки oldest_ip in bad_ips там нету.

floordiv
18.02.2020 15:18
#21291988
Задачи, конечно, элементарные… Высокую нагрузку, и следующую после неё, я решил буквально в одну строку

adante
18.02.2020 16:29
#21292384
Какой был проходной балл? или сколько надо было решить для поступления?
И какие временные рамки?
В куче компаний если вы просто решите все это прямо на собеседовании — это будет сразу оффер на джуниор/мидл.

feliz_hombre
19.02.2020 11:38
#21295718
Блоки с решением лучше было бы не спойлерить и спрятать, имхо :) так сложнее знакомиться со статьёй
1. Leono Автор
  19.02.2020 11:38
  #21295724
  готово!

homm
19.02.2020 15:20
#21297194
Решение первой задачи проще:
```
Counter(arr).most_common(1)
```
1. terrmit
  20.02.2020 00:37
  #21299734
  Это неверное решение. В условии задачи написано, что нужно вернуть наибольшее из чисел, которое чаще других встречается в массиве.
  Для массива [1, 1, 2, 2] в вашем решении ответ будет 1. Правильный ответ — 2.
1. mishush
  20.02.2020 00:37
  #21299736
  Если arr = [0, 0, 10, 10],
  то Counter(arr).most_common(1) вернёт [(0, 2)] — число 0 встречается 2 раза,
  а нужно вернуть 10, т.к. оно тоже встречается также 2 раза и больше 0.
  1. Senpos
    22.02.2020 19:32
    #21310786
    Вот это решает проблему:
    
    from collections import Counter from operator import itemgetter a = [0, 0, 10, 10] counter = Counter(a) result = max(counter.items(), key=itemgetter(1, 0))[0] print(result)
    
    Но оказалось, что решение в посте работает прилично быстрее.

avkhra
19.02.2020 18:58
#21298404
а есть где примеры задач на senior. яп не важен
1. QtRoS
  21.02.2020 10:08
  #21305762
  На позицию Senior уже не задачки на каком-то языке даются, а другое...

greenkey
20.02.2020 00:04
#21299636
А мне нравятся задачи на аттестации преподавателей, забавные и оригинальные.
Вообще ребята-методисты в яндексе по питону клевые.

crazylh
20.02.2020 10:03
#21300702
Спасибо за статью. А в чем состояла автоматизация проверки?

stilor
21.02.2020 08:34
#21305482
Вторая задача, строго говоря, O(1): находим корни характеристического уравнения последовательности, x^3-x^2-1=0 (обозначим x1, x2, x3 — у этого уравнения два из них комплексные) и подбираем коэффициенты A, B, C так, чтобы:
A + B + C = 0
A*x1 + B*x2 + C*x3 = 1
A*x1^2 + B*x2^2 + C*x3^2 = 2

После этого по формуле f(k) = A*x1^k + B*x2^k + C*x3^k можем посчитать любой элемент с заранее выбранной точностью, не используя рекуррентное соотношение.
1. mishush
  21.02.2020 14:15
  #21307052
  Для решения любой задачи не требовалось каких-либо специальных знаний в смежных областях.
  Путь в целом верный, но тяжёлый. Например,
  x1 = 1/3 * (1 + (1/2 * (29 - 3 * sqrt(93)))^(1/3) + (1/2 * (29 + 3 * sqrt(93)))^(1/3)), x2 = 1/3 - 1/6 * (1 - i * sqrt(3)) * (1/2 * (29 - 3 * sqrt(93)))^(1/3) - 1/6 * (1 + i * sqrt(3)) *(1/2 * (29 + 3 * sqrt(93)))^(1/3), x3 = 1/3 - 1/6 * (1 + i * sqrt(3)) * (1/2 * (29 - 3 * sqrt(93)))^(1/3) - 1/6 * (1 - i * sqrt(3)) *(1/2 * (29 + 3 * sqrt(93)))^(1/3).
  Далее,
  A = (2 - x2 - x3)/(x2 - x1)/(x3 - x1), B = (2 - x1 - x3)/(x1 - x2)/(x3 - x2), C = (2 - x1 - x2)/(x1 - x3)/(x2 - x3).
  Наконец, возведение чисел x1, x2, x3 в k-ю степень требует O(log(k)) времени.

diman40
21.02.2020 08:34
#21305484
Как в решении 1й задачи учтено ограничение на n-размерность массива?
Предлагаемый вариант решения разве можно считать 100% полным?

Nikolases
21.02.2020 08:34
#21305486
Вот в первой задаче нам нужно ввести n. Но введя этот код и проверив я не понял на что оно влияет, оно дальше даже не используется.

Так вот, вопрос такой, зачем в первой задаче число n если и без него работает
1. GCU
  21.02.2020 11:25
  #21306240
  Ну это скорее всего плохие тесты от организаторов, раз приведённый пример кода решает задачу. Можно привести пример с n=1, после чего дать на вход три числа [1, 2, 2] — правильный ответ будет 1, так как дальше первого элемента работать не должно согласно условиям задачи
  1. mishush
    21.02.2020 14:21
    #21307066
    Входные данные всегда были корректными. Если n = 1, то в следующей строке ровно одно число.

Senpos
22.02.2020 20:21
#21310898
Кодирование длин серий
Были участники, которые решили задачу с помощью регулярных выражений.
И правильно сделали, как мне кажется.
Сильно уж они все упрощают
import re def decoded_rle_value_len(value): pairs = re.findall(r'(?P<letter>[A-Z])(?P<count>\d*)', value) return sum(int(pair[1]) if pair[1] else 1 for pair in pairs) result = decoded_rle_value_len('A15BA5') print(result)

Как проверить навыки программирования на Python? Задачи от Яндекса +16

Частый элемент

Значения элементов последовательности

Реализовать JOIN

Удаление пустых значений

Высокая нагрузка

Кодирование длин серий

Детектор DDoS

Комментарии (22)

Leono Автор