Design Twitter - Leetcode 355 - Python

[@NeetCode]

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

[@pedroduckz]

any chance you could repost this? could be life savior :p

[@NeetCode]

@@pedroduckz Updated the links, they should work now :)

[@pedroduckz]

@@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?

[@oooo-rc2yf]

I've had nightmares about this one before. Thanks

[@blackda5686]

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.

[@danielsun716]

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?

[@morenoh149]

@@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. ```

[@user-jt4hk1rl8r]

@@danielsun716 in case you want to have an error raised if the target doesn’t exist

[@samarthtandale9121]

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); */

[@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.

[@prajwalhsuvarna]

one more asslicker

[@andrefreitas9936]

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...

[@ziadmohamed682]

In the worst case, you will end up iterating through almost all of posts which is not very optimal in a real life situation.

[@andrefreitas9936]

@ziadmohamed682 in a real life situation you dont always use the " best time complexity data structure" usually what happens is that how you am hybrid algorithm like STL C++ sort if the request is small usually you use a "worst algo" because it's faster for small inputs... Men it's there's a thing about big O that people dont understand, it's a bad notation to represent those things, it's only good to compare for big inputs

[@ziadmohamed682]

@@andrefreitas9936 What I meant was that you could have a real platform like Twitter where there are millions of tweets added everyday. So, going through all of the tweets of the platform,which could be billions, until you find people the user is following would be very impractical.

[@sikaydalapixia5924]

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]

which solution is o(n)?

[@CharlesGreenberg000]

@@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!

[@qts]

@@demaxl732 Maybe he means counting the minimum again each time. But this approach seems stupid to me.

[@mengzhugao7693]

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....

[@rishav9441]

My brain exploded while doing this question

[@tvkrishna71]

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

[@helloadventureworld]

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

[@Funder_]

Thanks!

[@NeetCode]

Thank you so much Ian!!!!!!

[@himabindu8086]

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.

[@7mada89]

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

[@abdonasr1222]

Glad to see that I approached & solved the problem exactly the same way you did before I see your video about it.❤

[@sase1017]

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

[@strawberriesandcream2863]

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.😅

[@leozinger]

No way this is LC medium. Hard af

[@ashelytang2592]

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

[@Ryan-sd6os]

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"?

[@nurhusni]

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?

[@isufahmed2923]

If you check if index>=0, don't you run the risk of adding an index of -1 to the minH?

[@abhishekbanerjee6140]

we should add the user to its own followMap during init right?

[@botten4187]

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

[@nguyen-dev]

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.

[@LuisMorales-yx8di]

I was unaware you get asked this on faang interviews unless this is system design question.

[@vaibhavbangia7100]

All the tweets have unique IDs.

[@deewademai]

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

[@amynguy]

instead of remove and test condition , just do discard

[@danielsun716]

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?

[@danielsun716]

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.

[@srinadhp]

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.

[@CharlesGreenberg000]

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?

[@melissachen1581]

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.

[@CharlesGreenberg000]

@@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!

[@K4RD050]

@@CharlesGreenberg000 I think this part was very confusing and wasn't well explained in the video. Thanks for clarifying!!

[@Alchemx80]

@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

[@yohoyu6676]

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.

[@ausumnviper]

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 ?

[@animalrocket4809]

yes

[@SamJul-g2y]

I passed with a O(N log N), although it's in the 5% slowest solution

[@yewang3097]

At line 18, what if a user we follow doesn't have any tweets? We should add `if index >= 0:` after line 18.

[@TM-iw5om]

This comment needs to be higher!

[@spiceybyte]

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

[@Ryan-sd6os]

you should probably say the variable type for tweetMap is List of List

[@truongkimson]

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?

[@erichoward8249]

I believe because K scales bigger then 10logk, so you drop the 10logk for a final answer of O(k)

[@truongkimson]

@@erichoward8249 oh that makes sense lol. Idk it wasnt obvious linear term i more significant. Thanks!

[@nivedithabaskaran1669]

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.

[@Mercenarybby]

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.

[@samxsharan]

In Python, we can call it as maxHeap i guess. to avoid confusion.

[@UdhavPawar]

Yes indeed it's a max heap coz most recent tweet ie. tweet with largest time will be top of heap

[@MP-ny3ep]

I'm sorry if this is a lame question but in which category does this come under? HLD LLD or machine coding?

[@NeetCode]

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.

[@MP-ny3ep]

@NeetCode thanks for the reply 👍

[@jojo23srb]

thank you king

[@stith_pragya]

Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@alexandershengzhili954]

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?

[@thisisnotok2100]

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.

[@shalsteven]

Not using any heap? How do you get 10 latest tweet then?

[@shalsteven]

@@seifmostafa58 but 10 recent tweets for each user will be different because each user follow a different set of users

[@minhhpd]

@@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.

[@botten4187]

​@@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

[@NhanSleeptight]

Thank you. A very interesting question to solve.

[@hamoodhabibi7026]

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.

[@kanku9818]

"count" is already negative

[@hamoodhabibi7026]

@@kanku9818 Oh ur right, I didn't think about just counting -= 1

[@VishalTyagi-z5n]

why cant we just simply merge those list then heapify it and heappop last min(10,len(templist)) times and get answer

[@garykim313]

No max heap. No custom sort for heaps. This is a rare occasion I prefer C++ over Python.

[@vinaychaurasiya2206]

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

[@leetcodeproject]

Your videos are helping lots of people.Thank you @NeetCode for work and time.

[@christendombaffler]

I don't get it - how is making the heap not instantly getting TLE'd to death? There are a lot of tweets.

[@duynghiatran8519]

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

[@hvaghani]

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 😂

[@NeetCode]

I use Paint3D

[@hvaghani]

@@NeetCode 👍

[@Eeeason-c5y]

Brilliant explanation!!!!!

[@houmankamali5617]

Isn't timestamp redundant if the tweet IDs are global and are incremented chronologically?

[@chrispangg]

The IDs are not incremented chronologically

[@osmanmusse9432]

Great video neetcode keep going

[@Ivan-ek6kg]

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.

[@letscode1000]

added at last

[@symbol767]

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.

[@asdfasyakitori8514]

Great video

[@dusvn1484]

This is mind blow

[@sidazhong2019]

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.

[@JunLiLin0616]

Overall t.c. should be O(k) I think. O(k + 10logk) -> O(k)

[@hienbui381]

can anyone please explain for me why we need to decrement the count by 1 at 15:20? Thank you!

[@chowtuk]

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

[@stellachieh]

great solutaion!!

[@aditidey9366]

thanks! it helped :)

[@s8x.]

nah this is insane

[@suryakiran2970]

Superb

[@ankushmehra9344]

if there is no Max heap in python Then Why even your using Python .

[@whonayem01]

Thanks

[@EranM]

10:30 that explanation is wrong.. It does improve running time common.. go over it again.

[@adiyogi-thefirstguru5144]

Hi, can you please do videos for algorithms and data structures? Pls consider 🙏

[@BeheadedKamikaze]

Have a look at WilliamFiset's channel, there are some excellent videos about all the data structures and algorithms you could think of 😄

[@adiyogi-thefirstguru5144]

@@BeheadedKamikaze thanks man 🙏

[@mehershrishtinigam5449]

C++ coders watching this like 😐😐😐😐😐😐😐😐😐😐😐😐

[@subhamgupta6235]

Explanation is too messy to Visualize ...Can u please solve it in a better way?

[@Bonnbon8]

i hope im not asked this

[@niyashiyas4303]

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); */

[@niazahmad7823]

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.

[@johnalvinm]

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

[@Kuo-HaoLai]

Nice and readable solution!

[@ShiftK]

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.

[@gotaogo3547]

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

[@stith_pragya]

Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