Dare2Solve
The problem involves simulating a simple version of Twitter where users can post tweets, follow and unfollow other users, and retrieve the 10 most recent tweets from the users they follow. We need to implement three core functionalities:
The key intuition here is that we can use a data structure (a heap) to efficiently retrieve the 10 most recent tweets. Each user will have their own tweet list, and we can merge the tweets of all followed users and the user themselves to generate the news feed. We also need to manage the follow relationships between users, which can be stored in a map of sets.
O(U + T), where U is the number of users and T is the total number of tweets.
class Tweet {
public:
int tweetId;
int userId;
int created;
Tweet(int tweetId, int userId, int created)
: tweetId(tweetId), userId(userId), created(created) {}
};
class MaxHeap {
struct Compare {
bool operator()(Tweet& a, Tweet& b) {
return a.created < b.created;
}
};
std::priority_queue<Tweet, std::vector<Tweet>, Compare> heap;
public:
void add(const Tweet& tweet) {
heap.push(tweet);
}
Tweet remove() {
Tweet top = heap.top();
heap.pop();
return top;
}
bool empty() const {
return heap.empty();
}
};
class Twitter {
std::unordered_map<int, std::vector<Tweet>> tweetMap;
std::unordered_map<int, std::unordered_set<int>> followMap;
int timestamp;
public:
Twitter() : timestamp(0) {}
void postTweet(int userId, int tweetId) {
tweetMap[userId].push_back(Tweet(tweetId, userId, timestamp++));
}
std::vector<int> getNewsFeed(int userId) {
MaxHeap maxHeap;
std::vector<int> result;
auto followList = followMap[userId];
followList.insert(userId);
for (int followeeId : followList) {
if (tweetMap.count(followeeId)) {
for (const Tweet& tweet : tweetMap[followeeId]) {
maxHeap.add(tweet);
}
}
}
for (int i = 0; i < 10 && !maxHeap.empty(); ++i) {
result.push_back(maxHeap.remove().tweetId);
}
return result;
}
void follow(int followerId, int followeeId) {
followMap[followerId].insert(followeeId);
}
void unfollow(int followerId, int followeeId) {
followMap[followerId].erase(followeeId);
}
};
class Tweet:
def __init__(self, tweetId, userId, created):
self.tweetId = tweetId
self.userId = userId
self.created = created
def __lt__(self, other):
return self.created > other.created
class MaxHeap:
def __init__(self):
self.heap = []
def add(self, tweet):
heappush(self.heap, tweet)
def remove(self):
return heappop(self.heap)
def is_empty(self):
return len(self.heap) == 0
class Twitter:
def __init__(self):
self.tweetMap = {}
self.followMap = {}
self.timestamp = 0
def postTweet(self, userId, tweetId):
tweet = Tweet(tweetId, userId, self.timestamp)
self.timestamp += 1
if userId not in self.tweetMap:
self.tweetMap[userId] = []
self.tweetMap[userId].append(tweet)
def getNewsFeed(self, userId):
max_heap = MaxHeap()
followList = self.followMap.get(userId, set())
followList.add(userId)
for followeeId in followList:
if followeeId in self.tweetMap:
for tweet in self.tweetMap[followeeId]:
max_heap.add(tweet)
feed = []
for _ in range(10):
if max_heap.is_empty():
break
feed.append(max_heap.remove().tweetId)
return feed
def follow(self, followerId, followeeId):
if followerId not in self.followMap:
self.followMap[followerId] = set()
self.followMap[followerId].add(followeeId)
def unfollow(self, followerId, followeeId):
if followerId in self.followMap:
self.followMap[followerId].discard(followeeId)
class Tweet {
int tweetId;
int userId;
int created;
public Tweet(int tweetId, int userId, int created) {
this.tweetId = tweetId;
this.userId = userId;
this.created = created;
}
}
class MaxHeap {
PriorityQueue<Tweet> heap;
public MaxHeap() {
heap = new PriorityQueue<>((a, b) -> b.created - a.created);
}
public void add(Tweet tweet) {
heap.offer(tweet);
}
public Tweet remove() {
return heap.poll();
}
public boolean isEmpty() {
return heap.isEmpty();
}
}
class Twitter {
private Map<Integer, List<Tweet>> tweetMap;
private Map<Integer, Set<Integer>> followMap;
private int timestamp;
public Twitter() {
tweetMap = new HashMap<>();
followMap = new HashMap<>();
timestamp = 0;
}
public void postTweet(int userId, int tweetId) {
tweetMap.computeIfAbsent(userId, k -> new ArrayList<>()).add(new Tweet(tweetId, userId, timestamp++));
}
public List<Integer> getNewsFeed(int userId) {
MaxHeap maxHeap = new MaxHeap();
Set<Integer> followList = followMap.getOrDefault(userId, new HashSet<>());
followList.add(userId);
for (int followeeId : followList) {
if (tweetMap.containsKey(followeeId)) {
for (Tweet tweet : tweetMap.get(followeeId)) {
maxHeap.add(tweet);
}
}
}
List<Integer> feed = new ArrayList<>();
for (int i = 0; i < 10 && !maxHeap.isEmpty(); i++) {
feed.add(maxHeap.remove().tweetId);
}
return feed;
}
public void follow(int followerId, int followeeId) {
followMap.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
if (followMap.containsKey(followerId)) {
followMap.get(followerId).remove(followeeId);
}
}
}
/**
* @param {number} followerId
* @param {number} followeeId
* @return {void}
*/
class Tweet {
constructor(tweetId, userId, created) {
this.created = created;
this.tweetId = tweetId;
this.userId = userId;
}
}
/**
* @param {number} followerId
* @param {number} followeeId
* @return {void}
*/
class MaxHeap {
constructor() {
this.heap = [];
}
add(val) {
this.heap.push(val);
this.heap.sort((a, b) => a.created - b.created);
}
peek() {
return this.heap[this.heap.length - 1];
}
remove() {
return this.heap.pop();
}
}
class Twitter {
constructor() {
this.tweetMap = new Map();
this.followMap = new Map();
this.timestamp = 0;
}
postTweet(userId, tweetId) {
const newTweet = new Tweet(tweetId, userId, this.timestamp);
const list = this.tweetMap.get(userId) || [];
list.push(newTweet);
this.tweetMap.set(userId, list);
this.timestamp++;
}
getNewsFeed(userId) {
const list = this.followMap.get(userId) || [];
const followerList = [...list, userId];
const maxHeap = new MaxHeap();
followerList.forEach((id) => {
if (this.tweetMap.get(id)) { // Get tweets posted by id
this.tweetMap.get(id).forEach(item => maxHeap.add(item));
}
});
const feed = [];
for (let i = 0; i < 10 && maxHeap.heap.length > 0; i++) {
feed.push(maxHeap.remove().tweetId);
}
return feed;
}
follow(followerId, followeeId) {
const set = this.followMap.get(followerId) || new Set();
set.add(followeeId);
this.followMap.set(followerId, set);
}
unfollow(followerId, followeeId) {
const set = this.followMap.get(followerId);
if (set && set.has(followeeId)) {
set.delete(followeeId);
this.followMap.set(followerId, set);
}
}
}