12.09.2017 07:30
nkmakarov 34 18500 Источник

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



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


Квалификацию можно пройти с 18 по 24 сентября включительно. В этом раунде вам нужно будет написать программы для решения шести задач. Можете использовать Java, C++, C# или Python. На всё про всё у вас будет четыре часа. В решающем раунде будут соревноваться те, кто справится как минимум с четырьмя квалификационными задачами. Финал пройдёт одновременно для всех участников — 30 сентября, с 12:00 до 16:00 по московскому времени. Итоги будут подведены 4 октября. Чтобы всем желающим было понятно, с чем они столкнутся на Блице, мы решили разобрать пару похожих задач на Хабре.


1. Robust Execution Manager


Первая задача связана с одной из систем обработки данных, разработанной в Яндексе, — Robust Execution Manager, REM. Он позволяет строить сложные процессы, включающие множество разных операций, и устанавливать зависимости между ними. Так, решение многих задач связано с обработкой пользовательских логов, содержащих информацию о заданных запросах, показанных документах, совершённых кликах и так далее. Поэтому вычисление поискового фактора CTR (click through rate, отношение числа кликов по документу к количеству его показов) зависит от задач обработки пользовательских логов, а от решения задачи вычисления CTR зависит задача доставки значений этого фактора в поисковый runtime. Таким образом, REM позволяет выстраивать цепочки обработки данных, в которых поставщик данных не обязан знать о том, кто эти данные в дальнейшем будет использовать.


В процесс исполнения цепочек обработки могут быть внесены коррективы. Например, уже после построения поисковых логов может выясниться, что значительный объем данных был доставлен с существенной задержкой, и поисковые логи необходимо перестроить. Естественно, после перестроения логов необходимо также перезапустить все процессы, которые от них зависели. Другой пример того же рода — попадание в пользовательские логи запросов, выполненных нашим поисковым роботом. Эти запросы не являются запросами пользователей, а поэтому вносят шум в вычисление поисковых факторов, расчёты экспериментов и так далее. Поэтому в этом случае логи также нужно обновить, после чего перезапустить все процессы их обработки. Поэтому REM поддерживает операцию обновления данных с последующим перезапуском всех задач, зависящих от этих данных.


1.1. Постановка задачи


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


1.2. Решение


Рассмотрим для начала решение задачи в случае, когда вершины из ответа не нужно упорядочивать. Тогда задача решается достаточно просто: запустим из выделенной вершины любой алгоритм обхода графа (например, обход в глубину), и запишем в ответ все посещённые вершины. Действительно, если задачи с номерами $j_1$, $j_2$, ..., $j_k$ зависят по данным от задачи $i$, то после перезапуска задачи $i$ необходимо перезапустить все эти задачи, а также те задачи, что зависят уже от них. Кроме того, каждую вершину нужно вывести ровно один раз. Оба этих условия обеспечиваются стандартными методами обхода графов.


Так может выглядеть решение для данной задачи
#include <iostream>
#include <vector>

using Graph = std::vector<std::vector<int>>;

void DFS(const Graph& graph,
         const int vertice,
         std::vector<bool>& used,
         std::vector<int>& result)
{
    used[vertice] = true;
    result.push_back(vertice);

    for (size_t idx = 0; idx < graph[vertice].size(); ++idx) {
        const int adjacent_vertice = graph[vertice][idx];
        if (!used[adjacent_vertice]) {
            DFS(graph, adjacent_vertice, used, result);
        }
    }
}

void Solve(const Graph& graph,
           const int from,
           std::vector<int>& result)
{
    std::vector<bool> used(graph.size(), false);
    DFS(graph, from, used, result);
}

