Problem
Das Observer-Muster lässt Objekte ein Subjekt abonnieren und benachrichtigt sie, sobald etwas passiert. Hier abonnieren Personen Themen, und jedes veröffentlichte Event geht an alle Abonnenten seines Themas.
Jedes Abonnement hat die Form <person> <topic>. Ein wiederholtes Abonnement hat keine zusätzliche Wirkung. Danach ist jedes Event in events ein Themenname: Jeder Abonnent dieses Themas erhält eine Benachrichtigung. Events zu Themen, denen niemand folgt, werden verworfen.
Implementiere event_subscribers(subscriptions, events).
Eingabe
subscriptions: Strings der Form "<person> <topic>" (Namen ohne Leerzeichen).
events: Themennamen in der Reihenfolge der Veröffentlichung.
Ausgabe
Gib "<person>:<count>" für jede Person mit mindestens einem Abonnement zurück, sortiert nach Namen (ordinale Zeichenreihenfolge).
Einschränkungen
1 ≤ Anzahl der Abonnements ≤ 10,000
0 ≤ Anzahl der Events ≤ 100,000
Beispiele
Eingabe:
events = ["news", "sports", "weather"]
subscriptions = ["bob sports", "alice news", "alice sports"]
Erwartete Ausgabe:
expected = ["alice:2", "bob:1"]Eingabe:
std::vector<std::string> events = {"news", "sports", "weather"};
std::vector<std::string> subscriptions = {"bob sports", "alice news", "alice sports"};
Erwartete Ausgabe:
std::vector<std::string> expected = {"alice:2", "bob:1"};Eingabe:
string[] events = new string[] {"news", "sports", "weather"};
string[] subscriptions = new string[] {"bob sports", "alice news", "alice sports"};
Erwartete Ausgabe:
string[] expected = new string[] {"alice:2", "bob:1"};Erläuterung
alice folgt news und sports und erhält daher beide Events; bob erhält nur sports; weather folgt niemand: ["alice:2", "bob:1"].
Eingabe:
events = []
subscriptions = ["zoe tech", "zoe tech"]
Erwartete Ausgabe:
expected = ["zoe:0"]Eingabe:
std::vector<std::string> events = {};
std::vector<std::string> subscriptions = {"zoe tech", "zoe tech"};
Erwartete Ausgabe:
std::vector<std::string> expected = {"zoe:0"};Eingabe:
string[] events = new string[] {};
string[] subscriptions = new string[] {"zoe tech", "zoe tech"};
Erwartete Ausgabe:
string[] expected = new string[] {"zoe:0"};Erläuterung
Das wiederholte Abonnement zählt einmal, und es wurden keine Events veröffentlicht: ["zoe:0"].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Gruppiere Abonnenten nach Thema, damit jedes Event sein Publikum schnell findet.
Hinweis 2
Nutze pro Thema ein Set, damit ein wiederholtes Abonnement nur einmal zählt.
Hinweis 3
Jeder, der etwas abonniert hat, steht im Ergebnis, auch mit null Benachrichtigungen.
Erwartete Komplexität
Zeit O(Abonnements + Events × Abonnenten pro Thema), zusätzlicher Speicher O(Abonnements)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.