Design a simplified version of Twitter that allows users to send tweets, follow/unfollow other users, and see the last 10 tweets of those who follow them (including themselves).

Implement the Twitter class:

Twitter() initializes a simple Twitter object

Void postTweet(int userId, int tweetId) : Creates a new tweet based on the given tweetId and userId. Each time this function is called, a different tweetId is used.

List getNewsFeed(int userId) : Retrieves the IDS of the last 10 tweets in the current user’s newsfeed. Every item in the news feed must be a tweet from someone the user follows or from the user himself. Tweets must be sorted chronologically from most recent to most distant.

Void Follow (int followerId, int followeeId) : User followerId follows user followeeId.

Void unfollow(int followerId, int followeeId) : User followerId does not follow user followeeId.

Example:

Enter ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] [[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]] output [null, null, [5], null, null, (6, 5), null, [5] Twitter = new Twitter(); twitter.postTweet(1, 5); // User 1 sends a new tweet (user ID = 1, Tweet ID = 5) twitter.getNewsfeed (1); Follow (1, 2); // User 1 should return a list of tweets with an id of 5. // User 1 follows user 2 twitter.posttweet (2, 6); // User 2 sends a new tweet (tweet id = 6) twitter.getNewsfeed (1); // User 1's fetch tweets should return a list of two tweets with ids -> [6, 5]. Tweet ID 6 should precede Tweet ID 5 because it was sent after 5. Unfollow (1, 2); // User 1 unfollows user 2 twitter.getNewsfeed (1); // When user 1 gets tweets, it should return a list of tweets with id 5. Because user 1 is no longer paying attention to user 2Copy the code

Analysis of the

This is actually very comprehensive, not only data structure, but also model design related things.

We maintain three classes:

  1. The User class maintains the User ID, the User focus list, and the tweets to use.
/ / the user table
var User = function (userId) {
    this.userId = userId;
    this.followSet = new Set(a);// The linked list is used to add message nodes
    this.feeds = null;
}
// Message node
var LinkNode = function (tweetId, next) {
    this.next = next || null;
    this.val = {
        tweetId,
        timestamp: timestamp++
    }
}
Copy the code
  • The concern list is maintained using a set collection
  • Because the latest tweet information needs to be put in the first place, we can choose linear data structure, such as number group, linked list, etc. When inserting data into the head of array, we need to move data, and there is a need for dynamic expansion, so we choose linked list.
  1. Heap, because JS has no priority queue, so we have to implement a heap ourselves. When we retrieve the latest 10 tweets, we also have each person’s tweets on the follow list in addition to their own tweets, sort of like multiple ordered linked lists merging, and we maintain the latest 10 tweets with a small top heap of length 10. (There is a small optimisation that skips tweets from a particular person when they are older than the current top tweets.)
// the js implementation heap
class Heap {
    constructor(compare, max) {
        this.heap = [];
        this.count = 0;
        // Default small top heap
        this.compare = compare || ((a, b) = > a < b);
        this.max = max || Infinity;
    }
}

Heap.prototype.push = function (val) {
    if (this.count === this.max) return false;
    this.heap[this.count++] = val;
    this.heapifyUp();
    return true;
}

Heap.prototype.pop = function () {
    if (this.count === 0) return false;
    const top = this.heap[0];
    this.swap(0.this.count - 1);
    this.count--;
    this.heapifyDown();
    return top;
}

Heap.prototype.heapifyDown = function () {
    const compare = this.compare;
    let i = 0;
    while (i < this.count) {
        let temp = i;
        if (i * 2 + 1 < this.count && compare(this.heap[i * 2 + 1].this.heap[i])) {
            temp = i * 2 + 1;
        }
        if (i * 2 + 2 < this.count && compare(this.heap[i * 2 + 2].this.heap[temp])) {
            temp = i * 2 + 2;
        }
        if (temp === i) break;
        this.swap(temp, i);
        i = temp;
    }
}

Heap.prototype.heapifyUp = function () {
    const compare = this.compare;
    let i = this.count - 1;
    while (i > 0) {
        if (compare(this.heap[i], this.heap[(i - 1) > >1]) {this.swap(i, (i - 1) > >1)
            i = (i - 1) > >1
        } else {
            break;
        }
    }
}

Heap.prototype.clear = function () {
    this.heap = [];
    this.count = 0;
}

Heap.prototype.swap = function (a, b) {[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]]
}

Heap.prototype.get = function () {
    return this.heap;
}

Heap.prototype.getTop = function () {
    return this.heap[0];
}

Heap.prototype.getSize = function () {
    return this.count;
}
Copy the code
  1. The Twitter class that maintains all user data and current heap information.
var Twitter = function () {
    / / the user table
    this.userMap = new Map(a);// Small top heap, used to merge data
    this.maxHeap = new Heap((a, b) = > a.timestamp < b.timestamp, MAX_FEEDS);
};
Copy the code

implementation

// Since date.now () may have equal values, in the actual case the timestamp should be used instead of the self-increasing num value
let timestamp = 0;
const MAX_FEEDS = 10;

var Twitter = function () {
    / / the user table
    this.userMap = new Map(a);// Small top heap, used to merge data
    this.maxHeap = new Heap((a, b) = > a.timestamp < b.timestamp, MAX_FEEDS);
};

/ / the user table
var User = function (userId) {
    this.userId = userId;
    this.followSet = new Set(a);// The linked list is used to add message nodes
    this.feeds = null;
}

// Message node
var LinkNode = function (tweetId, next) {
    this.next = next || null;
    this.val = {
        tweetId,
        timestamp: timestamp++
    }
}

// The current user inserts a news item
User.prototype.postTweet = function (tweetId) {
    const current = this.feeds;
    const node = new LinkNode(tweetId, current);
    this.feeds = node;
}

// User concerns
User.prototype.follow = function (followeeId) {
    // Follow account equals current account
    if (this.userId === followeeId) return;
    // The account is in the following list
    if (this.followSet.has(followeeId)) return;
    this.followSet.add(followeeId);
}
// The user retrieves the close
User.prototype.unfollow = function (followeeId) {
    // Follow account equals current account
    if (this.userId === followeeId) return;
    // The account does not exist in the following list
    if (!this.followSet.has(followeeId)) return;
    this.followSet.delete(followeeId)
}


/ * * *@param {number} userId 
 * @param {number} tweetId
 * @return {void}* /
Twitter.prototype.postTweet = function (userId, tweetId) {
    // The user does not exist in the user table
    if (!this.userMap.has(userId)) {
        this.userMap.set(userId, new User(userId));
    }
    const user = this.userMap.get(userId);
    user.postTweet(tweetId);
};

/ * * *@param {number} userId
 * @return {number[]}* /
Twitter.prototype.getNewsFeed = function (userId) {
    if (!this.userMap.has(userId)) return [];
    const user = this.userMap.get(userId);
    // Clean the heap before using it
    this.maxHeap.clear();
    // The current user has news
    if (user.feeds) {
        let current = user.feeds;
        while (current && this.maxHeap.getSize() < MAX_FEEDS) {
            this.maxHeap.push(current.val) current = current.next; }}// Focus on list processing, multiplexing
    let count = user.followSet.size;
    if (count) {
        for (let followeeId of user.followSet) {
            const curUser = this.userMap.get(followeeId)
            let current = curUser.feeds;
            while (current) {
                // The time of subsequent tweets of current followers is shorter than the heap top time, skip
                if (this.maxHeap.getSize() === MAX_FEEDS && current.val.timestamp < this.maxHeap.getTop().timestamp) {
                    break;
                } else {
                    if (this.maxHeap.getSize() === MAX_FEEDS) {
                        this.maxHeap.pop();
                    }
                    this.maxHeap.push(current.val); current = current.next; }}}}const ans = [];
    let heapCount = this.maxHeap.getSize();
    // Because it is a small top heap, the time stamp at the top is the smallest, so we put it at the end of the result array
    while (heapCount) {
        ans.unshift(this.maxHeap.pop().tweetId);
        heapCount--;
    }
    return ans;
};

/ * * *@param {number} followerId 
 * @param {number} followeeId
 * @return {void}* /
Twitter.prototype.follow = function (followerId, followeeId) {
    // The user does not exist in Twitter. Create a user
    if (!this.userMap.has(followerId)) {
        this.userMap.set(followerId, new User(followerId))
    }
    const user = this.userMap.get(followerId);
    // There is no following user account in Twitter
    if (!this.userMap.get(followeeId)) {
        this.userMap.set(followeeId, new User(followeeId))
    }
    user.follow(followeeId);
};

/ * * *@param {number} followerId 
 * @param {number} followeeId
 * @return {void}* /
Twitter.prototype.unfollow = function (followerId, followeeId) {
    // The user does not exist in Twitter. Create a user
    if (!this.userMap.has(followerId)) {
        this.userMap.set(followerId, new User(followerId))
    }
    const user = this.userMap.get(followerId);
    // There is no following user account in Twitter
    if (!this.userMap.get(followeeId)) {
        this.userMap.set(followeeId, new User(followeeId))
    }
    user.unfollow(followeeId);
};

/** * Your Twitter object will be instantiated and called as such: * var obj = new Twitter() * obj.postTweet(userId,tweetId) * var param_2 = obj.getNewsFeed(userId) * obj.follow(followerId,followeeId) * obj.unfollow(followerId,followeeId) */

Copy the code