Đề bài
Mẫu observer cho phép các đối tượng đăng ký theo dõi một chủ thể và được thông báo mỗi khi có chuyện xảy ra. Ở đây, mọi người đăng ký các chủ đề và mỗi sự kiện được phát sẽ tới tất cả những ai đăng ký chủ đề của nó.
Mỗi lượt đăng ký có dạng <person> <topic>. Đăng ký lặp lại không có thêm tác dụng. Sau đó, mỗi sự kiện trong events là một tên chủ đề: mọi người đăng ký chủ đề đó nhận một thông báo. Sự kiện thuộc chủ đề không ai theo dõi sẽ bị bỏ qua.
Hãy viết event_subscribers(subscriptions, events).
Đầu vào
subscriptions: Các chuỗi "<person> <topic>" (tên không chứa khoảng trắng).
events: Tên các chủ đề, theo thứ tự phát.
Đầu ra
Trả về "<person>:<count>" cho mỗi người có ít nhất một lượt đăng ký, sắp xếp theo tên (thứ tự ký tự ordinal).
Ràng buộc
1 ≤ số lượt đăng ký ≤ 10,000
0 ≤ số sự kiện ≤ 100,000
Ví dụ
Đầu vào:
events = ["news", "sports", "weather"]
subscriptions = ["bob sports", "alice news", "alice sports"]
Kết quả mong đợi:
expected = ["alice:2", "bob:1"]Đầu vào:
std::vector<std::string> events = {"news", "sports", "weather"};
std::vector<std::string> subscriptions = {"bob sports", "alice news", "alice sports"};
Kết quả mong đợi:
std::vector<std::string> expected = {"alice:2", "bob:1"};Đầu vào:
string[] events = new string[] {"news", "sports", "weather"};
string[] subscriptions = new string[] {"bob sports", "alice news", "alice sports"};
Kết quả mong đợi:
string[] expected = new string[] {"alice:2", "bob:1"};Giải thích
alice theo dõi news và sports nên nhận cả hai sự kiện; bob chỉ nhận sports; không ai theo dõi weather: ["alice:2", "bob:1"].
Đầu vào:
events = []
subscriptions = ["zoe tech", "zoe tech"]
Kết quả mong đợi:
expected = ["zoe:0"]Đầu vào:
std::vector<std::string> events = {};
std::vector<std::string> subscriptions = {"zoe tech", "zoe tech"};
Kết quả mong đợi:
std::vector<std::string> expected = {"zoe:0"};Đầu vào:
string[] events = new string[] {};
string[] subscriptions = new string[] {"zoe tech", "zoe tech"};
Kết quả mong đợi:
string[] expected = new string[] {"zoe:0"};Giải thích
Lượt đăng ký lặp lại chỉ tính một lần và không có sự kiện nào được phát: ["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
Nhóm người đăng ký theo chủ đề để mỗi sự kiện tìm đúng người nhận nhanh.
Gợi ý 2
Dùng một set cho mỗi chủ đề để đăng ký lặp lại chỉ tính một lần.
Gợi ý 3
Mọi người đã đăng ký đều có trong kết quả, kể cả khi nhận 0 thông báo.
Độ phức tạp mong đợi
thời gian O(số đăng ký + số sự kiện × số người theo dõi mỗi chủ đề), bộ nhớ phụ O(số đăng ký)
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.