Problème
Le patron observer permet à des objets de s'abonner à un sujet et d'être prévenus dès qu'il se passe quelque chose. Ici, des personnes s'abonnent à des sujets et chaque événement publié est envoyé à tous les abonnés de son sujet.
Chaque abonnement s'écrit <person> <topic>. Un abonnement répété n'a aucun effet supplémentaire. Ensuite, chaque événement de events est un nom de sujet : chaque abonné de ce sujet reçoit une notification. Les événements sur des sujets que personne ne suit sont ignorés.
Implémentez event_subscribers(subscriptions, events).
Entrée
subscriptions: Des chaînes "<person> <topic>" (les noms ne contiennent pas d'espaces).
events: Les noms de sujets, dans l'ordre de publication.
Sortie
Renvoyez "<person>:<count>" pour chaque personne ayant au moins un abonnement, triées par nom (ordre ordinal des caractères).
Contraintes
1 ≤ nombre d'abonnements ≤ 10,000
0 ≤ nombre d'événements ≤ 100,000
Exemples
Entrée :
events = ["news", "sports", "weather"]
subscriptions = ["bob sports", "alice news", "alice sports"]
Sortie attendue :
expected = ["alice:2", "bob:1"]Entrée :
std::vector<std::string> events = {"news", "sports", "weather"};
std::vector<std::string> subscriptions = {"bob sports", "alice news", "alice sports"};
Sortie attendue :
std::vector<std::string> expected = {"alice:2", "bob:1"};Entrée :
string[] events = new string[] {"news", "sports", "weather"};
string[] subscriptions = new string[] {"bob sports", "alice news", "alice sports"};
Sortie attendue :
string[] expected = new string[] {"alice:2", "bob:1"};Explication
alice suit news et sports, elle reçoit donc les deux événements ; bob ne reçoit que sports ; personne ne suit weather : ["alice:2", "bob:1"].
Entrée :
events = []
subscriptions = ["zoe tech", "zoe tech"]
Sortie attendue :
expected = ["zoe:0"]Entrée :
std::vector<std::string> events = {};
std::vector<std::string> subscriptions = {"zoe tech", "zoe tech"};
Sortie attendue :
std::vector<std::string> expected = {"zoe:0"};Entrée :
string[] events = new string[] {};
string[] subscriptions = new string[] {"zoe tech", "zoe tech"};
Sortie attendue :
string[] expected = new string[] {"zoe:0"};Explication
L'abonnement répété ne compte qu'une fois et aucun événement n'a été publié : ["zoe:0"].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Groupez les abonnés par sujet pour que chaque événement trouve vite son public.
Indice 2
Utilisez un ensemble par sujet pour qu'un abonnement répété ne compte qu'une fois.
Indice 3
Toute personne abonnée apparaît dans le résultat, même avec zéro notification.
Complexité attendue
temps O(abonnements + événements × abonnés par sujet), espace supplémentaire O(abonnements)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.