news.shamcode.ru | Как мы выбираем задания на отбор Route 256: подход и разбор задач

Однажды мы решили, что грамотных инженеров эффективнее всего растить самим. Так 3 года назад родился Route 256 — курсы Ozon для разработчиков и тестировщиков уровней junior и middle.

Во время курса ведущие специалисты Ozon погружают в индустрию e-com, знакомят с актуальным стеком и бизнес-задачами. Самые успешные выпускники получают оффер в команду Ozon.

В статье расскажем, почему для отбора мы используем алгоритмы, и покажем разбор задач с контеста.

Почему проект использует алгоритмические задачи в качестве средства отбора?

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

Но какого типа должен быть этот отбор?

Проекту необходимо отбирать студентов с релевантными знаниями, навыками, с необходимым опытом, образованием, потому что студенты проекта — это потенциальные сотрудники компании и курсы Route 256 в первую очередь создавались с целью последующего найма.

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

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

Алгоритмическая задача в этом контексте — это, прежде всего, определённый формат задания. Участник должен правильно, согласно условию задачи, обрабатывать входные данные и выводить верный ответ.

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

Подход к составлению задач

Итак, в прошлом разделе мы разобрали, почему проект предлагает участникам решить алгоритмические задачи в качестве отборочного испытания. Но всё же, знание алгоритмов и реальные рабочие задания — редко пересекающиеся плоскости. Необходимо подготавливать такие задачи, которые не отсеют потенциального успешного junior- или middle-разработчика компании только на основании того, что он не знаком с каким-то определённым, специфичным алгоритмом.

Авторы задач — это разработчики компании. Они каждый день сталкиваются с реальными рабочими задачами и как никто знают, с чем предстоит столкнуться студенту курса, когда тот попадёт на работу в компанию.

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

Также из контеста в контест авторы реализуют уже знакомый для многих тип задач: работа с определённым форматом хранения данных (например, JSON). По сути это такая же задача c ограничениями по времени и памяти, тестами, но её входные данные имеют вид популярного формата хранения данных.

А чтобы оценить реальные примеры задач контеста, предлагаем прочитать разбор.

Настало время перейти к разбору

Задача «3-правильная очередь»

Краткое условие без легенды

Есть три вида событий — , и . Один запрос может содержать только одну пару , и (именно в таком порядке). Запись происходит асинхронно, события запроса в очереди могут лежать непоследовательно, то есть после записи первого события первого запроса, могло записаться событие от другого запроса.
Требуется понять, возможно ли корректно разделить события на пары.

Пример

Для набора событий один из возможных вариантов — набор пар с индексами:

Разбор

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

Первым делом посчитаем количество всех трёх переменных —. С помощью этих переменных мы можем посчитать, какое количество пар , , должно быть в ответе.

Для этого нужно решить следующую систему уравнений:

$count_{AB} + count_{AC} = count_{A}$
$count_{AB} + count_{BC} = count_{B}$
$count_{AC} + count_{BC} = count_{C}$

Нас интересует только $count_{BC}$ , поэтому решением будет $count_{BC} = count_B - (n - count_C * 2) / 2$ .

Заведём два дека — один для позиций A( positions_a ), другой для позиций B( positions_b ). Будем идти с начала строки до её конца, на каждой позиции у нас есть три варианта, что делать:

если мы встретили , то просто положим её в ;
если мы встретили , то просто положим её в ;
если же мы встретили , то нужно понять, к кому её поставить в пару.
- Если не пуст и при этом $count_{bc}$ меньше количества уже набранных пар , то возьмем B с наименьшей позицией из него и поставим в пару к этой . На самом деле нам всегда выгоднее брать в пару к , чем в пару к A. Мы чуть позже это докажем.
- Если не пуст, то возьмем с наибольшей позицией из него и поставим в пару к этой .
- Если оба пусты, то значит, что к этой никого в пару поставить нельзя, и, следовательно, ответ — «Нельзя»

Если после этого цикла из оставшихся A и B можно собрать пары, то ответ — «Можно», а иначе — «Нельзя».

Для того чтобы это проверить, мы должны:

