Design Twitter - Leetcode 355 - Python
Vložit
- čas přidán 8. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Python Code: github.com/neetcode-gh/leetco...
Problem Link: neetcode.io/problems/design-t...
0:00 - Read the problem
1:30 - Drawing Explanation
12:06 - Coding Explanation
leetcode 355
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#design #twitter #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Recommend watching this one at 1.5x Speed!
Python Code: github.com/neetcode-gh/leetcode/blob/main/python/355-Design-Twitter.py
Java Code: github.com/neetcode-gh/leetcode/blob/main/java/355-Design-Twitter.java
any chance you could repost this? could be life savior :p
@@pedroduckz Updated the links, they should work now :)
@@NeetCode Hi there,
Sorry, newbie here.
I've tried to copy paste the code itself as is in your link, but it just won't work at all. Is it missing something?
I've had nightmares about this one before. Thanks
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.
If discard wont lead error usually, then why remove() exist? Is remove() faster than discard()? Then why does Python need to keep this built-in function which will lead an error?
@@danielsun716 docs for frozenset state
```
remove(elem)
Remove element elem from the set. Raises KeyError if elem is not contained in the set.
discard(elem)
Remove element elem from the set if it is present.
```
@@danielsun716 in case you want to have an error raised if the target doesn’t exist
My brain exploded while doing this question
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.
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 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 getRecentTweets(int count,const unordered_map &userStore) const {
vector recentTweets;
priority_queue heap;
for(auto itr=followeeIds.begin(); itr != followeeIds.end(); itr++)
{
const User *followee = &userStore.at(*itr);
if(followee->tweetHead != nullptr)
heap.push(followee->tweetHead);
}
if(tweetHead)
heap.push(tweetHead);
for(int i=0; iid);
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())
userStore[userId]=User(userId);
userStore[userId].post(tweetId);
}
vector 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())
userStore[followerId]=User(followerId);
if(userStore.find(followeeId) == userStore.end())
userStore[followeeId]=User(followeeId);
userStore[followerId].follow(followeeId);
}
void unfollow(int followerId, int followeeId) {
userStore[followerId].unfollow(followeeId);
}
private:
unordered_map userStore;
};
/**
* Your Twitter object will be instantiated and called as such:
* Twitter* obj = new Twitter();
* obj->postTweet(userId,tweetId);
* vector param_2 = obj->getNewsFeed(userId);
* obj->follow(followerId,followeeId);
* obj->unfollow(followerId,followeeId);
*/
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.
Thanks!
Thank you so much Ian!!!!!!
This was by far the best explaination I got for any problem...
Happy New Year to you and more power to you to provide more videos. You are helping so many people! Thank you!
Thanks again for a wonderful question and great explanation. Please think of doing more system design videos.
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....
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.
which solution is o(n)?
@@demaxl732 Instead of using complex heap merging you could just append the tweets from *all* the followed users and stick them in a single heap and take the 10 newest. Takes O(n) to heapify plus O(n) space but maybe good enough for a first pass!
@@demaxl732 Maybe he means counting the minimum again each time. But this approach seems stupid to me.
Thank you. A very interesting question to solve.
Great video neetcode keep going
It would be more optimal to use a defaultdict(deque) for tweetMap since only the most recent 10 tweets from any user are relevant.
I'm able to figure out how to implement a dictionary of lists, but how do you implement a dictionary of sets?
Brilliant explanation!!!!!
Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
thanks! it helped :)
No way this is LC medium. Hard af
great solutaion!!
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.😅
thank you king
Great video
Great explanation !!! One thing, since the constraint is 10 tweets, can we use a LinkedList/circular array by maintaining size = 10 (eg. remove from head, add to tail whenever size == 10) so that the space is limited to 10 tweets, per person ?
yes
At 19:05, is that only adding one tweet per followee by far?
The tweets are already sorted
I just add them to a list and then do a reverse loop to get the result
All the tweets have unique IDs.
@NeetCode - at 11:30 - do we not still end up with a final worst case time complexity of O(k log k)? We use heapify to initialize the heap, but for the next 9x operations we use heappush to insert the new IDs into the heap? Thank you for this video, fantastic as always
I think we just need to call heappush at most 10 times, so overall time complexity is O(K(initialize minHeap) + 10logk(pop from heap) + 10logk(push to heap)) = O(k). Please correct me if I missed anything.
I was unaware you get asked this on faang interviews unless this is system design question.
you should probably say the variable type for tweetMap is List of List
Thanks
for the getnewsfeed, how are we just assuming that -1 index exists and adding it to our heap, shouldnt there be a check before that"?
I don't get it. Should you say it as a maxHeap? Even though we are getting the minimum value from it, it is still gonna give us the most recent count (max count). Please correct me if I am wrong.
It is actually not the minimum value but we are trying to get the maximum value. Since we change it to negative, it happens to be getting the minimum value. for example, we have [(-7,128, 111, 4), (-5, 129, 112, 10), (-3, 131, 113, 5)] which is built upon using maxHeap idea. Then, we will pop the smallest which is -7 but technically that is the largest without negative sign(the most recent). After that we can add the tweet at index 3 of the followeeId with 111. Heap will sort it again and we continue the same process. Hope this makes sense.
In Python, we can call it as maxHeap i guess. to avoid confusion.
Yes indeed it's a max heap coz most recent tweet ie. tweet with largest time will be top of heap
Nicely explained as always. Btw which tool do you use for drawing? I use Microsoft paint but switching from dark and light theme frequently hurts my eyes 😂
I use Paint3D
@@NeetCode 👍
Superb
we should add the user to its own followMap during init right?
You need to heapify the right most elements from each tweet list by the followers, which should take O(10 * log(10)) time, did you assume this to be constant term?
I'm sorry if this is a lame question but in which category does this come under? HLD LLD or machine coding?
I would say this question is more of Object Oriented Design & Algorithms mixed together. Of course I know it's also asked as a system design question as well.
@NeetCode thanks for the reply 👍
0:22 it's quite the contrary for me. as a medium problem, it's too easy for me & i'm still struggling with lots of easy problems. i could solve it using only array & hash maps on the 1st try without struggling much.
i'm wondering tho, what made you thing it's a hard problem?
This LC is bad for DSA interview I think. It should be for system design interview.
When I start the question, I am unsure which methods I should optimize.
I thought the question's author want to run the background job (or event-driven) to update the feeds when user post(), follow() or unfollow() to have O(1) for all methods and accept a small delay to get latest feeds after follow/unfollow someone.
Can you solve few leetcode question in Java or make a video on how to understand a solution from other language and convert into other one! Please
I passed with a O(N log N), although it's in the 5% slowest solution
At line 18, what if a user we follow doesn't have any tweets? We should add `if index >= 0:` after line 18.
This comment needs to be higher!
can anyone please explain for me why we need to decrement the count by 1 at 15:20? Thank you!
he is doing the maxHeap in python, but there is no maxheap in python, so that he is doing in that way, he did said you won't need to do the -1,-2,-3 in java, did you watch the whole explanation? lol
nah this is insane
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?
I got it, so modify it once, the time complexity is logK, we need to modify it 10 times, so the time complexity is 10logK. But if we need to find the min, it should be 10KlogK, I think.
No max heap. No custom sort for heaps. This is a rare occasion I prefer C++ over Python.
I did this by just holding all the tweets in the same queue and beat 100% in speed. Never popped anything from the queue so used more memory.
Not using any heap? How do you get 10 latest tweet then?
@@seifmostafa58 but 10 recent tweets for each user will be different because each user follow a different set of users
Do you actually draw with your mouse? I can hear the clicks. If you do really write everything with your mouse, for 355 videos already kudos
If Object Oriented Design rounds are similar to this, I'll have fun, this problem was tricky with edge cases but I solved it on my own first try.
How come when we heappush to the minHeap we are pushing a positive "count" value?. I thought we wanted the maxHeap so we push a negative "-count" value so that our heap will pop and give us the most recent post or in other words the biggest count value we pushed in.
"count" is already negative
@@kanku9818 Oh ur right, I didn't think about just counting -= 1
Nice explanation! But, do you forgot to add the tweets create by the user itself? We need to get the most recent 10 tweets from user and the user's followee. I think you did not add the user's own tweet to the res.
added at last
Your videos are helping lots of people.Thank you @NeetCode for work and time.
Isn't timestamp redundant if the tweet IDs are global and are incremented chronologically?
The IDs are not incremented chronologically
I don't get it - how is making the heap not instantly getting TLE'd to death? There are a lot of tweets.
why cant we just simply merge those list then heapify it and heappop last min(10,len(templist)) times and get answer
We only heapify k elements once, that's O(k). Then, we pop 10 times, that's O(10logk). Shouldn't the time complexity be O(k + 10logk) = O(10logk) instead?
I believe because K scales bigger then 10logk, so you drop the 10logk for a final answer of O(k)
@@erichoward8249 oh that makes sense lol. Idk it wasnt obvious linear term i more significant. Thanks!
Surely this would fail because of how you terminate the search for earlier tweets once you hit 10 instead of searching through all of them?
User 1 [-5, -4, -3, -2, -1]
User 2 [-10, -9, -8, -7, -6]
User 3 [-15, -14, -13, -12, -11]
In your approach you'd start the heap with -15, -10, and -5 all in there, which would end up in the result. But -5 should not be in the result since the 10 most recent tweets from the combined lists should only come from user 2 and 3, no?
Hi Charles, I have the exact same question. Here is my simplified reasoning. Imagine that we are getting the most recent 3 tweets (instead of 5)
User A tweeted at times: 1am, 5am, 6am.
User B tweeted at times: 4am, 7am, 9am.
User C tweeted at times: 2am, 3am, 8am.
Based on Neetcode's algo, it would return the tweet at 6am,8 am and 9am but 6 should not be in the result.
However, neetcode's algo does pass leetcode because leetcode only has 16 test cases for this quesions and it does not consider this scenario that we concern about.
Let me know if you changed your thougts. I still think that neetcoded's approach on this specific question is incorrect and the test case for this question on lc is not comprehensive.
@@melissachen1581 I realized I got it wrong. Remember that once you pop from the heap, you then push the next one onto the heap. So eg in my example, you'd first pop -15, but then push -14 onto the heap. So that one would get popped next. You'd actually go -15, -14, -13, -12, etc due to popping and pushing, so you'd never hit -5. Sorry for the confusion!
C++ coders watching this like 😐😐😐😐😐😐😐😐😐😐😐😐
Hi, can you please do videos for algorithms and data structures? Pls consider 🙏
Have a look at WilliamFiset's channel, there are some excellent videos about all the data structures and algorithms you could think of 😄
@@BeheadedKamikaze thanks man 🙏
This problem is actually not that hard compared to the previous several DP problems. I solved it in 20 minutes. But the DP problems? I am 100% sure I have a 0% chance to solve it.
10:30 that explanation is wrong.. It does improve running time common.. go over it again.
i hope im not asked this
disclaimer: I did not go through the entire video. skipped to the definition of getNewsFeed method.
I opted to go for a class variable that would hold a "counter", and everytime anybody posts a new tweet this counter goes up. with this i just store the tweets with this class variable counter. and whenit comes to get the recent feed, i collect all the tweets for a user ( and its followers ), and just use nlargest heap to get the latest 10 with the class counter.
I am aware that this solution has other issues like eventually that class counter will overflow and will also have to be properly locked to avoid race conditions, but is this NOT viable solution?
note: i dislike these lines, just wanted to move forward with appending all the tweets that the user got, didn't want to go through more hazzle.
for tweet in user_tweets:
all_tweets.append(tweet)
also: i am not looking to show off, just curious on your thoughts.
def postTweet(self, userId: int, tweetId: int) -> None:
self.add_user(userId)
self.users[userId]["tweets"].append([Twitter.tweets, tweetId])
Twitter.tweets += 1
def getNewsFeed(self, userId: int) -> List[int]:
self.add_user(userId)
list_of_users = self.users[userId]["following"]
all_tweets = [*self.users[userId]["tweets"]]
for user in list_of_users:
user_tweets = self.users[user]["tweets"]
for tweet in user_tweets:
all_tweets.append(tweet)
latest_tweets = heapq.nlargest(10, all_tweets)
return [tweet[1] for tweet in latest_tweets]
leet code accepted it, it seems to reduce complexity in coding when attempting to connect all the user and followers tweets..
class Twitter:
def __init__(self):
self.count = 0
self.followed = defaultdict(set)
self.posts = defaultdict(list)
def postTweet(self, userId: int, tweetId: int) -> None:
self.posts[userId].append([self.count, tweetId])
self.count -= 1
def getNewsFeed(self, userId: int) -> List[int]:
min_heap = []
res = []
self.followed[userId].add(userId)
for followeeid in self.followed[userId]:
if followeeid in self.posts:
length = len(self.posts[followeeid])
tweet = 0
while tweet < length:
count, tweetId = self.posts[followeeid][tweet]
tweet += 1
min_heap.append([count, tweetId])
heapq.heapify(min_heap)
while min_heap and len(res) < 10:
count, tweetId = heapq.heappop(min_heap)
res.append(tweetId)
return res
def follow(self, followerId: int, followeeId: int) -> None:
self.followed[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
if followeeId in self.followed[followerId]:
self.followed[followerId].remove(followeeId)
....
This is your solution but i implemented it slightly differently. Its a bit inefficient (time wise, space wise its more efficient) but it was more understandable for me as i had less variable to take care of in the min_heap.
Alternative to not using index:
def getNewsFeed(self, userId: int) -> List[int]:
self.followmap[userId].add(userId)
res = []
minheap = []
for followeeId in self.followmap[userId]:
l = len(self.tweetmap[followeeId])
for i in range(l):
count, tweetId = self.tweetmap[followeeId][i]
minheap.append([count, tweetId])
heapq.heapify(minheap)
while minheap and len(res) < 10:
count, tweetId = heapq.heappop(minheap)
res.append(tweetId)
return res
Nice and readable solution!
I was also going with this solution since it's more intuitive. Just know that this will have slightly worse Time complexity since you're adding ALL tweets in the MinHeap, instead of only 10.
Nice explanation! In the getNewsFeed function, can we get all followee's (count, tweetID) tuple first, and then use heapq.nlargest(10, List[tuple]) to get top 10 latest tweets? I knew the Time and Space complexity might be worse, but can you compare these two solutions? Thanks
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