Description
Support posting uniquely identified tweets, following and unfollowing users, and retrieving up to ten newest tweet IDs from a user's own posts and followed users. Newer posts appear first.
Solution
def create_twitter():
return {"clock": 0, "posts": {}, "follows": {}}
def post_tweet(state, user_id, tweet_id):
state["clock"] += 1
state["posts"].setdefault(user_id, []).append((state["clock"], tweet_id))
def follow(state, follower_id, followee_id):
state["follows"].setdefault(follower_id, set()).add(followee_id)
def unfollow(state, follower_id, followee_id):
state["follows"].get(follower_id, set()).discard(followee_id)
def get_news_feed(state, user_id):
users = state["follows"].get(user_id, set()) | {user_id}
posts = [post for user in users for post in state["posts"].get(user, [])]
return [tweet for _, tweet in sorted(posts, reverse=True)[:10]]Examples
Example 1
- Input
[["Twitter"],["postTweet",1,5],["getNewsFeed",1],["follow",1,2],["postTweet",2,6],["getNewsFeed",1],["unfollow",1,2],["getNewsFeed",1]]- Output
[null,null,[5],null,null,[6,5],null,[5]]
Following includes user 2's tweet; unfollowing removes it.
Example 2
- Input
[["Twitter"],["getNewsFeed",9]]- Output
[null,[]]
A new user has an empty feed.
Example 3
- Input
[["Twitter"],["postTweet",1,100],["postTweet",1,2],["getNewsFeed",1]]- Output
[null,null,null,[2,100]]
Sequence numbers, not IDs, determine recency.
Approach
Assign each post a growing sequence number. Keep follow sets and per-user posts. To build a feed, collect posts from the user and their followees, sort by sequence descending, and return at most ten. Treat self-follow as redundant.
Time & space
post and follow updates: expected O(1). Feed: O(P log P) time and O(P) auxiliary space for P relevant posts. Persistent space O(T + F) for T posts and F follow relationships.