Design Twitter: merge k sorted timeline bằng heap

Bài toán này trông như một câu hỏi mini systems design — xây dựng một bản Twitter đơn giản với postTweet, follow, unfollow, và getNewsFeed. Nhưng khi bóc tách lớp ngôn ngữ sản phẩm, câu đố cốt lõi là: cho tối đa 500 user, mỗi người giữ một timeline cá nhân theo thứ tự thời gian, trả về 10 tweet gần nhất của người dùng và những người họ follow. Đó là bài toán top-10 merge của k sorted list. Cấu trúc dữ liệu bạn chọn quyết định getNewsFeed tốn O(N log N) trên tổng số tweet hay O(F log F) trên số lượng followee.

Đề bài

Thiết kế một phiên bản đơn giản của Twitter cho phép user đăng tweet, follow/unfollow người khác, và xem 10 tweet gần nhất trong news feed — bao gồm tweet của chính họ lẫn của những người họ đang follow, sắp xếp từ mới nhất đến cũ nhất. Đề gốc: LeetCode 355.

Ràng buộc:
- 1 <= userId, followerId, followeeId <= 500
- 0 <= tweetId <= 10^4
- Tất cả tweet đều có ID duy nhất.
- Có tối đa 3 * 10^4 lần gọi đến postTweet, getNewsFeed, follow, và unfollow.
- User không thể follow chính mình.

Constraints nói gì

1 <= userId, followerId, followeeId <= 500. Tối đa 500 user. Một hash map với key là userId là lựa chọn hiển nhiên. Giới hạn này cũng cho biết heap trong approach tối ưu không bao giờ có quá 500 entry — một entry mỗi followee — nên getNewsFeed bị chặn bởi O(500 * log 500), một hằng số trong thực tế.

0 <= tweetId <= 10^4. TweetId nhỏ, nhưng bài toán ghi rõ mỗi lần gọi postTweet dùng một tweetId duy nhất. Không thể dùng tweetId làm timestamp vì uniqueness trong [0, 10^4] không đảm bảo thứ tự thời gian — tweet ID 3 có thể được post sau tweet ID 7. Bạn cần một counter đơn điệu riêng.

Tối đa 3 * 10^4 lần gọi tổng cộng. Với tới 30,000 lần postTweet, approach ngây thơ sort toàn bộ N tweet mỗi lần getNewsFeed tốn O(N log N) mỗi lần gọi. Heap approach tránh hoàn toàn điều đó: getNewsFeed chỉ đụng vào đầu timeline của mỗi followee.

Approach 1: Brute force — danh sách toàn cục và sort mỗi lần đọc

Thứ đơn giản nhất hoạt động được: giữ một list phẳng tất cả tweet toàn hệ thống, tag với (userId, tweetId, timestamp). Mỗi lần getNewsFeed, lọc theo danh sách người dùng follow (cộng với chính họ), sort giảm dần theo timestamp, trả về 10 cái đầu.

from typing import List
 
class Twitter:
    def __init__(self):
        self.tweets: List[tuple] = []  # (userId, tweetId, timestamp)
        self.follows: dict = {}        # userId -> set of followeeIds
        self.timestamp: int = 0
 
    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets.append((userId, tweetId, self.timestamp))
        self.timestamp += 1
 
    def getNewsFeed(self, userId: int) -> List[int]:
        followees = self.follows.get(userId, set()).copy()
        followees.add(userId)
        relevant = [
            (tweet_id, ts)
            for uid, tweet_id, ts in self.tweets
            if uid in followees
        ]
        relevant.sort(key=lambda x: x[1], reverse=True)
        return [tweet_id for tweet_id, _ in relevant[:10]]
 
    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId == followeeId:
            return
        self.follows.setdefault(followerId, set()).add(followeeId)
 
    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId in self.follows:
            self.follows[followerId].discard(followeeId)

using System;
using System.Collections.Generic;
using System.Linq;
 
public class Twitter {
    private List<(int UserId, int TweetId, int Timestamp)> tweets;
    private Dictionary<int, HashSet<int>> follows;
    private int timestamp;
 
    public Twitter() {
        tweets = new List<(int, int, int)>();
        follows = new Dictionary<int, HashSet<int>>();
        timestamp = 0;
    }
 
    public void PostTweet(int userId, int tweetId) {
        tweets.Add((userId, tweetId, timestamp++));
    }
 