проверить, что размеры и равны;
проверить, что для всех i.

Пример решения

Пусть есть достаточно большая строка: BBAABABCCABACCCBCCBB .

Давайте на её примере разберём, как этот алгоритм будет работать.

Первым делом мы посчитаем count_A = 5 , count_B = 8 , count_C = 7 .

По формуле посчитаем $count_{BC} = count_B - (n - count_C * 2) / 2 = 8 - (20 - 7 * 2) / 2 = 8 - 3 = 5$ .

$positions_a = \{\}$ , $positions_b = \{\}$ , $count_{BC} = 5$ , встречаем символ B, кладём его индекс в .
$positions_a = \{\}$ , $positions_b = \{0\}$ , $count_{BC} = 5$ , встречаем символ B, кладём его индекс в .
$positions_a = \{\}$ , $positions_b = \{0, 1\}$ , $count_{BC} = 5$ , встречаем символ A, кладём его индекс в .
$positions_a = \{2\}$ , $positions_b = \{0, 1\}$ , $count_{BC} = 5$ , встречаем символ A, кладём его индекс в .
$positions_a = \{2, 3\}$ , $positions_b = \{0, 1\}$ , $count_{BC} = 5$ , встречаем символ B, кладём его индекс в .
$positions_a = \{2, 3\}$ , $positions_b = \{0, 1, 4\}$ , $count_{BC} = 5$ , встречаем символ A, кладём его индекс в .
$positions_a = \{2, 3, 5\}$ , $positions_b = \{0, 1, 4\}$ , $count_{BC} = 5$ , встречаем символ B, кладём его индекс в .
$positions_a = \{2, 3, 5\}$ , $positions_b = \{0, 1, 4, 6\}$ , $count_{BC} = 5$ , встречаем символ C, так как не пуста и $cnt_{bc} > 0$ , то достаём B с минимальным индексом и формируем пару с ним. Пара — $\{0, 7\}$ .
$positions_a = \{2, 3, 5\}$ , $positions_b = \{1, 4, 6\}$ , $count_{BC} = 4$ , встречаем символ C, так как не пуста и $count_{BC} > 0$ , то достаём B с минимальным индексом и формируем пару с ним. Пара — $\{1, 8\}$ .
$positions_a = \{2, 3, 5\}$ , $positions_b = \{4, 6\}$ , $count_{BC} = 3$ , встречаем символ A, кладём его индекс в .
$positions_a = \{2, 3, 5, 9\}$ , $positions_b = \{4, 6\}$ , $count_{BC} = 3$ , встречаем символ B, кладём его индекс в .
$positions_a = \{2, 3, 5, 9\}$ , $positions_b = \{4, 6, 10\}$ , $count_{BC} = 3$ , встречаем символ A, кладём его индекс в .
$positions_a = \{2, 3, 5, 9, 11\}$ , $positions_b = \{4, 6, 10\}$ , $count_{BC} = 3$ , встречаем символ C, так как не пуста и $count_{BC} > 0$ , то достаём B с минимальным индексом и формируем пару с ним. Пара — $\{12, 4\}$ .
$positions_a = \{2, 3, 5, 9, 11\}$ , $positions_b = \{6, 10\}$ , $count_{BC} = 2$ , встречаем символ C, так как не пуста и $count_{BC} > 0$ , то достаём B с минимальным индексом и формируем пару с ним. Пара — $\{13, 6\}$ .
$positions_a = \{2, 3, 5, 9, 11\}$ , $positions_b = \{10\}$ , $count_{BC} = 1$ , встречаем символ C, так как не пуста и $count_{BC} > 0$ , то достаём B с минимальным индексом и формируем пару с ним. Пара — $\{14, 10\}$ .
$positions_a = \{2, 3, 5, 9, 11\}$ , $positions_b = \{\}$ , $count_{BC} = 0$ , встречаем символ B, кладём его индекс в .
$positions_a = \{2, 3, 5, 9, 11\}$ , $positions_b = \{15\}$ , $count_{BC} = 0$ , встречаем символ C, так как не пуста, но $count_{BC} = 0$ , то достаём A с максимальным индексом и формируем пару с ним. Пара — $\{16, 11\}$ .
$positions_a = \{2, 3, 5, 9\}$ , $positions_b = \{15\}$ , $count_{BC} = 0$ , встречаем символ C, так как не пуста, но $count_{BC} = 0$ , то достаём A с максимальным индексом и формируем пару с ним. Пара — $\{17, 9\}$ .
$positions_a = \{2, 3, 5\}$ , $positions_b = \{15\}$ , $count_{BC} = 0$ , встречаем символ B, кладём его индекс в .
$positions_a = \{2, 3, 5\}$ , $positions_b = \{15, 18\}$ , $count_{BC} = 0$ , встречаем символ B, кладём его индекс в .

