Design Twitter - Leetcode 355 - Python

0:00 - Read the problem
1:30 - Drawing Explanation
12:06 - Coding Explanation

leetcode 355

#design #twitter #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[NeetCode]

Recommend watching this one at 1.5x Speed!

[oooo-rcyf]

I've had nightmares about this one before. Thanks

[Dudu-nj]

I wouldn't wish this question on even my worst enemy in an interview

[blackda]

14:20 In python set, we can use `discard` to remove elements even if it is not in the set without throwing error. Think it will simplify the code a little bit.

[rishav]

My brain exploded while doing this question

[mwnkt]

I just started my software engineering journey a year ago and always thought data structures and algorithms were hard until I found your channel 3 days ago 😀, thanks for the simple explanations, and keep doing what you're doing.

[sikaydalapixia]

I think the reason that this is medium difficulty because it actually does not require priority queue to pass this question.
The solution that is O(N) is good enough for passing this problem.

[tvkrishna]

It would be more optimal to use a defaultdict(deque) for tweetMap since only the most recent 10 tweets from any user are relevant.

[samarthtandale]

This question is Brilliant! Its litterally the reason to get up in the morning from you bed, just to design code to such questions. I struggled a lot with this, and after seeing a couple of tutorials on this, I came up with my C++ design for the solution of this question: ->
struct Tweet
{
int id;
Tweet *next;
int timeStamp;
static int time;

Tweet(int tweetId, Tweet *nextTweet=nullptr) {
id=tweetId;
next=nextTweet;
timeStamp = time++;
}
};
int Tweet::time = 0;

struct TweetComparison
{
bool operator()(const Tweet *tweet1, const Tweet *tweet2) {
return tweet1->timeStamp < tweet2->timeStamp;
}
};

struct User
{
int id;
Tweet *tweetHead;
unordered_set<int> followeeIds;

User() {}

User(int userId) {
id=userId;
tweetHead=nullptr;
}

void follow(int userId) {
followeeIds.insert(userId);
}
void unfollow(int userId) {
followeeIds.erase(userId);
}

void post(int tweetId) {
tweetHead = new Tweet(tweetId, tweetHead);
}
vector<int> getRecentTweets(int count, const unordered_map<int, User> &userStore) const {
vector<int> recentTweets;

priority_queue<Tweet*, vector<Tweet*>, TweetComparison> heap;

for(auto itr=followeeIds.begin(); itr != followeeIds.end(); itr++)
{
const User *followee = &userStore.at(*itr);
if(followee->tweetHead != nullptr)

}
if(tweetHead)
heap.push(tweetHead);


for(int i=0; i<count && !heap.empty(); i++)
{
Tweet *curr = heap.top();
heap.pop();



if(curr->next)
heap.push(curr->next);
}

return recentTweets;
}

};


class Twitter {
public:
Twitter() {

}
void postTweet(int userId, int tweetId) {
if(userStore.find(userId) == userStore.end())


}
vector<int> getNewsFeed(int userId) {
if(userStore.find(userId) == userStore.end())
return {};
return userStore[userId].getRecentTweets(10, userStore);
}
void follow(int followerId, int followeeId) {
if(userStore.find(followerId) == userStore.end())

if(userStore.find(followeeId) == userStore.end())



}
void unfollow(int followerId, int followeeId) {

}

private:
unordered_map<int, User> userStore;
};

/**
* Your Twitter object will be instantiated and called as such:
* Twitter* obj = new Twitter();
* obj->postTweet(userId, tweetId);
* vector<int> param_2 = obj->getNewsFeed(userId);
* obj->follow(followerId, followeeId);
* obj->unfollow(followerId, followeeId);
*/

[mengzhugao]

I think what also makes it to be a hard question is that you have to check many conditions, like whether the followee has tweets, unfollow exception and whether the index is valid....

[shortHMl]

This was by far the best explaination I got for any problem...

[himabindu]

The amount of tiny little important things i learn from your videos (which i cant even put in words if i have to explain) that should be taken care of while solving problems is making me fall in love with dsa, everyday. Thank you so much.

[mada]

The tweets are already sorted
I just add them to a list and then do a reverse loop to get the result

[andrefreitas]

using a vector<pair<int, int>> to store the posts of all users, and then just iterating them in reverse until 10 posts are iterated is much ez, also better time complexity.
just need to check if the post is from the userId or the post is from somone whom posterId follows...
a lot of people over complicate this question, this is a medium...

[danielsun]

10:47, I don't understand why @neetcode say use 10logK for using heap. For my opinion, shouldn't the time complexity of heap is NlogN? Then it should be 10KlogK, why neetcode said find the min using logK times? Shouldn't it be KlogK times?

[leafhurricane]

This was really hard to understand @Neetcode because the DrawingExplanation part was spent mostly in discussing time complexity.

[strawberriesandcream]

i was able to solve this with just a list for tweets storing the userId and tweetId, and a hashmap for followers. i reverse looped the list of tweets to get the most recent tweets. it's a much simpler solution but takes more time.😅

[bodong]

Great video, but one small problem: You added UserId to the followMap. But in LeetCode, the last constraint says: "A user cannot follow himself."

[deewademai]

At 19:05, is that only adding one tweet per followee by far?

[ashelytang]

I'm able to figure out how to implement a dictionary of lists, but how do you implement a dictionary of sets?