---
tags: leetcode
---

# [355. Design Twitter](https://leetcode.com/problems/design-twitter/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

struct postData {
    int postId;
    int timestamp;
    postData(int postId, int timestamp) : postId(postId), timestamp(timestamp) {}
};

class cmp {
public:
    bool operator() (postData &p1, postData &p2) {
        return p1.timestamp < p2.timestamp;
    }
};

class Twitter {
public:
    Twitter() : timestamp(0) {
    }

    void postTweet(int userId, int tweetId) {
        userToPosts[userId].push_back(postData(tweetId, timestamp));
        ++timestamp;
    }

    vector<int> getNewsFeed(int userId) {
        priority_queue<postData, vector<postData>, cmp> allPosts;
        auto userIter = userToPosts.find(userId);
        if (userIter != userToPosts.end() && !userIter->second.empty()) {
            vector<postData> &userPosts = userIter->second;
            for (auto &post : userPosts) {
                allPosts.push(post);
            }
        }

        auto followeeIter = userToFollowees.find(userId);
        if (followeeIter != userToFollowees.end() && !followeeIter->second.empty()) {
            unordered_set<int> &followees = followeeIter->second;
            for (auto &followeeId : followees) {
                auto followeeIter = userToPosts.find(followeeId);
                if (followeeIter == userToPosts.end())　{
                    continue;
                }

                vector<postData> &followeePosts = followeeIter->second;
                for (auto &post : followeePosts) {
                    allPosts.push(post);
                }
            }
        }

        vector<int> mostRecentPost;
        int postCnt = 10;
        while (postCnt > 0 && !allPosts.empty()) {
            mostRecentPost.push_back(allPosts.top().postId);
            allPosts.pop();
            --postCnt;
        }

        return mostRecentPost;
    }

    void follow(int followerId, int followeeId) {
        userToFollowees[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        userToFollowees[followerId].erase(followeeId);
    }

private:
    unordered_map<int, vector<postData>> userToPosts;
    unordered_map<int, unordered_set<int>> userToFollowees;
    int timestamp;
};

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter* obj = new Twitter();
 * obj->postTweet(userId,tweetId);
 * vector<int> param_2 = obj->getNewsFeed(userId);
 * obj->follow(followerId,followeeId);
 * obj->unfollow(followerId,followeeId);
 */

## Time Complexity
* `Twitter`
$O(1)$
* `postTweet`
$O(1)$
* `getNewsFeed`
$O(n)$
$n$ is the total number of posts at the moment when `getNewsFeed` is called.
* `follow`
$O(1)$
* `unfollow`
$O(1)$
## Space Complexity
* `Twitter`
$O(1)$
* `postTweet`
$O(1)$
* `getNewsFeed`
$O(n)$
$n$ is the total number of posts at the moment when `getNewsFeed` is called.
* `follow`
$O(1)$
* `unfollow`
$O(1)$
# Miscellaneous
<!--
# Test Cases

["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"]
[[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]

* Wrong Answer

["Twitter","postTweet","postTweet","getNewsFeed"]
[[],[1,5],[1,3],[1]]

* Wrong Answer

["Twitter","postTweet","getNewsFeed","follow","getNewsFeed","unfollow","getNewsFeed"]
[[],[1,1],[1],[2,1],[2],[2,1],[2]]

* Runtime Error

["Twitter","follow","getNewsFeed"]
[[],[1,5],[1]]

-->