В 2019 году нам потребовалось автоматизированно проверить умение писать Python-код у сотен разработчиков. Так мы отбирали будущих студентов для Школы бэкенд-разработки. Это не то же самое, что предложить решить задачу на листе бумаги, как на собеседовании. С другой стороны, мы также не могли переиспользовать условия задач, уже подготовленные для наших соревнований по программированию. Дело в том, что соревнования с целью определить лучших из лучших — это одно, а отбор специалистов с небольшим опытом в школу — совсем другое. Нам требовались задачи, по решению которых было бы видно, обладает ли разработчик базовыми навыками написания кода и умением грамотно использовать память и время. Вот какие условия мы составили.
Частый элемент
Дан массив a из n целых чисел. Напишите программу, которая найдет число, которое чаще других встречается в массиве. Ограничение времени: 2 с, ограничение памяти: 256 МБ.
Формат ввода
В первой строке входных данных записано число n (1 ≤ n ≤ 300 000).
Во второй строке записаны n целых чисел ai (0 ≤ ai ≤ 1 000 000 000).
Формат вывода
Выведите единственное число x, наибольшее из чисел, которое чаще других встречается в массиве a
Значения элементов последовательности
Последовательность 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.
Реализовать JOIN
Даны две таблицы 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 не важен.
Удаление пустых значений
Напишите программу, которая из JSON-структуры удаляет значения, являющиеся пустыми словарями ({}) или пустыми списками ([]), до тех пор, пока есть такие значения. Если удаляется значение в словаре, то удаляется и соответствующий ключ. Ограничение времени: 0,2 с, ограничение памяти: 6 МБ.
Формат ввода
В единственной строке входных данных содержится строка длины n (1 ≤ n ≤ 1000). Гарантируется, что эта строка является правильной JSON-строкой.
Формат вывода:
Выведите через пробел количество удаленных пустых словарей и количество удаленных пустых списков
Высокая нагрузка
Вам дана история сессий на некотором вымышленном сервисе. Каждая сессия характеризуется временем начала и временем окончания si и fi, для удобства все эти значения различны.
Найдите такой момент времени t, когда было активно наибольшее количество сессий. Если таких моментов несколько, то выведите самый ранний из них. Ограничение времени: 1 с, ограничение памяти: 256 МБ.
Формат ввода
В первой строке входных данных записано целое число n (1 ≤ n ≤ 1000). Далее в n строках записано через пробел по два целых числа si и fi (0 ≤ si < fi ≤ 1 000 000 000).
Формат вывода
Выведите искомый момент времени t.
Кодирование длин серий
Кодирование длин серий (RLE) — алгоритм сжатия данных, заменяющий повторяющиеся символы на один символ и число его повторов. Серией называется последовательность, состоящая из нескольких одинаковых символов (более одного). При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, содержащей сам повторяющийся символ и количество его повторов.
Например, строка AAAABBB будет сжата в строку A4B3, а строка AAAAAAAAAAAAAAABAAAAA — в строку A15BA5.
Вам дана сжатая строка, найдите длину исходной строки. Длина исходной строки не превышает 1000 символов, все символы исходной строки — заглавные буквы латинского алфавита. Ограничение времени: 2 с, ограничение памяти: 264 МБ.
Формат ввода
В единственной строке входных данных содержится непустая строка. Гарантируется, что эта строка является результатом корректного RLE-сжатия некоторой строки.
Формат вывода
Выведите длину исходной строки.
Детектор DDoS
Дан список из N IP-адресов. Назовем IP-адрес «плохим», если существует M подряд идущих строк, в которых этот IP-адрес встречается хотя бы K раз. Ограничение времени: 10 с, ограничение памяти: 10 МБ.
Формат ввода
Первая строка содержит число N (1 ≤ N ≤ 106).
Вторая строка содержит число M (1 ≤ M ≤ 103).
Третья строка содержит число K (1 ≤ K ≤ M).
В следующих N строках записаны IP-адреса, по одному на строку.
Формат вывода
Выведите список «плохих» IP-адресов в лексикографическом порядке.
Перечисленные задачи были первой частью вступительного задания в Школу бэкенд-разработки. Вторую часть (облачный сервис) мы опубликуем и разберём в ближайшие недели.
Если вам интересны соревнования для бэкендеров, почитайте разборы бэкенд-треков первого и второго чемпионата по программированию.
источник: https://habr.com новости