Данная задача относится к моему «любимому» типу — попробуй пойми что от тебя хотят.
Первая сложность задачи не в поиске самого решения, а в попытках сократить контекст и описания с половины экрана до нескольких строчек, убирая весь лор про Dota2, сенаторов и регламенты проведения голосований.
Безусловно, в реальных условиях так часто и бывает — вам приносят бизнес задачу/проблему, которую вы должны решить, а не готовое ТЗ, где все структурировано расписано на понятном вам языке. Но для задач на собеседовании это перебор. Время сильно ограничено, вы стрессуете и вместо того, чтобы думать над задачей - пытаетесь продраться через витиеватое описание.
Сложность: 🟡 Средняя
ℹ️ Описание
В мире Dota2 существует 2 партии
Radiant и Dire.Для того чтобы внести изменение в игру Dota2 необходимо провести голосование сената, каждый член которого принадлежит одной из двух партий.
Голосование идет раундами, в каждом раунде по очереди опрашивается каждый сенатор.
Сенатор может выполнить одно из двух действий:
- лишить следующего сенатора из противоположной партии права голоса;
- объявить победу своей партии, если не осталось сенаторов с правом голоса из противоположной партии.
Раунд начинается с крайнего левого сенатора.
Напишите функцию, которая будет рассчитывать результаты голосования сената.
⚠️ Ограничения
- Количество сенаторов (длина входящей строки) находится в диапазоне от 1 до 10000
- Входящая строка состоит из символов
R и D1️⃣ Пример
Входящие данные
RD
Ответ
Radiant
2️⃣ Пример
Входящие данные
RDD
Ответ
Dire
✅ Решение
На первый взгляд задача может решиться простым сравнением количества сенаторов из каждой партии.
На самом деле такое решение будет не верно, так как не учитывает порядок голосования. Это легко понять на примере
RDRDRDRDRDDD.Правильный подход для решения этой задачи — воспользоваться структурой данных «очередь», поместив в нее сенаторов в заданом порядке.
Тогда весь процесс сведется к двум действиям:
- Забрать из начала очереди сенатора, а после того как тот совершит ход (лешит права голоса ближайшего сенатора из противоположной партии), помещать его в конец очереди.
- Удалить из очереди сенаторов без права голоса.
Итоговый ответ мы получим, когда в очереди останутся представители только одной партии.
Посмотреть реализацию и подробный разбор примера в блоге
🅾️ Оценка сложности
По времени
O(n) — так как нам придется несколько раз проитерироваться по очереди.
По памяти
O(n) — так как мы выделяем память для работы с очередью.
#queue #medium