1
\$\begingroup\$

I am new to Java and would like to know whether my program is idiomatic. Please help me write idiomatic, terse code. My solution is functionally correct.

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user's news feed. Your design should support the following methods:

  • postTweet(userId, tweetId): Compose a new tweet.
  • getNewsFeed(userId): 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.
  • follow(followerId, followeeId): Follower follows a followee.
  • unfollow(followerId, followeeId): Follower unfollows a followee.

Solution

import java.util.*;

public class Twitter {

    class Tweet implements Comparable<Tweet> {
        public Tweet(int id, int stamp) {
            tweetId = id;
            timeStamp = stamp;
        }
        int tweetId;
        int timeStamp;

        public int compareTo(Tweet other) {
            return -(this.timeStamp - other.timeStamp);
        }
    }

    /** Initialize your data structure here. */
    private Map<Integer, List<Tweet>> tweetStore = new HashMap<>();
    private Map<Integer, Set<Integer>> followerStore = new HashMap<>();
    private int time = 0;

    public Twitter() {

    }

    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        time++;
        tweetStore.putIfAbsent(userId, new ArrayList<Tweet>());
        tweetStore.get(userId).add(new Tweet(tweetId, time));
    }

/** 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. */
    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> userIds = getActiveUsersOfInterest(userId);
        List<Integer> tweetIds = getRecentTweets(userIds,10);
        return tweetIds;
    }

    private Set<Integer> getActiveUsersOfInterest(int userId) {
        Set<Integer> setOfUsers = new HashSet<>();
        if(tweetStore.containsKey(userId)) {
            setOfUsers.add(userId);
        }
        if(followerStore.containsKey(userId)) {
            for(int followeeId: followerStore.get(userId)) {
                if(tweetStore.containsKey(followeeId)) {
                    setOfUsers.add(followeeId);
                }
            }
        }
        return setOfUsers;
    }

    private List<Integer> getRecentTweets(Set<Integer> activeUserIds,int size) {
        List<Integer> latestTweetsIds = new ArrayList<>();
        PriorityQueue<Tweet> maxHeap = new PriorityQueue<>();
        List<ListIterator<Tweet>> listIterators = new ArrayList<>();
        Map<Tweet,ListIterator<Tweet>> tweetToListIterator = new HashMap<>();
        for(int userId:activeUserIds ) {
            List<Tweet> tweets = tweetStore.get(userId);
            listIterators.add(tweets.listIterator(tweets.size()));
        }
        for(ListIterator<Tweet> listIterator :listIterators) {
            if(listIterator.hasPrevious()) {
                Tweet tweet = listIterator.previous();
                maxHeap.add(tweet);
                tweetToListIterator.put(tweet, listIterator);
            }
        }
        while(!maxHeap.isEmpty() && latestTweetsIds.size() < size) {
            Tweet tweet = maxHeap.remove();
            ListIterator<Tweet> listIterator = tweetToListIterator.get(tweet);
            tweetToListIterator.remove(tweet);
            latestTweetsIds.add(tweet.tweetId);
            if(listIterator.hasPrevious()) {
                Tweet t = listIterator.previous();
                maxHeap.add(t);
                tweetToListIterator.put(t, listIterator);
            }
        }
        return latestTweetsIds;
    }

/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        followerStore.putIfAbsent(followerId, new HashSet<Integer>());
        followerStore.get(followerId).add(followeeId);
    }

/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        if(followerStore.containsKey(followerId)) {
            followerStore.get(followerId).remove(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);
 */
\$\endgroup\$
1
\$\begingroup\$
class Tweet implements Comparable<Tweet> {
    ...
    public int compareTo(Tweet other) {
        return -(this.timeStamp - other.timeStamp);
    }
}

This is a strange definition of "comparable". For one thing, you should know that -(x - y) is just a complicated way of writing y - x. But more importantly, this definition of compareTo means that any two tweets with the same timestamp will compare equal! If you want your program to have a notion of "this tweet happened earlier-than/at-the-same-time-as/later-than this other tweet", that's fine; but don't hijack the Comparable interface to do so. Provide a method .compareTimes(Tweet other) or something.


private Map<Integer, List<Tweet>> tweetStore = new HashMap<>();
private Map<Integer, Set<Integer>> followerStore = new HashMap<>();

If you wanted to mimic a real database application slightly more closely, you could do this instead:

class User {
    UserId id;  // this is optional; see if you can make do without it!
    List<TweetId> tweets;
    Set<UserId> followers;
};

private Map<TweetId, Tweet> tweetStore = new HashMap<>();
private Map<UserId, User> tweetStore = new HashMap<>();

(I've used the semantic names UserId and TweetId instead of Integer, because I think in C++. In Java, you'll have to just say Integer for both and be careful not to mix them up.)


Your getRecentTweets method looks very heavyweight for what it's actually doing. Assuming the tweets in tweetStore.get(userId) are always kept sorted by timestamp, then all you need to do is:

  • For each of your N users, get an iterator to that user's most recent tweet.
  • Choose the most recent one of the N tweets currently pointed to by your N iterators. Append it to your timeline. Advance that iterator.
  • Repeat the previous step K times, where K is the number of tweets you'd like to have in your timeline.

This is just an N-way merge — mergesort without the sorting part. It should be in your mental toolbox; if it's not, study it until it's obvious.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can compare multiple fields when defining Comparable. The key point to multifield comparison is to make sure that, taken together, the compared fields uniquely identify the object. This defines a Strict total ordering. \$\endgroup\$ – Lie Ryan Jun 16 '16 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.