Получили $positions_a = \{2, 3, 5\}$ , $positions_b = \{15, 18, 19\}$ , их размеры равны и при этом $\forall_i: positions_a[i] < positions_b[i]$ .

Следовательно, ответ — «Можно».

Корректность

Одним из главных моментов нашего решения является утверждение про порядок выбора, а именно то, что мы всегда стараемся выбрать в первую очередь с минимальным индексом. Если же свободных нет, то стараемся выбрать с максимальным индексом.

Докажем по пунктам.

Докажем сначала, почему выгоднее выбрать минимальное B. Допустим, что наше решение выбрало пару $BC = \{x_1, y_1\}$ , а какое-то другое решение выбрало $BC = \{x_2, y_1\}$ , при этом . Тогда в этом решении для нашего была выбрана либо пара $AB = \{x_3, x_1\}$ , либо пара $BC = \{x_1, y_2\}$ . Так как , то мы можем без проблем поменять обе B местами( и ), то же самое и в случае смены местами и .
Затем докажем, почему выгоднее выбрать максимальное A. Допустим, что наше решение выбрало пару $AC = \{x_1, y_1\}$ , а какое-то другое решение выбрало $AC = \{x_2, y_1\}$ (при этом . Тогда в этом решении для нашего была выбрана либо пара $AB = \{x_1, x_3\}$ , либо пара $AC = \{x_1, y_2\}$ . Так как , то мы можем без проблем поменять A местами. То есть логика такая же, как и в предыдущем кейсе.
Затем докажем, что выгоднее выбирать B, а не A.

Если доказывать неформально, то все просто — в конце мы проверяем два массива по позициям, а следовательно, нам выгодно, чтобы в получившихся массивах все были как можно меньше, а — как можно больше.

Так как на каждом шаге мы выбираем минимальные и максимальные , то выбирать нам выгоднее, чем .

Более формально — допустим, в нашем решении мы выбрали $BC = \{x_1, y_1\}$ , а в каком-то другом $AC = \{x_2, y_1\}$ , тогда может быть либо в паре с каким-то другим и тогда мы без проблем можем поменять их пары (поскольку в нашем решении мы всегда выбираем минимальное), либо в паре с какой-то другой . Во втором случае, мы продолжаем менять связь в нашем решении (то есть из пары $\color{blue}{AB}\color{red}{BC}$ делаем $\color{blue}{A}\color{red}{B}\color{blue}{B}\color{red}{C}$ ) до тех пор, пока не дойдём до , связанной с (так как количество пар всегда одно и то же), и, следовательно, опять поменяем их местами.

Время работы и память

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

Затем по формуле мы считаем количество пар — это O(1).

Затем мы проходимся по всей строке, поддерживая при этом дек символов , , для каждой позиции мы либо вставляем в дек, либо удаляем, а также делаем константное количество сравнений, следовательно, цикл также работает за O(n).

Финальная часть (сравнение результирующих деков) также работает за O(n), следовательно, суммарная асимптотика — O(n).

Дополнительная память также линейная, так как мы поддерживаем деки элементов.

Задача «Три банка, три валюты»

Краткое условия без легенды

Банки A, B и C предлагают обмен валюты.

Каждый банк меняет рубли, доллары и евро по своему курсу. Вы можете обращаться в каждый из банков не более одного раза. Под одним обращением понимается 1 операция обмена валюты. Нельзя внутри одного банка совершить несколько операций обмена валют.

Вам необходимо перевести 1 рубль в максимально возможное количество долларов.

Пример теста

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

100:1 — 1 банк (курс обмена рублей на доллары).
100:1 — 1 банк (курс обмена рублей на евро).
1:100 — 1 банк (курс обмена долларов на рубли).
3:2 — 1 банк (курс обмена долларов на евро).
1:100 — 1 банк (курс обмена евро на рубли).
2:3 — 1 банк (курс обмена евро на доллары).
100:1 — 2 банк (курс обмена рублей на доллары).
100:1 — 2 банк (курс обмена рублей на евро).
1:10 — 2 банк (курс обмена долларов на рубли).
3:2 — 2 банк (курс обмена долларов на евро).
1:100 — 2 банк (курс обмена евро на рубли).
2:3 — 2 банк (курс обмена евро на доллары).
100:1 — 3 банк (курс обмена рублей на доллары).
100:1 — 3 банк (курс обмена рублей на евро).
1:100 — 3 банк (курс обмена долларов на рубли).
3:2 — 3 банк (курс обмена долларов на евро).
1:100 — 3 банк (курс обмена евро на рубли).
2:3 — 3 банк (курс обмена евро на доллары).

Итого получаем:

1 банк;

сurrency	RUR	USD	EUR
RUR	1:1	100:1	100:1
USD	1:100	1:1	3:2
EUR	1:100	2:3	1:1

2 банк;

сurrency	RUR	USD	EUR
RUR	1:1	100:1	100:1
USD	1:100	1:1	3:2
EUR	1:100	2:3	1:1

3 банк;

сurrency	RUR	USD	EUR
RUR	1:1	100:1	100:1
USD	1:100	1:1	3:2
EUR	1:100	2:3	1:1

Можно заметить, что в данном тесте у всех банков курсы одинаковые, а следовательно, на финальное количество долларов влияет только выбор и порядок пар валют для обмена.

Проверив все возможные порядки для этого теста, можно увидеть, что здесь больше всего долларов мы получим после следующего порядка: $RUR \Rightarrow EUR \Rightarrow USD$ .

Разбор

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

Одним из возможных решений будет рекурсивная функция $find\_biggest\_amount(amount, currency, used\_banks)$ , где amount — текущее количество валюты , а $used\_banks$ — номера уже использованных банков.

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

Например, если у нас были рубли, то шаги могут быть следующими:

поменять на рубли (в данном случае это то же самое, что и не сделать ничего);
поменять на доллары;
поменять на евро.

Пример решения

Покажем, как будет работать наше решение на тесте из условия.

Изначально мы начинаем с 1 рублем, то есть вызываем функцию $find\_biggest\_amount(1, rur, \{\})$ .
- Начинаем перебор банков с первого банка.
- Начинаем перебор возможных операций с перевода в рубли.
- Вызываем функцию.
Обрабатываем вызов $find\_biggest\_amount(1, rur, \{1\})$ .
- Начинаем перебор банков с второго банка.
- Начинаем перебор возможных операций с перевода в рубли.
- Вызываем функцию.
Обрабатываем вызов $find\_biggest\_amount(1, rur, \{1, 2\})$ .
- Начинаем перебор банков с третьего банка.
- Начинаем перебор возможных операций с перевода в рубли.
- Вызываем функцию.
Обрабатываем вызов $find\_biggest\_amount(1, rur, \{1, 2, 3\})$ . Так как больше свободных банков нет, то это конечный вызов, и возвращаемся в прошлый шаг перебора.
Вернулись к вызову $find\_biggest\_amount(1, rur, \{1, 2\})$ .
- Продолжаем перебор банков с третьего банка.
- Продолжаем перебор возможных операций с перевода в доллары.
- Вызываем функцию $find\_biggest\_amount(0.01, usd, \{1, 2, 3\})$ .
Обрабатываем вызов $find\_biggest\_amount(0.01, usd, \{1, 2, 3\})$ . Так как валюта — доллар, обновляем ответ. Так как больше свободных банков нет, то это конечный вызов, и возвращаемся в прошлый шаг перебора.
Вернулись к вызову $find\_biggest\_amount(1, rur, \{1, 2\})$ .
- Продолжаем перебор банков с третьего банка.
- Продолжаем перебор возможных операций с перевода в евро.
- Вызываем функцию $find\_biggest\_amount(0.01, eur, \{1, 2, 3\})$ .
Обрабатываем вызов $find\_biggest\_amount(0.01, eur, \{1, 2, 3\})$ . Так как больше свободных банков нет, то это конечный вызов, и возвращаемся в прошлый шаг перебора.
Вернулись к вызову $find\_biggest\_amount(1, rur, \{1, 2\})$ .
- Мы всё перебрали, поэтому возвращаемся в $find\_biggest\_amount(1, rur, \{1\})$ .

Давайте также сразу посмотрим и путь, дающий лучший ответ:

Изначально мы начинаем с 1 рублем, то есть начинаем с вызова $find\_biggest\_amount(1, rur, \{\})$ .
- Начинаем перебор банков с первого банка.
- Дойдём до операции перевода в евро.
- Вызываем функцию $find\_biggest\_amount(0.01, eur, \{1\})$ .
Обрабатываем вызов $find\_biggest\_amount(0.01, eur, \{1\})$ .
- Начинаем перебор банков с второго банка.
- Дойдём до операции перевода в доллар.
- Вызываем функцию $find\_biggest\_amount(0.015, usd, \{1, 2\})$ .
Обрабатываем вызов $find\_biggest\_amount(0.015, usd, \{1, 2\})$ .
- Начинаем перебор банков с третьего банка.
- Начинаем перебор возможных операций с перевода в рубли.
- Вызываем функцию $find\_biggest\_amount(0.015, usd, \{1, 2, 3\})$ .
Обрабатываем вызов $find\_biggest\_amount(0.015, usd, \{1, 2, 3\})$ . Это и будет ответ.

Корректность решения

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

Важное про вещественные числа

Вообще, в данной задаче прекрасно работали и вещественные числа, так как требовалась достаточно небольшая точность, поэтому решения с float или double должны были работать.

Также можно было использовать decimal или самому его написать, если хотелось большей точности.

Время работы и память

Наше решение будет перебирать все банки и все валюты, из чего мы получим $O(banks! \cdot currencies^{banks})$ , что в нашем случае будет O(1) , дополнительной памяти на рекурсию требуется столько же.

Задача «3-покер»

Краткое условие без легенды

У нас есть карты от 2 до туза и все 4 масти.

Игра происходит следующим образом:

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

Комбинации от большей к меньшей:

если две карты у игрока в руке и карта на столе имеют одинаковое значение, игрок собрал комбинацию «Сет со значением X».
если из двух карт у игрока в руке и карты на столе можно выбрать две карты с одинаковым значением , игрок собрал комбинацию «Пара со значением X».
иначе, берется карта с самым старшим значением из двух карт у игрока в руке и карты на столе, тогда игрок собрал комбинацию «Старшая карта X».

Если одинаковая самая старшая комбинация есть у нескольких игроков, все они объявляются выигравшими.

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

Пример теста

У первого человека на руках карты TS и TC, то есть 10 пики (ten spades) и 10 треф (ten clubs).
У второго человека на руках карты AD и AH, то есть туз бубён (ace diamonds) и туз червей (ace hearts).

Для победы подходит карта , так как тогда у первого игрока будет «Сет со значением X», а у второго «Пара со значением X» и первый игрок выигрывает.

Для победы не подходит карта , так как тогда у первого игрока будет «Пара со значением J», а у второго «Пара со значением A» и первый игрок проигрывает.

Разбор

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

Тогда решение разбивается на две части:

Как правильно перебрать все карты?
Как проверить, кто выиграет при какой-то карте?

Как правильно перебрать все карты?

Достаточно простым в реализации является следующий вариант.

Заведем массив всех значений (value):

$\textbf{2}, \textbf{3}, \textbf{4}, \textbf{5}, \textbf{6}, \textbf{7}, \textbf{8}, \textbf{9}, \textbf{T}, \textbf{J}, \textbf{Q}, \textbf{K}, \textbf{A}$ .

Заведем массив всех мастей (suit):

$\textbf{S}, \textbf{C}, \textbf{D}, \textbf{H}$ .

Также заведем словарь уже использованных карт, то есть карт, которые на руках у любого из игроков.

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

Пример перебора

В тесте из условия словарь использованных карт:

$\{TS, TC, AD, AH\}$ .

Промоделируем перебор:

, карта ещё не использована.
, карта ещё не использована.

$\dots$

, карта использована, не рассматриваем.
, карта ещё не использована.
, карта ещё не использована.
, карта ещё не использована.
, карта ещё не использована.
, карта ещё не использована.

$\dots$

, карта использована, не рассматриваем.

$\dots$

, карта ещё не использована.
, карта использована, не рассматриваем.

Таким образом мы получили список карт для проверки.

Как проверить, кто выиграет при какой-то карте?

Для карт можно завести отдельный класс или работать с ними, как со строками. Пример класса на Go:

type Value int

const (
	Value2 Value = iota
	Value3
	Value4
	Value5
	Value6
	Value7
	Value8
	Value9
	ValueT
	ValueJ
	ValueQ
	ValueK
	ValueA
)

func (v Value) String() string {
	return [...]string{"2", "3", "4", "5", "6", "7", "8", "9", "T", "J", "Q", "K", "A"}[v]
}

type Cars struct {
	Value    Value
    Suit     char
}

Сделаем функцию $check\_combination(card_1, card_2, card_3)$ , которая по трем картам возвращает комбинацию.

Первым делом заметим, что в комбинациях никак не участвует масть, поэтому нам достаточно проверять только значение.

Также очень удобно сделать отдельную структуру для комбинации: Combination, которую будет содержать количество одинаковых карт и значение, вот пример на языке Go:

type Combination struct {
	Value    Value
    Count    int
}

func (c Combination) Less(other Combination) bool {
	if c.Count != other.Count {
		return c.Count < other.Count
	}
	return c.Value < other.Value
}

Проверка комбинации же выглядит следующим образом:

Если , то возвращаем .
Если или , то возвращаем .
Если , то возвращаем .
Возвращаем .

Пример проверки

Для тройки TS, TC, TD мы пройдем следующий путь:

следовательно, возвращаем .

Для тройки AD, AH, TD мы пройдём следующий путь:

$card_1.Value = card_2.Value \neq card_3.Value$
, возвращаем .

< Combination(T, 3) , следовательно, первый игрок выиграл.

Время работы и память

Максимально возможное количество карт — 52.

Проверка, кто выиграл при выкладывании карты, работает за O(1).

Таким образом, всё решение работает за O(1).

Дополнительная память нам требуется только на хранение трех карт и получившейся комбинации, следовательно, дополнительной памяти также будет O(1).

Задача «JSON-категории»

Краткое условие без легенды

У каждого товара есть категория. При этом у некоторых категорий есть дочерние категории.

Назовём деревом категорий такую сущность:

Ваша задача — построить дерево категорий.

Дана информация об отношениях родительских и дочерних категорий в виде JSON-массива. Каждый элемент массива является словарем, с полями $\texttt{name}$ (название категории), $\texttt{id}$ (числовой идентификатор категории) и $\texttt{parent}$ (числовой идентификатор родительской категории).

Известно, что корневая категория имеет нулевой идентификатор и не имеет идентификатора родительской категории.

По данной информации постройте дерево категорий в виде JSON-словаря. Словарь для каждой категории должен иметь поля $\texttt{name}$ , $\texttt{id}$ и массив $\texttt{next}$ , состоящий из таких же словарей для дочерних категорий.

Пример теста

В тесте из условия был такой JSON:

[
   {
     "id":0,
     "name":"all"
   },
   {
      "id":1,
      "name":"clothes",
      "parent":0
   },
   {
      "id":2,
      "name":"shoes",
      "parent":0
   },
   {
      "id":55,
      "name":"sneakers",
      "parent":2
   }
]

Этому JSON соответствует следующее дерево категорий:

Финальное же представление дерева в виде JSON будет таким:

{
        "id": 0,
        "name": "all",
        "next": [
            {
                "id": 1,
                "name": "clothes",
                "next":[]
            },
            {
                "id": 2,
                "name": "shoes",
                "next": [
                    {
                        "id": 55,
                        "name": "sneakers",
                        "next":[]
                    }
                ]
            }
        ]
    }
]

