Design Twitter

Problem adopted from Leetcode: https://leetcode.com/problems/design-twitter/

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.

Approach:

• I began with a standard graph boilerplate. Then, I began to manipulate the basic graph operations to fit program in question.

• Building the connections was simple, but the most creative operation getNewsFeed.

  • With getNewsFeed, I took the approach of only adding tweets the users made on their profiles. Within my graph, the first node (key) contains all the information about the user. The remaining link in (value) in the graph were merely identifiers on where to look for the key nodes. So to find the news feed, I would iterate through the list of the persons friends, hash back to the first key, and grab the tweets. Each tweet as an associated time stamp that I later use to sort by time.

enum State {
    UnVisited, Visited, Visiting
};

class Node {
public:
    Node(string id) {
        this->id = id;
        state = UnVisited;
    }

    string id;
    State state;

    bool operator==(const Node &other) const
    {
        return (id == other.id);
    }

    void push_front(string &str, int timeStamp)
    {
        tweets.push_front(make_pair(str, timeStamp));
        if (tweets.size() > 10) {
            tweets.pop_front();
        }
    }

    std::list<pair<string, int>> getActivity()
    {
        return tweets;
    }

private:
    int otherdata1;
    string otherdata2, otherdata3;

    // string = tweet, int = time stamp
    std::list<pair<string, int>> tweets;

    typedef pair<string, int> p;
};

namespace std {
    template <>
    struct hash<Node>
    {
        std::size_t operator()(const Node& k) const
        {
            return ((hash<string>()(k.id)));
        }
    };
}

class Graph {
public:
    Graph() {}

    void traverse() {
        for (auto& i : graph) {
            cout << i.first.id << "(" << i.first.state << ") " << ": ";
            traverse_set(i.second);
        }
    }

    void postTweet(Node &personID, string tweetId)
    {
        const_cast<Node&>(graph.find(personID)->first).push_front(tweetId, time_stamp++);
    }

    void follow(Node &this_person, Node &follows)
    {
        add(this_person);
        add(follows);
        connect(this_person, follows);
    }

    void unfollow(Node &this_person, Node &follows)
    {
        remove_connection(this_person, follows);
    }

    void getNewsFeed(Node &personID)
    {
        /*
            1. Aggregate together all the tweets.
            2. Sort them by time stamp
            3. Output top 10.
            4. This should be sufficiently fast, since each
            node is limited to only 10 tweets.
        */
        typedef pair<string, int> p;
        list<p> all_tweets = aggregateTweets(const_cast<Node&>(graph.find(personID)->first));
        all_tweets.sort([](const p & a, const p & b)
                        { return a.second < b.second; });

        for (auto i : all_tweets)
            cout << i.first << "(" << i.second << ")" << endl;
    }

private:
    const bool directed = true;
    unordered_map<Node, unordered_set<Node>> graph;

    static int time_stamp;

    void add(Node &n)
    {
        if (exists(n)) { cout << "Node already exists" << endl; return; }
        graph.insert(make_pair(n, unordered_set<Node>()));
    }

    void erase(Node &n)
    {
        if (!exists(n)) { cout << "Node does not exist" << endl; return; }
        graph.erase(n);

        // removal should be everywhere in the graph, not just locally 
        // O(n)
        for (auto &i : graph) {
            if (i.second.find(n) != i.second.end()) {
                i.second.erase(n);
            }
        }
    }

    void connect(Node &src, Node &dst)
    {
        if (!exists(src)) graph.insert(make_pair(src, unordered_set<Node>()));
        if (!exists(dst)) graph.insert(make_pair(src, unordered_set<Node>()));
        else if (contains(graph.find(src)->second, dst)) {
            cout << "Node dst is already connected to src" << endl;
            return;
        }

        graph.find(src)->second.insert(dst);
    }

    std::unordered_set<Node>& findAdj(Node &n)
    {
        if (!exists(n)) {
            cout << "Node does not exist" << endl;
            return unordered_set<Node>();
        }
        return graph.find(n)->second;
    }

    void remove_connection(Node &this_person, Node &follows)
    {
        if (!exists(this_person) || !exists(follows)) {
            cout << "One or more person does not exist" << endl;
            return;
        }
        graph.find(this_person)->second.erase(follows);
    }

    void resetStates()
    {
        // have to be careful, since we are modifying the key
        // we are safe in this context since it is not used to hash
        for (auto &i : graph)
            const_cast<Node&>(i.first).state = UnVisited;
    }

    bool contains(unordered_set<Node> &s, Node &n)
    {
        return (s.find(n) != s.end());
    }

    list<pair<string, int>> aggregateTweets(Node &user)
    {    
        // includes user itself
        list<pair<string, int>> all_tw;
        list<pair<string, int>> user_list = user.getActivity();
        all_tw.insert(all_tw.end(), user_list.begin(), user_list.end());
        for (auto i : graph.find(user)->second) {
            list<pair<string, int>> l = const_cast<Node&>(graph.find(i)->first).getActivity();
            all_tw.insert(all_tw.end(), l.begin(), l.end());
        }

        return all_tw;
    }

    void traverse_set(unordered_set<Node> &s)
    {
        for (auto &i : s)
            cout << i.id << "(" << i.state << ")" << "-> ";
        cout << endl;
    }

    bool exists(const Node &n)
    {
        return (graph.find(n) != graph.end());
    }

    vector<string> errors = {
        "Person does not exist",
    };
};

int Graph::time_stamp = 0;

void test() 
{
    Graph twitter;
    Node dan("dan");
    Node alex("alex");
    Node vt("vt");
    Node dav("dav");
    Node lily("lily");
    Node mike("mike");

    twitter.follow(dan, alex);
    twitter.follow(dan, vt);
    twitter.follow(dan, mike);
    twitter.follow(lily, alex);
    twitter.follow(dav, mike);
    twitter.follow(dav, vt);
    twitter.follow(dav, lily);

    twitter.postTweet(dan,  "dan tweet");
    twitter.postTweet(alex, "alex tweet");
    twitter.postTweet(vt,   "vt tweet");
    twitter.postTweet(mike, "mike tweet");
    twitter.postTweet(dav,  "dav tweet");
    twitter.postTweet(lily, "lily tweet");

    twitter.getNewsFeed(dan); cout << endl;
    twitter.getNewsFeed(mike); cout << endl;
    twitter.getNewsFeed(dav); cout << endl;

    twitter.unfollow(dan, alex);
    twitter.unfollow(dav, mike);
    cout << "___________" << endl;

    twitter.getNewsFeed(dan); cout << endl;
    twitter.getNewsFeed(mike); cout << endl;
    twitter.getNewsFeed(dav); cout << endl;

    pause();
}

int main() 
{
    test();
}