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

Тем временем мы подготовили разбор задач чемпионата, которые предлагались фронтенд-разработчикам. Это задачи из квалификационного этапа. Напоминаем, что чемпионат проводился по четырём направлениям: бэкенд, фронтенд, машинное обучение и аналитика.

A. Градусник пробок


Условие


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

На вход функции дан массив цветов длины length и размер экрана width (length ≥ width), на котором будет изображен градусник. Используемые цвета GREEN, YELLOW и RED отвечают низкой, средней и высокой загруженности соответственно. Цвета сравнимы по степени загруженности дорог: GREEN < YELLOW < RED.

Исходный массив, начиная с первого элемента, разбивается на подряд идущие непересекающиеся подмассивы длины length / width (число всегда будет целым). В каждом подмассиве необходимо упорядочить цвета по возрастанию степени загруженности дорог, выбрать медианный цвет и заменить на него всю совокупность. В случае массива четной длины выбирается «нижняя медиана» (элемент с номером n/2 в упорядоченном ряду из n элементов). В итоге должен получиться массив цветов длины width.

Решение необходимо предоставить в виде CommonJS-модуля:

module.exports = function (segments, width) {
    // Your code here.
};

Вердикт RE также означает, что отправленное решение неверно.

Дополнительные параметры
Ввод Вывод 
const segments = ['GREEN', 'GREEN', 'RED', 'GREEN', 'YELLOW', 'RED', 'GREEN', 'YELLOW', 'RED', 'YELLOW'];
const width = 5;
 ['GREEN', 'GREEN', 'YELLOW', 'GREEN', 'YELLOW']

Решение


1. Ра��биваем исходный массив сегментов на сегменты длинной length / width.
2. В каждом сегменте выбираем медианный цвет, исходя из условия, и добавляем найденный цвет в результирующий массив.

solution.js
module.exports = function solution(segments, width) {
    const blockSize = segments.length / width;

    const result = [];

    for (let i = 0; i < width; i++) {
        result.push(getMedian(segments.slice(i * blockSize, (i + 1) * blockSize)));
    }

    return result;
};

function getMedian(array) {
    const map = {
        GREEN: 1,
        YELLOW: 2,
        RED: 3
    };

    return array.sort((a, b) => map[a] - map[b])[Math.floor((array.length - 1) / 2)];
}

B. Торрент-клиент


Условие


Вы решили написать свой торрент-клиент. Его особенностью будет то, что с его помощью можно передавать только текст.

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

Напишите функцию, которая дождется загрузки всех кусков текста и соберет из них исходную.

Функция принимает на вход объект с двумя полями: chunkCount и emitter, и возвращает промис, содержащий либо исходный текст, либо ошибку в виде строки заданного формата.

chunkCount — количество кусков, на которое был разбит текст.

У каждого куска текста есть уникальный идентификатор и время отправки. Куски с более поздним временем отправки располагаются дальше от начала текста.

emitter — объект, с помощью которого можно получать загруженные куски текста. Куски текста могут приходить с произвольными временными задержками. Порядок кусков может быть любым.

Если один и тот же кусок текста будет получен дважды до того, как загрузка успешно завершилась, функция должна выдать ошибку "Duplicate: <id>" (с id куска текста на месте <id>).

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

Если в течение секунды передача не завершилась, функция должна выдать ошибку "Timed out".

Входные данные соответствуют такому интерфейсу на TypeScript
(Общее описание интерфейсов TS.)

interface Input {
    chunkCount: number;
    emitter: Emitter;
}

interface Emitter {
    on: (callback: (chunk: Chunk) => void) => void;
}

interface Chunk {
    id: number;
    timestamp: Date;
    data: string;
}


Решение необходимо предоставить в виде CommonJS-модуля:

module.exports = function ({chunkCount, emitter}) {
    // возвращает Promise
};

Вердикт RE также означает, что отправленное решение неверно.

