Problema
Il pattern observer permette agli oggetti di iscriversi a un soggetto e di ricevere una notifica ogni volta che succede qualcosa. Qui le persone si iscrivono ad argomenti e ogni evento pubblicato arriva a tutti gli iscritti del suo argomento.
Ogni iscrizione è <person> <topic>. Un'iscrizione ripetuta non ha effetti aggiuntivi. Poi ogni evento in events è il nome di un argomento: ogni iscritto a quell'argomento riceve una notifica. Gli eventi su argomenti che nessuno segue vengono scartati.
Implementa event_subscribers(subscriptions, events).
Input
subscriptions: Stringhe "<person> <topic>" (i nomi non contengono spazi).
events: Nomi di argomenti, in ordine di pubblicazione.
Output
Restituisci "<person>:<count>" per ogni persona con almeno un'iscrizione, ordinate per nome (ordine ordinale dei caratteri).
Vincoli
1 ≤ numero di iscrizioni ≤ 10,000
0 ≤ numero di eventi ≤ 100,000
Esempi
Input:
events = ["news", "sports", "weather"]
subscriptions = ["bob sports", "alice news", "alice sports"]
Output atteso:
expected = ["alice:2", "bob:1"]Input:
std::vector<std::string> events = {"news", "sports", "weather"};
std::vector<std::string> subscriptions = {"bob sports", "alice news", "alice sports"};
Output atteso:
std::vector<std::string> expected = {"alice:2", "bob:1"};Input:
string[] events = new string[] {"news", "sports", "weather"};
string[] subscriptions = new string[] {"bob sports", "alice news", "alice sports"};
Output atteso:
string[] expected = new string[] {"alice:2", "bob:1"};Spiegazione
alice segue news e sports, quindi riceve entrambi gli eventi; bob riceve solo sports; nessuno segue weather: ["alice:2", "bob:1"].
Input:
events = []
subscriptions = ["zoe tech", "zoe tech"]
Output atteso:
expected = ["zoe:0"]Input:
std::vector<std::string> events = {};
std::vector<std::string> subscriptions = {"zoe tech", "zoe tech"};
Output atteso:
std::vector<std::string> expected = {"zoe:0"};Input:
string[] events = new string[] {};
string[] subscriptions = new string[] {"zoe tech", "zoe tech"};
Output atteso:
string[] expected = new string[] {"zoe:0"};Spiegazione
L'iscrizione ripetuta conta una volta sola e non è stato pubblicato alcun evento: ["zoe:0"].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Raggruppa gli iscritti per argomento così ogni evento trova subito il suo pubblico.
Suggerimento 2
Usa un set per argomento, così un'iscrizione ripetuta conta una volta sola.
Suggerimento 3
Chiunque si sia iscritto compare nel risultato, anche con zero notifiche.
Complessità attesa
tempo O(iscrizioni + eventi × iscritti per argomento), spazio aggiuntivo O(iscrizioni)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.