355. Design Twitter
2 hashMap(Map<Integer, List<Tweet>>, ) + list sort
T: O(mnlogmn)
S: O(mn)
class Twitter {
class Tweet {
int userId;
int tweetId;
int timestamp;
Tweet(int userId,
int tweetId,
int timestamp) {
this.userId = userId;
this.tweetId = tweetId;
this.timestamp = timestamp;
}
}
Map<Integer, List<Tweet>> postMap;
Map<Integer, Set<Integer>> followMap;
int timestamp = 0;
public Twitter() {
postMap = new HashMap<>();
followMap = new HashMap<>();
}
public void postTweet(int userId, int tweetId) {
postMap.putIfAbsent(userId, new ArrayList<>());
postMap.get(userId).add(new Tweet(userId, tweetId, timestamp++));
}
public List<Integer> getNewsFeed(int userId) {
List<Tweet> all = new ArrayList<>();
// PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.timestamp - a.timestamp);
for (int targetId : followMap.getOrDefault(userId, new HashSet<>())) {
for (Tweet tweet : postMap.getOrDefault(targetId, new ArrayList<>())) {
// pq.offer(tweet);
all.add(tweet);
}
}
for (Tweet tweet : postMap.getOrDefault(userId, new ArrayList<>())) {
// pq.offer(tweet);
all.add(tweet);
}
Collections.sort(all, (a, b) -> b.timestamp - a.timestamp);
List<Integer> result = new ArrayList<>();
// int n = 0;
// while (!pq.isEmpty() && n < 10) {
// result.add(pq.poll().tweetId);
// n++;
// }
int n = 0;
while (n < 10 && n < all.size()) {
result.add(all.get(n).tweetId);
n++;
}
return result;
}
public void follow(int followerId, int followeeId) { // follower follow followee
followMap.putIfAbsent(followerId, new HashSet<>());
followMap.get(followerId).add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
Set<Integer> set = followMap.getOrDefault(followerId, new HashSet<>());
if (set.contains(followeeId)) {
set.remove(followeeId);
}
}
}
/**
* Your Twitter object will be instantiated and called as such:
* Twitter obj = new Twitter();
* obj.postTweet(userId,tweetId);
* List<Integer> param_2 = obj.getNewsFeed(userId);
* obj.follow(followerId,followeeId);
* obj.unfollow(followerId,followeeId);
1. use 2 hashMap
Map<Integer, List<Tweet>> postMap;
use ArrayList save all tweets with timestamp, postTweet: O(1)
Map<Integer, Set<Integer>> followMap;
use set to save followee, in that way, unfollow is O(1)
follow is also O(1)
getNewsFeed()
use PQ, but needs to get all followee * tweets count
add all followee * tweets count: O(mn)
PQ: O(mnlogmn)
add all tweets into PQ to only add top 10 recent tweets to result
no difference comparing with just "sort" ...because I get all tweets here and add all into PQ
so actually this solution is using list, add all followee * tweets count, then sort
add all followee * tweets count: O(mn)
sort: O(mnlogmn)
*/hashMap(Map<Integer, User>) + User has tweet linkedlist, + PQ
getNewsFeed()
T: O(this user's followed count + 10)...actually I think it still need to add all..
T: postTweet, follow, unfollow: O(1)
S: O(user*followed + user* tweets count)class Twitter {
int timestamp = 0;
class Tweet {
private int tweetId;
private Tweet next;
private int timestamp;
Tweet(int tweetId,
int timestamp) {
this.tweetId = tweetId;
this.next = null;
this.timestamp = timestamp;
}
}
class User {
private int id;
private Tweet head;
private Set<Integer> followed;
User(int userId) {
this.id = userId;
this.head = null;
followed = new HashSet<>();
follow(userId); // follow yourself
}
public void follow(int userId) {
this.followed.add(userId);
}
public void unfollow(int userId) {
if (followed.contains(userId) && this.id != userId) { // 不可以取消關注自己
this.followed.remove(userId);
}
}
public void post(int tweetId, int timestamp) {
Tweet tweet = new Tweet(tweetId, timestamp);
tweet.next = head;
head = tweet;
}
}
private Map<Integer, User> postMap;
public Twitter() {
postMap = new HashMap<>();
}
public void postTweet(int userId, int tweetId) {
postMap.putIfAbsent(userId, new User(userId));
postMap.get(userId).post(tweetId, timestamp++);
}
public List<Integer> getNewsFeed(int userId) {
List<Integer> result = new ArrayList<>();
if (!postMap.containsKey(userId)) {
return result; // 根本沒這人
}
Set<Integer> followed = postMap.get(userId).followed;
PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.timestamp - a.timestamp);
for (int f : followed) {
User u = postMap.get(f);
if (u == null) {
continue;
}
Tweet head = u.head;
if (head == null) {
continue;
}
pq.offer(head);
}
while (!pq.isEmpty() && result.size() < 10) {
Tweet tweet = pq.poll();
result.add(tweet.tweetId);
if (tweet.next != null) {
pq.offer(tweet.next);
}
}
return result;
}
public void follow(int followerId, int followeeId) { // follower follow followee
postMap.putIfAbsent(followerId, new User(followerId));
postMap.get(followerId).follow(followeeId);
}
public void unfollow(int followerId, int followeeId) {
if (postMap.containsKey(followerId)){
postMap.get(followerId).unfollow(followeeId);
}
}
}
/**
* Your Twitter object will be instantiated and called as such:
* Twitter obj = new Twitter();
* obj.postTweet(userId,tweetId);
* List<Integer> param_2 = obj.getNewsFeed(userId);
* obj.follow(followerId,followeeId);
* obj.unfollow(followerId,followeeId);
getNewsFeed()
T: O(this user's followed count + 10)
T: postTweet, follow, unfollow: O(1)
S: O(user*followed + user* tweets count)
*/still use 2 map + pq, but stop earlier, this is faster
Runtime: 10 ms, faster than 97.95% of Java online submissions
pq change to use minHeap, 當遇到 timestmap 比 heap peek 大的, 就把那個小的丟掉, 放入大的
這樣可以提早結束
最後用 linkedlist addFirst 的技巧, 達到大的在前面的效果(因為 minHeap 事先排出來最小的..
class Twitter {
class Tweet {
int userId;
int tweetId;
int timestamp;
Tweet(int userId,
int tweetId,
int timestamp) {
this.userId = userId;
this.tweetId = tweetId;
this.timestamp = timestamp;
}
}
Map<Integer, List<Tweet>> postMap;
Map<Integer, Set<Integer>> followMap;
int timestamp = 0;
public Twitter() {
postMap = new HashMap<>();
followMap = new HashMap<>();
}
public void postTweet(int userId, int tweetId) {
postMap.putIfAbsent(userId, new ArrayList<>());
postMap.get(userId).add(new Tweet(userId, tweetId, timestamp++));
}
public List<Integer> getNewsFeed(int userId) {
PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> a.timestamp - b.timestamp);
LinkedList<Integer> result = new LinkedList<>();
for (int targetId : followMap.getOrDefault(userId, new HashSet<>())) {
for (Tweet tweet : postMap.getOrDefault(targetId, new ArrayList<>())) {
if (pq.size() < 10) {
pq.offer(tweet);
} else if (tweet.timestamp > pq.peek().timestamp) {
pq.poll();
pq.offer(tweet);
}
}
}
for (Tweet tweet : postMap.getOrDefault(userId, new ArrayList<>())) {
if (pq.size() < 10) {
pq.offer(tweet);
} else if (tweet.timestamp > pq.peek().timestamp) {
pq.poll();
pq.offer(tweet);
}
}
int n = 0;
while (!pq.isEmpty() && n < 10) {
result.addFirst(pq.poll().tweetId);
}
return result;
}
public void follow(int followerId, int followeeId) { // follower follow followee
followMap.putIfAbsent(followerId, new HashSet<>());
followMap.get(followerId).add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
Set<Integer> set = followMap.getOrDefault(followerId, new HashSet<>());
if (set.contains(followeeId)) {
set.remove(followeeId);
}
}
}Last updated