Паттерн observer позволяет объектам подписаться на субъект и получать уведомление, когда что-то происходит. Здесь люди подписываются на темы, и каждое опубликованное событие приходит всем подписчикам его темы.
Каждая подписка имеет вид <person> <topic>. Повторная подписка ничего не добавляет. Затем каждое событие в events — это название темы: каждый подписчик этой темы получает одно уведомление. События тем, на которые никто не подписан, отбрасываются.
Реализуйте event_subscribers(subscriptions, events).
Входные данные
subscriptions: Строки вида "<person> <topic>" (в именах нет пробелов).
events: Названия тем в порядке публикации.
Выходные данные
Верните "<person>:<count>" для каждого человека, у которого есть хотя бы одна подписка, отсортировав по имени (порядковое сравнение символов).
Ограничения
1 ≤ число подписок ≤ 10,000
0 ≤ число событий ≤ 100,000
Примеры
Ввод:
events = ["news", "sports", "weather"]
subscriptions = ["bob sports", "alice news", "alice sports"]
Ожидаемый вывод:
expected = ["alice:2", "bob:1"]Ввод:
std::vector<std::string> events = {"news", "sports", "weather"};
std::vector<std::string> subscriptions = {"bob sports", "alice news", "alice sports"};
Ожидаемый вывод:
std::vector<std::string> expected = {"alice:2", "bob:1"};Ввод:
string[] events = new string[] {"news", "sports", "weather"};
string[] subscriptions = new string[] {"bob sports", "alice news", "alice sports"};
Ожидаемый вывод:
string[] expected = new string[] {"alice:2", "bob:1"};Пояснение
alice подписана на news и sports, поэтому получает оба события; bob получает только sports; на weather никто не подписан: ["alice:2", "bob:1"].
Ввод:
events = []
subscriptions = ["zoe tech", "zoe tech"]
Ожидаемый вывод:
expected = ["zoe:0"]Ввод:
std::vector<std::string> events = {};
std::vector<std::string> subscriptions = {"zoe tech", "zoe tech"};
Ожидаемый вывод:
std::vector<std::string> expected = {"zoe:0"};Ввод:
string[] events = new string[] {};
string[] subscriptions = new string[] {"zoe tech", "zoe tech"};
Ожидаемый вывод:
string[] expected = new string[] {"zoe:0"};Пояснение
Повторная подписка считается один раз, и событий не было: ["zoe:0"].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Сгруппируйте подписчиков по темам, чтобы каждое событие быстро находило получателей.
Подсказка 2
Используйте множество на тему, чтобы повторная подписка считалась один раз.
Подсказка 3
Каждый подписавшийся есть в ответе, даже с нулём уведомлений.
Ожидаемая сложность
время O(подписки + события × подписчики на тему), доп. память O(подписки)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.