Медианы, подмассивы и времена года: ещё порция задач для QA-инженеров

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



Медианы


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

Пусть медиана массива $a_{0}, a_{1},...a_{n−1}$ определяется, как $⌊n / 2⌋$-й элемент в отсортированном порядке. Например:

  • Медиана массива [1, 3, 2] равна 2.
  • Медиана массива [5, 3, 2, 8] равна 5.
  • Медиана массива [7] равна 7.

Вам дан массив из n элементов $a_{0}, a_{1}, . . . a_{n−1}$. Необходимо для каждого $i$ найти медиану среди массива $a_{0}, a_{1}, . . . a_{i−1}, a_{i+1}, . . . a_{n−1}$ (исходный массив без элемента $a_{i}$).

Формат входных данных


В первой строке входных данных содержится одно целое число $n$ — размер массива ($2 ≤ n ≤ 105$). Во второй строке содержатся $n$ целых чисел $a_{0}, a_{1}, . . . a_{n−1}$, разделённые пробелом — элементы массива ($1 ≤ a_i ≤ 109$).

Формат выходных данных


Выведите $n$ чисел $m_{0}, m_{1}, . . . m_{n−1}$ — каждое в отдельной строке — искомые медианы для каждого $i$.

Решение
Для того, чтобы решить эту задачу, нужно заметить занятное свойство. Давайте отсортируем массив, а затем посмотрим, какой элемент будет медианой, если удалить конкретный элемент.

Мы знаем, что длина массива $n$, тогда, по определению из условия, медианой будет $\lfloor \frac{n}{2} \rfloor$-й элемент. Для простоты рассмотрим два случая чётности $n$ отдельно.

Пусть $n$ — чётное. Так как элементы нумеруются с нуля, то изначально медианой будет элемент с индексом $\frac{n}{2}$. Более того, если удалить нулевой, первый или любой другой элемент с индексом меньше $ \frac{n}{2}$, то произойдёт сдвиг влево и $\frac{n}{2}$-й элемент исходного массива станет $\frac{n}{2} — 1$-м элементом, и таким образом останется медианой ($\lfloor \frac{n-1}{2} \rfloor = \frac{n}{2} - 1$). А что будет, если удалить элемент с индексом больше либо равным чем $\frac{n}{2}$? Количество элементов тоже сократится на единицу, но теперь на $\frac{n}{2} - 1$-й позиции останется тот же элемент, что стоял там в оригинальном массиве. Таким образом, чтобы решить исходную задачу нужно найти два числа $x = a[\frac{n}{2} - 1]$ и $y = a[\frac{n}{2}]$ в отсортированном массиве $a$, а затем пройтись по оригинальному массиву, и если текущий элемент массива $a[i] < y$, то ответ будет $y$, иначе — $x$.

Случай нечётного $n$ чуть сложнее с точки зрения идеи, потому что после удаления одного элемента массив станет чётной длины и в нём не так легко искать медиану. Однако, с точки зрения кода решения всё абсолютно аналогично, однако теперь вместо $x : a[\frac{n}{2}]$, а вместо $y : a[\frac{n}{2} + 1]$. Изменение индексов происходит из-за округления в формуле $\lfloor \frac{n}{2} \rfloor$ при вычислении медианы.

Построение строки


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

Изначально у вас есть пустая строка, далее к ней применяется $n$ модификаций. Есть два вида модификаций:

  • Дописать в конец строки символ $c$.
  • Развернуть строку.

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

Формат входных данных


В первой строке входных данных содержится одно целое число $n$ — количество модификаций ($1 ≤ n ≤ 105$). В следующих $n$ строках содержатся описания модификаций.

  • «+c», если в конец строки нужно дописать «c» — строчный символ латинского алфавита.
  • «!», если строку нужно развернуть.

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

Формат выходных данных


Выведите итоговую строку.

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

Вот бы у нас была структура данных, которая позволяет добавлять элементы и в начало, и в конец… Такая структура данных есть, называется дек, и у неё есть стандартные реализации во многих языках программирования! Тогда решение может быть таким:

  • Поддерживаем дек символов добавленных в строку и переменную $is\_inversed$, которая показывает, развёрнута ли строка.
  • Если приходит запрос разворота, инвертируем значение $is\_inversed$.
  • Если приходит запрос добавления символа в конец, то, если $is\_inversed$ — истина, добавляем символ в начало дека, иначе — в конец.
  • Последнее, что нужно не забыть сделать, это вывести дек в естественном порядке, если $is\_inversed$ — ложь, иначе вывести элементы дека с конца.


