How do you solve Design Twitter on LeetCode?

Design Twitter (LeetCode #355) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a hash map for user relationships allows for efficient follow/unfollow operations.

What is the brute force solution for Design Twitter?

The brute force approach for Design Twitter is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we can store all tweets in a list and retrieve the user's feed by filtering through the list. This is straightforward but inefficient, especially as the number of tweets grows. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Design Twitter?

Design Twitter uses the following concepts: Hash Table, Linked List, Design, Heap (Priority Queue). The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Design Twitter?

Think about how to efficiently manage relationships between users. Consider the implications of data structure choices on performance. Be prepared to discuss trade-offs between simplicity and efficiency.

What are common mistakes when solving Design Twitter?

Not considering edge cases like unfollowing oneself. Failing to maintain the order of tweets when retrieving the news feed.

#355

Design Twitter

Medium

Hash TableLinked ListDesignHeap (Priority Queue)Hash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a combination of a hash map and a priority queue to efficiently manage tweets and retrieve the most recent ones. This reduces the time complexity significantly while maintaining clarity.

⚙️

Algorithm

3 steps

1Step 1: Use a hash map to store user follow relationships.
2Step 2: Store tweets in a list with timestamps to maintain order.
3Step 3: Use a priority queue to retrieve the 10 most recent tweets efficiently.

solution.py29 lines

1from collections import defaultdict, deque
2import heapq
3
4class Twitter:
5    def __init__(self):
6        self.tweets = []
7        self.followed = defaultdict(set)
8        self.time = 0
9
10    def postTweet(self, userId, tweetId):
11        self.tweets.append((self.time, userId, tweetId))
12        self.time += 1
13
14    def getNewsFeed(self, userId):
15        feed = []
16        followed_users = self.followed[userId] | {userId}
17        for time, uid, tid in reversed(self.tweets):
18            if uid in followed_users:
19                feed.append(tid)
20                if len(feed) == 10:
21                    break
22        return feed
23
24    def follow(self, followerId, followeeId):
25        self.followed[followerId].add(followeeId)
26
27    def unfollow(self, followerId, followeeId):
28        if followerId != followeeId:
29            self.followed[followerId].discard(followeeId)

ℹ

Complexity note: The time complexity is O(n) for getting the news feed since we may need to check all tweets in the worst case, but we only keep the last 10 in our feed. The space complexity is O(n) due to storing all tweets and user relationships.

1Using a hash map for user relationships allows for efficient follow/unfollow operations.
2Storing tweets with timestamps helps maintain the order of tweets.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.