355. Design Twitter - Medium

前往題目

想法

• 卡在getNewsFeed

思路

OOD方式

1. 定義Tweet物件和User物件，包含各種訊息
2. postTweet直接用id取得用戶物件然後post
3. getNewsFeed一開始先檢查userId是否存在，接著疊代該用戶追蹤的用戶們，取得他們最新的tweet，然後第二個循環就開始取得10個最新tweet，先加入最新的tweet，然後同時也加入該tweet的下一個，這樣一直循環直到滿足條件就會是取到最新的10個(這裡的code很有意思)
4. follow要檢查followerId以及followeeId是否都存在，如果都存在一樣取得用戶物件然後follow
5. unfollow要檢查followerId是否存在，以及followerId不能和followeeId一樣，因為不允許unfollow自己。最後一樣取得User物件啥後unfollow

Code

Discussion Answer

class Twitter {

    private static int timeStamp = 0;

    private class Tweet {
        public int id;
        public int time;
        public Tweet nextTweet;

        public Tweet(int id) {
            this.id = id;
            time = timeStamp;
            ++timeStamp;
            nextTweet = null;
        }
    }

    private class User {
        public int id;
        public Set<Integer> followed;
        public Tweet tweetHead;

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

        public void follow(int id) {
            followed.add(id);
        }

        public void unfollow(int id) {
            followed.remove(id);
        }

        public void post(int tweetId) {
            Tweet t = new Tweet(tweetId);
            // New post becomes the new head since it's the latest
            t.nextTweet = tweetHead;
            tweetHead = t;
        }
    }

    // userId -> User object
    private Map<Integer, User> idToUser;

    public Twitter() {
        idToUser = new HashMap<>();
    }

    public void postTweet(int userId, int tweetId) {
        if (!idToUser.containsKey(userId)) {
            idToUser.put(userId, new User(userId));
        }
        idToUser.get(userId).post(tweetId);
    }

    public List<Integer> getNewsFeed(int userId) {
        List<Integer> res = new LinkedList<>();

        // Check user presence
        if (!idToUser.containsKey(userId))
            return res;

        // Obtain following accounts of the current user
        Set<Integer> followingIds = idToUser.get(userId).followed;
        // PQ to sort tweets according to their times
        // from latest to the oldest
        PriorityQueue<Tweet> pq = new PriorityQueue<Tweet>(
            followingIds.size(), (a, b) -> (b.time - a.time)
            );

        // Add all the tweet heads from the followingIds to the pq
        for (int id : followingIds) {
            // Obtain its tweetHead
            Tweet t = idToUser.get(id).tweetHead;

            // Add to the pq
            if (t != null) {
                pq.add(t);
            }
        }

        int count = 0;

        // Obtain the latest 10 tweets
        while (!pq.isEmpty() && count < 10) {
            // 加入最新的tweet
            Tweet t = pq.poll();
            res.add(t.id);
            ++count;
            if (t.nextTweet != null) {
                // 然後再加入最新tweet的下一個，好繼續和其餘的做比較
                pq.add(t.nextTweet);
            }
        }

        return res;
    }

    public void follow(int followerId, int followeeId) {
        // Check follower and followee presence
        if (!idToUser.containsKey(followerId)) {
            idToUser.put(followerId, new User(followerId));
        }

        if (!idToUser.containsKey(followeeId)) {
            idToUser.put(followeeId, new User(followeeId));
        }

        // Follow the followee
        idToUser.get(followerId).follow(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        // Check follower and followee presence
        if (!idToUser.containsKey(followerId) ||
                followerId == followeeId) {
            // Invalid operation
            return;
        }
        idToUser.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);
 */