Подмассивы


На складе хранятся шурупы в заводских упаковках по $X$ штук. Задача упаковщика Ивана — распределить шурупы по заказам покупателей в соответствии с заказанным количеством, не нарушая при этом хронологический порядок заказов. То есть пока полностью не укомплектован $i$-тый заказ, Иван не приступает к комплектации $i+1$-го заказа.

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

Дан массив из $n$ элементов $a_{0}, a_{1}, . . . a_{n−1}$ и число $X$. Вам требуется найти число подмассивов $[a_{l},a_{l+1},...a_{r}]$, для которых сумма $a_{l} +a_{l+1} +···+a_{l}$ делится на $X$ без остатка.

Формат входных данных


В первой строке входных данных содержится два целых числа $n$ и $X$($1 ≤ n ≤ 105$, $1 ≤ X ≤ 109$). Во второй строке содержится $n$ целых чисел $a_{0}, a_{1}, . . . a_{n−1}$, разделённых пробелом — элементы массива ($1 ≤ a_{i} ≤ 109$).

Формат выходных данных


Выведите одно число — количество подмассивов, сумма элементов которых кратна числу $X$.

Пример 1


Входные данные Выходные данные
3 2
1 1 1		 2

Пример 2


Входные данные Выходные данные
4 3
1 2 2 1		 3

Примечание:

В первом примере подходят подмассивы $[a_{0}, a_{1}]$ и $[a_{1}, a_{2}]$. Во втором примере подходят подмассивы $[a_{0}, a_{1}]$, $[a_{2}, a_{3}]$ и $[a_{0}, a_{1}, a_{2}, a_{3}]$.

Решение
Для решения задачи воспользуемся методом префиксных сумм. Посчитаем массив $sum[i] = \sum_{0}^{i} a[i]$. Самое распространённое применение метода префиксных сумм — вычисление суммы на отрезке за $O(1)$. Однако, если в данной задаче мы будем считать суммы всех подотрезков, то нам не нужна такая оптимизация, так как решение будет работать за квадратичную асимптотику и не пройдёт ограничения по времени.

Давайте внимательнее посмотрим на сумму на отрезке от $l$ до $r$ включительно: $sum(l, r) = sum[r] — sum[l-1]$. Как мы знаем из свойств деления с остатком, $sum(l, r)$ будет делиться на $X$ без остатка тогда и только тогда, когда $sum[r]$ и $sum[l - 1]$ имеют одинаковый остаток при делении на $X$ (не обязательно $0$).

Давайте для каждого $r$ найдём количество подходящих $l$. То есть нам нужно найти количество таких индексов $l$, чтобы $l \le r$ и $sum[r]$ и $sum[l — 1]$ имели одинаковый остаток при делении на $X$. Один из самых простых способов сделать это — воспользоваться ассоциативным массивом (map или dict, например) и, рассматривая индексы $r$ слева направо, подсчитывать для каждого встреченного остатка префиксной суммы при делении на $X$ сколько раз мы его встретили ранее. Тогда мы сможем за $O(1)$ или за $O(\log n)$ для каждого $r$ посчитать количество подходящих $l$.

Псевдокод описанного прохода:

ans = 0;
mark[0] = 1;
for i from 0 to n - 1
    ans += mark[sum[i] % X];
    mark[sum[i] % X]++;

$ans$ — суммарное количество искомых подотрезков, а $mark$ — ассоциативный массив остатков префиксных сумм.

Времена года


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

products

CREATE TABLE 'products' (
'id' int(11) NOT NULL,
'product' varchar(50) NOT NULL
);

INSERT INTO 'products' ('id', 'product') VALUES
(1, 'Книга'),
(2, 'Торт'),
(3, 'Шампанское');

orders

CREATE TABLE 'orders' (
'id' int(11) NOT NULL,
'product' int(11) NOT NULL,
'customer' int(11) NOT NULL
);

INSERT INTO 'orders' ('id', 'product', 'customer') VALUES
(1, 1, 1),
(1, 2, 1),
(2, 3, 2),
(2, 2, 2),
(3, 1, 3),
(3, 2, 3),
(3, 3, 3),
(4, 1, 1),
(4, 1, 1);

customers

CREATE TABLE 'customers' (
'id' int(11) NOT NULL,
'name' varchar(50) NOT NULL,
'birthday' date
);

INSERT INTO 'customers' ('id', 'name', 'birthday') VALUES
(1, 'Сергей', '1990-07-01'),
(2, 'Андрей', '1997-12-10'),
(3, 'Павел', '2001-01-07');

