69.Design Twitter

MediumHeap / Priority Queue · 6/7

Problem

Design a simplified Twitter where users post tweets, follow/unfollow each other, and see the 10 most recent tweets in their news feed. Implement Twitter:

Twitter() initializes the object.
void postTweet(int userId, int tweetId) — user userId posts a new tweet with unique id tweetId.
List<Integer> getNewsFeed(int userId) — up to 10 most recent tweet ids posted by the user or anyone they follow, ordered most recent first.
void follow(int followerId, int followeeId) and void unfollow(int followerId, int followeeId).

Examples

Input:  ["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"]
        [[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]
Output: [null,null,[5],null,null,[6,5],null,[5]]
Explanation: After following user 2, user 1 sees tweet 6 (newer) then 5. After unfollowing, only 5.

Input:  ["Twitter","postTweet","postTweet","getNewsFeed","follow","getNewsFeed"]
        [[],[1,1],[2,2],[2],[2,1],[2]]
Output: [null,null,null,[2],null,[2,1]]
Explanation: User 2 initially sees only their own tweet; after following 1, both, newest first.

Constraints

1 <= userId, followerId, followeeId <= 500
0 <= tweetId <= 10^4
All tweets have unique ids.
At most 3 * 10^4 calls in total to postTweet, getNewsFeed, follow, and unfollow.
A user cannot follow themselves (test data never does this, but the code should not break if it happens).

💡 Key Insight

Each user's own tweets are naturally sorted by time (appended in posting order). A news feed is therefore a merge of F sorted lists where we only need the top 10 — exactly the "merge k sorted lists" pattern. Seed a max-heap with each followee's newest tweet, pop the most recent, and push that user's next-older tweet; stop after 10 pops.

Brute Force (Global Timeline Scan)

TimeO(1) for postTweet, follow, unfollow; O(T) for getNewsFeed, where T is the total number of tweets (a user who follows nobody active may scan everything).SpaceO(T + E)

Intuition

Store every tweet in one global list in posting order. To build a feed, walk the list backwards (newest first) and keep tweets authored by the user or someone they follow, until 10 are collected.

Algorithm

postTweet: append [userId, tweetId] to timeline.
follow / unfollow: add/remove in following.get(followerId) (a set).
getNewsFeed: scan timeline from the end; include a tweet if its author is userId or in the follow set; stop at 10.

Visualization

timeline (oldest -> newest): [u1:5] [u3:7] [u2:6]
user 1 follows {2}

scan from newest: u2:6 keep, u3:7 skip, u1:5 keep -> [6, 5]

Code

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class Twitter {
    private final List<int[]> timeline = new ArrayList<>(); // [userId, tweetId]
    private final Map<Integer, Set<Integer>> following = new HashMap<>();

    public Twitter() {
    }

    public void postTweet(int userId, int tweetId) {
        timeline.add(new int[] {userId, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> followees = following.getOrDefault(userId, new HashSet<>());
        List<Integer> feed = new ArrayList<>();
        for (int i = timeline.size() - 1; i >= 0 && feed.size() < 10; i--) {
            int author = timeline.get(i)[0];
            if (author == userId || followees.contains(author)) {
                feed.add(timeline.get(i)[1]);
            }
        }
        return feed;
    }

    public void follow(int followerId, int followeeId) {
        following.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        Set<Integer> set = following.get(followerId);
        if (set != null) {
            set.remove(followeeId);
        }
    }
}

Complexity

Time: O(1) for postTweet, follow, unfollow; O(T) for getNewsFeed, where T is the total number of tweets (a user who follows nobody active may scan everything).
Space: O(T + E) — all tweets plus follow edges E.

Per-User Lists + Sort

TimeO(R log R) for getNewsFeed, where R is the number of tweets by the user and followees; O(1) for the rest.SpaceO(T + E).

Intuition

Keep each user's tweets in their own list with a global timestamp. For a feed, collect every tweet of the user and their followees, sort by timestamp descending, and take the first 10. This only touches relevant tweets but sorts all of them.

Algorithm

postTweet: append [time++, tweetId] to tweets.get(userId).
getNewsFeed: gather all tweets from userId and each followee into one list.
Sort by time descending; return the first 10 tweet ids.

Visualization

user 1: [(0,5)]   user 2: [(1,6), (3,8)]   user 1 follows {2}
gather: (0,5) (1,6) (3,8)
sort desc by time: (3,8) (1,6) (0,5) -> [8, 6, 5]

Code

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class Twitter {
    private int time = 0;
    private final Map<Integer, List<int[]>> tweets = new HashMap<>(); // userId -> [time, tweetId]
    private final Map<Integer, Set<Integer>> following = new HashMap<>();

    public Twitter() {
    }

    public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[] {time++, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> users = new HashSet<>(following.getOrDefault(userId, new HashSet<>()));
        users.add(userId); // include own tweets exactly once
        List<int[]> all = new ArrayList<>();
        for (int u : users) {
            all.addAll(tweets.getOrDefault(u, new ArrayList<>()));
        }
        all.sort((a, b) -> Integer.compare(b[0], a[0])); // newest first
        List<Integer> feed = new ArrayList<>();
        for (int i = 0; i < all.size() && i < 10; i++) {
            feed.add(all.get(i)[1]);
        }
        return feed;
    }

    public void follow(int followerId, int followeeId) {
        following.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        Set<Integer> set = following.get(followerId);
        if (set != null) {
            set.remove(followeeId);
        }
    }
}

Complexity

Time: O(R log R) for getNewsFeed, where R is the number of tweets by the user and followees; O(1) for the rest.
Space: O(T + E).

Per-User Lists + Max-Heap MergeOptimal

TimeO(F log F) for getNewsFeedSpaceO(T + E) for storage, O(F) for the heap.

Intuition

Each user's list is already sorted by time, so we never need a full sort. Put the newest tweet of each relevant user into a max-heap keyed by timestamp, along with the index of that tweet in its list. Pop the newest overall; then push the same user's previous tweet (index − 1). Ten pops give the feed.

Algorithm

Same storage as Approach 2.
getNewsFeed(userId): users = followees ∪ {userId}.
For each user with tweets, push [time, tweetId, userId, index = last].
While heap non-empty and feed.size() < 10: pop top, add its tweet id; if index > 0, push that user's tweet at index - 1.

Dry Run

User 1 posted 5 (t=0), 9 (t=4); user 2 posted 6 (t=1), 8 (t=3); user 1 follows 2.

flowchart TD
    A["seed heap with newest per user<br/>{t4:9 (u1), t3:8 (u2)}"] --> B["pop t4:9 -> feed [9]<br/>push u1 t0:5"]
    B --> C["heap {t3:8, t0:5}"]
    C --> D["pop t3:8 -> feed [9,8]<br/>push u2 t1:6"]
    D --> E["heap {t1:6, t0:5}"]
    E --> F["pop t1:6, pop t0:5<br/>feed [9,8,6,5]"]

Code

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

class Twitter {
    private int time = 0;
    private final Map<Integer, List<int[]>> tweets = new HashMap<>(); // userId -> [time, tweetId]
    private final Map<Integer, Set<Integer>> following = new HashMap<>();

    public Twitter() {
    }

    public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[] {time++, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> users = new HashSet<>(following.getOrDefault(userId, new HashSet<>()));
        users.add(userId);
        // heap entry: [time, tweetId, userId, index in that user's list]
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
        for (int u : users) {
            List<int[]> list = tweets.get(u);
            if (list != null && !list.isEmpty()) {
                int last = list.size() - 1;
                maxHeap.offer(new int[] {list.get(last)[0], list.get(last)[1], u, last});
            }
        }
        List<Integer> feed = new ArrayList<>();
        while (!maxHeap.isEmpty() && feed.size() < 10) {
            int[] top = maxHeap.poll();
            feed.add(top[1]);
            int prev = top[3] - 1;
            if (prev >= 0) { // push that user's next-older tweet
                int[] t = tweets.get(top[2]).get(prev);
                maxHeap.offer(new int[] {t[0], t[1], top[2], prev});
            }
        }
        return feed;
    }

    public void follow(int followerId, int followeeId) {
        following.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        Set<Integer> set = following.get(followerId);
        if (set != null) {
            set.remove(followeeId);
        }
    }
}

Complexity

Time: O(F log F) for getNewsFeed — seeding F followees, then at most 10 pops/pushes of O(log F); O(1) for the other operations.
Space: O(T + E) for storage, O(F) for the heap.

Complexity Comparison

Approach	postTweet	getNewsFeed	Space
Global Timeline Scan	O(1)	O(T)	O(T + E)
Per-User Lists + Sort	O(1)	O(R log R)	O(T + E)
Per-User Lists + Heap Merge	O(1)	O(F log F)	O(T + E)

Common Pitfalls

Ordering by tweetId instead of a timestamp — tweet ids are unique but not increasing with time.
Forgetting the user's own tweets, or counting them twice when the user also appears in their follow set.
unfollow on a user who never followed anyone — guard against a null set.
Mutating the stored follow set when adding userId for the feed — copy it first, otherwise unfollow(self) semantics get messy.