Разбор

В этой задаче можно было написать решение и с самостоятельным составлением JSON, но можно было использовать готовые библиотеки, разрешённые в задаче ("encoding/json" в Go или её аналоги в других языках).

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

Первым делом было удобно реализовать специальные структуры для категории и для целого дерева категорий.

type Category struct {
	ID       int    `json:"id"`
	Name     string `json:"name"`
	ParentID int    `json:"parent"`
}

type Tree struct {
	ID   int     `json:"id"`
	Name string  `json:"name"`
	Next []*Tree `json:"next"`
}

Нам нужно получить из входных данных что-то достаточно осмысленное. Для этого мы построчно считаем входной файл, сложим результат в одну строку и из JSON получим массив категорий. Пример кода на Go:

inputString := ""
for i := 0; i < n; i++ {
    line, _ := in.ReadString('\n')
    inputString += line
}

categories := make([]Category, 0)
json.Unmarshal([]byte(inputString), &categories)

Таким образом, мы получим массив категорий, с которым позже сможем комфортно работать.

Создадим словарь вершин дерева, то есть map[int]*Tree , который по id Tree будет возвращать соответсвующую структуру.

Нам нужно собрать из массива категорий дерево, это можно сделать с помощью dfs или с помощью цикла.

В цикле мы будем класть в tree.next все вершины, у которых.

