41 — LLD: In-memory Twitter

Understanding the Problem

A minimal Twitter — post, follow, unfollow, and a news feed of the 10 most recent tweets from a user and everyone they follow. LeetCode 355 is the canonical version. The only interesting algorithmic choice is how you merge the latest tweets from many followees: a naive flatten-and-sort is O(T log T); a merge-K-sorted with a max-heap is O(K + 10 log K).

What is In-memory Twitter?

Per-user tweet lists, per-user follow sets, and a feed that merges the top 10 tweets across all followees (plus the user themselves). Global ordering is a single monotonic counter, not wall-clock time.

---

Requirements

Clarifying Questions

You: Tweet ordering — by a globally incrementing counter or by timestamp?

Interviewer: Globally incrementing counter. No timestamps needed.

So any atomic counter gives total ordering. No clock skew issues.

You: Does a user need to explicitly self-follow to see their own tweets in the feed?

Interviewer: No. Include own tweets automatically.

The peer set for the feed is followees ∪ {self}.

You: What is the scale?

Interviewer: Millions of users, average 100 tweets per user, average 200 followees.

Feed assembly reads at most 200 + 1 = 201 per-user deques. Heap merge is the right algorithm.

Final Requirements

1. postTweet(userId, tweetId) — append a tweet with a monotonically increasing order.
2. follow(follower, followee) / unfollow(follower, followee).
3. getNewsFeed(userId) — 10 most recent tweets from user + everyone they follow.
4. Thread-safe under concurrent posts and feed reads.

Out of scope: Direct messages, retweets, likes, deletions, media, notifications.

Deferred tradeoff: Unbounded per-user tweet lists grow forever; cap to the last few hundred per user in production, but that is a tweakable parameter.

---

Core Entities and Relationships

Two maps, one counter. Each user owns a deque of tweets (newest first). Each follower owns a set of followees. That is the whole state.

Entity	Responsibility
Tweet	(id, order) value.
User (implicit)	Per-user tweet deque + followee set — modeled as entries in two maps, not a dedicated class.
Twitter	Facade. Owns the counter, both maps, and the feed algorithm.

Why no User class? Because the only per-user state is a tweet list and a follow set. Making User a class adds indirection without giving you anything. If user profile data arrives, we will introduce it then.

Design is iterative. When scale blows past a single process, the per-user deques move to a distributed KV; the feed becomes a fanout-on-write vs. fanout-on-read decision.

---

Class Design

Tweet (value)

• id: int.
• order: long — unique, monotonically increasing.

Twitter

State:

• counter: AtomicLong — the global order counter.
• tweets: ConcurrentHashMap<Integer, Deque<Tweet>> — userId → newest-first deque.
• followees: ConcurrentHashMap<Integer, Set<Integer>>.
• FEED_SIZE = 10.

Methods: postTweet, follow, unfollow, getNewsFeed.

Java

public class Twitter {
    private static class Tweet {
        final int id;
        final long order;
        Tweet(int id, long order) { this.id = id; this.order = order; }
    }

    private final AtomicLong counter = new AtomicLong();
    private final Map<Integer, Deque<Tweet>> tweets = new ConcurrentHashMap<>();
    private final Map<Integer, Set<Integer>> followees = new ConcurrentHashMap<>();
    private static final int FEED_SIZE = 10;

    public void postTweet(int userId, int tweetId) { /* ... */ }
    public void follow(int follower, int followee) { /* ... */ }
    public void unfollow(int follower, int followee) { /* ... */ }
    public List<Integer> getNewsFeed(int userId) { /* ... */ }
}

C++

class Twitter {
    struct Tweet { int id; long order; };
    std::atomic<long> counter{0};
    std::unordered_map<int, std::deque<Tweet>> tweets;
    std::unordered_map<int, std::unordered_set<int>> followees;
    std::mutex mtx;
public:
    void postTweet(int uid, int tid);
    void follow(int a, int b);
    void unfollow(int a, int b);
    std::vector<int> getNewsFeed(int uid);
};

TypeScript

export class Twitter {
  private counter = 0;
  private tweets = new Map<number, { id: number; order: number }[]>();  // newest first
  private followees = new Map<number, Set<number>>();

  postTweet(userId: number, tweetId: number): void { /* ... */ }
  follow(a: number, b: number): void { /* ... */ }
  unfollow(a: number, b: number): void { /* ... */ }
  getNewsFeed(userId: number): number[] { /* ... */ }
}

Design principles at play:

• Facade: Twitter is the single entry point; internal maps are private.
• Information Expert: The counter lives where it is incremented (in Twitter).
• Merge-K-sorted algorithm: The feed is the interesting piece; the data structures are chosen to make it cheap.

---

Implementation

Core Logic: postTweet

