Design Twitter

medium heap hash map design

Problem

Implement postTweet, follow, unfollow, and getNewsFeed (10 most-recent tweets posted by users the requester follows, including themselves).

InputpostTweet(1, 5); getNewsFeed(1); follow(1, 2); postTweet(2, 6); getNewsFeed(1)

Output[5], [6, 5]

For getNewsFeed, merge each followee's recent posts using a max-heap over (timestamp, post).

ops (semicolon-separated)

from collections import defaultdict
import heapq
class Twitter:
    def __init__(self):
        self.t = 0
        self.tweets = defaultdict(list)    # user -> [(time, tweet)]
        self.follows = defaultdict(set)
    def postTweet(self, user, tweet):
        self.t += 1
        self.tweets[user].append((self.t, tweet))
    def getNewsFeed(self, user):
        self.follows[user].add(user)
        heap = []
        for u in self.follows[user]:
            for entry in self.tweets[u][-10:]:
                heapq.heappush(heap, (-entry[0], entry[1]))
        out = []
        while heap and len(out) < 10:
            out.append(heapq.heappop(heap)[1])
        return out
    def follow(self, a, b): self.follows[a].add(b)
    def unfollow(self, a, b):
        if a != b: self.follows[a].discard(b)

class Twitter {
  constructor() { this.t = 0; this.tweets = new Map(); this.follows = new Map(); }
  _tw(u) { if (!this.tweets.has(u)) this.tweets.set(u, []); return this.tweets.get(u); }
  _fo(u) { if (!this.follows.has(u)) this.follows.set(u, new Set()); return this.follows.get(u); }
  postTweet(user, tweet) { this.t++; this._tw(user).push([this.t, tweet]); }
  getNewsFeed(user) {
    this._fo(user).add(user);
    let pool = [];
    for (const u of this._fo(user)) pool = pool.concat(this._tw(u).slice(-10));
    pool.sort((a, b) => b[0] - a[0]);
    return pool.slice(0, 10).map(x => x[1]);
  }
  follow(a, b) { this._fo(a).add(b); }
  unfollow(a, b) { if (a !== b) this._fo(a).delete(b); }
}

class Twitter {
    int t = 0;
    Map<Integer, List<int[]>> tweets = new HashMap<>();
    Map<Integer, Set<Integer>> follows = new HashMap<>();
    public void postTweet(int user, int tweet) {
        tweets.computeIfAbsent(user, k -> new ArrayList<>()).add(new int[]{ ++t, tweet });
    }
    public List<Integer> getNewsFeed(int user) {
        follows.computeIfAbsent(user, k -> new HashSet<>()).add(user);
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int u : follows.get(user)) {
            List<int[]> lst = tweets.getOrDefault(u, List.of());
            for (int i = Math.max(0, lst.size() - 10); i < lst.size(); i++) heap.offer(lst.get(i));
        }
        List<Integer> out = new ArrayList<>();
        while (!heap.isEmpty() && out.size() < 10) out.add(heap.poll()[1]);
        return out;
    }
    public void follow(int a, int b) { follows.computeIfAbsent(a, k -> new HashSet<>()).add(b); }
    public void unfollow(int a, int b) { if (a != b && follows.containsKey(a)) follows.get(a).remove(b); }
}

class Twitter {
    int t = 0;
    unordered_map<int, vector<pair<int, int>>> tweets;
    unordered_map<int, unordered_set<int>> follows;
public:
    void postTweet(int user, int tweet) { tweets[user].push_back({ ++t, tweet }); }
    vector<int> getNewsFeed(int user) {
        follows[user].insert(user);
        priority_queue<pair<int, int>> heap;
        for (int u : follows[user]) {
            auto& lst = tweets[u];
            for (int i = max(0, (int)lst.size() - 10); i < (int)lst.size(); i++) heap.push(lst[i]);
        }
        vector<int> out;
        while (!heap.empty() && (int)out.size() < 10) { out.push_back(heap.top().second); heap.pop(); }
        return out;
    }
    void follow(int a, int b) { follows[a].insert(b); }
    void unfollow(int a, int b) { if (a != b) follows[a].erase(b); }
};

Explanation

This is a small design problem: we store data in simple structures and the only clever part is merging feeds. We keep a global timestamp t so every tweet has a strict order, a map tweets from user to a list of (time, tweet), and a map follows from user to a set of who they follow.

postTweet just bumps t and appends (t, tweet) to that user's list. follow and unfollow add to or remove from the follow set (a user never unfollows themselves).

The interesting method is getNewsFeed. We want the 10 most recent tweets across the user and everyone they follow. We make sure the user follows themselves, then gather the last 10 tweets from each followee and push them into a heap.

Python's heapq is a min-heap, but we want newest-first. The trick is to push (-time, tweet) so the largest timestamp becomes the smallest key and pops out first. We pop up to 10 times to build the feed in newest-to-oldest order.

Example: user 1 posts tweet 5 (time 1), so feed is [5]. After follow(1, 2) and user 2 posting tweet 6 (time 2), the heap orders by time and returns [6, 5]. After unfollow(1, 2), user 1 only sees their own, so the feed is [5] again.

Time: O(k log k) for feed (k followees) Space: O(users + tweets)