Как стать автором
Поиск
Написать публикацию
Обновить
248
Рейтинг
Ozon Tech
Команда разработки ведущего e‑com в России

Города, инверсии и логистика: разбор задач для QA-инженеров

Время на прочтение9 мин
Количество просмотров5.5K
Блог компании Ozon TechБлог компании VKIT-инфраструктура*Занимательные задачкиУчебный процесс в IT
Друзья, недавно мы опубликовали разбор задач из отборочного контеста на курс «Автоматическое тестирование веб-сервисов на Go». А теперь предлагаем поломать голову над задачами для QA-инженеров: сначала попробуйте найти решение самостоятельно, а потом сравните с нашими вариантами.



Хэш


Разработчику складских решений Андрею необходимо создать копию базы данных о заказах и деперсонализировать данные в ней. На вход приходит текстовая строка, содержащая разделённые пробелом номер заказа, имя, фамилию и стоимость заказа:

order_id first_name second_name price

Необходимо написать скрипт на Bash (запуск под Ubuntu 20.04), который выведет те же данные, но с хешированными именем и фамилией. Хешировать необходимо утилитой sha1sum.

Решение
Утилита sha1sum возвращает два значения: хэш и название файла. Её можно применить к строке, например, командой echo $string | sha1sum, однако в таком случае помимо искомой хэш-суммы мы получим ещё записанный через пробел символ «-». Как можно от него избавиться? Один из вариантов — воспользоваться утилитой head с опцией -c40, которая оставит первые 40 байт вывода утилиты sha1sum, содержащие искомый хэш, и отбросит остальное.

Финальное решение может выглядеть так:

  1. Прочитаем входные данные: 
    read order_id first_name second_name price

  2. Затем посчитаем хэш и отбросим лишнее:
    hash1=$(echo $first_name | sha1sum | head -c40)
hash2=$(echo $second_name | sha1sum | head -c40)

  3. Выведем требуемые данные:
    echo $order_id $hash1 $hash2 $price



Города


Света любит путешествовать по новым странам. Собираясь в Бразилию, она опросила всех своих знакомых, в каких городах Бразилии они были. Каждый город Света обозначила отдельным символом и составила из всех ответов друзей длинную текстовую строку. Теперь ей хочется увидеть самый часто посещаемый город. Для этого нужно заменить каждый символ строки, кроме самого частого, на символ «*».

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


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

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


Выведите искомую строку с заменёнными символами.

Решение
Эта задача является чисто технической и сводится к тому, что нужно найти самый часто встречающийся символ в строке, а затем заменить вхождения всех остальных символов на символ «*».

Для выполнения первой части решения можно использовать, например, ассоциативный массив (map или dict в зависимости от вашего языка программирования) и посчитать количество вхождений каждого символа, а затем линейным проходом найти максимум. Также можно вспомнить, что все строчные латинские буквы кодируются подряд, а значит можно вычесть из кода символа буквы код буквы «a» и вместо ассоциативного массива использовать обычный длиной 26.

А завершить решение можно обычным линейным проходом по исходной строке и выводом либо самого частого символа, либо «*».

Инверсии


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

Дан массив из $n$ элементов $a_0$, $a_1$,… $a_n-1$. Инверсией в массиве называется любая пара индексов $i$, $j$, в которой $i < j$ и $a_i > a_j$. Назовем величиной инверсии i, j абсолютную разность соответствующих элементов $|a_i - a_j|$. Требуется найти максимальную по величине инверсию в этом массиве.

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


В первой строке входных данных содержится одно целое число $n$ — размер массива ($2 <= n <= 10^5$). Во второй строке содержатся n целых чисел $a_0$, $a_1$,… $a_{n-1}$, разделённых пробелом — элементы массива ($-10^9 <= a_i <= 10^9$).

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


Выведите одно число — максимальную величину инверсии в массиве. Если ни одной инверсии в массиве нет, то выведите 0.