1. Fetch the user's deque (lazy create).
2. Stamp the tweet with counter.incrementAndGet().
3. offerFirst to keep newest-first order.

Core Logic: follow / unfollow

Straightforward set operations on the followees map. Guard against unfollow(self, self) by returning early.

Core Logic: getNewsFeed (the interesting one)

Bad Solution: Collect every tweet from every followee into a single list, sort by order, take top 10. Cost: O(T log T) where T is total tweets across followees.

Good Solution: Per-user deques are already sorted newest-first. Merge-K-sorted using a max-heap over iterators. Each extraction is O(log K) and you need only 10. Total cost: O(K + 10 log K). For K = 201 peers, that is ~230 comparisons — thousands of times cheaper than the naive sort.

Great Solution: Same heap merge, but with early termination after 10 items. Also precompute the peer set with a Set to avoid duplicate self-follow traversal.

Implementations

Java

public void postTweet(int userId, int tweetId) {
    tweets.computeIfAbsent(userId, k -> new ConcurrentLinkedDeque<>())
          .offerFirst(new Tweet(tweetId, counter.incrementAndGet()));
}

public void follow(int follower, int followee) {
    followees.computeIfAbsent(follower, k -> ConcurrentHashMap.newKeySet()).add(followee);
}

public void unfollow(int follower, int followee) {
    if (follower == followee) return;
    Set<Integer> s = followees.get(follower);
    if (s != null) s.remove(followee);
}

public List<Integer> getNewsFeed(int userId) {
    Set<Integer> peers = new HashSet<>();
    peers.add(userId);
    Set<Integer> f = followees.get(userId);
    if (f != null) peers.addAll(f);

    PriorityQueue<PeekingIterator<Tweet>> pq = new PriorityQueue<>(
        (a, b) -> Long.compare(b.peek().order, a.peek().order)
    );
    for (int u : peers) {
        Deque<Tweet> d = tweets.get(u);
        if (d == null || d.isEmpty()) continue;
        pq.offer(new PeekingIterator<>(d.iterator()));
    }
    List<Integer> out = new ArrayList<>(FEED_SIZE);
    while (!pq.isEmpty() && out.size() < FEED_SIZE) {
        PeekingIterator<Tweet> it = pq.poll();
        out.add(it.next().id);
        if (it.hasNext()) pq.offer(it);
    }
    return out;
}

private static class PeekingIterator<T> implements Iterator<T> {
    private final Iterator<T> src;
    private T cached;
    private boolean has;
    PeekingIterator(Iterator<T> src) { this.src = src; advance(); }
    private void advance() { has = src.hasNext(); if (has) cached = src.next(); }
    public T peek() { return cached; }
    public boolean hasNext() { return has; }
    public T next() { T r = cached; advance(); return r; }
}

C++

void Twitter::postTweet(int uid, int tid) {
    std::lock_guard<std::mutex> lk(mtx);
    tweets[uid].push_front({tid, counter.fetch_add(1)});
}

void Twitter::follow(int a, int b) {
    std::lock_guard<std::mutex> lk(mtx);
    followees[a].insert(b);
}

void Twitter::unfollow(int a, int b) {
    if (a == b) return;
    std::lock_guard<std::mutex> lk(mtx);
    followees[a].erase(b);
}

std::vector<int> Twitter::getNewsFeed(int uid) {
    std::lock_guard<std::mutex> lk(mtx);
    std::unordered_set<int> peers{uid};
    if (followees.count(uid)) peers.insert(followees[uid].begin(), followees[uid].end());

    using It = std::pair<std::deque<Tweet>::const_iterator, std::deque<Tweet>::const_iterator>;
    auto cmp = [](const It& a, const It& b){ return a.first->order < b.first->order; };
    std::priority_queue<It, std::vector<It>, decltype(cmp)> pq(cmp);
    for (int u : peers) {
        auto it = tweets.find(u);
        if (it != tweets.end() && !it->second.empty())
            pq.emplace(it->second.begin(), it->second.end());
    }
    std::vector<int> out;
    while (!pq.empty() && out.size() < 10) {
        auto [cur, end] = pq.top(); pq.pop();
        out.push_back(cur->id);
        if (std::next(cur) != end) pq.emplace(std::next(cur), end);
    }
    return out;
}

TypeScript

postTweet(userId: number, tweetId: number): void {
  if (!this.tweets.has(userId)) this.tweets.set(userId, []);
  this.tweets.get(userId)!.unshift({ id: tweetId, order: ++this.counter });
}

follow(a: number, b: number): void {
  if (!this.followees.has(a)) this.followees.set(a, new Set());
  this.followees.get(a)!.add(b);
}

unfollow(a: number, b: number): void {
  if (a === b) return;
  this.followees.get(a)?.delete(b);
}

