Design Twitter

Leetcode Problem 355: Design Twitter

Problem Summary

Design a simplified version of Twitter that supports four operations. postTweet(userId, tweetId) composes a new tweet with the given id by the specified user. Each call uses a unique tweet id. getNewsFeed(userId) retrieves the 10 most recent tweet ids in the user's news feed, which includes tweets posted by the user and by the users they follow, ordered from most recent to least recent. follow(followerId, followeeId) makes the follower start following the followee. unfollow(followerId, followeeId) makes the follower stop following the followee.

Constraints:

• User ids and followee/follower ids are between 1 and 500.
• Tweet ids are non-negative integers up to 10,000.
• All tweets have unique ids.
• At most 30,000 calls will be made across all operations.

Techniques

• Hash Table
• Linked List
• Design
• Heap (Priority Queue)

Solution

import { Heap } from "../heap";

interface Tweet { 
    id: number,
    counter: number
}

class Twitter {
    private counter: number = 0

    constructor(
        private readonly tweets: Map<number, Tweet[]> = new Map(),
        private readonly following: Map<number, Set<number>> = new Map()
    ) { }

    postTweet(userId: number, tweetId: number): void {
        if (this.tweets.has(userId)) {
            this.tweets.get(userId)!.push({ id: tweetId, counter: this.counter++ })
        } else {
            this.tweets.set(userId, [{ id: tweetId, counter: this.counter++ }])
        }
    }

    getNewsFeed(userId: number): number[] {
        const users = new Set<number>([userId, ...(this.following.get(userId) ?? [])]);
        const heap = new Heap<Tweet>((a, b) => a.counter - b.counter);

        for (const user of users) {
            for (const tweet of this.tweets.get(user) ?? []) {
                heap.insert(tweet);
                if (heap.size() > 10) heap.extract();
            }
        }

        const feed: number[] = [];
        while (heap.size() > 0) {
            feed.push(heap.extract()!.id);
        }

        return feed.reverse(); 
    }

    follow(followerId: number, followeeId: number): void {
        if (this.following.has(followerId)) {
            this.following.get(followerId)!.add(followeeId)
        } else {
            this.following.set(followerId, new Set([followeeId]))
        }
    }

    unfollow(followerId: number, followeeId: number): void {
        this.following.get(followerId)?.delete(followeeId);
    }
}