Дополнительные параметры
Примеры
Ввод Вывод 
{
    chunkCount: 3,
    emitter: {on: (fn) => {
        fn({id: 5314, data: 'The Good, ', timestamp: new Date('2019-01-01')});
        fn({id: 1543, data: 'd the Ugly', timestamp: new Date('2019-01-03')});
        fn({id: 2494, data: 'the Bad an', timestamp: new Date('2019-01-02')});
    }}
}
Resolved with "The Good, the Bad and the Ugly" 
{
    chunkCount: 1,
    emitter: {on: (fn) => {
        fn({id: 0, data: 'hello', timestamp: new Date('2019-01-01')});
        fn({id: 0, data: 'world', timestamp: new Date('2019-01-02')});
    }}
}
Rejected with "Duplicate id: 0" 
{
    chunkCount: 2,
    emitter: {on: (fn) => {}}
}
Rejected with "Timed out"

Решение


  • Сохраняем загруженные куски в объект chunk.
  • При этом проверяем на существование id. Если он уже существует, то отменяем промис.
  • После загрузки всех кусков сортируем и объединяем их.
  • Параллельно с этим нужно выставить таймаут 1 с.


solution.js
module.exports = function ({chunkCount, emitter: {on}}) {
    return new Promise((resolve, reject) => {
        const chunks = {};
        let chunksDownloaded = 0;
        on(({id, data, timestamp}) => {
            if (typeof chunks[id] !== 'undefined') {
                reject(`Duplicate: ${id}`);
            } else {
                chunks[id] = {data, timestamp};
                chunksDownloaded += 1;

                if (chunksDownloaded === chunkCount) {
                    const result = Object.values(chunks)
                        .sort((a, b) => a.timestamp - b.timestamp)
                        .map(({data}) => data)
                        .join('');
                    resolve(result);
                }
            }
        });
        setTimeout(() => {
            reject('Timed out');
        }, 1000);
    });
};

C. Бинарное дерево


Условие


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

Необходимо найти и исправить ошибки в коде task.js. Должен экспортироваться класс для работы с бинарным деревом. Интерфейс класса:

type Data = number;

type ITraverseCallback = (data: Data) => void;

interface IBinaryTreeNode {
    data: Data;
    left: IBinaryTreeNode | null;
    right: IBinaryTreeNode | null;

    static create(...items: Data[]): IBinaryTreeNode;

    constructor(data: Data);

    insert(data: Data): this;
    remove(data: Data): IBinaryTreeNode | null;
    search(data: Data): IBinaryTreeNode | null;

    inorder(callback: ITraverseCallback): this;
    preorder(callback: ITraverseCallback): this;
    postorder(callback: ITraverseCallback): this;
}

Замечание: Считать JSDoc правильным.

Вердикт RE также означает, что отправленное решение неверно.

Дополнительные параметры
Пример ввода:
let output = '';

BinaryTreeNode.create(10, 5, 13, 7, 20, 12).inorder((data) => {
    output += data + '-';
});

Вывод:
5-7-10-12-13-20-

Решение


/**
 * @typedef Data
 * @type {Number}
 */

class BinaryTreeNode {
    /**
     * @param  {...Data} items
     * @returns {BinaryTreeNode}
     */
    static create(...items) {
        // e - английская.
        const root = new BinaryTreeNode(items[0]);
        // После return нельзя переносить строки.
        // Нужен .slice(1), иначе добавится дублирующий первый элемент.
        return items.slice(1).reduce((node, data) => node.insert(data), root);
    }

    /**
     * @param {Data} data
     */
    constructor(data) {
        /**
         * @type {Data}
         */
        this.data = data;
        // Не забываем инициализировать ветки.
        /**
         * @type {BinaryTreeNode | null}
         */
        this.left = null;
        /**
         * @type {BinaryTreeNode | null}
         */
        this.right = null;
    }

    /**
     * Вставляет данные в ноду.
     * Проходит по всем детям, чтобы найти верное место для вставки.
     *
     * @param {Date} data
     * @returns {BinaryTreeNode}
     */
    insert(data) {
        // Неверное условие бинарного дерева.
        if (data < this.data) {
            if (this.left === null) {
                this.left = new BinaryTreeNode(data);
            } else {
                this.left.insert(data);
            }
        } else {
            if (this.right === null) {
                this.right = new BinaryTreeNode(data);
            } else {
                this.right.insert(data);
            }
        }

        // Метод должен соответствовать спецификации, нужно вернуть экземпляр.
        return this;
    }

