Какие алгоритмы разработчики Яндекса реализовывают каждый день23.04.2020 11:18

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

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

В статье четыре примера. Два на C++, один на TypeScript и один на Python. Способность быстро писать относительно простые алгоритмы без багов — общая необходимость, она не зависит от специализации разработчика.

1. Поисковые подсказки в Яндекс.Маркете и ассоциативные массивы

В конце 2016-го года моя команда занималась поисковыми подсказками в мобильной версии Яндекс.Маркета. Нам нужно было адаптировать решения, уже принятые в большом Поиске, к реалиям поиска по товарам. Результаты той работы пользователи Маркета могут видеть и сейчас:

Поисковые подсказки в мобильном Яндекс.Маркете

Старые подсказки Маркета содержали только названия товаров и, скажем, среди них нельзя было встретить строчку «купить телевизор», хотя такой запрос пользователи задавали довольно часто. Поэтому среди прочего мы хотели добавить в саджест Маркета тексты поисковых запросов. Но эти запросы содержат специфические товарные стоп-слова или стоп-фразы — ничего не меняющие в смысле, но очень часто встречающиеся, например: «где купить», «дёшево», «лучший». Такие фразы пользователи дописывают в любые части любых запросов, и из-за этого первая версия нового алгоритма постоянно предлагала дописать к запросу что-то вроде «купить» и «дёшево», и это выглядело максимально странно.

Мы хотели подсказывать только содержательные продолжения запросов. Реализовать это можно было многими способами, но не хотелось тратить много времени на программирование идеального решения, так что сделали следующее: товарные стоп-фраз собрали в отдельный словарь, каждую фразу превратили в набор хешей от нормализованных слов и пар нормализованных слов; аналогичное действие совершили с поисковыми запросами. Затем запросы, в множестве хешей для которых встречались хеши стоп-фраз, выкидывались. Основную логику реализовывала функция:

bool ContainsStopHash(const TString& text,
                      TEasyParser& easyParser,
                      const THashSet& stopHashes)
{
    std::vector words;
    easyParser.ParseUTF8Text(text, &words);

    size_t unigramHash = 0;
    size_t bigramHash = 0;

    for (const TString& word : words) {
        const size_t lastUnigramHash = unigramHash;
        const size_t wordHash = word.hash();
        unigramHash = wordHash;
        bigramHash ^= wordHash;
        if (stopHashes.contains(unigramHash) || stopHashes.contains(bigramHash)) {
            return true;
        }
        bigramHash ^= lastUnigramHash;
    }
    return false;
}

Здесь TEasyParser — класс, реализующий превращение текста в вектор слов, приведённых к начальным формам, THashSet — аналог std::unordered_set, а TString — наш класс для строк.

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

2. Reservoir sampling на MapReduce

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

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

Пример фактового ответа

Общий объём данных для каждого из ключей может быть сколь угодно большим, поэтому нельзя, например, вычитать все данные и перемешать их, нужно делать что-то более хитрое. Тем не менее, можно адаптировать идею из стандартной реализации метода std: shuffle.

Если коротко, то идея следующая. Допустим, нужно случайным образом перемешать массив. Будем обрабатывать элементы по одному, слева направо; рассматривая очередной элемент с номером i, сгенерируем случайное число от 0 до i включительно и обменяем значениями текущий элемент и элемент на выбранной позиции.

Адаптировать этот алгоритм к нашей ситуации можно так. Представим, что мы перемешиваем входные данные случайным образом, а затем берём K стартовых элементов — очевидно, это будет статистически корректный способ. Чтобы получить первые K элементов, не нужно хранить весь перемешанный массив, по существу можно хранить только первые K элементов. В алгоритм std: shuffle тогда можно внести такое изменение: если очередной элемент меняется местами с одним из первых K элементов — помещаем его туда, а если нет, то не делаем ничего.

Другими словами: будем обрабатывать входные элементы по одному и при обработке очередного i-го элемента будем выбирать случайный номер от 0 до i включительно. Если этот номер меньше, чем K — поместим текущий объект в ответ, при необходимости исключив из него какой-то ранее уже добавленный элемент. Код reducer’а выглядит так:

void Do(TMRReader* input, TMRWriter* output) override {
    TVector sample;

    TMersenne mersenne;
    size_t passedItems = 0;

    for (; input->IsValid(); input->Next()) {
        ++passedItems;
        size_t position = mersenne.GenRand64() % passedItems;

        if (position >= ItemsToTake) {
            continue;
        }

        if (sample.size() < ItemsToTake) {
            sample.push_back(input->GetRow());
        } else {
            sample[position] = input->GetRow();
        }
    }

    Shuffle(sample.begin(), sample.end(), mersenne);
    for (const TNode& node : sample) {
        output->Add(node);
    }
}