    public IList<int> GetNewsFeed(int userId) {
        var followees = new HashSet<int>();
        if (follows.ContainsKey(userId))
            foreach (var f in follows[userId]) followees.Add(f);
        followees.Add(userId);
 
        return tweets
            .Where(t => followees.Contains(t.UserId))
            .OrderByDescending(t => t.Timestamp)
            .Take(10)
            .Select(t => t.TweetId)
            .ToList();
    }
 
    public void Follow(int followerId, int followeeId) {
        if (followerId == followeeId) return;
        if (!follows.ContainsKey(followerId))
            follows[followerId] = new HashSet<int>();
        follows[followerId].Add(followeeId);
    }
 
    public void Unfollow(int followerId, int followeeId) {
        if (follows.ContainsKey(followerId))
            follows[followerId].Remove(followeeId);
    }
}

Độ phức tạp. postTweet: O(1). getNewsFeed: O(N log N) với N là tổng số tweet đã được post. follow/unfollow: O(1). Space: O(N + F) với F là tổng số follow relationship.

Vấn đề rõ ràng: khi số tweet tăng lên, mỗi lần getNewsFeed trả O(N log N) dù người dùng chỉ follow 3 người. Brute force đụng vào toàn bộ lịch sử chỉ để tìm 10 item. Dữ liệu bạn cần — tweet gần nhất của mỗi followee — bị chôn vùi trong đống dữ liệu chưa được tổ chức.

Approach 2: Per-user linked list được merge bằng heap

Insight cốt lõi: tweet của một user luôn đến theo thứ tự thời gian. Nếu bạn lưu tweet của mỗi user dưới dạng linked list (mới nhất ở đầu), bạn đã có F sorted sequence. Merge F sorted sequence để lấy top-10 element chính là pattern "merge k sorted lists" — và một max heap làm điều đó trong O(F log F) mà không cần đụng vào phần lớn dữ liệu.

Cấu trúc:

• user_tweets: hash map từ userId đến head của linked list tweet.
• follows: hash map từ userId đến set followeeId.
• Một counter timestamp đơn điệu toàn cục, tăng mỗi lần postTweet.

Mỗi tweet node giữ tweet_id, timestamp, và pointer next đến tweet trước đó của user (tweet cũ hơn).

import heapq
from typing import List, Optional
 
class Tweet:
    def __init__(self, tweet_id: int, timestamp: int):
        self.tweet_id = tweet_id
        self.timestamp = timestamp
        self.next: Optional['Tweet'] = None
 
class Twitter:
    def __init__(self):
        self.user_tweets: dict = {}   # userId -> Tweet (head)
        self.follows: dict = {}       # userId -> set of followeeIds
        self.timestamp: int = 0
 
    def postTweet(self, userId: int, tweetId: int) -> None:
        new_tweet = Tweet(tweetId, self.timestamp)
        self.timestamp += 1
        new_tweet.next = self.user_tweets.get(userId)
        self.user_tweets[userId] = new_tweet
 
    def getNewsFeed(self, userId: int) -> List[int]:
        followees = self.follows.get(userId, set()).copy()
        followees.add(userId)
 
        # Max heap theo timestamp (negate vì Python dùng min-heap)
        heap = []
        for fid in followees:
            head = self.user_tweets.get(fid)
            if head:
                heapq.heappush(heap, (-head.timestamp, head))
 
        result = []
        while heap and len(result) < 10:
            _, tweet = heapq.heappop(heap)
            result.append(tweet.tweet_id)
            if tweet.next:
                heapq.heappush(heap, (-tweet.next.timestamp, tweet.next))
 
        return result
 
    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId == followeeId:
            return
        self.follows.setdefault(followerId, set()).add(followeeId)
 
    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId in self.follows:
            self.follows[followerId].discard(followeeId)

using System;
using System.Collections.Generic;
 
public class Tweet {
    public int TweetId;
    public int Timestamp;
    public Tweet Next;
 
    public Tweet(int tweetId, int timestamp) {
        TweetId = tweetId;
        Timestamp = timestamp;
        Next = null;
    }
}
 
public class Twitter {
    private Dictionary<int, Tweet> userTweets;
    private Dictionary<int, HashSet<int>> follows;
    private int timestamp;
 
    public Twitter() {
        userTweets = new Dictionary<int, Tweet>();
        follows = new Dictionary<int, HashSet<int>>();
        timestamp = 0;
    }
 
    public void PostTweet(int userId, int tweetId) {
        var newTweet = new Tweet(tweetId, timestamp++);
        if (userTweets.ContainsKey(userId))
            newTweet.Next = userTweets[userId];
        userTweets[userId] = newTweet;
    }
 
    public IList<int> GetNewsFeed(int userId) {
        var followees = new HashSet<int>();
        if (follows.ContainsKey(userId))
            foreach (var f in follows[userId]) followees.Add(f);
        followees.Add(userId);
 
        // C# PriorityQueue (min-heap mặc định); negate timestamp để có max behavior
        var pq = new PriorityQueue<Tweet, int>();
        foreach (var fid in followees) {
            if (userTweets.TryGetValue(fid, out var head))
                pq.Enqueue(head, -head.Timestamp);
        }
 
        var result = new List<int>();
        while (pq.Count > 0 && result.Count < 10) {
            var tweet = pq.Dequeue();
            result.Add(tweet.TweetId);
            if (tweet.Next != null)
                pq.Enqueue(tweet.Next, -tweet.Next.Timestamp);
        }
        return result;
    }
 
    public void Follow(int followerId, int followeeId) {
        if (followerId == followeeId) return;
        if (!follows.ContainsKey(followerId))
            follows[followerId] = new HashSet<int>();
        follows[followerId].Add(followeeId);
    }
 
    public void Unfollow(int followerId, int followeeId) {
        if (follows.ContainsKey(followerId))
            follows[followerId].Remove(followeeId);
    }
}

Độ phức tạp. postTweet: O(1) — prepend vào linked list. getNewsFeed: O(F log F) để build heap ban đầu cộng O(10 log F) cho 10 bước extraction, tổng O(F log F). follow/unfollow: O(1). Space: O(T + F) với T là tổng số tweet và F là tổng số follow relationship.

Trace tay qua ví dụ

Chuỗi thao tác trong ví dụ:

postTweet(1, 5)   # timestamp=0, user 1 head: [5, t=0]
getNewsFeed(1)    # followees = {1}, heap: [(-0, tweet_5)], pop -> [5]
follow(1, 2)      # follows[1] = {2}
postTweet(2, 6)   # timestamp=1, user 2 head: [6, t=1]
getNewsFeed(1)    # followees = {1, 2}
unfollow(1, 2)    # follows[1] = {}
getNewsFeed(1)    # followees = {1}

Phần thú vị nhất là getNewsFeed(1) sau cả hai lần post và follow:

followees = {1, 2}

Build heap:
  user 1 head: tweet(id=5, t=0)  -> push (-0, tweet_5)
  user 2 head: tweet(id=6, t=1)  -> push (-1, tweet_6)

heap = [(-1, tweet_6), (-0, tweet_5)]  # min-heap, -1 nhỏ hơn nên tweet_6 ra trước

Pop 1: tweet_6 (t=1, id=6)  -> result = [6], tweet_6.next = None, không push gì
Pop 2: tweet_5 (t=0, id=5)  -> result = [6, 5], tweet_5.next = None, không push gì

heap rỗng, len(result) = 2 < 10, vòng lặp kết thúc.
Return [6, 5]

Sau unfollow(1, 2), getNewsFeed(1) chỉ thấy followees = {1}. Heap bắt đầu chỉ với tweet_5, pop nó, và trả về [5]. Tweet_6 không bao giờ được đụng vì user 2 không còn trong followee set.

Các edge case thực sự quan trọng

User không có tweet nào gọi getNewsFeed: phép kiểm tra user_tweets.get(fid) trả về None, không có gì được push vào heap. Danh sách kết quả trả về rỗng, đúng với yêu cầu.

User không follow ai: follows.get(userId, set()) trả về empty set; sau khi thêm userId vào, followee set chỉ có {userId}. Feed chỉ hiển thị tweet của chính user. Đúng.

unfollow gọi với relationship không tồn tại: discard trong Python và Remove trong C# là no-op với phần tử không tồn tại. Không có exception nào bị throw. Hoàn toàn safe.

Ít hơn 10 tweet tổng cộng: vòng lặp while heap and len(result) < 10 thoát khi heap rỗng. Kết quả là danh sách không đủ 10 phần tử — đúng với yêu cầu bài toán ("retrieves the 10 most recent" — trả về ít hơn nếu không đủ).