for _, i := range arr {
    t := new(Tree)
    t.ID = i.ID
    t.Name = i.Name
    t.Next = make([]*Tree, 0)
    treeByNode[i.ID] = t
}
for _, i := range arr {
    if i.ID != 0 {
        treeByNode[i.ParentID].Next = append(treeByNode[i.ParentID].Next, treeByNode[i.ID])
    }
}

Положим полученное дерево в JSON и выведем ответ:

bytes, _ := json.Marshal(treeByNode[0]) // 0 - root category

Пример решения

Разберём работу решения на тесте из условия.

После парсинга входных данных мы получим массив категорий:

categories = [
    Category{ID: 0, Name: "all", ParentID: null},
    Category{ID: 1, Name: "clothes", ParentID: 0},
    Category{ID: 2, Name: "shoes", ParentID: 0},
    Category{ID: 55, Name: "sneakers", ParentID: 2},
]

После создания дерева мы получим следующее:

treeByNode = {
    0: *Tree{ID: 0, Name: "all", next: []},
    1: *Tree{ID: 1, Name: "clothes", next: []},
    2: *Tree{ID: 2, Name: "shoes", next: []},
    55: *Tree{ID: 55, Name: "sneakers", next: []},
}

Финальный же цикл сделает следующее:

i.id = 0; continue;

i.id = 1; i.ParentID = 0; 
tree[treeByNode[0]].next.append(treeByNode[1]); 
tree[treeByNode[0]].next = [treeByNode[1]];

i.id = 2; i.ParentID = 0;
tree[treeByNode[0]].next.append(treeByNode[2]);
tree[treeByNode[0]].next = [treeByNode[1], treeByNode[2]];

i.id = 55; i.ParentID = 2;
tree[treeByNode[2]].next.append(treeByNode[55]);
tree[treeByNode[2]].next = [treeByNode[55]];

Мы получим такое дерево:

treeByNode = {
    0: *Tree{ID: 0, Name: "all", next: [treeByNode[1], treeByNode[2]]},
    1: *Tree{ID: 1, Name: "clothes", next: []},
    2: *Tree{ID: 2, Name: "shoes", next: [treeByNode[55]]},
    55: *Tree{ID: 55, Name: "sneakers", next: []},
}

Время работы и память

Encode и decode JSON работают за линейное от его размера время.

Дерево мы строим также за линейное время, следовательно, итоговая асимптотика — O(len(json)) .

Дополнительной памяти нам также требуется — O(len(json)) , так как нам требуется сохранить финальный JSON, а также требуется строка с исходным JSON.