Напишите запрос, который покажет, количество купленных товаров (в штуках) по временам года. Время года вывести в виде целого числа: 1 — зима, 2 — весна, 3 — лето, 4 — осень. Предполагается, что каждая строка заказа отражает факт покупки одной штуки указанного товара.

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

Формат выходных данных


Запрос должен возвращать два столбца:

  • season — целое число от 1 до 4: время года;
  • volume — целое число больше 0: количество товаров в штуках, купленных покупателями, родившимися в указанное время года.

Решение
Найти таблицу конкретных покупок, избавившись от анонсированных в условии битых ссылок можно довольно легко, ведь благодаря таблице orders у нас есть связь между id из таблицы products и id из таблицы customers. Если бы нам было достаточно сгруппировать покупки по датам рождения, мы могли бы сделать такой запрос:

SELECT
    birthday,
    COUNT(*) AS volume
FROM
    customers
INNER JOIN
    orders
ON customers.id = orders.customer
INNER JOIN
    products
ON products.id = orders.product
GROUP BY birthday;

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

  • Выделение месяца, приведение его к числу, а дальше формула: $season = (month % 12 + 1) / 3 + 1$, где $%$ — операция остатка при делении, а $/$ — целочисленное деление.
  • Можно было выделить месяц, а затем при помощи условных операторов разобрать принадлежность числа к одному из четырёх диапазонов.
  • Можно было действовать ещё «грубее», воспользовавшись командой LIKE. Например, проверить, что текущая дата рождения относится к зиме можно так: birthday LIKE '%-12-%' OR birthday LIKE '%-01-%' OR birthday LIKE '%-02-%'.

Итоговый запрос может быть, например, таким:

SELECT
    CASE WHEN birthday LIKE '%-12-%' OR birthday LIKE '%-01-%' OR birthday LIKE '%-02-%' THEN
        1 else
        CASE WHEN birthday LIKE '%-03-%' OR birthday LIKE '%-04-%' OR birthday LIKE '%-05-%' THEN
            2 else
            CASE WHEN birthday LIKE '%-06-%' OR birthday LIKE '%-07-%' OR birthday LIKE '%-08-%' THEN
                3 else
                4
            end
        end
    end AS season,
    COUNT(*) AS volume
FROM
    customers
INNER JOIN
    orders
ON customers.id = orders.customer
INNER JOIN
    products
ON products.id = orders.product
GROUP BY season;


На этом наш разбор задач из дополнительного раунда для поступления на курс «Автоматическое тестирование веб-сервисов на Go» закончен. Напишите, что вам было решить сложнее всего?
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Какую задачу вы считаете самой интересной?
0% Медианы 0
0% Построение строки 0
0% Подмассивы 0
0% Времена года 0
0% Посмотреть варианты 0
Никто еще не голосовал. Воздержавшихся нет.
Источник: https://habr.com/ru/company/ozontech/blog/663052/

Вернуться к списку

Интересные статьи

Интересные статьи

Задача выбора (назначения). Венгерский метод решения
Задача выбора (назначения). Венгерский метод решения
Среди задач линейного программирования выделяют задачи, обладающие определенной спецификой, мотивирующей поиск и разработку специфических методов их решения. Эти методы существенно проще общего симпле...
АТАТА: распутываем задачу про палиндром
АТАТА: распутываем задачу про палиндром
Очень часто авторы алгоритмических задач делают ход конём: они берут задачу с простыми формулировками, заменяют их сложными и непонятными эквивалентами и выдают вам «сложную» задачу. В эт...
Тестируем ruGPT-3 на новых задачах
Тестируем ruGPT-3 на новых задачах
Рекомендательные системы с нуля, чат-боты и многое другое Погрузившись в пучину текстовых данных, в октябре этого года мы обучили модели ruGPT-3 — модели для русского языка на основе арх...
Хочешь, чтобы тебе поставили корректную дизайн-задачу? Помоги продакту ее поставить
Однажды в деревне мой дядя Слава спросил, чем я занимаюсь. Большой, мол, уже, 25 лет. Должен же чем-то заниматься. Я ответил, что работаю в Москве дизайнером мобильных приложений. Он ...
Jira REST API. Интеграция Jira с Битрикс КП
Jira REST API. Интеграция Jira с Битрикс КП
Как-то у нас исторически сложилось, что Менеджеры сидят в Битрикс КП, а Разработчики в Jira. Менеджеры привыкли ставить и решать задачи через КП, Разработчики — через Джиру.