Чемпионат по программированию: разбираем задачи для фронтенд-разработчиков

На днях победители чемпионата по программированию, который завершился в начале лета, получили заслуженные призы. Для этого мы позвали их, а также всех остальных финалистов из топ-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;

Решение

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

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".

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')});
    }}
}

{
    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')});
    }}
}

{
    chunkCount: 2,
    emitter: {on: (fn) => {}}
}

Решение

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

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-странице.

Решение

Изменения нужно производить только с селектором .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 }
]; 

Решение

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

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

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;
};

Автор: Leono

Источник