Python solution


  • 43
    class Twitter(object):
    
        def __init__(self):
            self.timer = itertools.count(step=-1)
            self.tweets = collections.defaultdict(collections.deque)
            self.followees = collections.defaultdict(set)
    
        def postTweet(self, userId, tweetId):
            self.tweets[userId].appendleft((next(self.timer), tweetId))
    
        def getNewsFeed(self, userId):
            tweets = heapq.merge(*(self.tweets[u] for u in self.followees[userId] | {userId}))
            return [t for _, t in itertools.islice(tweets, 10)]
    
        def follow(self, followerId, followeeId):
            self.followees[followerId].add(followeeId)
    
        def unfollow(self, followerId, followeeId):
            self.followees[followerId].discard(followeeId)

  • 0
    Y

    very concise! But can anybody explain this part of the code in getNewsFeed()? | {userId}


  • 0

    Just handling the "Each item in the news feed must be posted by users who the user followed or by the user herself."


  • 0

    @StefanPochmann: not sure if merging the heaps is the right thing to do. You could've used a heap in which you store only the heads and then do 10 extractions (similar to what we do when we merge k sorted linked lists. Check out https://leetcode.com/discuss/108303/simple-and-clean-python-code-o-logk-for-getting-news-feed, but I am sure you already noticed that. Beautiful code, as always.


  • 0

    @agave Um, that's exactly what heapq.merge does.


  • 0

    According to the documentation:

    heapq.merge(): "Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an iterator over the sorted values."

    Ok, it's an iterator, fair enough. But what is the complexity ofitertools.islice afterwards? Not sure about that.


  • 0

    Same complexity as yours. You implemented it differently, but you're really doing the exact same thing.


  • 0

    Cool, thanks.


  • 0

    I have learnt a lot about python technique from your answers, thx~ Python is cool and you use it in a cool way ~


  • 0
    C

    thanks a lot. That is a really elegant solution. I learned a lot


  • 0
    A

    A little bit optimized way for getNewsFeed.

        r = heapq.nlargest(10, chain.from_iterable(self._tweets[u][-10:] for u in ({userId} | self._follow[userId])), key = lambda x: x[1])
        return [x[0] for x in r]
    

    where
    x - tweet, (tweetId, tweetTime)

    For each user I get at most 10 latest tweets to the heap, not all.


  • 1

    @alexei5 No, that's actually much worse than mine. I'm not going through all of their tweets. Everything I use is lazy and doesn't look at more than it absolutely needs to. I recommend you read the source code of heapq.merge. Also, @agave's description above and his solution might help understand it.


  • 0
    A

    @StefanPochmann, yeah. You are right.
    Thank you!


  • 0
    K

    Concise and beautiful solution. You have deep insights of Python - Both the language and the programming paradim. Thanks for sharing.


  • 0
    C

    Wow, I like your code. Thank you for sharing. You are my mentor.


  • 0
    C

    @StefanPochmann :
    If i want to use timestamp instead of timer, I think i have to use sorted function instead of heapq.merge.

    def postTweet(self, userId, tweetId):
            self.tweets[userId].append((datetime.now(), tweetId))
    
    def getNewsFeed(self, userId):
            tweets = sorted(itertools.chain(*(self.tweets[followeeId] for followeeId in self.followees[userId] | {userId})), key=lambda pair: pair[0], reverse=True)
            return [tweet for timestampe, tweet in itertools.islice(tweets, 10)]
    

    Is there a better code?


  • 0
    L

    @StefanPochmann Would this be the equivalent of what you were trying to do in getNewsFeed()? I'm essentially going through all the tweets of user along with all the tweets of the user's followers. It seems like your getNewsFeed is doing the same thing, but I could be mistaken.

            h=[]
            for i in self.tweets[userId]:
                heapq.heappush(h,i)
            for i in self.followees[userId]:
                for j in self.tweets[i]:
                    heapq.heappush(h,j)
            res=[]
            i=0
            while h and i<10:
                res.append(heapq.heappop(h)[1])
                i+=1
            return res

  • 0

    @livelearn No, yours is less efficient. You push everything. Mine pushes only what's needed. That is, it first pushes only the first element of each source. And then when taking an element, it pushes only the next one from the same source. I still really recommend reading the heapq.merge source code. It's pretty easy to understand.


  • 0
    L

    @StefanPochmann Without looking into merge, I see that the input to merge is the self.followees[userId] | {userId} which gives the intersection of all possible values so isn't that the same in in my case since tweets I post are independent of what another user I follow posted?

    I guess are you saying heapq.merge is more efficient than heapq.heappush?


  • 1

    @livelearn said in Python solution:

    @StefanPochmann Without looking into merge

    Why don't you look into it?

    the input to merge is the self.followees[userId] | {userId} which gives the intersection of all possible values

    Intersection? You mean union? Anyway, it's not the tweets of all those users. It's only the users. (And then their lists of tweets, but not the tweets themselves.)

    I guess are you saying heapq.merge is more efficient than heapq.heappush?

    No idea how you want me to compare those. They do vastly different things.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.