Guard self-follow: constraint ghi rõ "A user cannot follow himself", và implementation của chúng ta enforce điều này bằng early return khi followerId == followeeId. Logic heap sẽ không bị phá vỡ nếu thiếu guard này — user đã xuất hiện trong followee set từ trước — nhưng nó sẽ gây duplicate work và có thể làm follows map bị sai.

Bảng so sánh

N = tổng số tweet đã post. F = số followee của user đang xem feed (bị chặn bởi 500). T = tổng số tweet. Heap approach tách chi phí getNewsFeed khỏi tổng tweet volume — user follow 3 người chỉ trả cho 3, không phải 30,000 tweet lịch sử.

Pattern nền tảng và khi nào nên dùng

Mental model ở đây là merge k sorted sequence bằng heap. Timeline của mỗi followee là một sequence đã được sort (timestamp giảm dần khi duyệt theo pointer next). Bạn không cần sort chúng với nhau toàn cục — chỉ cần phần tử lớn nhất tiếp theo tại bất kỳ thời điểm nào, và một heap gồm k head cho bạn điều đó trong O(log k).

Pattern này xuất hiện bất cứ khi nào bạn có nhiều stream đã được sort trước và cần top-m element mà không cần đọc tất cả. Heap hoạt động như một con trỏ ưu tiên: nó luôn trỏ vào phần tử đầu của mỗi stream, tiến lên phần tử thắng, và lặp lại cho đến khi có đủ kết quả.

Lựa chọn linked list cho timeline của mỗi user là có chủ đích. Prepend là O(1). Bạn không bao giờ cần random access vào lịch sử của một user — bạn luôn bắt đầu từ head và đi tiếp khi cần. Array cũng hoạt động (append + duyệt ngược), nhưng linked list làm rõ ý định "đi từ head về trước" và tránh index arithmetic.

Tôi sẽ ship cái nào và tại sao

Heap approach, không cần suy nghĩ. Brute force ổn cho demo 5 tweet nhưng xuống cấp tuyến tính theo tổng tweet volume — và tweet volume chính là thứ tăng mãi trong production. Heap approach chặn getNewsFeed ở O(F log F) với F bị giới hạn bởi 500. Xấu nhất là 500 * log(500) ~ 4,500 operation mỗi lần gọi. Đó là hằng số.

Tôi cũng lưu ý rằng C# PriorityQueue (có từ .NET 6) xử lý priority inversion gọn gàng bằng cách negate timestamp lúc push, khớp chính xác với pattern heapq của Python. Nếu runtime cũ hơn .NET 6, một SortedSet với custom comparer hoạt động nhưng cần tie-breaking cẩn thận để tránh hai entry có cùng timestamp bị collapse thành một.

Trong phỏng vấn thực tế, tôi sẽ code brute force trước để confirm interface đúng, sau đó đề xuất và implement heap upgrade với lý giải rõ ràng "đây là lý do version đầu không scale được."

Vị trí trong heap series

Series heap cho đến nay đã cover các bài toán selection tĩnh: Last Stone Weight (1046), Kth Largest Element (215), K Closest Points (973), Task Scheduler (621). Bài này thêm một chiều mới — heap không giữ câu trả lời cuối cùng, mà hoạt động như merge cursor trên nhiều stream độc lập. Đó là cách dùng cấu trúc dữ liệu khác hẳn về bản chất.

Merge k Sorted Lists (23) là dạng thuần túy của những gì getNewsFeed làm. Không có class, không có follow graph — chỉ là k linked list và một heap. Nếu bạn muốn cô lập bước merge khỏi phần bookkeeping, giải 23 trước.

Find Median from Data Stream (295) cũng giữ hai heap như cursor, nhưng trên một thứ tự sort duy nhất được chia tại median. Ý tưởng "heap như position tracker thay vì answer holder" là giống nhau; cách chia thì khác.

Design Twitter (bài này) với getNewsFeed thực chất là "Merge k Sorted Lists" với follow-graph filter quyết định k stream nào cần merge. Bỏ follow/unfollow ra, bài toán về cơ bản là bài 23.

Smallest Range Covering Elements from K Lists (632) là dạng tổng quát khó nhất: thay vì top-10, bạn cần cửa sổ nhỏ nhất chứa ít nhất một phần tử từ mỗi list. Skeleton heap-of-heads giống nhau, điều kiện dừng phức tạp hơn nhiều.