Dota2 Senate

Данная задача относится к моему «любимому» типу — попробуй пойми что от тебя хотят.

Первая сложность задачи не в поиске самого решения, а в попытках сократить контекст и описания с половины экрана до нескольких строчек, убирая весь лор про Dota2, сенаторов и регламенты проведения голосований.
Безусловно, в реальных условиях так часто и бывает — вам приносят бизнес задачу/проблему, которую вы должны решить, а не готовое ТЗ, где все структурировано расписано на понятном вам языке. Но для задач на собеседовании это перебор. Время сильно ограничено, вы стрессуете и вместо того, чтобы думать над задачей - пытаетесь продраться через витиеватое описание.

Сложность: 🟡 Средняя

ℹ️ Описание

В мире Dota2 существует 2 партии Radiant и Dire.
Для того чтобы внести изменение в игру Dota2 необходимо провести голосование сената, каждый член которого принадлежит одной из двух партий.

Голосование идет раундами, в каждом раунде по очереди опрашивается каждый сенатор.
Сенатор может выполнить одно из двух действий:
- лишить следующего сенатора из противоположной партии права голоса;
- объявить победу своей партии, если не осталось сенаторов с правом голоса из противоположной партии.
Раунд начинается с крайнего левого сенатора.

Напишите функцию, которая будет рассчитывать результаты голосования сената.

⚠️ Ограничения

- Количество сенаторов (длина входящей строки) находится в диапазоне от 1 до 10000
- Входящая строка состоит из символов R и D


1️⃣ Пример

Входящие данные

RD

Ответ

Radiant

2️⃣ Пример

Входящие данные

RDD

Ответ

Dire

✅ Решение

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

Правильный подход для решения этой задачи — воспользоваться структурой данных «очередь», поместив в нее сенаторов в заданом порядке.
Тогда весь процесс сведется к двум действиям:
- Забрать из начала очереди сенатора, а после того как тот совершит ход (лешит права голоса ближайшего сенатора из противоположной партии), помещать его в конец очереди.
- Удалить из очереди сенаторов без права голоса.

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

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

🅾️ Оценка сложности

По времени

O(n) — так как нам придется несколько раз проитерироваться по очереди.

По памяти

O(n) — так как мы выделяем память для работы с очередью.

#queue #medium

Количество последних вызовов

Сложность: 🟢 Легкая

ℹ️ Описание

Вам дан класс RecentCounter, который подсчитывает количество последних вызовов за определенный период времени. Реализуйте этот класс.

Конструктор RecentCounter инициализирует счетчик с нулевым количеством последних вызовов.
Класс имеет метод ping, который принимает в качестве аргумента параметр t (время в миллисекундах последнего вызова) и в качестве ответа возвращает количество вызовов, произошедших за последние 3000 мс.

Гарантируется, что каждый вызов ping использует строго большее значение t, чем предыдущий вызов.

⚠️ Ограничения

— Значение t находится в диапазоне от 1 до 10^9
— Каждый пример будет вызывать ping со строго возрастающими значениями t
— Для проверки будет совершено не более 10^4 вызовов метода ping

1️⃣ Пример

```golang



counter := Constructor()

counter.Ping(1)
counter.Ping(100)
counter.Ping(3001)
counter.Ping(3002)
counter.Ping(3003)
```

Ответ: 4

Пояснение: За последние 3000 мс было сделано 4 вызова в следующее время [100, 3001, 3002, 3003].

2️⃣ Пример

counter := Constructor()

counter.Ping(1)
counter.Ping(100)
counter.Ping(3001)

Ответ: 3

Пояснение: За последние 3000 мс было сделано 4 вызова в следующее время [1, 100, 3001].

✅ Решение

Эта задача решается буквально в несколько строчек.

Для хранения вызовов определим массив calls внутри класса, который при инициализации экземпляра получает значение пустого массива.

Далее в реализации метода ping сначала надо добавить время нового вызова в массив calls, а потом удалить из начала все элементы, которые вываливаются из интервала в 3000 миллисекунд, тем самым реализовав простую очередь. В конце нужно лишь вернуть длину оставшегося массива.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

Основная временная сложность нашего метода ping заключается в цикле, который в худшем случае будет выполнять 3000 итераций для извлечения всех устаревших элементов, а в лучшем случае — одну итерацию. Исходя из этого сложность равна O(3000) = O(1).

По памяти

Сложность O(1), так как максимальная длина нашего массива вызовов — 3000 элементов. По условию задачи, каждое новое значение в нем является целым числом и строго больше предыдущего, поэтому мы точно можем определить максимальный размер массива.

#queue #easy