Java Solutions with Two Maps and PriorityQueue


  • 22
    Y

    I use a map to track the tweets for each user. When we need to generate a news feed, I merge the news feed for all the followees and take the most recent 10. This is unlikely to perform, but the code passes the OJ. I'm sure design interviews ask for performance trade-offs and just posting this code in a design interview will not help you get an offer.

    public class Twitter {
        Map<Integer, Set<Integer>> fans = new HashMap<>();
        Map<Integer, LinkedList<Tweet>> tweets = new HashMap<>();
        int cnt = 0;
    
        public void postTweet(int userId, int tweetId) {
            if (!fans.containsKey(userId)) fans.put(userId, new HashSet<>());
            fans.get(userId).add(userId);
            if (!tweets.containsKey(userId)) tweets.put(userId, new LinkedList<>());
            tweets.get(userId).addFirst(new Tweet(cnt++, tweetId));
        }
    
        public List<Integer> getNewsFeed(int userId) {
            if (!fans.containsKey(userId)) return new LinkedList<>();
            PriorityQueue<Tweet> feed = new PriorityQueue<>((t1, t2) -> t2.time - t1.time);
            fans.get(userId).stream()
                .filter(f -> tweets.containsKey(f))
                .forEach(f -> tweets.get(f).forEach(feed::add));
            List<Integer> res = new LinkedList<>();
            while (feed.size() > 0 && res.size() < 10) res.add(feed.poll().id);
            return res;
        }
    
        public void follow(int followerId, int followeeId) {
            if (!fans.containsKey(followerId)) fans.put(followerId, new HashSet<>());
            fans.get(followerId).add(followeeId);
        }
    
        public void unfollow(int followerId, int followeeId) {
            if (fans.containsKey(followerId) && followeeId != followerId) fans.get(followerId).remove(followeeId);
        }
    
        class Tweet {
            int time;
            int id;
    
            Tweet(int time, int id) {
                this.time = time;
                this.id = id;
            }
        }
    }

  • 6
    L

    Great solution. There are two possible places I think can improve the time complexity as well as space.

    A. Since we will get 10 most tweets from each user. We can just save up to 10 tweets for each user. And we can use Dqueue to do that.

    B. In getNewsFeed(). we can use minHeap instead so that PQueue only needs to save 10 tweets. And after each iteration if PQueue's size is bigger than 10, take the tweet with the min timestamp out of PQ.


  • 0
    S

    This can't pass the test now... There's a null pointer exception for input:
    ["Twitter","follow","getNewsFeed"]
    [[],[1,5],[1]]


  • 0
    Y

    @lsy1991121 Thanks. I have added a filter and it passes now.


  • 0

    thank you for sharing, clear and thoughtful


  • 0

    Using deque, hashmap and hashset.

        Deque<Integer[]> posts;
        Map<Integer, Set<Integer>> relation;
        
        public Twitter() {
            posts = new ArrayDeque();
            relation = new HashMap();
        }
        
        public void postTweet(int userId, int tweetId) {
            posts.addFirst(new Integer[]{userId, tweetId});
        }
        
        public List<Integer> getNewsFeed(int userId) {
            Set<Integer> followees;
            if(relation.containsKey(userId)){
               followees  = relation.get(userId);
            } else {
               followees = new HashSet();
            }
            
            Iterator<Integer[]> iter = posts.iterator();
            List<Integer> news = new ArrayList();
            while(iter.hasNext()){
               if(news.size() == 10) break; 
               Integer[] post = iter.next();
               if(post[0] == userId || followees.contains(post[0])){
                   news.add(post[1]);
               } 
            }
            return news;
        }
        
        public void follow(int followerId, int followeeId) {
            Set<Integer> followees;
            if(relation.containsKey(followerId)){
               followees  = relation.get(followerId);
            } else {
               followees = new HashSet();
            }   
            followees.add(followeeId);
            relation.put(followerId, followees);
        }
        
        public void unfollow(int followerId, int followeeId) {
            Set<Integer> followees;
            if(relation.containsKey(followerId)){
               followees  = relation.get(followerId);
            } else {
               followees = new HashSet();
            }   
            followees.remove(followeeId);
            relation.put(followerId, followees);        
        }

Log in to reply
 

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