getNewsFeed(userId: number): number[] {
  const peers = new Set<number>([userId]);
  for (const p of this.followees.get(userId) ?? []) peers.add(p);
  // Cursor-based merge. Simulate a heap with a sorted-cursor array since JS has no built-in heap.
  type Ptr = { arr: { id: number; order: number }[]; i: number };
  const cursors: Ptr[] = [];
  for (const u of peers) {
    const arr = this.tweets.get(u);
    if (arr && arr.length > 0) cursors.push({ arr, i: 0 });
  }
  const out: number[] = [];
  while (out.length < 10 && cursors.length > 0) {
    let best = 0;
    for (let k = 1; k < cursors.length; k++) {
      if (cursors[k].arr[cursors[k].i].order > cursors[best].arr[cursors[best].i].order) best = k;
    }
    const c = cursors[best];
    out.push(c.arr[c.i].id);
    c.i++;
    if (c.i >= c.arr.length) cursors.splice(best, 1);
  }
  return out;
}

Thread Safety

ConcurrentHashMap for both user → tweets and follower → followees. ConcurrentLinkedDeque for the per-user tweet list. AtomicLong counter.

Read-while-post race: getNewsFeed might see a tweet mid-insertion. offerFirst is atomic, so either the tweet is visible or it is not — no torn state. The iteration order during a concurrent offerFirst may skip the new head, which is acceptable (the feed is eventually consistent).

For unfollow-while-reading: the peers set is snapshotted at the start of getNewsFeed, so a concurrent unfollow does not affect the in-flight read.

Verification

Sequence: post(1, 101), post(2, 201), follow(1, 2), post(2, 202), getNewsFeed(1).

Step	tweets	followees
post(1, 101)	1: [T(101, order=1)]	{}
post(2, 201)	2: [T(201, 2)]	{}
follow(1, 2)	unchanged	1 →
post(2, 202)	2: [T(202, 3), T(201, 2)]	unchanged
feed(1)	peers = {1, 2}; heap pops order 3 → 202, order 2 → 201, order 1 → 101	returns [202, 201, 101]

Trace the heap: start with two cursors, one at T(202, 3) and one at T(101, 1). Peek the max → 3 → pop 202 → advance cursor to T(201, 2). Peek again → 2 → pop 201 → advance cursor; that deque exhausted. Peek → 1 → pop 101. Output order: [202, 201, 101].

---

Complete Code Implementation

Java

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;

public class Twitter {
    private static class Tweet {
        final int id;
        final long order;
        Tweet(int id, long order) { this.id = id; this.order = order; }
    }

    private final AtomicLong counter = new AtomicLong();
    private final Map<Integer, Deque<Tweet>> tweets = new ConcurrentHashMap<>();
    private final Map<Integer, Set<Integer>> followees = new ConcurrentHashMap<>();
    private static final int FEED_SIZE = 10;

    public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, k -> new ConcurrentLinkedDeque<>())
              .offerFirst(new Tweet(tweetId, counter.incrementAndGet()));
    }

    public void follow(int follower, int followee) {
        followees.computeIfAbsent(follower, k -> ConcurrentHashMap.newKeySet()).add(followee);
    }

    public void unfollow(int follower, int followee) {
        if (follower == followee) return;
        Set<Integer> s = followees.get(follower);
        if (s != null) s.remove(followee);
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> peers = new HashSet<>();
        peers.add(userId);
        Set<Integer> f = followees.get(userId);
        if (f != null) peers.addAll(f);

        PriorityQueue<PeekingIterator<Tweet>> pq = new PriorityQueue<>(
            (a, b) -> Long.compare(b.peek().order, a.peek().order));
        for (int u : peers) {
            Deque<Tweet> d = tweets.get(u);
            if (d == null || d.isEmpty()) continue;
            pq.offer(new PeekingIterator<>(d.iterator()));
        }
        List<Integer> out = new ArrayList<>(FEED_SIZE);
        while (!pq.isEmpty() && out.size() < FEED_SIZE) {
            PeekingIterator<Tweet> it = pq.poll();
            out.add(it.next().id);
            if (it.hasNext()) pq.offer(it);
        }
        return out;
    }

    private static class PeekingIterator<T> implements Iterator<T> {
        private final Iterator<T> src;
        private T cached;
        private boolean has;
        PeekingIterator(Iterator<T> src) { this.src = src; advance(); }
        private void advance() { has = src.hasNext(); if (has) cached = src.next(); }
        public T peek() { return cached; }
        public boolean hasNext() { return has; }
        public T next() { T r = cached; advance(); return r; }
    }
}

C++

#include <algorithm>
#include <atomic>
#include <deque>
#include <mutex>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>

