News Notification

Darin
plain_text
2 months ago
14 kB
Indexable
Never
package NewsNotification;

// Kim Đức
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;

class UserSolution {
	// Tạo Map để truy xuất đối tượng dễ dàng từ keyword (thông thường là String hoặc ID)
	// map id channel -> đối tượng Channel
	Map<Integer, Channel> mapChannel = new HashMap<>();
	// map id user -> đối tượng User
	Map<Integer, User> mapUser = new HashMap<>();
	// map id news -> đối tượng News
	Map<Integer, News> mapNews = new HashMap<>();

	// lưu danh sách notifications được gửi tới users, sắp xếp theo thời gian tăng dần ?
	// tại sao không sắp xếp giảm dần cho time và id ???
	Queue<News> heap = new PriorityQueue<>((a, b) -> a.time - b.time);

	void init(int N, int K) {
		mapChannel.clear();
		mapUser.clear();
		mapNews.clear();
		heap.clear();
	}

	void registerUser(int mTime, int mUID, int mNum, int mChannelIDs[]) {
		User user = mapUser.computeIfAbsent(mUID, k -> new User());
		for (int i = 0; i < mNum; i++) {
			Channel channel = mapChannel.computeIfAbsent(mChannelIDs[i],
					k -> new Channel());
			channel.users.put(mUID, mTime);
			user.channels.add(channel);
		}
	}

	// return the number of registered mapUser of mapNews channel mChannelID
	int offerNews(int mTime, int mNewsID, int mDelay, int mChannelID) {
		News noti = new News(mTime + mDelay, mNewsID, mChannelID);
		mapNews.put(mNewsID, noti);
		heap.add(noti);
		return mapChannel.get(mChannelID).users.size();
	}

	//If a news article is canceled, the provided article is deleted. If an article is deleted before notifications are given, the news channel does not send notifications.
	//If the article is deleted after notifications are given, the notifications users received are deleted immediately.
	//In other words, if a news article is provided at the time of mTime and the article is deleted before the time of (mTime + mDelay), news notifications are not given.
	//If the article is deleted after or at the time of (mTime + mDelay), the news notifications users received are deleted as well.
	// khi xóa một news, chắc chắn channel sẽ xóa article này
	// nếu article chưa được gửi tới người dùng (lưu trong hệ thống notifications heap) thì hiển nhiên heap không có đối tượng này
	// nếu articel đã được gửi thì xóa cả notification đó khỏi hệ thống
	// --> chốt lại là đằng nào cũng xóa 
	// --> không cần quan tâm time release, mà gộp luôn thành noti time = release time + delay time
	void cancelNews(int mTime, int mNewsID) {
		News article = mapNews.get(mNewsID);
		Channel channel = mapChannel.get(article.channelID);
		// xóa khỏi channel và hệ thống notifications
		channel.news.remove(article);
		heap.remove(article);
		// có thể xóa thêm ở mapNews, nhưng không cần thiết
	}

