LeetCode 355: Design Twitter Solution

Master LeetCode problem 355 (Design Twitter), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

355. Design Twitter

Medium

Hash Table Linked List Design Heap (Priority Queue)

Problem Explanation

Explanation

To design a simplified version of Twitter, we can use a combination of data structures like HashMaps and priority queues to efficiently implement the required functionalities. Here's an overview of the algorithmic idea:

Each user will have a unique user ID and a list of tweets they have posted.
We will maintain a HashMap to store the users and their corresponding tweets.
To implement the follow and unfollow functionalities, we can use another HashMap to store the followers for each user.
For the getNewsFeed functionality, we will retrieve the 10 most recent tweets from the user's feed, including their own tweets and the tweets of users they follow. We can achieve this by using a priority queue to keep track of the latest tweets.
When a user posts a tweet, we will update their tweet list and add the tweet to the priority queue for efficient retrieval.

Time Complexity:

postTweet: O(1)
follow: O(1)
unfollow: O(1)
getNewsFeed: O(n log k) where n is the total number of tweets and k is the number of users the user follows

Space Complexity: O(n + k) where n is the total number of tweets and k is the number of users

Solution Code

import java.util.*;

class Twitter {
    int timestamp;
    Map<Integer, List<int[]>> tweets;
    Map<Integer, Set<Integer>> follows;

    public Twitter() {
        this.timestamp = 0;
        this.tweets = new HashMap<>();
        this.follows = new HashMap<>();
    }

    public void postTweet(int userId, int tweetId) {
        tweets.putIfAbsent(userId, new ArrayList<>());
        tweets.get(userId).add(new int[]{tweetId, timestamp++});
    }

    public List<Integer> getNewsFeed(int userId) {
        PriorityQueue<int[]> feed = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        if (tweets.containsKey(userId)) {
            feed.addAll(tweets.get(userId));
        }

        if (follows.containsKey(userId)) {
            for (int followeeId : follows.get(userId)) {
                if (tweets.containsKey(followeeId)) {
                    feed.addAll(tweets.get(followeeId));
                }
            }
        }

        List<Integer> result = new ArrayList<>();
        while (!feed.isEmpty() && result.size() < 10) {
            result.add(feed.poll()[0]);
        }
        return result;
    }

    public void follow(int followerId, int followeeId) {
        follows.putIfAbsent(followerId, new HashSet<>());
        follows.get(followerId).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        follows.putIfAbsent(followerId, new HashSet<>());
        follows.get(followerId).remove(followeeId);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 355 (Design Twitter)?

This page provides optimized solutions for LeetCode problem 355 (Design Twitter) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 355 (Design Twitter)?

The time complexity for LeetCode 355 (Design Twitter) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 355 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 355 in Java, C++, or Python.

Back to LeetCode Solutions