Design Twitter Visualizer

Calls pointer walks the calls · return value underneath

Users followMap · tweetMap, oldest to newest

minHeap one entry per followee: their newest unread tweet · newest at the root

minHeap list tweet id in the box, its author below

res the feed being built, newest first

class Twitter { private int count; // counts down: newer = smaller private Map<Integer, List<int[]>> tweetMap; // {count, id} private Map<Integer, Set<Integer>> followMap; public Twitter() { count = 0; tweetMap = new HashMap<>(); followMap = new HashMap<>(); } public void postTweet(int userId, int tweetId) { tweetMap.putIfAbsent(userId, new ArrayList<>()); tweetMap.get(userId).add(new int[]{count, tweetId}); count--; } public List<Integer> getNewsFeed(int userId) { List<Integer> res = new ArrayList<>(); PriorityQueue<int[]> minHeap = new PriorityQueue<>( (a, b) -> a[0] - b[0]); followMap.putIfAbsent(userId, new HashSet<>()); followMap.get(userId).add(userId); for (int followeeId : followMap.get(userId)) { if (tweetMap.containsKey(followeeId)) { List<int[]> list = tweetMap.get(followeeId); int index = list.size() - 1; int[] t = list.get(index); minHeap.offer(new int[]{ t[0], t[1], followeeId, index - 1}); } } while (!minHeap.isEmpty() && res.size() < 10) { int[] top = minHeap.poll(); res.add(top[1]); int index = top[3]; if (index >= 0) { int[] t = tweetMap.get(top[2]).get(index); minHeap.offer(new int[]{ t[0], t[1], top[2], index - 1}); } } return res; } public void follow(int followerId, int followeeId) { followMap.putIfAbsent(followerId, new HashSet<>()); followMap.get(followerId).add(followeeId); } public void unfollow(int followerId, int followeeId) { if (followMap.containsKey(followerId)) { followMap.get(followerId).remove(followeeId); } }}

call: —
count: 0
minHeap: []
res: []
returned: []

Why it works

Brute force gathers every tweet from the user and everyone they follow, sorts by time and keeps 10: O(T log T) per feed, where T can be every tweet ever posted.
Each user's tweet list is already sorted by time, so the feed is a k-way merge of sorted lists. Put each followee's newest tweet in a heap; the root is the newest of all. After popping it, push that author's next older tweet. Invariant: the heap holds exactly one unread tweet per followee that still has some, the newest one.
Cost: building the heap is f pushes, O(f log f), then at most 10 pops and pushes on a heap of size ≤ f, O(10 log f). A bottom-up heapify would cut the build to O(f); with PriorityQueue the f offers cost O(f log f), which is fine for a handful of followees.
Pitfalls: the global count goes down, so the newest tweet has the smallest count and the min-heap PriorityQueue pops it first. A user's own tweets count: getNewsFeed adds the user to their own follow set. And unfollowing someone you do not follow must be a no-op: Set.remove just returns false, but a follower with no set yet must not hit a NullPointerException, hence the containsKey check.
Related: Merge k Sorted Lists (23) is the same heap merge over linked lists.