    /**
     * Удаляет ноду по переданным данным.
     * Обходит всех детей, чтобы найти ноду.
     *
     * @param {Data} data
     * @returns {BinaryTreeNode | null}
     */
    remove(data) {
        // Для всех условий нужны {}.
        // Неверное условие бинарного дерева.
        if (data < this.data) {
            // Пропущена проверка на существование `this.left`.
            this.left = this.left && this.left.remove(data);
        } else if (data > this.data) {
            // Пропущена проверка на существование `this.right`.
            this.right = this.right && this.right.remove(data);
        } else {
            if (this.left === null && this.right === null) {
                return null;
            }

            if (this.left === null) {
                return this.right;
            } else if (this.right === null) {
                return this.left;
            }

            const aux = findMinNode(this.right);
            this.data = aux.data;

            this.right = this.right.remove(aux.data);
        }

        // Метод должен соответствовать спецификации, нужно вернуть экземпляр.
        return this;
    }

    /**
     * Ищет ноду по переданным данным.
     *
     * @param {Data} data
     * @returns {BinaryTreeNode | null}
     */
    search(data) {
        // Неверное условие бинарного дерева.
        if (data < this.data) {
            // Пропущена проверка на существование `this.left`.
            return this.left && this.left.search(data);
        }
        if (data > this.data) {
            // Пропущена проверка на существование `this.right`.
            return this.right && this.right.search(data);
        }
        // Не забываем, что если нода не нашлась, то надо вернуть `null`.
        if (data === this.data) {
            return this;
        }
        return null;
    }

    /**
     * Обход дерева по порядку, начиная рекурсивно с левой ветви через вершину и к правой ветви.
     * Данные получаются в отсортированном порядке.
     *
     * @param {Function} callback
     * @returns {BinaryTreeNode}
     */
    inorder(callback) {
        if (this.left !== null) {
            this.left.inorder(callback);
        }

        callback(this.data);

        if (this.right !== null) {
            this.right.inorder(callback);
        }

        // Метод должен соответствовать спецификации, нужно вернуть экземпляр.
        return this;
    }

    /**
     * Прямой обход дерева, начиная с вершины и двигаясь рекурсивно от левой ветви к правой.
     *
     * @param {Function} callback
     * @returns {BinaryTreeNode}
     */
    preorder(callback) {
        callback(this.data);

        if (this.left !== null) {
            // Рекурсия должна быть на тот же метод.
            this.left.preorder(callback);
        }

        if (this.right !== null) {
            this.right.preorder(callback);
        }

        // Метод должен соответствовать спецификации, нужно вернуть экземпляр.
        return this;
    }

    /**
     * Обратный обход дерева, начиная с левой ветви и двигаясь рекурсивно через правую ветвь к вершине.
     *
     * @param {Function} callback
     * @returns {BinaryTreeNode}
     */
    postorder(callback) {
        if (this.left !== null) {
            this.left.postorder(callback);
        }

        if (this.right !== null) {
            // Рекурсия должна быть на тот же метод.
            this.right.postorder(callback);
        }

        // Неверная реализация метода, сама нода должна посещаться последней.
        callback(this.data);

        return this;
    }
}

/**
 * Находит минимальную ноду, начиная с переданной.
 *
 * @param {BinaryTreeNode} node
 * @returns {BinaryTreeNode}
 */
function findMinNode(node) {
    // В условии тернарника не должно быть присваиваний.
    // Перепутаны ветки тернарника true и false.
    if (node.left === null) {
        return node;
    } else {
        return findMinNode(node.left);
    }
}

module.exports = BinaryTreeNode;

D. Логотип Яндекс.Карт


Условие


Дизайнер обновил логотип Яндекс.Карт (масштаб x5):



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

Использовать картинки (даже через data:uri) нельзя.

Дополнительные параметры

— Цвета центрального круга: #fff
— Цвет внешнего круга: #f33
— Цвет «ножки»: #e00000

