Short O(n) getNewsFeed using Stack. Java solution.


  • 0
    L
    public class Twitter {
        public class Tweet{
            int id; int userId;
            public Tweet (int id, int userId) { this.id = id; this.userId = userId; }
        }
        
        LinkedList<Tweet> tweetStack= new LinkedList<>();
        HashMap<Integer, HashSet<Integer>> users = new HashMap<>();
    
        public void postTweet(int userId, int tweetId) {
            if (!users.containsKey(userId)) users.put(userId, new HashSet<>());
            tweetStack.push(new Tweet(tweetId, userId));
        }
    
        public List<Integer> getNewsFeed(int userId) {
            if (!users.containsKey(userId)) users.put(userId, new HashSet<>());
            List<Integer> result = new ArrayList<>();
            for (Tweet tweet : tweetStack){
                if (users.get(userId).contains(tweet.userId) || tweet.userId == userId) result.add(tweet.id);
                if (result.size() == 10) break;
            }
            return result;
        }
        
        public void follow(int followerId, int followeeId) {
            if (!users.containsKey(followerId)) users.put(followerId, new HashSet<>());
            users.get(followerId).add(followeeId);
        }
        
        public void unfollow(int followerId, int followeeId) {
            if (!users.containsKey(followerId)) users.put(followerId, new HashSet<>());
            users.get(followerId).remove(followeeId);
        }
    }
    

Log in to reply
 

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