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
@@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?
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. ```
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.
using a vector 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...
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.
@@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!
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.
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....
You used diff algo from Merge K Sorted Lists(merge two list into one temp list, then merge with another one), but in this solution, you used simple minHeap
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.😅
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?
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.
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.
Doesnt the solution make the implicit assumption, that the tweet IDs for each user are monotonically increasing? Since you're always pulling the newest tweet for each user simply from the back of a queue. That isnt specified in the task description
@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.
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.
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 ?
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 😂
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?
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!
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.
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?
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.
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.
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.
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.
@@shalsteven The timeline of the entire program is the same. You keep the timeline of all tweets. For each user you go from top to bottom and filter out nonfollowee tweets, O(n). I don't understand why we need to heapify because it's not like you can tweet in the past.
@@minhhpd technically the problem statement doesnt say that the tweet IDs per user are monotonically increasing. Especially when you'd actually design twitter, you would have to expect that tweets are sometimes processed out of order
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
This seems to be a much simpler solution : class Twitter { HashMap users; List res; public Twitter() { users = new HashMap(); res = new ArrayList(); } public void postTweet(int userId, int tweetId) { if(!users.containsKey(userId)) users.put(userId, new ArrayList(Arrays.asList(userId))); res.add(new Pair(userId, tweetId)); } public List getNewsFeed(int userId) { List ans = new ArrayList(); int i = res.size()-1; while(ans.size()=0){ if(users.get(userId).contains(res.get(i).getKey())) ans.add(res.get(i).getValue()); i--; } return ans; } public void follow(int followerId, int followeeId) { if(!users.containsKey(followerId)) users.put(followerId, new ArrayList(Arrays.asList(followerId))); users.get(followerId).add(followeeId); if(!users.containsKey(followeeId)) users.put(followeeId, new ArrayList(Arrays.asList(followeeId))); } public void unfollow(int followerId, int followeeId) { if(users.get(followerId).contains(followeeId)) users.get(followerId).remove(Integer.valueOf(followeeId)); } } /** * Your Twitter object will be instantiated and called as such: * Twitter obj = new Twitter(); * obj.postTweet(userId,tweetId); * List param_2 = obj.getNewsFeed(userId); * obj.follow(followerId,followeeId); * obj.unfollow(followerId,followeeId); */
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.
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
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
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.
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..
![[UA] NAVI проти G2 Esports | Blast Premier Fall Final](http://i.ytimg.com/vi/QWlIm4FGESQ/mqdefault.jpg)
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
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);
*/
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.
one more asslicker
Thanks!
Thank you so much Ian!!!!!!
My brain exploded while doing this question
using a vector 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...
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.
This was by far the best explaination I got for any problem...
It would be more optimal to use a defaultdict(deque) for tweetMap since only the most recent 10 tweets from any user are relevant.
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.
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....
Glad to see that I approached & solved the problem exactly the same way you did before I see your video about it.❤
You used diff algo from Merge K Sorted Lists(merge two list into one temp list, then merge with another one), but in this solution, you used simple minHeap
The tweets are already sorted
I just add them to a list and then do a reverse loop to get the result
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.😅
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?
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.
If you check if index>=0, don't you run the risk of adding an index of -1 to the minH?
No way this is LC medium. Hard af
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"?
we should add the user to its own followMap during init right?
I was unaware you get asked this on faang interviews unless this is system design question.
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.
Doesnt the solution make the implicit assumption, that the tweet IDs for each user are monotonically increasing? Since you're always pulling the newest tweet for each user simply from the back of a queue. That isnt specified in the task description
@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.
All the tweets have unique IDs.
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.
thank you king
Thank you. A very interesting question to solve.
Great video neetcode keep going
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
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
I'm able to figure out how to implement a dictionary of lists, but how do you implement a dictionary of sets?
Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Brilliant explanation!!!!!
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 👍
At 19:05, is that only adding one tweet per followee by far?
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?
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!
Then that user wouldn't have existed in the tweetMap in the first place. It's a good thing for us we don't have to deal with deleting tweets
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!
@@CharlesGreenberg000 I think this part was very confusing and wasn't well explained in the video. Thanks for clarifying!!
you should probably say the variable type for tweetMap is List of List
I don't get it - how is making the heap not instantly getting TLE'd to death? There are a lot of tweets.
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 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
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!
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
why cant we just simply merge those list then heapify it and heappop last min(10,len(templist)) times and get answer
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 👍
Great video
No max heap. No custom sort for heaps. This is a rare occasion I prefer C++ over Python.
Your videos are helping lots of people.Thank you @NeetCode for work and time.
I passed with a O(N log N), although it's in the 5% slowest solution
10:30 that explanation is wrong.. It does improve running time common.. go over it again.
great solutaion!!
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
nah this is insane
thanks! it helped :)
Isn't timestamp redundant if the tweet IDs are global and are incremented chronologically?
The IDs are not incremented chronologically
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.
Thanks
Superb
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
@@shalsteven The timeline of the entire program is the same. You keep the timeline of all tweets. For each user you go from top to bottom and filter out nonfollowee tweets, O(n). I don't understand why we need to heapify because it's not like you can tweet in the past.
@@minhhpd technically the problem statement doesnt say that the tweet IDs per user are monotonically increasing. Especially when you'd actually design twitter, you would have to expect that tweets are sometimes processed out of order
C++ coders watching this like 😐😐😐😐😐😐😐😐😐😐😐😐
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
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 🙏
Explanation is too messy to Visualize ...Can u please solve it in a better way?
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.
i hope im not asked this
This seems to be a much simpler solution :
class Twitter {
HashMap users;
List res;
public Twitter() {
users = new HashMap();
res = new ArrayList();
}
public void postTweet(int userId, int tweetId) {
if(!users.containsKey(userId)) users.put(userId, new ArrayList(Arrays.asList(userId)));
res.add(new Pair(userId, tweetId));
}
public List getNewsFeed(int userId) {
List ans = new ArrayList();
int i = res.size()-1;
while(ans.size()=0){
if(users.get(userId).contains(res.get(i).getKey())) ans.add(res.get(i).getValue());
i--;
}
return ans;
}
public void follow(int followerId, int followeeId) {
if(!users.containsKey(followerId)) users.put(followerId, new ArrayList(Arrays.asList(followerId)));
users.get(followerId).add(followeeId);
if(!users.containsKey(followeeId)) users.put(followeeId, new ArrayList(Arrays.asList(followeeId)));
}
public void unfollow(int followerId, int followeeId) {
if(users.get(followerId).contains(followeeId)) users.get(followerId).remove(Integer.valueOf(followeeId));
}
}
/**
* Your Twitter object will be instantiated and called as such:
* Twitter obj = new Twitter();
* obj.postTweet(userId,tweetId);
* List param_2 = obj.getNewsFeed(userId);
* obj.follow(followerId,followeeId);
* obj.unfollow(followerId,followeeId);
*/
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.
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
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.
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..