Решение
Чтобы найти максимальную по величине инверсию в массиве, найдём для каждого элемента $a_k$ максимальную по величине инверсию $i, j$, в которой $i < j$ и $j = k$. Если бы ограничения позволяли решать эту задачу за квадратичную асимптотику, то можно было бы просто перебрать все $i < k$, для которых верно $a_i > a_k$ (только такие индексы $i$ могут составлять инверсию с индексом $k$), и среди них выбрать индекс, для которого разность $a_i - a_k$ максимальна.

Давайте оптимизируем решение до линейной асимптотики. Заметим, что при фиксированном $k$ разность $a_i — a_k$ будет максимальна при максимальном $a_i $. То есть мы можем поддерживать максимальное значение в массиве среди элементов $a_0, a_1 \dots a_{k-1}$ и использовать его в качестве кандидата для вычисления ответа для текущего $k$.

Также не забудем рассмотреть случай, когда в массиве отсутствуют инверсии. Это можно сделать, например, взяв максимум из $0$ и полученного ответа.

Общее поле


Для автоматического поиска похожих товаров в ассортименте маркетплейса Ozon применяются различные методики, среди которых — сравнение по значению характеристик товара. Характеристики для различных товарных групп имеют разную структуру данных, и в общем виде могут быть представлены в формате JSON с произвольной вложенностью полей. На степень похожести товаров в этом случае должны влиять не только значения полей, но и их конкретный путь в структуре JSON. Требуется составить алгоритм, позволяющий оценить степень схожести товаров. Одним из элементов этого алгоритма будет поиск общих полей в двух различных фрагментах JSON.

Вам дано два JSON. Требуется найти в них такое общее поле, у которого будет самая длинная строка, характеризующая путь до него. Если таких строк несколько, то необходимо найти лексикографически наименьшую из них.

Пояснение к примерам


В первом примере у JSON-ов два общих поля с путём длиной три: fps и a.z. При этом a.z лексикографически меньше.

Во втором примере в первом JSON есть очень длинный путь a[2].b[0][0], однако во втором JSON путь не такой же, а a[1].b[0][0], поэтому это поле не считается общим.

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


В первой строке задан первый JSON. Во второй строке задан второй JSON. Гарантируется, что длина каждой строки не превышает 3000.

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


Выведите максимальный по длине и лексикографически наименьший путь до общего поля данных JSON-ов.

Решение
Задача делится на две части: парсинг JSON-а и обход полученной структуры.

В первой части можно пойти трудным путём и самостоятельно написать парсинг, а можно воспользоваться стандартными реализациями. Например, в Python есть модуль json, а в JavaScript объект JSON.

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

Вот авторское решение задачи на Python:

import json

def get_paths(json, prefix, ans):
    if type(json) is dict:
        for k, v in json.items():
            get_paths(v, prefix + '.' + k, ans)
    elif type(json) is list:
        for i in range(len(json)):
            get_paths(json[i], prefix + '[' + str(i) + ']', ans)        
    else:
        ans.append(prefix[1:])

first = json.loads(input())
second = json.loads(input())
ans1 = []
ans2 = []
get_paths(first, '', ans1)
get_paths(second, '', ans2)

intersection_set = set.intersection(set(ans1), set(ans2))
intersection_list = list(intersection_set)
intersection_list = sorted(intersection_list, key=lambda x: (-len(x), x))
print(intersection_list[0])


Даты


Напишите скрипт, который будет получать на вход stdin параметры d1 и d2 в формате YYYY-MM-DD, и считать разницу между этими датами в днях. Скрипт проверяется на Bash 5.1.4 (запуск под Ubuntu 20.04).

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


Две даты через пробел в формате YYYY-MM-DD.

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


Одно целое число — разница в днях.

Решение
Чтобы решить задачу, необходимо уметь пользоваться функцией date, которая позволяет получить из строки дату и преобразить её в формат unix time. Давайте так и поступим, затем найдём разность и переведём её в дни:

  1. Считываем даты из входного потока:
    read s1 s2
d1=`date -d "$s1" "+%Y-%m-%d"`
d2=`date -d "$s2" "+%Y-%m-%d"`

  2. Переводим даты в unix time:
    ut1=`date -d "$d1" +%s`