Решение нужно предоставить в виде CSS-файла. Ваш файл будет подключен как solution.css к HTML-странице вида:

<!DOCTYPE html>
<html>
    <head>
        <style>
            body {
                margin: 0;
            }
        </style>
        <link rel="stylesheet" href="solution.css">
    </head>
    <body>
        <div></div>
    </body>
</html>

Важно: логотип должен находиться в верхнем левом углу страницы, вплотную прижатый к нему.

Ваше решение будет тестироваться в браузере Google Chrome 69.

Рекомендуем использовать плагины для pixel-perfect-верстки, например PerfectPixel.

Решение


// Сам блок используем для отрисовки белого круга с красной границей.
div {
    position: absolute;
    width: 6px;
    height: 6px;
    border: 5px solid #f33;
    border-radius: 8px;
    background: #fff;
}

// Псевдоэлемент используем для отрисовки «ножки» пина.
// Для этого рисуем треугольник, и поворачиваем его на заданные 9 градусов.
div::after {
    content: '';
    position: absolute;
    top: 6px;
    left: 2px;
    border-top: 15px solid #e00000;
    border-right: 7px solid transparent;
    transform: rotate(9deg);
    z-index: -1;
}


E. Кирпичная сетка


Условие


Разработчик Иван решил отрефакторить CSS-стили страницы, после чего поломал ее внешний вид.

Первоначальный дизайн:

Необходимо привести внешний вид в соответствие с первоначальным дизайном с наименьшим количеством изменений в текущем CSS-файле.

Важно: При добавлении элементов в список, сетка должна аналогично разрастаться вниз.

CSS-стили после рефакторинга: ./solution.css.

После исправлений нужно предоставить обновленный CSS-файл. Данный файл будет подключен как исправленный solution.css к HTML-странице.

Дополнительные параметры
Ваше решение будет тестироваться в браузере Google Chrome 69. Семейство и другие параметры шрифтов изменять не надо. При этом локально у вас может не совпадать шрифт с ожидаемым состоянием, т. к. скриншоты сделаны в Ubuntu.

Рекомендуем использовать плагины для pixel-perfect-верстки, например PerfectPixel.

Решение


Изменения нужно производить только с селектором .event и его наследниками.

:root {
    --color-gray: #4e4d4d;
    --color-main: #000000;

    --width-layout: 900px;

    --paddingx5: 50px;
    --paddingx4: 40px;
    --paddingx3: 30px;
    --paddingx2: 20px;
    --padding: 10px;

    --font-size-largex2: 40px;
    --font-size-large: 20px;
    --font-size-medium: 16px;
    --font-size-small: 14px;
}

body {
    margin: 0 auto;
    padding: var(--paddingx5) var(--paddingx4);
    font: var(--font-size-small)/1.4 arialregular;
    color: var(--color-main);
    width: var(--width-layout);
}

.hgroup {
    margin-bottom: var(--paddingx4);
    text-align: center;
}
    .hgroup__title {
        font-size: var(--font-size-largex2);
        font-weight: normal;
        margin: 0;
    }

    .hgroup__desc {
        font-size: var(--font-size-large);
        font-weight: normal;
        color: var(--color-gray);
        margin: 0;
    }

.events {
    list-style: none;
    margin: 0;
    padding: 0;
    
    // Убираем стили для грида.
    // Для решения нужно было использовать колонки.
    columns: 3;
    column-gap: var(--paddingx4);
}
    .events__item {
        // Чтобы не было разрывов.
        break-inside: avoid;
        // Чтобы margin не залезал на другую колонку.
        padding-bottom: var(--paddingx4);
    }

.card {
    text-decoration: none;
    color: var(--color-main);
    display: block;
}
    .card:hover .card__title {
        text-decoration: underline;
    }

    .card__image {
        width: 100%;
        display: block;
        height: 100px;
        background: var(--color-gray);
        margin-bottom: var(--padding);
    }

    .card__title {
        margin: 0 0 var(--padding);
    }

    .card__summary {
        margin: 0;
        color: var(--color-gray);
    }

