File: news-feed-system/news_feed.py

Date: 2026-06-05

Time: 13:23

news-feed-system/news_feed.py

Purpose

This file implements the core of a News Feed System — the kind you'd design in a system design interview (think Twitter/Facebook feed). It owns the entire feed lifecycle: social graph management, post creation, feed generation, and ranking. Its central design question is the fan-out strategy: how and when posts get distributed to followers' feeds.

Key Components

Data Models

Enums

SocialGraph

Manages bidirectional follow relationships with two mirrored dicts (followers, following). All operations are O(1) via sets. Returns *copies* from getfollowers/getfollowing to prevent external mutation.

PostStore

Owns post persistence and retrieval. Maintains two indices:

getuserposts sorts on every call (no pre-sorted index), which is fine for an interview implementation but worth noting. like_post is idempotent — returns False if the user already liked.

NewsFeedService

The orchestrator. Configurable at construction time with strategy, ranking mode, celebrity threshold, and cache size.

feedcache: A dict[str, deque[str]] mapping user IDs to bounded deques of post IDs. The maxlen on the deque enforces the cache size limit — oldest entries are silently evicted when the deque is full. This is only used by push and hybrid strategies.

Key methods:

| Method | Contract |

|--------|----------|

| create_post | Creates post, conditionally fans out based on strategy |

| get_feed | Retrieves, ranks, paginates feed for a user |

| follow | Updates graph + backfills cache for push strategies |

| unfollow | Updates graph + purges author's posts from cache |

| _score | Computes ranking score: either raw timestamp or timestamp + log-engagement |

Patterns

Strategy pattern — The FeedStrategy enum selects between three distinct feed-generation paths (getfeedpush, getfeedpull, getfeedhybrid). The strategy is chosen at construction and affects both write path (createpost) and read path (get_feed).

Celebrity/hotspot optimization — The hybrid strategy uses celebrity_threshold (default 1000 followers) to split users into two tiers. Non-celebrities get push fan-out (write-time distribution). Celebrities skip fan-out; their posts are pulled at read time. This mirrors the real-world Twitter/Instagram approach to avoid O(millions) writes when a celebrity posts.

K-way merge — getfeedpull uses heapq.merge to merge pre-sorted per-user timelines into a single stream without materializing everything first. The key is negated (-p.createdat) to get newest-first ordering from the min-heap.

Cursor-based pagination — getfeed supports both offset pagination (page/pagesize) and cursor-based filtering (cursor as a timestamp). The cursor filter runs before ranking, so it works correctly with both chronological and relevance modes.

Dependencies

Imports: All stdlib — heapq (k-way merge), uuid (post/comment IDs), collections.defaultdict/deque (feed cache), dataclasses, enum, math.log (engagement scoring).

Imported by: testnewsfeed.py — the test suite exercises all three strategies and both ranking modes.

No external dependencies. This is a self-contained in-memory simulation.

Flow

Write Path (Post Creation)


create_post(author, content, ...)
  → PostStore.create_post()  (stores post, indexes by author)
  → strategy check:
      PUSH:   _fan_out_write → appendleft to every follower's deque
      HYBRID: if follower_count ≤ threshold → _fan_out_write
              else → no-op (pulled at read time)
      PULL:   no-op

Read Path (Feed Generation)


get_feed(user, page, cursor)
  → strategy dispatch:
      PUSH:   hydrate post IDs from deque cache
      PULL:   heapq.merge across all followed users' timelines
      HYBRID: push posts + pull from celebrity follows, deduplicate
  → cursor filter (created_at < cursor)
  → score each post (_score)
  → sort by score descending
  → paginate [start:start+page_size]

Follow/Unfollow

Follow backfills the new follower's cache with the followee's existing posts (for push/hybrid with non-celebrities). Unfollow purges the unfollowed user's posts from the cache via removeauthorfromcache, which does a full linear scan and rebuild of the deque.

Invariants

1. Idempotent likes — likepost checks userid in post.liked_by before incrementing. Returns False on duplicate.

2. Bounded cache — deque(maxlen=cache_size) guarantees the feed cache never exceeds the configured size per user.

3. Celebrity threshold determines fan-out path — In hybrid mode, a user with followercount > celebritythreshold is *never* pushed; they're always pulled. There's no migration if someone crosses the threshold after posts are already cached.

4. Feed cache stores IDs, not objects — Posts are hydrated at read time, so engagement counts are always current.

5. Comments require an existing post — add_comment raises ValueError if the post doesn't exist. This is the only explicit validation/error in the module.

Error Handling

Minimal, by design:

Topics to Explore

Beliefs