ut2=`date -d "$d2" +%s`

  3. Считаем разность секунд и переводим в дни:
    diff=$(($ut1 - $ut2))
diff_days=$(($diff / (60 * 60 * 24)))

  4. Выводим абсолютное значение разности (можно было бы написать if, но такой «чит» выглядит лаконичнее: он переводит значение в строку и удаляет лидирующий минус, если он есть):
    echo ${diff_days#-}


Бонус:

Уже после написания разбора обнаружилось два забавных факта:

  1. Во всех тестах вторая дата идёт хронологически позже первой.
  2. Формат даты в условии не надо дополнительно парсить, а можно сразу переводить в unix time.

Таким образом, немного упрощённое решение выглядит так:

read d1 d2

ut1=`date -d $d1 +%s`
ut2=`date -d $d2 +%s`

diff=$(($ut2 - $ut1))
diff_days=$(($diff / (60 * 60 * 24)))

echo $diff_days


Регионы


После начала пандемии значительная часть сотрудников центрального офиса Ozon разъехалась по различным регионам страны. Теперь для того, чтобы оптимально использовать рабочее время при проведении онлайн-встреч, нужно учитывать часовой пояс, в котором проживает каждый сотрудник. Для этого HR-специалисту необходимо собрать данные по смешанным командам (в которых часть сотрудников живёт в Москве, а часть — в других регионах). Данные о сотрудниках хранятся в таблицах:

local_employees

id   name      second_name
1    Андрей    Иванов
2    Ольга     Смирнова
3    Иван      Иванов

remote_employees

Id   first_name   second_name    region
1    Сергей       Кузнецов       Казань
2    Илья         Фомин          Ижевск
3    Анна         Сергеевна      Казань
4    Артём        Сидоров        Владимир

Напиши запрос, который сгруппирует всех владельцев ПВЗ Ozon в одну таблицу с указанием региона. Для локальных сотрудников нужно указать регион «Москва». Затем отсортировать всё по региону.

Пример ожидаемого ответа:

Артём   Сидоров  Владимир
Илья    Фомин    Ижевск
Сергей  Кузнецов Казань
Анна    Сергеева Казань
Андрей  Иванов   Москва
Ольга   Смирнова Москва
Иван    Иванов   Москва

Решение
Нужно добавить колонку к local_employees, а затем объединить получившуюся таблицу с таблицей remote_employees. Чтобы получить таблицу local_employees с колонкой региона можно выполнить, например, такой запрос:

SELECT
        name, second_name, "Москва"
FROM
        local_employees

Для объединения можно использовать команду UNION ALL (команда UNION не подойдёт по смыслу). Остаётся только упорядочить итоговую таблицу по региону, что довольно легко сделать. Итоговое решение может выглядеть, например, так:

SELECT
    first_name, second_name, region
FROM
    remote_employees
UNION ALL
    SELECT
            name, second_name, "Москва"
    FROM
            local_employees
ORDER BY region


Логистика


В компании-грузоперевозчике составлен маршрут для грузовика (последовательность посещаемых пунктов погрузки и выгрузки). Но маршрут учитывает только географию местности. Теперь нужно так скорректировать объёмы грузов, которые заказаны в каждой точке, чтобы после каждой операции погрузки или выгрузки объём занятого в кузове места «колебался» вокруг заданного значения (например, вокруг половины от всего объёма кузова). То есть, если в данный момент объём меньше половины, то после посещения следующей точки он должен стать строго больше половины, и наоборот. Обозначим целыми числами величину заказа (в штуках) в каждой точке маршрута. Положительное число означает погрузку в автомобиль, а отрицательное — выгрузку из автомобиля. Предполагается, что в начальной точке грузовик заполнен ровно наполовину. Нужно так скорректировать объёмы заказов на минимально возможные величины, чтобы удовлетворить заданному условию «колебания» занятого объёма. Формально поставленную задачу можно описать следующим образом:

Дан массив из $n$ элементов $a_0$, $a_1$,… $a_n-1$. Также определим функцию префиксной суммы $prefix\_sum(i) = a_0 + a_1 + ... + a_i$.

Вам разрешено делать с массивом следующие операции:

  • Увеличить любой элемент массива на единицу.
  • Уменьшить любой элемент массива на единицу.

С помощью минимального количества таких операций вам необходимо получить новый массив, для которого любая префиксная сумма $prefix\_sum(i)$ либо положительная, либо отрицательная, и при этом для любого $i < n — 1$ знак $prefix\_sum(i)$ не должен быть равен знаку $prefix\_sum(i + 1)$.


Пояснение к примерам


В первом примере можно за две операции получить массив $[-1, 2, -2]$. Во втором тесте массив уже удовлетворяет необходимые условия.

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


В первой строке входных данных содержится одно целое число $n$ — размер массива ($1 < n < 10^5$). Во второй строке содержатся n целых чисел $a_0$, $a_1$,… $a_n-1$, разделённые пробелом — элементы массива ($-10^9 < a_i < 10^9$).

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


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

Решение
Если мы зафиксируем финальный знак нулевого элемента, который равен $prefix\_sum(0)$, то знаки остальных префиксных сумм нам уже будут известны. Например, если $a_0 = prefix\_sum(0) > 0$, то $prefix\_sum(0), prefix\_sum(2), prefix\_sum(4) \dots$ должны быть положительными, а $prefix\_sum(1), prefix\_sum(3), prefix\_sum(5) \dots$ — отрицательными.

Пусть мы знаем $prefix\_sum(i-1)$, а также требуемый знак для $prefix\_sum(i)$. Какое наименьшее количество операций требуется применить к элементу $a_i$, чтобы сумма

$prefix\_sum(i) = prefix\_sum(i-1) + a_i$ стала нужного знака? Рассмотрим два случая:

  1. Если $prefix\_sum(i) = prefix\_sum(i-1) + a_i$ уже нужного знака, тогда количество требуемых операций равно нулю.
    Иначе есть три подслучая:

    1. Если $prefix\_sum(i-1) + a_i > 0$, то нужно применить операцию уменьшения $prefix\_sum(i-1) + a_i + 1$ раз, чтобы получить $-1$ — это будет минимальное количество операций, так как префиксная сумма $0$ нам не подходит, а сумму $-2$ и меньше получать смысла нет: мы сейчас сделаем операций больше, а потом придётся использовать больше операций увеличения, чтобы получить положительное число.
    2. Если $prefix\_sum(i-1) + a_i < 0$, то применим $-(prefix\_sum(i-1) + a_i ) + 1$ операцию увеличения, чтобы получить $1$.
    3. Если же $prefix\_sum(i-1) + a_i = 0$, то достаточно одной операции в зависимости от требуемого знака.

В итоге, для решения задачи предлагаем рассмотреть два случая: когда $prefix\_sum(0) > 0$ и когда $prefix\_sum(0) < 0$; для каждого из них найти ответ и взять минимальное значение из двух. Получаем решение за линейную асимптотику.

Заключение


Это были задачи из отборочного и основного раунда для поступления на курс «Автоматическое тестирование веб-сервисов на Go». Какие дались вам легче всего, а какие труднее? И расскажите о своих решениях, которые оказались проще или эффективнее наших :)
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Какую задачу вы считаете самой интересной?
0% Хэш0
0% Города0
0% Инверсии0
14.29% Общее поле2
0% Даты0
0% Регионы0
14.29% Логистика2
71.43% Посмотреть варианты10
Проголосовали 14 пользователей. Воздержались 6 пользователей.
Теги:
Хабы:
Всего голосов 12: ↑11 и ↓1+22
Комментарии0
Ozon Tech
Команда разработки ведущего e‑com в России
10
Карма
0
Рейтинг
Роман Чудин @xe1by

Product Manager All Cups

Отправить сообщение

Публикации

Информация

Сайт
ozon.tech
Дата регистрации
Дата основания
Численность
5 001–10 000 человек
Местоположение
Россия

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr