Room 04 · The Grind — Heap / Priority Queue

Design Twitter

MEDIUM✓ CHIP-TIMEDLC #355 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: A tiny social feed: post a tweet, follow or unfollow another user, and pull the 10 most recent tweets — yours and everyone you follow — newest first.

A miniature social feed lets users post tweets, follow or unfollow each other, and pull their own news feed — the 10 most recent tweets from themselves and everyone they follow, newest first.

Following is one-directional and users start unfollowed from everyone; a user's feed always includes their own tweets even without explicitly following themselves.

Every action — posting, following, unfollowing, and reading the feed — has to stay responsive as the number of users and tweets grows, not just correct on a small example.

user and tweet counts can reach the low thousands
the feed returns at most 10 tweets, most recent first
a user always sees their own tweets in their feed, follow or not
unfollowing someone not currently followed is simply ignored

EX 01

Twitter()

postTweet(1, 5)

getNewsFeed(1) → [5]

follow(1, 2)

postTweet(2, 6)

getNewsFeed(1) → [6, 5]

unfollow(1, 2)

getNewsFeed(1) → [5]

post, follow, post, unfollow — feed tracks each change

EX 02

Twitter()

postTweet(1, 101)

postTweet(1, 102)

postTweet(1, 103)

postTweet(1, 104)

postTweet(1, 105)

postTweet(1, 106)

postTweet(1, 107)

postTweet(1, 108)

postTweet(1, 109)

postTweet(1, 110)

postTweet(1, 111)

postTweet(1, 112)

getNewsFeed(1) → [112, 111, 110, 109, 108, 107, 106, 105, 104, 103]

twelve tweets from one user — feed truncates to the newest 10

EX 03

Twitter()

postTweet(1, 10)

postTweet(2, 20)

follow(1, 2)

postTweet(1, 11)

getNewsFeed(1) → [11, 20, 10]

interleaved posts across two users, merged by time

The hintstake only what you need

HINT 1 THE NUDGE

Every tweet needs a sense of 'when' relative to every other tweet, across every user — one global counter that only ever increases does that job.

HINT 2 THE STRUCTURE

A feed request only ever needs the freshest tail of each relevant user's tweets, not their whole history — trimming to the last 10 per user before comparing saves real work.

HINT 3 ONE STEP FROM THE ANSWER

Merge each followed user's most-recent tweets like merging sorted lists: seed a heap with one candidate per user, pop the newest, and pull that user's next-most-recent tweet in behind it, stopping once 10 are collected.

Coach's boardthe pattern, step by step

MERGING TWO TIMELINESPATTERN · HEAP-MERGE RECENT TWEETSpost(1,10) · post(2,20) · follow(1,2) · post(1,11) · getNewsFeed(1)

new Twitter

u1 post 10

u2 post 20

1 follows 2

u1 post 11

feed for 1

STATE

users → {}

follows → {}

STEP 1

Start empty. Every tweet gets a global time stamp so we can always tell what's newest across every user.

STEP 1 / 7 · ← → WORK TOO

The splitstwo paces, two languages

grind/design-twitter.py — RACE PACE

LANG ▸

PACE ▸

class Twitter:
    def __init__(self):
        self.time = 0
        self.userTweets = collections.defaultdict(list)  # user -> [(time, tweetId), ...]
        self.follows = collections.defaultdict(set)

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.userTweets[userId].append((self.time, tweetId))
        self.time += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        watch = self.follows[userId] | {userId}
        heap = []  # (-time, tweetId, user, indexIntoThatUsersList)
        for u in watch:
            lst = self.userTweets.get(u)
            if lst:
                idx = len(lst) - 1
                t, tid = lst[idx]
                heapq.heappush(heap, (-t, tid, u, idx))

        result = []
        while heap and len(result) < 10:
            _, tid, u, idx = heapq.heappop(heap)
            result.append(tid)
            if idx > 0:
                idx -= 1
                t2, tid2 = self.userTweets[u][idx]
                heapq.heappush(heap, (-t2, tid2, u, idx))
        return result

    def follow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].discard(followeeId)

TIME O(F LOG F) PER FEEDSPACE O(USERS + TWEETS)PYTHON · RACE PACE · 35 LN

class Twitter:
    def __init__(self):
        self.tweets = []  # (time, userId, tweetId), every tweet ever posted
        self.time = 0
        self.follows = collections.defaultdict(set)

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets.append((self.time, userId, tweetId))
        self.time += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        watch = self.follows[userId] | {userId}
        candidates = [t for t in self.tweets if t[1] in watch]  # touches the whole timeline
        candidates.sort(key=lambda t: -t[0])
        return [t[2] for t in candidates[:10]]

    def follow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].discard(followeeId)

TIME O(TOTAL TWEETS LOG TOTAL) PER FEEDSPACE O(TOTAL TWEETS)PYTHON · TRAINING PACE · 21 LN

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

    public Twitter() {
    }

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

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> watch = new HashSet<>(follows.getOrDefault(userId, Collections.emptySet()));
        watch.add(userId);

        // heap entries: [time, tweetId, user, indexIntoThatUsersList]
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int u : watch) {
            List<int[]> lst = userTweets.get(u);
            if (lst != null && !lst.isEmpty()) {
                int idx = lst.size() - 1;
                int[] tw = lst.get(idx);
                heap.offer(new int[] { tw[0], tw[1], u, idx });
            }
        }

        List<Integer> result = new ArrayList<>();
        while (!heap.isEmpty() && result.size() < 10) {
            int[] top = heap.poll();
            result.add(top[1]);
            int idx = top[3];
            if (idx > 0) {
                idx--;
                int[] tw = userTweets.get(top[2]).get(idx);
                heap.offer(new int[] { tw[0], tw[1], top[2], idx });
            }
        }
        return result;
    }

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

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

TIME O(F LOG F) PER FEEDSPACE O(USERS + TWEETS)JAVA · RACE PACE · 52 LN

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

    public Twitter() {
    }

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

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> watch = follows.getOrDefault(userId, Collections.emptySet());
        List<int[]> candidates = new ArrayList<>();
        for (int[] t : tweets) {
            if (t[1] == userId || watch.contains(t[1])) {
                candidates.add(t);
            }
        }
        candidates.sort((a, b) -> b[0] - a[0]);
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < Math.min(10, candidates.size()); i++) {
            result.add(candidates.get(i)[2]);
        }
        return result;
    }

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

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

TIME O(TOTAL TWEETS LOG TOTAL) PER FEEDSPACE O(TOTAL TWEETS)JAVA · TRAINING PACE · 39 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED