В прошлой статье я рассказывал про One Day Offer Fronted, сегодня поделюсь впечатлениями об аналогичном мероприятии для бэкенд разработчиков.

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

Коротко о правилах: 4 задачи, на решение дается 3 часа. Минимальный порог для прохождения 100 баллов т.е. достаточно решить любые 2. Задачи можно решать на Java, С++ или Python.

Задача 1 Сложный массив (50 баллов)

Дан массив , элементами которого могут быть целые числа или массивы такой же структуры. Некоторые массивы могут быть пустыми или содержать только один вложенный массив.

Например массив может иметь следующую структуру: [1, 2, 3, [5, 5], 6, [7, 8, 9, [10, 11]]].

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

В единственной строке записано представление массива. Элементы массива (числа и массивы) разделены запятой и пробелом. Перед первым элементом каждого массива записан символ '[', после последнего элемента записан символ ']'. Гарантируется, что все числа по абсолютной величине менее . В массиве есть хотя бы одно число. Размер входных данных не превышает 1MB.

Сложно сказать есть ли тут подвох и прошел бы вариант с парсингом json и использованием flatten. Но я решил действовать прямолинейно - удаляю все скобки и спличу по запятой.

numbers = line
    .replace(' ', '')
    .replace('[', '')
    .replace(']', '')
    .split(',')
    
collections.Counter(numbers)

Задача 2 Лучшее приближение (50 баллов)

Расстояние Хэмминга (кодовое расстояние) — число позиций, в которых соответствующие символы двух слов одинаковой длины различны. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых -ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.

Вам даны пары бинарных строк одинаковой длины . Найдите бинарную строку , для которой величина минимальна ( — расстояние Хемминга между строками и ). Если бинарных строк минимизирующих данную величину несколько, выведите любую из них.

Такого рода задачи в разных вариациях есть на литкоде, с формулировкой про монетки. Например, монетки надо перевернуть определенным образом, чтобы отсортировать последовательность за минимальное количество переворотов (или перестановок).

Тут похожий принцип. Максимальная величина будет минимальной, если строка будет отличаться от и на одинаковое расстояние.

#любопытный факт: эта функция была сгенерирована copilot-ом, по сигнатуре def hamming
def hamming(a, b):
    return sum(c1 != c2 for c1, c2 in zip(a, b))

def getMinHamming(a, b):
    # Количество переворотов равно половине расстояния между a и b
    # Таким образом расстояние до a и до b будет одинаковым и следовательно максимум будет минимальным
    flipCount = hamming(a, b) // 2

    result = [char for char in a]
    for i in range(len(b)):
        #если значения не совпадают, меняем первые flipCount знаков
        if b[i] != a[i]:
            result[i] = b[i]
            flipCount -= 1
        if flipCount == 0:
            break
    
    return ''.join(result)

Задача 3 i10n (25 баллов)

Для некоторых терминов с большим количество букв принято использовать сокращения: вместо или вместо .

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

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

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

Заведем словарь где ключ сокращенное слово, а значение - слово которое можно сократить этим префиксом. Для каждой строки перебираем префиксы и проверяем есть ли они в словаре, если его там нет - сохраняем. Если есть увеличиваем префикс для слова в словаре и для слова. Мне понадобилось еще несколько словарей, чтобы отслеживать строки которые уже появлялись в результатах, и связывать строку со сжатой. Код получился очень грязным, но свою задачу выполняет.

#Для сохранения промежуточных результатов
usedResults = {}
#ключ - сжатый текст, значение - исходный текст
result = {}
#ключ - исходный текст, значение - сжатый текст для быстрого поиска
resultMapper = {}

def compress(st, n):
    if prefix * 2 >= len(st) - 1:
        return st

    return st[:n] + str(len(st) - n * 2) + st[-n:]


def updateResult(compressed, prefix):
    tmp = resultMapper[compressed]
    del resultMapper[compressed]
    del result [tmp]
    compressed = compress(tmp, prefix)
    resultMapper[compressed] = tmp
    result[tmp] = compressed

for st in data:
    for i in range(len(st) // 2):
        compressed = compress(st, i+1)

        
        if not compressed in usedResults:
            usedResults[compressed] = True

            if compressed in resultMapper:
                updateResult(compressed, i+2)
                continue

            result[st] = compressed
            resultMapper[compressed] = st
            break
    
        # такая строка уже была, удалим ее из словаря и перезапишем ее новым значением
        if compressed in resultMapper:
            updateResult(compressed, i+2)

Задача 4 Arithmetics Inc. (75 баллов)

Компания Arithmetics Inc. разрабатывает программное обеспечение для работы с бесконечными арифметическими прогрессиями. Необходимо разработать структуру данных, которая будет хранить арифметические прогрессии и поддерживать следующие операции:

1. Операция первого типа позволяет добавить новую арифметическую прогрессию в структуру.
2. Операция второго типа позволяет удалить заданную арифметическую прогрессию из структуры.
3. Операция третьего типа находит арифметическую прогрессию с минимальным первым элементом и возвращает найденный элемент, предварительно заменив стартовый элемент в прогрессии на следующей в ней.

Если таких прогрессий несколько, то обрабатывается прогрессия, у которой минимальный идентификатор.

На вход подается одно целое положительное число Далее на вход подаются строк в следующем формате:

- Если это операция первого типа, то на вход подаются четыре числа — первый элемент и разность добавляемой прогрессии, а также ее идентификатор.
- Если это операция второго типа, то на вход подаются два числа — идентификатор прогрессии, которую необходимо удалить.
- Если это операция третьего типа, то на вход подается одно число . В этот момент хотя бы одна прогрессия будет находиться в структуре.

Гарантируется, что все арифметических прогрессий различны. Удаляемая прогрессия, гарантированно находится в структуре данных.

Интересная задачка, где за туманной формулировкой, предлагается сделать очередь с приоритетом. Пример решения есть в документации python. Если коротко, то решение основывается на куче и словаре. Куча используется для вставки за , а словарь используется для хранения признака удаленного элемента, чтобы обеспечить удаление за константное время.

Необходимое количество баллов набрано с запасом. Похожие задачи я решал раньше, поэтому проблем не возникло. Осталось дождаться собеседования 30 июля.

Своим результатом, я в принципе доволен, я люблю порешать задачки на время. В итоге задачи мне понравились, особенно третья. Четвертая задача тоже интересная, если решать ее первый раз. В последнее время я готовлюсь к собеседованиям на литкоде и заметил, что раньше в было больше задач на графы. Теперь больше задач на очереди, графов почти нет, интересно почему так.

Спасибо за внимание.