company_banner

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


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

    В 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()

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

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

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

      +1
      Режим зануды:
      В последнем примере кода если адрес уже есть в списке плохих, то от него остаётся счётчик, который уйдёт в отрицательные числа, и тогда при некоторых условиях число счётчиков превысит 1000.
      print('\n'.join(current_ip for current_ip in sorted(bad_ips)))

      Зачем так, можно же
      print('\n'.join(sorted(bad_ips)))
        0
        В последнем примере кода если адрес уже есть в списке плохих, то от него остаётся счётчик, который уйдёт в отрицательные числа, и тогда при некоторых условиях число счётчиков превысит 1000.

        Не понял момент про отрицательное значение счетчика. Когда адрес добавляется в список плохих, то его счетчик удаляется. Если этот адрес встречается дальше, ты мы его просто пропускаем.
          0
          Всё верно, после добавления ip в список плохих счётчик удаляется и далее пропускается, счётчик ip не увеличивается.
          Однако ip попадает в очередь и позже удаляется из очереди, при этом счётчик ip всегда уменьшается (при уменьшении счётчик для ip тоже создаётся), дополнительной проверки oldest_ip in bad_ips там нету.
        +1

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

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

            Блоки с решением лучше было бы не спойлерить и спрятать, имхо :) так сложнее знакомиться со статьёй

              +1
              готово!
              0

              Решение первой задачи проще:


              Counter(arr).most_common(1)
                +1
                Это неверное решение. В условии задачи написано, что нужно вернуть наибольшее из чисел, которое чаще других встречается в массиве.
                Для массива [1, 1, 2, 2] в вашем решении ответ будет 1. Правильный ответ — 2.
                  0
                  Если arr = [0, 0, 10, 10],
                  то Counter(arr).most_common(1) вернёт [(0, 2)] — число 0 встречается 2 раза,
                  а нужно вернуть 10, т.к. оно тоже встречается также 2 раза и больше 0.
                    0

                    Вот это решает проблему:


                    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)

                    Но оказалось, что решение в посте работает прилично быстрее.

                  0
                  а есть где примеры задач на senior. яп не важен
                    0

                    На позицию Senior уже не задачки на каком-то языке даются, а другое...

                    0
                    А мне нравятся задачи на аттестации преподавателей, забавные и оригинальные.
                    Вообще ребята-методисты в яндексе по питону клевые.
                      0

                      Спасибо за статью. А в чем состояла автоматизация проверки?

                        0
                        Вторая задача, строго говоря, 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 можем посчитать любой элемент с заранее выбранной точностью, не используя рекуррентное соотношение.
                          0
                          Для решения любой задачи не требовалось каких-либо специальных знаний в смежных областях.
                          Путь в целом верный, но тяжёлый. Например,
                          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)) времени.
                          0
                          Как в решении 1й задачи учтено ограничение на n-размерность массива?
                          Предлагаемый вариант решения разве можно считать 100% полным?
                            0
                            Вот в первой задаче нам нужно ввести n. Но введя этот код и проверив я не понял на что оно влияет, оно дальше даже не используется.

                            Так вот, вопрос такой, зачем в первой задаче число n если и без него работает
                              0
                              Ну это скорее всего плохие тесты от организаторов, раз приведённый пример кода решает задачу. Можно привести пример с n=1, после чего дать на вход три числа [1, 2, 2] — правильный ответ будет 1, так как дальше первого элемента работать не должно согласно условиям задачи
                                0
                                Входные данные всегда были корректными. Если n = 1, то в следующей строке ровно одно число.
                              0
                              Кодирование длин серий
                              Были участники, которые решили задачу с помощью регулярных выражений.

                              И правильно сделали, как мне кажется.


                              Сильно уж они все упрощают
                              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)

                              С другой стороны, решение в статье более прямолинейное и его, возможно, проще осмыслить.

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

                              Самое читаемое