Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Event Subscribers

Deliver events to the subscribers of each topic, observer style, and count what everyone receives.

Bạn sẽ học được gì

  • Map topics to the people who follow them
  • Notify every subscriber of an event
  • Ignore duplicate subscriptions with a set

Đề bài

Xem bản dịch

The observer pattern lets objects subscribe to a subject and get notified whenever something happens. Here, people subscribe to topics and every published event goes to everyone subscribed to its topic.

Each subscription is <person> <topic>. A repeated subscription has no extra effect. Then each event in events is a topic name: every subscriber of that topic receives one notification. Events on topics nobody follows are dropped.

Implement event_subscribers(subscriptions, events).

Input

subscriptions: "<person> <topic>" strings (names have no spaces).

events: Topic names, in publishing order.

Output

Return "<person>:<count>" for every person who has at least one subscription, sorted by name (ordinal character order).

Ràng buộc

1 ≤ number of subscriptions ≤ 10,000

0 ≤ number of events ≤ 100,000

Ví dụ

Ví dụ 1
Đầu vào:
subscriptions = ["bob sports", "alice news", "alice sports"]
events = ["news", "sports", "weather"]

Kết quả mong đợi:
expected = ["alice:2", "bob:1"]
Đầu vào:
std::vector<std::string> subscriptions = {"bob sports", "alice news", "alice sports"};
std::vector<std::string> events = {"news", "sports", "weather"};

Kết quả mong đợi:
std::vector<std::string> expected = {"alice:2", "bob:1"};
Đầu vào:
string[] subscriptions = new string[] {"bob sports", "alice news", "alice sports"};
string[] events = new string[] {"news", "sports", "weather"};

Kết quả mong đợi:
string[] expected = new string[] {"alice:2", "bob:1"};

Giải thích

alice follows news and sports, so she gets both events; bob only gets sports; nobody follows weather: ["alice:2", "bob:1"].

Ví dụ 2
Đầu vào:
subscriptions = ["zoe tech", "zoe tech"]
events = []

Kết quả mong đợi:
expected = ["zoe:0"]
Đầu vào:
std::vector<std::string> subscriptions = {"zoe tech", "zoe tech"};
std::vector<std::string> events = {};

Kết quả mong đợi:
std::vector<std::string> expected = {"zoe:0"};
Đầu vào:
string[] subscriptions = new string[] {"zoe tech", "zoe tech"};
string[] events = new string[] {};

Kết quả mong đợi:
string[] expected = new string[] {"zoe:0"};

Giải thích

The repeated subscription counts once, and no events were published: ["zoe:0"].

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Group subscribers by topic so each event finds its audience quickly.

Gợi ý 2

Use a set per topic so a repeated subscription counts once.

Gợi ý 3

Everyone who subscribed appears in the result, even with zero notifications.

Độ phức tạp mong đợi

O(subscriptions + events × subscribers per topic) time, O(subscriptions) extra space

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.