Здесь TMersenne — наша реализация алгоритма mersenne twister, то есть хороший генератор псевдослучайных чисел, TNode — структура, хранящая одну строку MapReduce-таблицы.

Эта реализация позволяет тратить объём дополнительной памяти, пропорциональный длине ответа и не зависящий от объёма входных данных.

3. Обработка параметров и TypeScript

Алгоритмы в широком смысле слова приходится писать не только бэкенд-разработчикам. В этом примере — отрывок кода клиентской части одного из наших сервисов.

При обработке url’ов иногда приходится сталкиваться с неудобствами в работе с параметрами. Например, url может содержать путь /action?param=¶m=1;2;3¶m=8, тогда стандартные средства работы с параметрами url порождают такую структуру:

{
    "param" : ["", "1;2;3", "8"]
}

С такой структурой неудобно работать, так как элементы массива невозможно обрабатывать единообразно. Было бы удобнее работать, например, с такой структурой:

{
    "param" : ["1", "2", "3", "8"]
}

Для её получения была написана функция:

export type TParamValue = string | string[];
export type TParams = Record;

export function normalizeParams(params: TParams): TParams {
    const result = {};

    for (const [paramName, paramValue] of Object.entries(params)) {
        // массив может быть при наличии двух одинаковых query-параметров
        if (Array.isArray(paramValue)) {
            result[paramName] = paramValue.reduce((acc, part) => {
                if (part) {
                    acc = acc.concat(part.split(';').filter(Boolean));
                }

                return acc;
            }, []);
        } else if (paramValue) {
            result[paramName] = paramValue.split(';').filter(Boolean);
        }
    }

    return result;
}

Здесь разработчику потребовалось продемонстрировать два важных навыка. Первый — обнаружить и обработать все краевые случаи. Второй — написать реализацию достаточно быстро и надёжно: если на реализацию, тестирование и отладку подобного кода тратить уж слишком много времени, поддерживать необходимый темп релизов никак не получится.

4. Python для аналитики

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

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

count = 0
firstPos = -1
clicks = 0

for block in blocks:
    result = bl.GetMainResult()
    if result.IsA('TWebResult'):
        url = result.Url
        pos = result.Pos
        propValue = result.PropValue

        if propValue in interestingValues:
            count += 1

            if firstPos == -1:
                firstPos = pos

            for cl in bl.GetClicks():
                clicks += 1

yield Record(count=count,pos=pos,clicks=clicks)

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

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

5. Как это соотносится с собеседованиями

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

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

def foo(nums):
    current = 0
    best = 0;
    for n in nums:
        if n > 0:
            current += 1
            best = max(best, current)
        else:
            current = 0
    return best

Вторая задача. Даны две строки. Необходимо проверить, являются ли они анаграммами: отличаются ли они только порядком следования букв. Требуется сделать это за линейное время и при этом не менять входные параметры.

def dictFromString(s):
    d = defaultdict(int)
    for c in s:
        d[c] += 1
    return d

def areAnagrams(a, b):
    return dictFromString(a) == dictFromString(b)

Третья задача. Генерация правильных скобочных последовательностей: дано число n. Необходимо распечатать все правильные скобочные последовательности длины 2n в лексикографическом порядке.

def generate(cur, open, closed, n):
    if len(cur) == 2 * n:
        print cur
        return
    if open < n:
        generate(cur + '(', open + 1, closed, n)
    if closed < open:
        generate(cur + ')', open, closed + 1, n)
def parens(n):
    generate('', 0, 0, n)

Итого, и в работе, и на собеседованиях программисту нужно уметь:

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

Кандидаты, претендующие на позиции старших и ведущих специалистов, обязательно проходят и другие секции — архитектуру, machine learning, управление проектами, в общем, те, которые соответствуют их сильным сторонам. Поэтому не стоит думать, что алгоритмические секции на собеседованиях дают несправедливое преимущество программистам-олимпиадникам: чтобы претендовать на старшие позиции, нужно не только уметь бодро писать код, но и обладать более специфичными знаниями.

Большое спасибо Никите Макарову aka nkmakarov, Сергею Вавинову, Елене Кунаковой, Егору Омельченко за помощь в подготовке статьи и отрывков кода!