F. Поездки на метро


Условие


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

Вам необходимо написать функцию getCheapestTickets(days, tickets), принимающую на вход график дежурств Пети (days) и возможные варианты билетов-абонементов (tickets), а на выходе дающую список билетов (в виде индексов из входного массива вариантов билетов), которые нужно купить Пете.

График дежурств Пети задан в виде отсортированного массива чисел (от 1 до 100 включительно), каждое из которых обозначает порядковый номер дня дежурства:

[2, 5, 10, 45] // Петя должен дежурить на второй, пятый, десятый и сорок пятый день относительно текущей даты.

Каждый билет-абонемент описывается следующим интерфейсом:

interface Ticket {
    duration: number; // количество дней, в течение которых билет действует со дня первой поездки по нему, включая этот день (от 1 до 100 включительно)
    cost: number; // стоимость билета (от 1 до 100 включительно)
}

Количество вариантов билетов не более 10, и гарантируется, что все билеты имеют разную стоимость, причем чем большее число дней действует билет, тем ниже его стоимость в пересчете на один день.

Решение необходимо предоставить в виде CommonJS-модуля:

module.exports = function (days, tickets) {
    // Your code here.
};

Вердикт RE также означает, что отправленное решение неверно.

Дополнительные параметры
Примеры

Ввод Вывод 
const days = [1, 2, 4, 6, 7, 8, 9, 10, 20];
const tickets = [
    { cost: 3, duration: 1 },
    { cost: 10, duration: 7 },
    { cost: 20, duration: 30 }
];
[0, 0, 1]

В первый и второй дни Пете нужно купить однодневные билеты, в четвертый день семидневный, на двадцатый день еще раз однодневный.

Суммарная стоимость таких билетов будет минимально возможной: 19.

Решение


Одно из возможных решений — методом динамического программирования, а именно:

1. Берем первый день дежурства Пети.
2. Чтобы найти лучшее решение для этого дня, рассчитаем возможные варианты по каждому из билетов. Каждый такой вариант складывается из стоимости билета и стоимости лучшего решения в день дежурства, следующего за днем окончания действия этого билета. Второе слагаемое рассчитыва��м аналогично, таким образом получая рекурсию.
3. Дополнительно учитываем количество билетов, если таких вариантов оказывается несколько.
4. Особое внимание следует уделить кэшированию решений в промежуточных днях.

solution.js
module.exports = function (days, tickets) {
    if (days.length === 0 || tickets.length === 0) {
        return [];
    }

    tickets = tickets
        .map((ticket, idx) => ({
            ...ticket,
            idx
        }))
        .sort((a, b) => a.duration - b.duration);

    const daysSolutions = new Map();

    function getDaySolution(idx) {
        if (daysSolutions.has(idx)) {
            return daysSolutions.get(idx);
        }

        const solution = {
            totalCost: Number.POSITIVE_INFINITY,
            totalTickets: Number.POSITIVE_INFINITY,
            ticketToBuy: null,
            next: null
        };

        for (let i = 0, j = idx; i < tickets.length && j < days.length; i++) {
            while (j < days.length && days[j] < days[idx] + tickets[i].duration) {
                j++;
            }

            const nextDaySolution = j < days.length ? getDaySolution(j) : null;
            let totalCost = tickets[i].cost;
            let totalTickets = 1;

            if (nextDaySolution) {
                totalCost += nextDaySolution.totalCost;
                totalTickets += nextDaySolution.totalTickets;
            }

            if (
                totalCost < solution.totalCost ||
                (totalCost === solution.totalCost && totalTickets < solution.totalTickets)
            ) {
                solution.totalCost = totalCost;
                solution.totalTickets = totalTickets;
                solution.ticketToBuy = tickets[i].idx;
                solution.next = nextDaySolution;
            }
        }

        daysSolutions.set(idx, solution);

        return solution;
    }

    let solution = getDaySolution(0);
    const res = [];

    while (solution) {
        res.push(solution.ticketToBuy);
        solution = solution.next;
    }

    return res;
};


Вот ссылка на разбор задач для бэкенд-разработчиков.