int main() {
    int vertices, edges;
    std::cin >> vertices >> edges;

    Graph graph(vertices + 1);

    for (int edge = 0; edge < edges; ++edge) {
        int from, to;
        std::cin >> from >> to;
        graph[from].push_back(to);
    }

    int reset_vertice;
    std::cin >> reset_vertice;

    std::vector<int> result;

    Solve(graph, reset_vertice, result);

    for (std::vector<int>::const_iterator it = result.begin();
         it != result.end();
         ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Теперь мы знаем, как сформировать множество вершин, составляющих ответ, но не знаем, как его упорядочить. Рассмотрим пример: пусть от подзадачи $A$ зависят подзадачи $B$ и $C$. В таком случае нам неважно, в каком порядке запускать подзадачи $B$ и $C$. Но что, если между ними существует явная или неявная (через другие подзадачи) зависимость?



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


Используем для решения возникшей проблемы топологическую сортировку вершин, входящих в ответ, то есть, введём некоторый порядок на этом множестве вершин, например: $v_1$, $v_2$,...,$v_k$, и при этом будет верно, что, если $j > i$, то $v_j$ не зависит прямо или косвенно от $v_i$. Известно, что такое упорядочение возможно, если граф не содержит циклов. Топологическая сортировка вершин достигается при помощи обхода в глубину: когда для некоторой вершины посещены все её потомки, она добавляется в начало списка. Итоговый список будет искомой сортировкой вершин графа.


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


Так будет выглядеть полное решение нашей задачи
#include <iostream>
#include <vector>

using Graph = std::vector<std::vector<int>>;

void DFS(const Graph& graph,
         const int vertice,
         std::vector<bool>& used,
         std::vector<int>& result)
{
    used[vertice] = true;
    for (size_t idx = 0; idx < graph[vertice].size(); ++idx) {
        const int adjacent_vertice = graph[vertice][idx];
        if (!used[adjacent_vertice]) {
            DFS(graph, adjacent_vertice, used, result);
        }
    }
    result.push_back(vertice);
}

void Solve(const Graph& graph,
           const int from,
           std::vector<int>& result)
{
    std::vector<bool> used(graph.size(), false);
    DFS(graph, from, used, result);
}

int main() {
    int vertices, edges;
    std::cin >> vertices >> edges;

    Graph graph(vertices + 1);

    for (int edge = 0; edge < edges; ++edge) {
        int from, to;
        std::cin >> from >> to;
        graph[from].push_back(to);
    }

    int reset_vertice;
    std::cin >> reset_vertice;

    std::vector<int> result;

    Solve(graph, reset_vertice, result);

    for (std::vector<int>::const_reverse_iterator it = result.rbegin();
         it != result.rend();
         ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

2. Количество различных бинарных деревьев поиска


Эта задача не имеет непосредственного отношения к библиотекам и программам, разрабатываемым в Яндексе, зато она очень интересная и поэтому часто становится темой для обсуждений на кофепоинтах в свободную минуту. Она является несколько упрощённой версией задачи 9D с codeforces.


2.1. Постановка задачи


Необходимо вычислить, каково количество различных бинарных деревьев поиска, в вершинах которых записаны числа от 1 до $N$. Например, если $N = 3$, существует ровно пять различных деревьев, изображённых на картинке ниже:



Если $N = 5$, то количество деревьев равняется 42. Именно поэтому задача очень нравится нашим разработчикам, среди которых немало ценителей творчества Дугласа Адамса.


2.2. Решение с использованием динамического программирования


Эта задача является достаточно простой для тех, кто знаком с методами динамического программирования. Обозначим за $T_k$ количество различных бинарных деревьев поиска, образованных числами $1$, $2$, ..., $K$. Предположим, что мы знаем $T_0$, $T_1$, $T_2$, ..., $T_N$ и хотим вычислить $T_{N+1}$.


Ясно, что в корне любого дерева будет находиться некоторое число из множества ${1,...,N+1.}$ Обозначим это число за $ t$. Тогда в силу свойств дерева поиска левое поддерево содержит числа $1,...,t-1$, а правое — ${t+1,...,N+1}$. Количество различных возможных способов сформировать левое поддерево тогда равняется $T_{t-1}$, а правое — $T_{N - t + 1}$. Поэтому общее количество деревьев, составленных из чисел $1$, $2$, ..., $N + 1$ и имеющих в корне значение $t$, равняется произведению $T_{t-1}\cdot T_{N - t + 1}$. Для того, чтобы найти общее количество деревьев, необходимо просуммировать это произведение для всех возможных значений $t$:


$T_{N+1} = \sum_{t=1}^{N+1} T_{t-1} \cdot T_{N - t + 1} = \sum_{t=0}^{N} T_{t} \cdot T_{N - t}$


Приведем пример реализации, для разнообразия на языке программирования Python
N = int(raw_input())

result = [1, 1]

for count in xrange(2, N + 1):
    result.append(0)
    for root in xrange(1, count + 1):
        result[-1] += result[root - 1] * result[count - root]

print result[N]

2.3. Связь с числами Каталана


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


$T_{N+1} = C_{N+1} = \frac{C_{2N + 2}^{N+1} }{N + 2}$


В процессе решения задачи про бинарные деревья мы получили рекуррентную формулу, полностью аналогичную рекуррентной формуле, возникающей при решении задачи про количество правильных скобочных последовательностей длины $2N$, которая, как правило, и используется для введения чисел Каталана в курсах по комбинаторике.



Яндекс.Блиц будет проходить на платформе Контест, где мы обычно проводим Алгоритм. Для участия нужно зарегистрироваться. Мы обязательно пришлём вам напоминание о старте раундов.

Комментарии (34)


  1. Varim
    12.09.2017 10:37
    #10411822

    del


  1. deniskin
    12.09.2017 12:01
    #10411938
    +2

    Что такое разработка свеже-социального поиска в Яндексе? Вижу подпись у автора публикации, стало любопытно.


    1. ashagraev
      12.09.2017 12:08
      #10411970
      +1

      Привет :)


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


      С тех пор служба сильно выросла и занимается много чем ещё, но новое подходящее название мы придумать не смогли. Поэтому так и оставили её службой свеже-социального поиска :)


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


      О поисковой свежести я писал вот тут: https://habrahabr.ru/company/yandex/blog/329946/, а потом рассказывал вот тут: https://events.yandex.ru/lib/talks/4690/


      1. deniskin
        12.09.2017 12:13
        #10411980
        +1

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


        1. ashagraev
          12.09.2017 12:15
          #10411988

          Всегда приятно, когда люди интересуются этой темой!


  1. aynanenane
    12.09.2017 12:11
    #10411974
    +9

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

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


    1. ashagraev
      12.09.2017 12:49
      #10412084
      +1

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


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


  1. humbug
    12.09.2017 12:12
    #10411978
    +2

    Яндекс, а вы за решение задач на собеседовании (которое у вас длится 8ч = 4 секции по 2ч) платите деньги? Если да, то Блиц — это существенное снижение ваших затрат на подбор персонала (экономите на бедных проггерах и человекочасах HR и технических специалистов), если нет, то вы нарушаете ТК.

    Если б у меня был выбор, решать за деньги или просто так, я бы выбрал деньги) Объясните, в чем смысл этого Блиц?


    1. kronos
      12.09.2017 12:28
      #10412024
      +3

      Порешать задачки на время и получить фан, почему нет?


      1. saw_tooth
        12.09.2017 12:38
        #10412046
        +2

        Как будто на работе фана не хватает…


      1. humbug
        12.09.2017 12:44
        #10412066
        +6

        Я не понимаю, зачем что-то делать бесплатно, если можно за это получить деньги. У вас наверно интересная разновидность Стокгольмского синдрома.


    1. Femistoklov
      12.09.2017 13:35
      #10412160

      Очевидно, отфильтровать студентов тех, кто готов проходить несколько собеседований по несколько часов и взять лучших.


    1. wataru
      12.09.2017 14:41
      #10412264
      +1

      Я не настоящий сваршик, но отвечу. Очевидно, это чтобы сэкономить деньги: человекочасы рекрутеров. За участие в интервью, я почти уверен, Яндекс не платит. Вообще не знаю ни одной компании, где бы платили. Это же не тестовое задание, которое с натяжкой и иногда хотя бы теоретически можно где-то использовать. Интервью — это задачки-пазлы на 30-60 минут. Которые интервьювер и так умеет решать.


      Со стороны претендентов на работу, этот Блиц — просто замена телефонному интервью. Кому-то это может быть просто приятнее, чем пытаться по телефону что-то объяснить рекрутеру.


    1. ashagraev
      12.09.2017 15:08
      #10412306
      +1

      С точки зрения участника может быть несколько мотивов.


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

      Ещё у этого соревнования есть особенность: задачи в нём некоторым образом связаны с теми задачами, которые приходится решать разработчикам Яндекса в повседневной жизни. Примеры таких связей мы постарались описать в статье. Это понимание может быть интересно и само по себе, и как способ понять, стоит ли пытаться устроиться на работу в Яндекс.


    1. alexeykuzmin0
      12.09.2017 16:01
      #10412428
      +1

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


  1. Legion21
    12.09.2017 12:20
    #10412000
    -1

    Яндекс, для меня, далеко не престижное место работы))) Тем более они загибаются, это отражается на всех их продуктах… а на такси в регионах и подавно


    1. Elsedar
      12.09.2017 13:41
      #10412166
      -2

      А что не так с их такси? Как только оно стало доступно в моем городе, пользуюсь только им. Однозначно лучшее приложение из доступных.


  1. DesolatoR
    12.09.2017 15:03
    #10412302
    +3

    в правилах: только для граждан РФ и РБ :(


  1. 2creker
    12.09.2017 15:13
    #10412318
    +2

    У Вас небольшая опечатка: не T_{i-1}, а T_{t-1}.

    Не понятно какое значение принимает T_0. По определению T_k — это кол-во разных деревьев с числами
    от 1 до k.

    Попробуем провести рассуждение для конкретных значений N+1 и t.
    Пусть N+1 = 3. Мы хотим найти T_{N+1} = T_{3}.

    Ясно, что в корне любого дерева будет находиться некоторое число из множества 1,...,3.
    Обозначим это число за t. Положим t=3.
    Тогда в силу свойств дерева поиска левое поддерево содержит числа 1,..,3-1 = 1,..2.
    А правое 3+1,… Но это больше N+1, поэтому правое поддерево — пустое.
    Посмотрим на рисунок — все верно — для t=3, правое поддерево — пустое.

    Количество различных возможных способов сформировать левое поддерево тогда равняется T_{2} = 2(это можно самому нарисовать),
    а правое T_{3-3} = T_{0}. Но справа деревьев нет, значит T_{0} = 0.

    Но тогда получается, что общее кол-во поддеревьев для t=3 = T_{2} * T_{0} = 2 * 0 = 0

    Хотя по рисунку — их 2.

    Формула работает, только если положить, что T_{0} = 1


    1. nkmakarov Автор
      12.09.2017 15:26
      #10412356
      +2

      Спасибо за внимательность! Опечатку в тексте и в формуле исправили.

      Что касается T_0, то в сумме эта величина используется только при t=N или при t=0. В обоих случаях все элементы, кроме корня, попадают только в одно из поддеревьев. Значит, количество таких вариантов совпадает с количеством способов составить дерево поиска из N элементов. Поэтому, действительно, в этой задаче нужно положить T_0 = 1.


    1. alexeykuzmin0
      12.09.2017 16:03
      #10412432

      В общем-то, все логично, деревьев из 0 узлов ровно одно — дерево без узлов.


    1. aavezel
      14.09.2017 10:07
      #10415590

      Тут на мой взгляд тоже опечатка. Нужно начало брать не T_{0}, а T_{1}=1. Тогда не придется вводить факт допущения.


      1. ashagraev
        14.09.2017 17:48
        #10416344
        +1

        Почему же? Вопрос о количестве деревьев поиска с нулём вершин вполне валиден. Более того, «пустые объекты» в комбинаторике широко используются в самых разных ситуациях. Ну, например, сочетания из нуля объектов можно встретить в формуле бинома Ньютона :)


  1. wizi4d
    12.09.2017 16:05
    #10412436
    +1

    Сразу вспомнилась статья Эти токсичные, токсичные собеседования
    Цитата из статьи:

    «Ведь нужно проверять фундаментальные знания»
    Вы так в этом уверены? Кому именно нужно? Здесь всё же не кафедра университета и не олимпиадный кружок, предлагаю вспомнить, зачем вы вообще ищете человека. Правильно. Писать API, проектировать инфраструктуру, рисовать кнопки, чинить баги, понимать задачу из общения с бизнесом, делать продукт дороже и круче. И делать всё это в срок и за деньги.


    1. MacIn
      12.09.2017 16:49
      #10412534
      +1

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


      1. wizi4d
        12.09.2017 17:29
        #10412614
        +3

        Я не отрицаю полезность этих знаний. Я всего лишь говорю о том, что их значение очень часто переоценивают.
        Не думаю, что в команде нужно, чтобы все были шикарными алгоритмистами. Знание паттернов, умение писать «чистый» код и прокачанные softskills, как правило, более полезны в реальной работе.


        1. MacIn
          12.09.2017 17:49
          #10412662
          +1

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


    1. TheKnight
      12.09.2017 17:34
      #10412634
      +3

      Занудства ради, из вспомнившейся вам статьи:

      Далее должна следовать обязательная ремарка про людей, пишущих поисковое ядро Google / Yandex.

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


    1. lookid
      12.09.2017 21:45
      #10412990
      -4

      Всё упирается в то, что вопросы "Покажите свои коммиты в хром или в какой-нибудь поисковик" спрашивать не имеет смысла. Человек сам об этом расскажет, если такое было.


      не олимпиадный кружок

      Яндекс больше "олимпиадный кружок", чем какой-нибудь Люксофт или Епам. Мы сейчас не говорим, о том, что Епам богаче Я. Или что Варгейминг богаче Я. Да, богаче. Но разговор не об этом.


  1. Laney1
    13.09.2017 09:11
    #10413422
    +4

    судя по сложности задач и отведенному времени, в финал вполне может пройти несколько тысяч человек. Это что, стрельбы из яндекс.танка по HR-службе?))


    1. Zalina
      13.09.2017 20:04
      #10414968

      Так там будет несколько разных по сложности задач. Эти две — просто пример.


  1. Agaspher20
    13.09.2017 10:41
    #10413520

    Объясните мне пожалуйста, а где в решении 1-й задачи топологическая сортировка.
    Имплементирован простой обход графа в глубину.
    При попадании в вершину никакой проверки на наличие других входящих ребер нет.
    Получается в первом примере задача решена неправильно.

    Буду жутко благодарен за развернутый ответ, особенно если я не прав.


    1. nkmakarov Автор
      13.09.2017 11:15
      #10413594
      +1

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


    1. wataru
      13.09.2017 11:41
      #10413640

      Это свойство DFS. Он всегда сначала выйдет из вершины, от которой ничего не зависит. В противном слечае, ДФС бы зашел в зависимую вершину и вышел из нее раньше, чем из текущей. Поэтому достаточно выводить в ответ вершины по мере выхода из них (будет развернутая топологическая сортировка).