	// hàm này có 2 nhiệm vụ riêng biệt:
	// 1. trả về số các noti mà user mUID nhận trước hoặc vào mTime (không tính các article bị xóa)
	// 2. lưu 3 articles mới nhất mà user mUID nhận, theo quy tắc
	//	In the case where the user mUID received 2 or more notifications at the same time, the news article with the higher ID number is the latest article.
	//	If the number of notifications received is less than or equal to 2, save only the ID of the received mapNews article in the order in which the latest one is saved first.
	int checkUser(int mTime, int mUID, int mRetIDs[]) {
		// lấy ra tất cả các noti có time <= mTime trong DB
		// thêm nó vào channel.news của chính nó
		while (!heap.isEmpty() && heap.peek().time <= mTime) {
			News noti = heap.poll();
			Channel channel = mapChannel.get(noti.channelID);
			channel.news.add(noti);
			// ??? tại sao phải add vào treeSet news trong khi nó đã có sẵn trong đây
			// đây là một sự nhầm lẫn, thực ra treeSet news trong đối tượng channel chưa hề được thêm article khi nó được thêm 
			// trong method offerNews, nó chỉ bị xóa khỏi channel ở cancelNews thôi

			// khi được thêm vào channel.news, nó sẽ được xếp theo thứ tự giảm dần của time và ID
		}
		int total = 0; // tổng số noti nhận được trước và bằng mTime
		TreeSet<News> top3 = new TreeSet<>((a, b) -> a.time == b.time ? b.id
				- a.id : b.time - a.time);
		for (Channel channel : mapUser.get(mUID).channels) {
			int registerTime = channel.users.get(mUID);
			// trả về danh sách noti mà user mUID nhận sau khi đăng ký kênh
			// do channel.news là một treeSet sắp xếp giảm dần theo time và ID nên dùng headSet
			// tại sao không phải News(registerTime, -1, -1)
			Set<News> noticed = channel.news.headSet(new News(registerTime + 1,
					-1, -1));
			total += noticed.size();
			int cnt = 0;
			for (News news : noticed) {
				if (cnt++ == 3) // ++cnt là sai
					break;
				if (top3.add(news) && top3.size() > 3)
					top3.pollLast(); // vứt bớt thằng nhỏ nhất cả về time và id
			}

			// After calling the function, all notifications the user mUID received are deleted. As a result, the number of notifications becomes 0.
			// sau khi gọi function này thì mọi noti user nhận đều bị xóa --> mẹo ở đây là ta cập nhật registerTime của user với mọi channel mà nó đăng ký
			// lưu trong channel.users
			channel.users.put(mUID, mTime);
		}
		int i = 0;
		for (News news : top3)
			mRetIDs[i++] = news.id;
		return total;
	}
}

// User, có ID, đăng ký nhiều channel, mỗi channel có 1 ID
// mỗi channel có nhiều mapNews, mối mapNews có 1 ID
// có mqh user -> channels --> trong đối tượng User cần List các channels
class User {
	List<Channel> channels = new ArrayList<>();
}

// có mqh channel -> user --> trong đối tượng Channel cần List các users
// tuy nhiên khi User đăng ký, có 1 thông tin quan trọng kèm theo là thời gian đăng ký ???
// ArrayList không phù hợp --> HashMap
class Channel {
	// Danh sách users: map id user -> thời gian user đăng ký
	Map<Integer, Integer> users = new HashMap<>(); // ? 

	// tại sao phải dùng treeSet để lưu news ??? dùng arrayList không được sao ???
	// hỗ trợ cho phương thức checkUser
	// đây là chỗ lưu news của Channel nhưng thực ra không phải cứ khi thêm news thì treeSet này được gọi để add
	// treeSet này chỉ được gọi khi remove và hỗ trợ method checkUser
	TreeSet<News> news = new TreeSet<>((a, b) -> a.time == b.time ? b.id - a.id
			: b.time - a.time);
}

class News {
	int time, id, channelID;

	News(int mTime, int mID, int mChannelID) {
		time = mTime; // thời gian news được cung cấp cho user / tức time này là noti time = release time + delay time
		id = mID;
		channelID = mChannelID;
	}
}

