Впечатления от Weekend Offer для бэкенд-разработчиков31.07.2022 12:01

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

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

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

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

Дан массив , элементами которого могут быть целые числа или массивы такой же структуры. Некоторые массивы могут быть пустыми или содержать только один вложенный массив.
Например массив может иметь следующую структуру: [1, 2, 3, [5, 5], 6, [7, 8, 9, [10, 11]]].
Если интерпретировать массив как простую последовательность чисел, определите элементы в массиве, который встречается наибольшее количество раз.
В единственной строке записано представление массива. Элементы массива (числа и массивы) разделены запятой и пробелом. Перед первым элементом каждого массива записан символ '[', после последнего элемента записан символ ']'. Гарантируется, что все числа по абсолютной величине менее $10^{9}$ . В массиве есть хотя бы одно число. Размер входных данных не превышает 1MB.

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

решение

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

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

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

пример

Ввод
5 3
01000 00110
00000 11111
00001 00111
Вывод
01100
01010
00011

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

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

решение

#любопытный факт: эта функция была сгенерирована 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 символов. Для каждой строки определим сокращение , где — некоторый непустой префикс строки , — некоторый непустой суффикс строки , — целое число больше единицы, которое задает количество пропущенных букв между префиксом и суффиксом. Будем рассматривать только такие сокращения, где длины и совпадают.
Из всех сокращений для каждого слова из набора найдите такое, что никакое другое слово не может быть сокращено таким же образом.
Выведите строк, по одной строке для каждого слова из входных данных (в порядке следования во входных данных) — минимальное по длине подходящее под условие задачи сокращение, если подходящего сокращения нет, выведите слово без сокращения.

пример

Ввод

10
aaaa
abaa
abab
bbbb
baba
aaaaaaaaaaaaaaaaaaaa
abaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbb
sjfdhlsakdjfhsald
sdfasdfsadfafdsfdd

Вывод

aaaa
abaa
a2b
b2b
b2a
aa16aa
ab16aa
b18b
s15d
s16d

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

решение

#Для сохранения промежуточных результатов
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. Операция третьего типа находит арифметическую прогрессию с минимальным первым элементом и возвращает найденный элемент, предварительно заменив стартовый элемент в прогрессии на следующей в ней.
Если таких прогрессий несколько, то обрабатывается прогрессия, у которой минимальный идентификатор.
На вход подается одно целое положительное число $q (1 \le q \le 10^5 )$ Далее на вход подаются строк в следующем формате:
— Если это операция первого типа, то на вход подаются четыре числа $1, a_1, d, id (0 \le |a_1|, |d| \le 10^9, 1 \le id \le 10^9)$ — первый элемент и разность добавляемой прогрессии, а также ее идентификатор.
— Если это операция второго типа, то на вход подаются два числа — идентификатор прогрессии, которую необходимо удалить.
— Если это операция третьего типа, то на вход подается одно число . В этот момент хотя бы одна прогрессия будет находиться в структуре.
Гарантируется, что все арифметических прогрессий различны. Удаляемая прогрессия, гарантированно находится в структуре данных.

пример

Ввод

15 1 3 -4 1 1 -5 4 3 1 -2 10 2 3 3 2 3 3 3 2 2 1 -5 4 4 3 2 1 3 3 3

Вывод

-5 -2 3 -1 -5 -5 -1 3

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

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

Общение с рекрутером и собеседование

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

В комментах к прошлой статье отметили, что, возможно, мне просто не повезло. Теперь, похоже, мне не повезло дважды?

Интересно было бы узнать какая цель у этих мероприятий.

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

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