class Twitter {
    struct Tweet { int id; long order; };
    std::atomic<long> counter{0};
    std::unordered_map<int, std::deque<Tweet>> tweets;
    std::unordered_map<int, std::unordered_set<int>> followees;
    std::mutex mtx;
public:
    void postTweet(int uid, int tid) {
        std::lock_guard<std::mutex> lk(mtx);
        tweets[uid].push_front({tid, counter.fetch_add(1)});
    }
    void follow(int a, int b) {
        std::lock_guard<std::mutex> lk(mtx);
        followees[a].insert(b);
    }
    void unfollow(int a, int b) {
        if (a == b) return;
        std::lock_guard<std::mutex> lk(mtx);
        followees[a].erase(b);
    }
    std::vector<int> getNewsFeed(int uid) {
        std::lock_guard<std::mutex> lk(mtx);
        std::unordered_set<int> peers{uid};
        if (followees.count(uid)) peers.insert(followees[uid].begin(), followees[uid].end());
        using It = std::pair<std::deque<Tweet>::const_iterator, std::deque<Tweet>::const_iterator>;
        auto cmp = [](const It& a, const It& b){ return a.first->order < b.first->order; };
        std::priority_queue<It, std::vector<It>, decltype(cmp)> pq(cmp);
        for (int u : peers) {
            auto it = tweets.find(u);
            if (it != tweets.end() && !it->second.empty())
                pq.emplace(it->second.begin(), it->second.end());
        }
        std::vector<int> out;
        while (!pq.empty() && out.size() < 10) {
            auto [cur, end] = pq.top(); pq.pop();
            out.push_back(cur->id);
            if (std::next(cur) != end) pq.emplace(std::next(cur), end);
        }
        return out;
    }
};

TypeScript

export class Twitter {
  private counter = 0;
  private tweets = new Map<number, { id: number; order: number }[]>();
  private followees = new Map<number, Set<number>>();

  postTweet(userId: number, tweetId: number): void {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId)!.unshift({ id: tweetId, order: ++this.counter });
  }

  follow(a: number, b: number): void {
    if (!this.followees.has(a)) this.followees.set(a, new Set());
    this.followees.get(a)!.add(b);
  }

  unfollow(a: number, b: number): void {
    if (a === b) return;
    this.followees.get(a)?.delete(b);
  }

  getNewsFeed(userId: number): number[] {
    const peers = new Set<number>([userId]);
    for (const p of this.followees.get(userId) ?? []) peers.add(p);
    type Ptr = { arr: { id: number; order: number }[]; i: number };
    const cursors: Ptr[] = [];
    for (const u of peers) {
      const arr = this.tweets.get(u);
      if (arr && arr.length > 0) cursors.push({ arr, i: 0 });
    }
    const out: number[] = [];
    while (out.length < 10 && cursors.length > 0) {
      let best = 0;
      for (let k = 1; k < cursors.length; k++) {
        if (cursors[k].arr[cursors[k].i].order > cursors[best].arr[cursors[best].i].order) best = k;
      }
      const c = cursors[best];
      out.push(c.arr[c.i].id);
      c.i++;
      if (c.i >= c.arr.length) cursors.splice(best, 1);
    }
    return out;
  }
}

---

Extensibility

1. "Celebrities with millions of followers?"

Fanout-on-read for celebrities (do not precompute their followers' feeds — the fan-out is huge). Fanout-on-write for normal users (pre-push tweets into each follower's inbox). Combine both: "hybrid" fanout.

Flag users above a threshold as celebrities. On post, the system decides the strategy per user.

Tradeoff: Hybrid is the most expensive to reason about but the only one that scales to Twitter-sized social graphs.

2. "Pagination — load older tweets?"

Add a sinceOrder parameter to getNewsFeed. The heap-merge ignores tweets with order >= sinceOrder and returns the next 10 below it.

public List<Integer> getNewsFeed(int userId, long sinceOrder) {
    // filter each cursor's starting position to first tweet with order < sinceOrder
}

3. "Delete tweet?"

Add a deleted: boolean flag on Tweet. Skip deleted tweets during feed assembly. Lazy deletion avoids the cost of rewriting the deque on delete.

Tradeoff: Deleted tweets still consume memory until eviction. If tombstone accumulation is a concern, schedule a compaction pass.

---

What is Expected at Each Level

Level	Expectations
Junior (L4)	Flat global tweet list; O(N) scan per feed.
Mid (L5)	Per-user deque, naive flatten-and-sort for feed.
Senior (L5A)	Heap-merge with PeekingIterator for O(K + 10 log K). ConcurrentHashMap + ConcurrentLinkedDeque for thread safety. Mentions Twitter-sized fanout as a scale-out extension.
Staff (L6)	Fanout-on-write vs. fanout-on-read vs. hybrid, Redis-backed feeds, caching strategy, read-your-writes guarantees, anti-abuse filters, ranking by ML signals.