Design Twitter Leetcode Problem 355 [Python Solution]
Welcome to another coding adventure!
Today, we're going to tackle a challenging LeetCode problem, Design Twitter This problem falls under the medium category and is related to data structures like heaps and priority queues.
It's essential to understand the trade-offs involved in designing each function efficiently.
We'll break down the problem step by step and implement a Python solution.
Problem Overview
Problem Statement: Design a simplified version of Twitter where users can post tweets, follow/unfollow other users, and see the 10 most recent tweets in their news feed.
You are required to implement the following functions:
Twitter(): Initializes your Twitter object.postTweet(userId, tweetId): Composes a new tweet with ID tweetId by the user userId.
Each call to this function will be made with a unique tweetId.
3. getNewsFeed(userId): Retrieves the 10 most recent tweet IDs in the user's news feed.
Each item in the news feed must be posted by users whom the user followed or by the user themself.
Tweets must be ordered from most recent to least recent.
4. follow(followerId, followeeId): The user with ID followerId starts following the user with ID followeeId.
5. unfollow(followerId, followeeId): The user with ID followerId starts unfollowing the user with ID followeeId.
Constraints:
– 1 <= userId, followerId, followeeId <= 500
– 0 <= tweetId <= 10^4
– All tweets have unique IDs.
– At most 3 * 10^4 calls will be made to postTweet, getNewsFeed, follow, and unfollow.
Let's dive into solving this problem efficiently.
Understanding the Constraints
Before we begin implementing the solution, let's take a closer look at the constraints provided.
Understanding these constraints is crucial for designing an efficient solution.
- User IDs, tweet IDs, and follow/unfollow operations have limits.
- The tweet IDs are unique.
- A large number of calls will be made to our functions, so efficiency is critical.
Design Twitter LeetCode Problem Solution
To solve this problem, we'll break it down into several key components:
-
Constructor (Twitter Initialization): We'll initialize data structures to store tweets, follower relationships, and the tweet count.
-
Post Tweet: We'll implement a function to allow users to post tweets.
We need to keep track of each user's tweets, including the tweet's timestamp.
- Get News Feed: This function retrieves the 10 most recent tweet IDs from the user's news feed.
We'll need to consider tweets from both the user and the users they follow.
We'll use a heap (min-heap) to efficiently retrieve the most recent tweets.
- Follow and Unfollow: We'll create functions to manage user relationships.
Users can follow and unfollow other users.
We'll use data structures to track these relationships.
Let's implement these components one by one.
1. Constructor (Twitter Initialization)
In the constructor, we'll initialize the following data structures:
– count: This variable will help us assign timestamps to tweets.
– tweetMap: A dictionary (hash map) that maps user IDs to a list of tweets.
Each tweet is represented as a pair of (timestamp, tweetID).
– followMap: A dictionary that maps user IDs to a set of followees' IDs.
class Twitter:
def __init__(self):
self.count = 0
self.tweetMap = defaultdict(list) # userId -> list of [count, tweetIds]
self.followMap = defaultdict(set) # userId -> set of followeeId
2. Post Tweet
Users can post tweets with a unique tweet ID.
We'll add the tweet to the user's tweet list, ensuring that it includes a timestamp to maintain order.
def postTweet(self, userId: int, tweetId: int) -> None:
self.tweetMap[userId].append([self.count, tweetId])
self.count -= 1
3. Get News Feed
Retrieving the user's news feed is the most complex part of this solution.
We want the 10 most recent tweets from users the given user follows, including their own tweets.
We'll use a min-heap to efficiently retrieve the most recent tweets.
Here's the code for this function:
def getNewsFeed(self, userId: int) -> List[int]:
res = []
minHeap = []
# Ensure the user follows themself
self.followMap[userId].add(userId)
# Populate the minHeap with the latest tweets from followed users
for followeeId in self.followMap[userId]:
if followeeId in self.tweetMap:
index = len(self.tweetMap[followeeId]) - 1
count, tweetId = self.tweetMap[followeeId][index]
heapq.heapp
ush(minHeap, [count, tweetId, followeeId, index])
# Extract the 10 most recent tweets
while minHeap and len(res) < 10:
count, tweetId, followeeId, index = heapq.heappop(minHeap)
res.append(tweetId)
# Get the previous tweet from the same user and add it to the heap
if index > 0:
index -= 1
count, tweetId = self.tweetMap[followeeId][index]
heapq.heappush(minHeap, [count, tweetId, followeeId, index])
return res
4. Follow and Unfollow
Users can follow and unfollow other users.
These functions manage the follow relationships.
def follow(self, followerId: int, followeeId: int) -> None:
self.followMap[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
# Ensure a user does not unfollow themself
if followerId != followeeId:
self.followMap[followerId].discard(followeeId)
Related Interview Questions By Company:
Related Interview Questions By Difficulty:
Related Interview Questions By Category:
Putting It All Together
With the functions above, we've implemented the core functionality of our Twitter design.
Users can post tweets, follow/unfollow each other, and get their news feed.
The min-heap helps ensure efficient retrieval of the most recent tweets in the news feed.
Remember to handle edge cases and constraints properly, and this solution should pass the LeetCode tests.
That's it!
You've successfully designed a simplified version of Twitter.
This problem challenges your data structure and algorithm skills, making it a great addition to your coding repertoire.
Happy coding!
