Java OO Design with most efficient function getNewsFeed


  • 155
    public class Twitter {
        private static int timeStamp=0;
        
        // easy to find if user exist
        private Map<Integer, User> userMap;
        
        // Tweet link to next Tweet so that we can save a lot of time
        // when we execute getNewsFeed(userId)
        private class Tweet{
            public int id;
            public int time;
            public Tweet next;
            
            public Tweet(int id){
                this.id = id;
                time = timeStamp++;
                next=null;
            }
        }
        
        
        // OO design so User can follow, unfollow and post itself
        public class User{
            public int id;
            public Set<Integer> followed;
            public Tweet tweet_head;
            
            public User(int id){
                this.id=id;
                followed = new HashSet<>();
                follow(id); // first follow itself
                tweet_head = null;
            }
            
            public void follow(int id){
                followed.add(id);
            }
            
            public void unfollow(int id){
                followed.remove(id);
            }
            
            
            // everytime user post a new tweet, add it to the head of tweet list.
            public void post(int id){
                Tweet t = new Tweet(id);
                t.next=tweet_head;
                tweet_head=t;
            }
        }
        
        
        
    
        /** Initialize your data structure here. */
        public Twitter() {
            userMap = new HashMap<Integer, User>();
        }
        
        /** Compose a new tweet. */
        public void postTweet(int userId, int tweetId) {
            if(!userMap.containsKey(userId)){
                User u = new User(userId);
                userMap.put(userId, u);
            }
            userMap.get(userId).post(tweetId);
                
        }
        
    
        
        // Best part of this.
        // first get all tweets lists from one user including itself and all people it followed.
        // Second add all heads into a max heap. Every time we poll a tweet with 
        // largest time stamp from the heap, then we add its next tweet into the heap.
        // So after adding all heads we only need to add 9 tweets at most into this 
        // heap before we get the 10 most recent tweet.
        public List<Integer> getNewsFeed(int userId) {
            List<Integer> res = new LinkedList<>();
    
            if(!userMap.containsKey(userId))   return res;
            
            Set<Integer> users = userMap.get(userId).followed;
            PriorityQueue<Tweet> q = new PriorityQueue<Tweet>(users.size(), (a,b)->(b.time-a.time));
            for(int user: users){
                Tweet t = userMap.get(user).tweet_head;
                // very imporant! If we add null to the head we are screwed.
                if(t!=null){
                    q.add(t);
                }
            }
            int n=0;
            while(!q.isEmpty() && n<10){
              Tweet t = q.poll();
              res.add(t.id);
              n++;
              if(t.next!=null)
                q.add(t.next);
            }
            
            return res;
            
        }
        
        /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
        public void follow(int followerId, int followeeId) {
            if(!userMap.containsKey(followerId)){
                User u = new User(followerId);
                userMap.put(followerId, u);
            }
            if(!userMap.containsKey(followeeId)){
                User u = new User(followeeId);
                userMap.put(followeeId, u);
            }
            userMap.get(followerId).follow(followeeId);
        }
        
        /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
        public void unfollow(int followerId, int followeeId) {
            if(!userMap.containsKey(followerId) || followerId==followeeId)
                return;
            userMap.get(followerId).unfollow(followeeId);
        }
    }
    
    /**
     * Your Twitter object will be instantiated and called as such:
     * Twitter obj = new Twitter();
     * obj.postTweet(userId,tweetId);
     * List<Integer> param_2 = obj.getNewsFeed(userId);
     * obj.follow(followerId,followeeId);
     * obj.unfollow(followerId,followeeId);
     */

  • 10
    N

    Impress by using the pointer to make the priorityQueue working more efficiently.


  • 3

    I think if you maintain an additional set of newsFeed under User, the function getNewsFeed will be even more efficient.

    The idea is upon tweet creation, broadcast it to all followers' newsFeed. Upon follow, add followee's tweets to follower's newsFeed, and delete them upon unfollow. The assumption is that these 3 functions are called much less frequent than getNewsFeed.


  • 4
    J

    "The idea is upon tweet creation, broadcast it to all followers' newsFeed." This is not a good idea. For popular accounts, the followers can be millions. it's not reasonable to broadcast to all of them since most of them may not want to get the newsFeeds.

    I think the current design in this post is reasonable, you should refresh the newsFeeds based on the current account request, not based on the followees' post.


  • 3

    @Jason_Weng This is reasonable in some cases. It's called Push Model and Instagram uses it.


  • 0
    I

    @UpTheHell said in Java OO Design with most efficient function getNewsFeed:

    private static int timeStamp=0;

    can timeStamp be a member of Tweet?


  • 0
    I

    @iambright
    just make Tweet class static.


  • -1
    H

    @UpTheHell

    Thank you for sharing your solution. I learned quite a bit from this post. Anyways, your getNewsFeed() method has a bug and it does not produce the right result. After look at it for a while, I found where the bug is. Basically, it missing the following block right after the declaration of the q and before the for loop.

        Tweet tweet_head = userMap.get(userId).tweet_head;
        if (tweet_head != null) {
            q.add(tweet_head);
        }

  • 0

    @hieu.trinh Do you run the code?
    When a new user is instantiated he will follow himself first. So he is in the followed list.

    public User(int id){
                this.id=id;
                followed = new HashSet<>();
                follow(id); // first follow itself
                tweet_head = null;
            }
    

  • 0
    D

    @lufangjianle A little problem, if you only store the nearest 10 tweets in user's newsFeed, once I unfollow a person , I remove his tweets from my newsFeed, I forgot the outdated tweets before this fellow, so there will be not enough 10. It will cause space problem if you store all the tweets history. But , if it copes with @UpTheHell 's function, recollect 10th if you follow or unfollow a person, will be more perfect!


  • 0

  • 0
    H

    @UpTheHell
    I did not see follow(id); in the User's constructor. I got it now. Thanks.


  • 0
    N

    Build the heap will take O(nlogn) time where n is the number of followed. I think just using an n-way merge will cost only 10*n which is faster theoretically.

    Please correct me if I am wrong.


  • 1

    @namxh This is my way to merge n sorted list and we only need to save n tweets in memory. Can you show me your way to do it?


  • 0
    N

    @UpTheHell
    Let p is the list of pointers to the last node of n lists (p[i] is the last node of list i).

    For i: 1 to 10
      Find max in p (call it p[k]), push max to the newsFeed, p[k] = p[k].next
    

    You may want to correct min/max, first/last according to your implementation.


  • 12

    @lufangjianle I read this article http://highscalability.com/blog/2013/7/8/the-architecture-twitter-uses-to-deal-with-150m-active-users.html, then solved this problem in the way more or less as you said.

    Since the traffic to read timeline is much larger than post a tweet, Twitter chose to precompute the timeline in Redis cluster. When the followee posts, the follower list will be pulled out of a service called Social Graph by Fanout service. Then it will inserts the new tweet id into each timeline of the follower.

    Of course, this is an out-of-date article. It is supposed to be changed a lot. :) Here is key part of my solution. The timeline is precomputed beforehand.

        public void postTweet(int userId, int tweetId) {
            Tweet tw = new Tweet(tweetId);
            if (getTweets(userId).add(tw)) {
                getTimeline(userId).add(tw);
                for (int follower : getFollower(userId))
                    getTimeline(follower).add(tw);
            }
        }
    
        public List<Integer> getNewsFeed(int userId) {
            List<Integer> ret = new ArrayList<>();
            int size = 0;
            for (Tweet tw : getTimeline(userId)) {
                if (++size > 10) break;
                ret.add(tw.id);
            }
            return ret;
        }
    

  • 0

    @namxh Ok, I had the exact same thought and found some very interesting info about heaps. Turns out if you build the heap through a succession of inserts (as has been done in this solution) then you will get O(nlogn) build time. But there is a better way where by you just insert the elements into a tree keeping the balance property and then follow with a heapify to correct the heap. This way is more optimal and gets you O(n) build time. Here is the info from Wikipedia

    https://en.wikipedia.org/wiki/Binary_heap

    for this solution the total cost seems to be O(nlogn) + O(10logn) -> nlogn but it could be improved if the heapify was used instead of the successive insert.


  • 0

    @cdai WOW Thanks for the article, was trying to find some similar stuff. :D


  • 0
    Z
    //c++ version
    class Tweet {
    public:
    	Tweet(int tweetId, int timestamp) {
    		this->tweetId = tweetId;
    		this->timestamp = timestamp;
    		next = nullptr;
    	}
    	friend class User;
    	friend class Twitter;
    private:
    	int tweetId;
    	int timestamp;
    	Tweet *next;
    };
    
    class User {
    public:
    	User(int userId) {
    		this->userId = userId;
    		tweetsHead = nullptr;
    		followees.insert(userId);//first follow himself
    	}
    	~User(){
    		Tweet* tmp = tweetsHead;
    		while (tweetsHead) {
    			tmp = tweetsHead->next;
    			delete tweetsHead;
    			tweetsHead = tmp;
    		}
    	}
    	void post(int tweetId, int timestamp) {
    		Tweet *t = new Tweet(tweetId, timestamp);
    		t->next = tweetsHead;
    		tweetsHead = t;
    	}
    	void follow(int followeeId) {
    		followees.insert(followeeId);
    	}
    	void unfollow(int followeeId) {
    		if (followees.find(followeeId) != followees.end() && followeeId != userId) {
    			followees.erase(followeeId);
    		}
    	}
    	friend class Twitter;
    private:
    	int userId;
    	Tweet *tweetsHead;
    	unordered_set<int> followees;
    };
    
    
    
    class Twitter {
    public:
    	/** Initialize your data structure here. */
    	Twitter() {
    
    	}
    	~Twitter() {
    		for (pair<int, User*> p : userMap) {
    			delete p.second;
    		}
    	}
    	/** Compose a new tweet. */
    	void postTweet(int userId, int tweetId) {
    		if (userMap.find(userId) == userMap.end()) {
    			User *newUser = new User(userId);
    			userMap[userId] = newUser;
    		}
    		userMap[userId]->post(tweetId, timestamp);
    		timestamp++;
    	}
        //comparator used in priority_queue
        class Comparator {
    	public:
    		bool operator() (const Tweet* tp1, const Tweet* tp2) {
    			return tp1->timestamp < tp2->timestamp;
    		}
    	};
    	/** 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. */
    	vector<int> getNewsFeed(int userId) {
    		vector<int> res;
    		if (userMap.find(userId) == userMap.end()) return res;
    		priority_queue<Tweet*, vector<Tweet*>, Comparator> p;
    		for (int u : userMap[userId]->followees) {//construct priority queue
    			if (userMap[u]->tweetsHead != nullptr)
    				p.push(userMap[u]->tweetsHead);
    		}
    		for (int i = 0; i < 10 && !p.empty(); ++i) {
    			Tweet* t = p.top();
    			res.push_back(t->tweetId);
    			p.pop();
    			if (t->next) p.push(t->next);
    		}
    		return res;
    	}
    
    	/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    	void follow(int followerId, int followeeId) {
    		if (userMap.find(followerId) == userMap.end()) {
    			User *u = new User(followerId);
    			userMap[followerId] = u;
    		}
    		if (userMap.find(followeeId) == userMap.end()) {
    			User *u = new User(followeeId);
    			userMap[followeeId] = u;
    		}
    		userMap[followerId]->follow(followeeId);
    	}
    
    	/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    	void unfollow(int followerId, int followeeId) {
    		if (userMap.find(followerId) == userMap.end() || userMap.find(followeeId) == userMap.end()) {
    			return;
    		}
    
    		userMap[followerId]->unfollow(followeeId);
    	}
    private:
    	int timestamp = 0;
    	unordered_map<int, User*> userMap;
    };
    
    /**
    * Your Twitter object will be instantiated and called as such:
    * Twitter obj = new Twitter();
    * obj.postTweet(userId,tweetId);
    * vector<int> param_2 = obj.getNewsFeed(userId);
    * obj.follow(followerId,followeeId);
    * obj.unfollow(followerId,followeeId);
    */
    

  • 0
    X

    It's really a nice C++ OOP translation from original Java code. Thanks so much for your elegant solution.


Log in to reply
 

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