Design Twitter

MediumDesign · Heap (K-way Merge) · Hash Map🧩 Data Structure Design LeetCode #355 ↗Updated Oct 30, 2026

Problem

Build a tiny social feed. postTweet(userId, tweetId) publishes a tweet with a unique id; follow(a, b) / unfollow(a, b) make user a start or stop following b; getNewsFeed(userId) returns the ids of the 10 most recent tweets written by the user or anyone they follow, newest first.

InputpostTweet(1,5) getNewsFeed(1)Output[5]

Inputfollow(1,2) postTweet(2,6) getNewsFeed(1)Output[6,5]

Inputunfollow(1,2) getNewsFeed(1)Output[5]

1 ≤ userId ≤ 500 · 0 ≤ tweetId ≤ 10⁴, all unique · ≤ 3·10⁴ calls in total

Try it yourself

Java

class Twitter {
    public Twitter() {
        
    }

    public void postTweet(int userId, int tweetId) {
        
    }

    public List<Integer> getNewsFeed(int userId) {
        
    }

    public void follow(int followerId, int followeeId) {
        
    }

    public void unfollow(int followerId, int followeeId) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Each user's tweets are already in time order, so a feed is a merge of sorted lists — but only the top 10 are needed. A max-heap holding one cursor per followed user pops the newest tweet 10 times and stops.

PatternData Structure Design

Instinct Implement a class whose methods must all hit a time bound (often O(1)) - write each method's target cost, then glue a hash map to a structure that keeps order.

Memory hack Finder plus keeper - a hash map finds it fast, a list/heap/array keeps the order, and every method updates both.

Open the Data Structure Design guide →

Approaches

Brute ForceGlobal Timeline Scan

Time feed O(T), others O(1)Space O(T + F)

Append every tweet {author, id} to one global list. For a feed, scan that list from newest to oldest and keep tweets whose author is the user or someone they follow, stopping after 10 hits.

Java

class Twitter {
    private final List<int[]> timeline = new ArrayList<>(); // {authorId, 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> follows = following.getOrDefault(userId, Collections.emptySet());
        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 || follows.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> s = following.get(followerId);
        if (s != null) s.remove(followeeId);
    }
}

Tiny code, but a feed may scan every tweet ever posted (T = total tweets).

BetterPer-User Tweets, Collect Last 10 Each & Sort

Time feed O(F log F)Space O(T + F)

Store tweets per author with a global timestamp. For a feed, take at most the last 10 tweets from the user and each followee (older ones can never make the top 10), sort the candidates by time descending, and return the first 10.

Java

class Twitter {
    private int clock = 0;
    private final Map<Integer, List<int[]>> tweets = new HashMap<>(); // {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[]{clock++, tweetId});
    }
    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> sources = new HashSet<>(following.getOrDefault(userId, Set.of()));
        sources.add(userId);
        List<int[]> candidates = new ArrayList<>();
        for (int u : sources) {
            List<int[]> list = tweets.getOrDefault(u, List.of());
            for (int i = list.size() - 1; i >= Math.max(0, list.size() - 10); i--) {
                candidates.add(list.get(i));
            }
        }
        candidates.sort((a, b) -> Integer.compare(b[0], a[0])); // newest first
        List<Integer> feed = new ArrayList<>();
        for (int i = 0; i < Math.min(10, candidates.size()); i++) {
            feed.add(candidates.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> s = following.get(followerId);
        if (s != null) s.remove(followeeId);
    }
}

Independent of total tweet count, but sorts ~10·F candidates every time.

OptimalK-way Merge with a Max-Heap

Time feed O(F + 10 log F)Space O(T + F)

Seed a max-heap (by timestamp) with the newest tweet of every source, remembering which list and index it came from. Pop the newest, add it to the feed, and push the next older tweet from the same author. Ten pops and the feed is done.

Java

class Twitter {
    private int clock = 0;
    private final Map<Integer, List<int[]>> tweets = new HashMap<>(); // {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[]{clock++, tweetId});
    }
    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> sources = new HashSet<>(following.getOrDefault(userId, Set.of()));
        sources.add(userId);
        // heap entry: {time, tweetId, authorId, index in author's list}
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
        for (int u : sources) {
            List<int[]> list = tweets.get(u);
            if (list == null || list.isEmpty()) continue;
            int i = list.size() - 1;
            heap.offer(new int[]{list.get(i)[0], list.get(i)[1], u, i});
        }
        List<Integer> feed = new ArrayList<>();
        while (!heap.isEmpty() && feed.size() < 10) {
            int[] top = heap.poll();
            feed.add(top[1]);
            int next = top[3] - 1; // next older tweet by the same author
            if (next >= 0) {
                int[] t = tweets.get(top[2]).get(next);
                heap.offer(new int[]{t[0], t[1], top[2], next});
            }
        }
        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> s = following.get(followerId);
        if (s != null) s.remove(followeeId);
    }
}

Touches only what the feed needs — the classic merge-k-sorted-lists answer.

Pro tip

Use a global counter as the timestamp — tweet ids are unique but say nothing about posting order.

At a glance

Level	Approach	Time	Space
Brute Force	Global Timeline Scan	`feed O(T), others O(1)`	`O(T + F)`
Better	Per-User Tweets, Collect Last 10 Each & Sort	`feed O(F log F)`	`O(T + F)`
Optimal	K-way Merge with a Max-Heap	`feed O(F + 10 log F)`	`O(T + F)`

Common pitfalls

Sorting by tweet id instead of posting time — ids are not chronological.
Leaving out the user's own tweets, or listing them twice after a self-follow.
unfollow on a user who follows nobody — guard the null set.

Interview tips

Ask about ordering (global clock) and duplicate follows before coding.
Connect the feed to “Merge k Sorted Lists” — it signals the heap.
Mention push vs pull: precomputing feeds on post trades write cost for read speed.

Pattern

K-way merge with a heap → top-k newest/smallest items across many individually sorted lists.

My notes saved in this browser