Capstone: mạng xã hội mini với graph và feed

Giới thiệu

Bạn dựng mạng xã hội mini chạy được. Có gợi ý bạn và bảng tin.

Kiến thức cần nhớ

Đồ thị theo dõi

• Mỗi người là một đỉnh, theo dõi là một mũi tên.
• Ví dụ đời thường: giống sơ đồ ai theo dõi ai.
• Cần hỏi nhanh: đang theo dõi ai, ai theo dõi mình.
• Bạn chung là người cả hai cùng theo dõi.

Gợi ý bạn bằng BFS

• BFS lan hai tầng từ bạn để tìm ứng viên.
• Chấm điểm bằng số bạn chung và tương tác.
• Ví dụ đời thường: giống giới thiệu bạn của bạn.
• Trả top 10 kèm lý do gợi ý.

Bảng tin và chống spam

• Bảng tin gom bài của người đang theo dõi.
• Chấm mỗi bài bằng độ mới và tương tác.
• Ví dụ đời thường: giống chọn tin hot lên đầu.
• Bloom filter chặn link độc trước khi đăng.

# tìm bạn chung đơn giản
def ban_chung(a, b):
    return a & b  # giao hai tập theo dõi
me = {"An", "Binh"}
ban = {"Binh", "Chi"}
print(ban_chung(me, ban))  # ra {'Binh'}

Ví dụ

• A theo dõi B, B theo dõi C -> gợi ý C cho A.
• Bài mới nhiều like -> xếp hạng cao hơn.

💻 Bài tập

Ngôn ngữ: Python 3 (hoặc Go). Dùng code đồ thị, heap, Bloom, cache các ngày trước. Nộp vào day-160-capstone/.

Bài 1: Mô hình dữ liệu và API

class SocialGraph:
    def follow(self, a: int, b: int): ...
    def unfollow(self, a: int, b: int): ...
    def following(self, a: int) -> set[int]: ...
    def followers(self, a: int) -> set[int]: ...
    def mutuals(self, a: int, b: int) -> set[int]: ...   # cùng theo dõi
    def post(self, user: int, text: str, ts: float) -> int: ...
    def like(self, user: int, post_id: int): ...

Sinh dữ liệu: 100.000 user, phân bố theo dõi theo luật lũy thừa (vài người rất nổi tiếng), 10^6 bài.

Bài 2: Gợi ý theo dõi và bảng tin

suggest cho user mới 0 theo dõi -> trả người nổi tiếng nhất
feed không chứa bài của người đã unfollow

Bài 3: Chống spam và đo (nâng cao)

1. Bloom filter 10^6 link độc. Bài chứa link độc bị chặn khi đăng.
2. Cache LRU cho feed 60 giây, xóa khi người mình theo dõi đăng bài.
3. Đo p50/p99 của suggest và feed với 1000 truy vấn ngẫu nhiên. So fan-out on write và on read cho người nổi tiếng: bộ nhớ và độ trễ.
4. REPORT.md: sơ đồ, bảng số liệu, đánh đổi push/pull.

✅ Tiêu chí hoàn thành

• API có test cho follow/unfollow/mutuals.
• suggest có lý do, feed đúng thứ tự điểm.
• Bảng push vs pull có số thật.
• Link độc bị chặn, có test.

❓ Câu hỏi ôn tập

1. Mũi tên theo dõi chỉ hướng nào?
2. BFS gợi ý bạn đi mấy tầng?
3. Bảng tin chấm bài bằng gì?
4. Bloom filter đặt ở đâu?

🌕 Bạn đã hoàn thành ngày 160. Làm hết bài tập phía trên rồi sang ngày tiếp theo.