- PVSM.RU - https://www.pvsm.ru -
Редко когда кандидат проходит только одно техническое собеседование — обычно их несколько. Среди причин, почему человеку они могут даваться непросто, можно назвать и ту, что каждый раз приходится общаться с новыми людьми, думать о том, как они восприняли твой ответ, пытаться интерпретировать их реакцию. Мы решили попробовать использовать формат контеста, чтобы сократить количество итераций для всех участников процесса.
Для Блица [2] мы выбрали исключительно алгоритмические задачи. Хотя для оценки раундов и применяется система ACM, в отличие от спортивного программирования все задания максимально приближены к тем, которые постоянно решают в продакшене Поиска. Те, кто решит успешно хотя бы четыре задачи из шести, могут считать, что прошли первый этап отбора в Яндекс. Почему алгоритмы? В процессе работы часто меняются задачи, проекты, языки программирования, платформы — те, кто владеет алгоритмами, всегда смогут перестроиться и быстро научиться новому. Типичная задача на собеседовании — составить алгоритм, доказать его корректность, предложить пути оптимизации.
Квалификацию можно пройти с 18 по 24 сентября включительно. В этом раунде вам нужно будет написать программы для решения шести задач. Можете использовать Java, C++, C# или Python. На всё про всё у вас будет четыре часа. В решающем раунде будут соревноваться те, кто справится как минимум с четырьмя квалификационными задачами. Финал пройдёт одновременно для всех участников — 30 сентября, с 12:00 до 16:00 по московскому времени. Итоги будут подведены 4 октября. Чтобы всем желающим было понятно, с чем они столкнутся на Блице, мы решили разобрать пару похожих задач на Хабре.
Первая задача связана с одной из систем обработки данных, разработанной в Яндексе, — Robust Execution Manager, REM. Он позволяет строить сложные процессы, включающие множество разных операций, и устанавливать зависимости между ними. Так, решение многих задач связано с обработкой пользовательских логов, содержащих информацию о заданных запросах, показанных документах, совершённых кликах и так далее. Поэтому вычисление поискового фактора CTR (click through rate, отношение числа кликов по документу к количеству его показов) зависит от задач обработки пользовательских логов, а от решения задачи вычисления CTR зависит задача доставки значений этого фактора в поисковый runtime. Таким образом, REM позволяет выстраивать цепочки обработки данных, в которых поставщик данных не обязан знать о том, кто эти данные в дальнейшем будет использовать.
В процесс исполнения цепочек обработки могут быть внесены коррективы. Например, уже после построения поисковых логов может выясниться, что значительный объем данных был доставлен с существенной задержкой, и поисковые логи необходимо перестроить. Естественно, после перестроения логов необходимо также перезапустить все процессы, которые от них зависели. Другой пример того же рода — попадание в пользовательские логи запросов, выполненных нашим поисковым роботом. Эти запросы не являются запросами пользователей, а поэтому вносят шум в вычисление поисковых факторов, расчёты экспериментов и так далее. Поэтому в этом случае логи также нужно обновить, после чего перезапустить все процессы их обработки. Поэтому REM поддерживает операцию обновления данных с последующим перезапуском всех задач, зависящих от этих данных.
Задача заключается в реализации именно этой операции. Входными данными будет ациклический ориентированный граф с выделенной вершиной. Граф описывает некоторый процесс обработки данных, при этом вершины представляют этапы этого процесса, а рёбра — зависимости между ними. Выделенная вершина соответствует одной из подзадач, которую необходимо перезапустить из-за изменений в данных. После перезапуска необходимо будет также перезапустить и все подзадачи, зависящие от неё по данным. Необходимо написать программу, которая выводит список этих подзадач, причём в порядке, в котором их необходимо будет перезапустить.
Рассмотрим для начала решение задачи в случае, когда вершины из ответа не нужно упорядочивать. Тогда задача решается достаточно просто: запустим из выделенной вершины любой алгоритм обхода графа (например, обход в глубину), и запишем в ответ все посещённые вершины. Действительно, если задачи с номерами , , ..., зависят по данным от задачи , то после перезапуска задачи необходимо перезапустить все эти задачи, а также те задачи, что зависят уже от них. Кроме того, каждую вершину нужно вывести ровно один раз. Оба этих условия обеспечиваются стандартными методами обхода графов.
#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;
}
Теперь мы знаем, как сформировать множество вершин, составляющих ответ, но не знаем, как его упорядочить. Рассмотрим пример: пусть от подзадачи зависят подзадачи и . В таком случае нам неважно, в каком порядке запускать подзадачи и . Но что, если между ними существует явная или неявная (через другие подзадачи) зависимость?
В ситуации, изображённой на картинке, сначала нужно исполнять задачу , а уже потом . Но стандартные методы обхода не позволяют этого добиться. Нам нужен другой алгоритм!
Используем для решения возникшей проблемы топологическую сортировку вершин [3], входящих в ответ, то есть, введём некоторый порядок на этом множестве вершин, например: , ,...,, и при этом будет верно, что, если , то не зависит прямо или косвенно от . Известно, что такое упорядочение возможно, если граф не содержит циклов. Топологическая сортировка вершин достигается при помощи обхода в глубину: когда для некоторой вершины посещены все её потомки, она добавляется в начало списка. Итоговый список будет искомой сортировкой вершин графа.
Таким образом, поставленная задача решается при помощи обхода в глубину, в процессе которого мы одновременно строим множество вершин, представляющих ответ, и осуществляем топологическую сортировку этих вершин. Топологическая сортировка гарантирует, что соответствующие вершинам графа подзадачи перечислены в правильном порядке.
#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;
}
Эта задача не имеет непосредственного отношения к библиотекам и программам, разрабатываемым в Яндексе, зато она очень интересная и поэтому часто становится темой для обсуждений на кофепоинтах в свободную минуту. Она является несколько упрощённой версией задачи 9D с codeforces [4].
Необходимо вычислить, каково количество различных бинарных деревьев поиска, в вершинах которых записаны числа от 1 до . Например, если , существует ровно пять различных деревьев, изображённых на картинке ниже:
Если , то количество деревьев равняется 42. Именно поэтому задача очень нравится нашим разработчикам, среди которых немало ценителей творчества Дугласа Адамса.
Эта задача является достаточно простой для тех, кто знаком с методами динамического программирования. Обозначим за количество различных бинарных деревьев поиска, образованных числами , , ..., . Предположим, что мы знаем , , , ..., и хотим вычислить .
Ясно, что в корне любого дерева будет находиться некоторое число из множества Обозначим это число за . Тогда в силу свойств дерева поиска левое поддерево содержит числа , а правое — . Количество различных возможных способов сформировать левое поддерево тогда равняется , а правое — . Поэтому общее количество деревьев, составленных из чисел , , ..., и имеющих в корне значение , равняется произведению . Для того, чтобы найти общее количество деревьев, необходимо просуммировать это произведение для всех возможных значений :
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]
Задачу можно решить с использованием полученной формулы. Однако те, кому хорошо знакома комбинаторика, могли бы узнать в этом выражении формулу для вычисления чисел Каталана [5]. Поэтому можно для получения ответа использовать формулу с использованием биномиальных коэффициентов:
В процессе решения задачи про бинарные деревья мы получили рекуррентную формулу, полностью аналогичную рекуррентной формуле, возникающей при решении задачи про количество правильных скобочных последовательностей длины , которая, как правило, и используется для введения чисел Каталана в курсах по комбинаторике.
Яндекс.Блиц будет проходить на платформе Контест, где мы обычно проводим Алгоритм. Для участия нужно зарегистрироваться [2]. Мы обязательно пришлём вам напоминание о старте раундов.
Автор: Никита Макаров
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/java/263696
Ссылки в тексте:
[1] Image: https://habrahabr.ru/company/yandex/blog/337690/
[2] Блица: https://yandex.ru/promo/jobs/blitz/newhire#registration
[3] топологическую сортировку вершин: https://ru.wikipedia.org/wiki/%D0%A2%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
[4] задачи 9D с codeforces: http://codeforces.com/problemset/problem/9/D
[5] чисел Каталана: https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0
[6] Источник: https://habrahabr.ru/post/337690/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.