//[Problem Description]
//Several news channels provide news notification services to registered users.
//If a user registers for the notification service of a news channel, the user receives news notifications whenever a news article is provided to the news channel.
//The news channel provided with a news article gives news notifications to registered users after the delayed time of mDelay.
//In other words, if a news channel was provided with a news article at the time of mTime, the news channel gives news notifications to registered users at the time of (mTime + mDelay).
//The delayed time of mDelay may differ by news article.
//If a news article is canceled, the provided article is deleted. If an article is deleted before notifications are given, the news channel does not send notifications.
//If the article is deleted after notifications are given, the notifications users received are deleted immediately.
//In other words, if a news article is provided at the time of mTime and the article is deleted before the time of (mTime + mDelay), news notifications are not given.
//If the article is deleted after or at the time of (mTime + mDelay), the news notifications users received are deleted as well.
//News notifications have the following functions.
//  1) Register user : A user registers for news notification services provided by news channels.
//  2) Provide news : A news article is provided to a news channel. The news channel gives notifications to registered users when time passes as much as the delayed time of mDelay from the time the article was provided.
// 3) Cancel news : The article is deleted. The article provided to the news channel is deleted. If notifications about this article are already-given ones, the given notifications are deleted as well.
// 4) Check user : Check what the article is about and the number of notifications a user received.
//Given the information about news channels and user registration, you are required to write a program that checks the notifications users received.
//Implement each required function by referring to the following API description.
//The following is the description of API to be written in the User Code.
//
//void init(int N, int K)
//This function is called in the beginning of each test case.
//There are a total of N users and K news channels providing news notification services.
//Currently, the time is 0, and no articles are provided.
// 
//Parameters
//  N : the number of users receiving news notifications ( 1 ≤ N ≤ 500 )
//  K : the number of news channels giving news notifications ( 1 ≤ K ≤ 500 )
//void registerUser(int mTime, int mUID, int mNum, int mChannelIDs[])
//At the time of mTime, user mUID registers with each of a total of mNum news channels mChannelIDs[] to receive news notifications.
//If there are notifications given to users at the time of mTime, register the user mUID with the news channels after sending the notification.
//All news channels mChannelIDs[] are different.
//The same mUID may be called several times. However, for the same user, news channels are never the same.
//As in the example below, when user 11 was called again, different news channels were called.
//registerUser(1, 11, 2, {111, 222})
//registerUser(25, 11, 3, {444, 333, 555})
//Parameters
//  mTime       : the current time ( 1 ≤ mTime ≤ 1,000,000,000 )
//  mUID        : the user ID ( 1 ≤ mUID ≤ 1,000,000,000 )
//  mNum       : the number of news channels the user registered with ( 1 ≤ mNum ≤ 30 )
//  mChannelIDs[] : the ID of the news channels the user registered with ( 1 ≤ mChannelIDs[] value ≤ 1,000,000,000 )
//int offerNews(int mTime, int mNewsID, int mDelay, int mChannelID)
//At the time of mTime, a news article mNewsID with the delayed time of mDelay is provided to the news channel mChannelID, and return the number of users registered for the notification service of the news channel mChannelID.
//The news channel mChannelID gives the news notification mNewsID to registered users at the time of (mTime + mDelay).
//It is guaranteed that there are one or more users who registered for the notification service of the news channel mChannelID.
//The same mNewsID is never called again.
//Parameters
//  mTime : the current time ( 1 ≤ mTime ≤ 1,000,000,000 )
//  mNewsID : the ID of the news article (1 ≤ mNewsID ≤ 1,000,000,000 )
//  mDelay : the delayed time of the news article ( 1 ≤ mDelay ≤ 10,000 )
//  mChannelID : the ID of the news channel provided with the article ( 1 ≤ mChannelID ≤ 1,000,000,000 )
//Returns
//  The number of registered users of news channel mChannelID
//void cancelNews(int mTime, int mNewsID)
//At the time of mTime, the news article mNewsID is canceled, so it is deleted.
//If notifications about the news article mNewsID are sent to users, the news notification mNewsID that users have must be deleted as well.
//The news article mNewsID is provided by offerNews().
//The news article mNewsID may be a deleted one as it may have been canceled beforehand.
//Parameters
//  mTime   : the current time ( 1 ≤ mTime ≤ 1,000,000,000 )
//  mNewsID : the ID of the news article to be canceled (1 ≤ mNewsID ≤ 1,000,000,000 )
//int checkUser(int mTime, int mUID, int mRetIDs[])
//Return the number of notifications that user mUID received at the time of mTime, and save the IDs of the news articles given to user mUID on a maximum of 3 mRetIDs[] with the latest one saved first. Exclude notifications about deleted news articles.
//If there are notifications being sent to users at the time of mTime, after sending notifications, return the number of notifications the users received.
//After calling the function, all notifications the user mUID received are deleted. As a result, the number of notifications becomes 0.
//In the case where the user mUID received 2 or more notifications at the same time, the news article with the higher ID number is the latest article.
//If the number of notifications received is less than or equal to 2, save only the ID of the received news article in the order in which the latest one is saved first.
//Return 0 if user mUID received no notifications.
//It is guaranteed that user mUID is a user who registered for news notification services. 
//Parameters
//  mTime   : the current time ( 1 ≤ mTime ≤ 1,000,000,000 )
//  mUID    : the ID of the user who checks notifications ( 1 ≤ mUID ≤ 1,000,000,000 )
//  mRetIDs[] : the place where the IDs of received news articles are saved in the order in which the latest one is saved first
// 
//Returns
//  the number of news notifications user mUID received (excluding notifications of deleted articles)