News Notification (Solution 2)
Darin
plain_text
a year ago
22 kB
2
Indexable
package NewsNotification;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
// Kim Đức
// Cải tiến cách làm của DTT
// trong class User sẽ tạo một TreeSet để lưu các noti mà user đó nhận
// trong hàm offerNews và cancelNews, thêm noti và treeSet của đối tượng user
// nhưng khó khăn ở đây là trong offerNews không có user ID
// nếu ta lấy các user ids qua channel ids để thêm noti vào cũng ok
// nhưng lại có khó khăn là registerTime khác nhau, sẽ có noti có trước registerTime
// nhưng vẫn được thêm vào treeSet của user
// thay vì dùng heap, lưu ngay news vào treeSet của Channel
class UserSolution3 {
Map<Integer, Channel> mapChannel = new HashMap<>();
Map<Integer, User> mapUser = new HashMap<>();
Map<Integer, News> mapNews = new HashMap<>();
// 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);
}
}
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);
Channel channel = mapChannel.get(mChannelID);
channel.news.add(noti);
return mapChannel.get(mChannelID).users.size();
}
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
}
int checkUser(int mTime, int mUID, int mRetIDs[]) {
// cần lọc ra từ channel.news các news có time <= mTime
// nhưng muốn lọc thì phải có đối tượng channel -> cần channelID ->
// cần lấy channelID trong vòng for, từ danh sách channel của user mUID
int total = 0;
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);
// lấy hết các news có mTime, mà treeSet này lại sắp xếp giảm dần (theo id và time), nên muốn lấy được hết cần
// set 2 thuộc tính id và channelID của đối tượng News thật cao
SortedSet<News> filter = channel.news.tailSet(new News(mTime,
Integer.MAX_VALUE, Integer.MAX_VALUE));
Set<News> noticed1 = filter.headSet(new News(registerTime,
Integer.MAX_VALUE, Integer.MAX_VALUE));
// Set<News> noticed = filter.headSet(new News(registerTime + 1, -1,
// -1)); // mảng này lưu mọi News mà user mUID nhận được từ channel do căn mốc thời gian từ registerTime -> mTime
total += noticed1.size();
int cnt = 0;
for (News news : noticed1) {
if (cnt++ == 3)
break;
if (top3.add(news) && top3.size() > 3)
top3.pollLast();
}
channel.users.put(mUID, mTime);
}
int i = 0;
for (News news : top3)
mRetIDs[i++] = news.id;
return total;
}
class User {
List<Channel> channels = new ArrayList<>();
}
class Channel {
Map<Integer, Integer> users = new HashMap<>();
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;
id = mID;
channelID = mChannelID;
}
}
}
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 users of news channel mChannelID
// đưa news vào channel
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);
// có thể thêm vào channel -> sai vì channel.news được sử dụng không phải để lưu tất cả noti --> xem checkUser
// Channel channel = mapChannel.get(mChannelID);
// channel.news.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(); // tại sao xóa, nếu cần dùng sau này thì sao?
// mục đích là chuyển sang treeSet của channel.news, do đó xóa cũng ok
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
// vào cùng một thời điểm, một channel có thể nhận được nhiều news --> điều này đã không được nhắc tới trong đề bài
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)
package NewsNotification;
// Vũ Hà Thanh
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class UserSolution2 {
private PriorityQueue<News> pendingNews;
private HashMap<Integer, News> news;
private HashMap<Integer, User> users;
private HashMap<Integer, Channel> channels;
public void init(int n, int k) {
pendingNews = new PriorityQueue<>();
news = new HashMap<>();
users = new HashMap<>();
channels = new HashMap<>();
}
private void update(int time) {
while (!pendingNews.isEmpty()) {
News news = pendingNews.peek();
if (news.time > time)
break;
pendingNews.poll();
if (!news.removed) {
news.index = news.channel.publishedNews.size();
news.channel.publishedNews.add(news);
}
}
}
public void registerUser(int time, int uid, int num, int[] gids) {
update(time);
User user = users.computeIfAbsent(uid, k -> new User());
for (int i = 0; i < num; ++i) {
Channel channel = channels.computeIfAbsent(gids[i],
k -> new Channel());
channel.users.add(user);
user.channels.put(channel, channel.publishedNews.size());
}
}
public void cancelNews(int time, int nid) {
update(time);
News news = this.news.get(nid);
if (news == null || news.removed)
return;
news.removed = true;
if (news.time <= time) {
Channel channel = news.channel;
for (User user : channel.users) {
int limit = user.channels.get(channel);
if (news.index >= limit) {
++user.removed;
}
}
}
}
public int offerNews(int time, int nid, int delay, int gid) {
update(time);
Channel channel = channels.computeIfAbsent(gid, k -> new Channel());
News news = new News(nid, time + delay, channel);
pendingNews.add(news);
this.news.put(nid, news);
return channel.users.size();
}
public int checkUser(int time, int uid, int[] retids) {
update(time);
User user = users.get(uid);
int result = -user.removed;
user.removed = 0;
PriorityQueue<News> queue = new PriorityQueue<>();
for (Map.Entry<Channel, Integer> entry : user.channels.entrySet()) {
Channel channel = entry.getKey();
int limit = entry.getValue();
result += channel.publishedNews.size() - limit;
int x = 0;
for (int i = channel.publishedNews.size() - 1; i >= limit && x != 3; --i) {
News news = channel.publishedNews.get(i);
if (news.removed)
continue;
++x;
queue.add(news);
if (queue.size() > 3 && queue.poll() == news)
break;
}
entry.setValue(channel.publishedNews.size());
}
while (!queue.isEmpty()) {
retids[queue.size() - 1] = queue.poll().id;
}
return result;
}
private static class User {
public HashMap<Channel, Integer> channels = new HashMap<>();
public int removed = 0;
}
private static class Channel {
public ArrayList<News> publishedNews = new ArrayList<>();
public ArrayList<User> users = new ArrayList<>();
}
private static class News implements Comparable<News> {
public int id;
public int time;
public int index;
public boolean removed;
public Channel channel;
public News(int id, int time, Channel channel) {
this.id = id;
this.time = time;
this.channel = channel;
}
@Override
public int compareTo(News o) {
return time == o.time ? id - o.id : time - o.time;
}
}
}