Java solution - easy to follow


  • 1
    O

    This solution takes O(n) for getNewsFeed() and O(1) for all other operations. I believe it's not so cool, but may be used as a starting point.

    public class Twitter {
    
    private static class Tweet {
        int tweetId;
        int userId;
        Tweet(int tweetId, int userId) {
            this.tweetId = tweetId;
            this.userId = userId;
        }
    }
    
    private static final int NEWS_FEED_SIZE = 10;
    private Deque<Tweet> tweets = new ArrayDeque<>();
    private Map<Integer, Set<Integer>> followeesByFollower = new HashMap<>();
    
    public Twitter() {
    }
    
    public void postTweet(int userId, int tweetId) {
        tweets.add(new Tweet(tweetId, userId));
    }
    
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> newsFeed = new ArrayList<>(NEWS_FEED_SIZE);
        Set<Integer> followees = followeesByFollower.get(userId);
        for (Iterator<Tweet> it = tweets.descendingIterator(); it.hasNext() && newsFeed.size() < NEWS_FEED_SIZE; ) {
            Tweet tweet = it.next();
            if (tweet.userId == userId || (followees != null && followees.contains(tweet.userId))) {
                newsFeed.add(tweet.tweetId);
            }
        }
        return newsFeed;
    }
    
    public void follow(int followerId, int followeeId) {
        if(followeesByFollower.containsKey(followerId)) {
            followeesByFollower.get(followerId).add(followeeId);
        } else {
            Set<Integer> followees = new HashSet<>();
            followees.add(followeeId);
            followeesByFollower.put(followerId, followees);
        }
    }
    
    public void unfollow(int followerId, int followeeId) {
        if (followeesByFollower.containsKey(followerId)) {
            Set<Integer> followees = followeesByFollower.get(followerId);
            if (followees.contains(followeeId)) {
                followees.remove(followeeId);
            }
        }
    }
    }

  • 0
    C

    the most straightforward solution I have ever seen, thx


Log in to reply
 

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