Хакатон в Школе бэкенд-разработки
В 2019 году нам потребовалось автоматизированно проверить умение писать Python-код у сотен разработчиков. Так мы отбирали будущих студентов для Школы бэкенд-разработки. Это не то же самое, что предложить решить задачу на листе бумаги, как на собеседовании. С другой стороны, мы также не могли переиспользовать условия задач, уже подготовленные для наших соревнований по программированию. Дело в том, что соревнования с целью определить лучших из лучших — это одно, а отбор специалистов с небольшим опытом в школу — совсем другое. Нам требовались задачи, по решению которых было бы видно, обладает ли разработчик базовыми навыками написания кода и умением грамотно использовать память и время. Вот какие условия мы составили.
Частый элемент
Автор решения: Михаил Шушпанов mishush. Задачу решили 50% участников
Дан массив a из n целых чисел. Напишите программу, которая найдет число, которое чаще других встречается в массиве. Ограничение времени: 2 с, ограничение памяти: 256 МБ.
Формат ввода
В первой строке входных данных записано число n (1 ≤ n ≤ 300 000).
Во второй строке записаны n целых чисел ai (0 ≤ ai ≤ 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% участников
Последовательность f0, f1, f2,… задана рекуррентными соотношениями f0 = 0, f1 = 1, f2 = 2, fk = fk–1 + fk–3.
Напишите программу, которая вычисляет n элементов этой последовательности c номерами k1, k2, ..., kn. Ограничение времени: 1 с, ограничение памяти: 10 МБ.
Формат ввода
В первой строке входных данных записано целое число n (1 ≤ n ≤ 1000).
Во второй строке записаны n целых неотрицательных чисел (0 ≤ ki ≤ 16000), разделенных пробелами.
Формат вывода
Выведите через пробел значения fk1, fk2, ..., fkn.
Решение
В задаче нужно было не только подобрать оптимальный по времени алгоритм, но и использовать как можно меньше дополнительной памяти. Большинство присланных решений не уложились в ограничения по времени или по памяти.
Заметим, что для вычисления 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
Автор: Дмитрий Терров 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 ≤ 106).
Вторая строка содержит число M (1 ≤ M ≤ 103).
Третья строка содержит число 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()Перечисленные задачи были первой частью вступительного задания в Школу бэкенд-разработки. Вторую часть (облачный сервис) мы опубликуем и разберём в ближайшие недели.
Если вам интересны соревнования для бэкендеров, почитайте разборы бэкенд-треков первого и второго чемпионата по программированию.
Автор: Леонид Клюев
