355.Design Twitter

Tags: [heap], [map], [data_structure]

Link: https://leetcode.com/problems/design-twitter/#/description

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user's news feed. Your design should support the following methods:

1. postTweet(userId, tweetId): Compose a new tweet.
2. getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
3. follow(followerId, followeeId): Follower follows a followee.
4. unfollow(followerId, followeeId): Follower unfollows a followee.

Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

Solution: heap, map

import time

class Twitter(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.user_to_tweets = {}
        self.user_to_followees = {}

    def postTweet(self, userId, tweetId):
        """
        Compose a new tweet.
        :type userId: int
        :type tweetId: int
        :rtype: void
        """
        tweet = (tweetId, userId, time.time())
        if userId not in self.user_to_tweets:
            self.user_to_tweets[userId] = [tweet]
        else:
            self.user_to_tweets[userId].append(tweet)

    def getNewsFeed(self, userId):
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        :type userId: int
        :rtype: List[int]
        """
        tweets = []
        tweets += self.user_to_tweets.get(userId, [])
        for followee in self.user_to_followees.get(userId, set()):
            tweets += self.user_to_tweets.get(followee, [])

        max_heap = self.build_max_heap(tweets)
        heap_size = len(max_heap)

        news_feed = []
        while heap_size and len(news_feed) < 10:
            tweet = self.heap_pop(max_heap, heap_size)
            news_feed.append(tweet[0])
            heap_size -= 1

        return news_feed


    def build_max_heap(self, tweets):
        if not tweets:
            return []

        size = len(tweets)
        for i in xrange(((size - 1) - 1) / 2, -1, -1):
            self.heapify(tweets, i, size)

        return tweets

    def heapify(self, heap, index, size):
        curr = heap[index][2]
        new_curr_index = index

        if 2 * index + 1 < size:
            left = heap[2 * index + 1][2]
            if curr < left:
                curr, left = left, curr
                new_curr_index = 2 * index + 1

        if 2 * index + 2 < size:
            right = heap[2 * index + 2][2]
            if curr < right:
                curr, right = right, curr
                new_curr_index = 2 * index + 2

        if index != new_curr_index:
            heap[index], heap[new_curr_index] = heap[new_curr_index], heap[index]
            self.heapify(heap, new_curr_index, size)

    def heap_pop(self, heap, heap_size):
        if not heap_size:
            raise ValueError('heap is empty')

        root = heap[0]
        heap[0], heap[heap_size - 1] = heap[heap_size - 1], heap[0]
        self.heapify(heap, 0, heap_size - 1)
        return root

    def follow(self, followerId, followeeId):
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        :type followerId: int
        :type followeeId: int
        :rtype: void
        """
        if followerId == followeeId:
            return
        if followerId not in self.user_to_followees:
            self.user_to_followees[followerId] = set([followeeId])
        else:
            self.user_to_followees[followerId].add(followeeId)

    def unfollow(self, followerId, followeeId):
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        :type followerId: int
        :type followeeId: int
        :rtype: void
        """
        if followerId == followeeId:
            return
        if followerId in self.user_to_followees and followeeId in self.user_to_followees[followerId]:
            self.user_to_followees[followerId].remove(followeeId)

# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)

Revelation:

• Build the heap, heapify, heap_pop, heap sort, reference: https://zhaonanli.gitbooks.io/algorithm/content/heap-sort.html
• When we meet this kind of the problem, we can start from thinking some straight forward solution, then do the optimization for it. Don't need get the most optimal solution at very beginning.

Note:

• In Python, heapq.heapify(), heapq.heappush(), and heapq.heappop() don't accept the "key" argument. But we can define a custom class and override the __cmp__ function to guide the heapq, how to do the heapify. (But for this question, Leetcode compiler doesn't allow you to define a custom class, so I just implement my own heap).
• Time complexity of "postTweet" = O(1).
• Time complexity of "getNewsFeed" = O(n * k * lg10), n = (number of followees) + 1, k = (max(number of tweets of followee)).

Solution: PriorityQueue

from Queue import PriorityQueue
import time

class Twitter(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.user_to_tweets = {}
        self.user_to_followees = {}

    def postTweet(self, userId, tweetId):
        """
        Compose a new tweet.
        :type userId: int
        :type tweetId: int
        :rtype: void
        """
        tweet = (tweetId, userId, time.time())
        if userId not in self.user_to_tweets:
            self.user_to_tweets[userId] = [tweet]
        else:
            self.user_to_tweets[userId].append(tweet)

    def getNewsFeed(self, userId):
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        :type userId: int
        :rtype: List[int]
        """
        prio_queue = PriorityQueue()
        for tweet in self.user_to_tweets.get(userId, []):
            prio_queue.put((-tweet[2], tweet))

        for followee in self.user_to_followees.get(userId, []):
            for tweet in self.user_to_tweets.get(followee, []):
                prio_queue.put((-tweet[2], tweet))

        news_feed = []
        while not prio_queue.empty() and len(news_feed) < 10:
            _, tweet = prio_queue.get()
            news_feed.append(tweet[0])

        return news_feed

    def follow(self, followerId, followeeId):
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        :type followerId: int
        :type followeeId: int
        :rtype: void
        """
        if followerId == followeeId:
            return
        if followerId not in self.user_to_followees:
            self.user_to_followees[followerId] = set([followeeId])
        else:
            self.user_to_followees[followerId].add(followeeId)

    def unfollow(self, followerId, followeeId):
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        :type followerId: int
        :type followeeId: int
        :rtype: void
        """
        if followerId == followeeId:
            return
        if followerId in self.user_to_followees and followeeId in self.user_to_followees[followerId]:
            self.user_to_followees[followerId].remove(followeeId)

# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)

Note:

• In Python, PriorityQueue, can accept the tuple as input, the first element of the tuple is the weight of the entry, which guide how PriorityQueue sort these entries inside. Here we use (-timestamp) as the weight of the tweet.
• Time complexity of "getNewsFeed" = O(max(lg((n * k)!), (n * k * lg10))), n = (number of followees) + 1, k = max(number of tweets of followee).
• lg(a) + lg(b) + lg(c) = lg(a*b*c).