Problema
O padrão observer permite que objetos assinem um sujeito e sejam notificados sempre que algo acontece. Aqui, pessoas assinam tópicos e cada evento publicado vai para todos os assinantes do seu tópico.
Cada assinatura é <person> <topic>. Uma assinatura repetida não tem efeito extra. Depois, cada evento em events é o nome de um tópico: cada assinante desse tópico recebe uma notificação. Eventos de tópicos que ninguém segue são descartados.
Implemente event_subscribers(subscriptions, events).
Entrada
subscriptions: Strings "<person> <topic>" (nomes não têm espaços).
events: Nomes de tópicos, na ordem de publicação.
Saída
Retorne "<person>:<count>" para cada pessoa com pelo menos uma assinatura, ordenadas pelo nome (ordem ordinal de caracteres).
Restrições
1 ≤ número de assinaturas ≤ 10,000
0 ≤ número de eventos ≤ 100,000
Exemplos
Entrada:
events = ["news", "sports", "weather"]
subscriptions = ["bob sports", "alice news", "alice sports"]
Saída esperada:
expected = ["alice:2", "bob:1"]Entrada:
std::vector<std::string> events = {"news", "sports", "weather"};
std::vector<std::string> subscriptions = {"bob sports", "alice news", "alice sports"};
Saída esperada:
std::vector<std::string> expected = {"alice:2", "bob:1"};Entrada:
string[] events = new string[] {"news", "sports", "weather"};
string[] subscriptions = new string[] {"bob sports", "alice news", "alice sports"};
Saída esperada:
string[] expected = new string[] {"alice:2", "bob:1"};Explicação
alice segue news e sports, então recebe os dois eventos; bob recebe só sports; ninguém segue weather: ["alice:2", "bob:1"].
Entrada:
events = []
subscriptions = ["zoe tech", "zoe tech"]
Saída esperada:
expected = ["zoe:0"]Entrada:
std::vector<std::string> events = {};
std::vector<std::string> subscriptions = {"zoe tech", "zoe tech"};
Saída esperada:
std::vector<std::string> expected = {"zoe:0"};Entrada:
string[] events = new string[] {};
string[] subscriptions = new string[] {"zoe tech", "zoe tech"};
Saída esperada:
string[] expected = new string[] {"zoe:0"};Explicação
A assinatura repetida conta uma vez só e nenhum evento foi publicado: ["zoe:0"].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Agrupe os assinantes por tópico para que cada evento encontre seu público rápido.
Dica 2
Use um conjunto por tópico para que uma assinatura repetida conte só uma vez.
Dica 3
Todos que assinaram aparecem no resultado, mesmo com zero notificações.
Complexidade esperada
tempo O(assinaturas + eventos × assinantes por tópico), espaço extra O(assinaturas)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.