Design Twitter

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

Design Twitter

Design a simplified version of Twitter where users can post tweets, follow/unfollow others, and see the 10 most recent tweets in their news feed.

Core Operations

postTweet(userId, tweetId)
getNewsFeed(userId)
follow(followerId, followeeId)
unfollow(followerId, followeeId)

Scaling Hint

Pull strategy: When a user requests their feed, merge the $K$ recent tweets from themselves and everyone they follow using a Max-Heap.

Hard

Examples

Input: postTweet(1, 5), getNewsFeed(1), follow(1, 2), postTweet(2, 6), getNewsFeed(1), unfollow(1, 2), getNewsFeed(1)
Output: [[5], [6, 5], [5]]

Approach 1

Level I: Map of Lists (Brute Force Sort)

Intuition

Store each user's tweets in a Map<UserId, List<TweetId>>. For getNewsFeed, collect all tweets from the user and their followees into a single list, sort them by timestamp, and return the top 10.

⏱ Feed: O(N log N) where N is tweets of followed users. Other ops: O(1).💾 O(TotalTweets + TotalFollows).

Detailed Dry Run

User 1 follows 2. User 1 tweets: [T1]. User 2 tweets: [T2]. Feed: Sort([T1, T2]) -> [T2, T1].

java

class Twitter {
    private static int time = 0;
    class Tweet { int id, t; Tweet(int i, int tt){id=i; t=tt;} }
    Map<Integer, List<Tweet>> tweets = new HashMap<>();
    Map<Integer, Set<Integer>> follows = new HashMap<>();
    public void postTweet(int u, int t) {
        tweets.putIfAbsent(u, new ArrayList<>());
        tweets.get(u).add(new Tweet(t, time++));
    }
    public List<Integer> getNewsFeed(int u) {
        List<Tweet> all = new ArrayList<>(tweets.getOrDefault(u, new ArrayList<>()));
        if(follows.containsKey(u)) for(int f : follows.get(u)) all.addAll(tweets.getOrDefault(f, new ArrayList<>()));
        Collections.sort(all, (a, b) -> b.t - a.t);
        List<Integer> res = new ArrayList<>();
        for(int i=0; i<Math.min(10, all.size()); i++) res.add(all.get(i).id);
        return res;
    }
    public void follow(int f, int fe) { if(f!=fe) follows.computeIfAbsent(f, k->new HashSet<>()).add(fe); }
    public void unfollow(int f, int fe) { if(follows.containsKey(f)) follows.get(f).remove(fe); }
}

Approach 2

Level II: Global List + Filtering

Intuition

Maintain a single global list of all tweets. When getNewsFeed(userId) is called, iterate backwards through the list and pick the first 10 tweets that were posted by the user or their followees.

⏱ Feed: O(T) where T is total tweets in system. Other ops: O(1).💾 O(T + F).

java

class Twitter {
    class Tweet { int uid, tid; Tweet(int u, int t) { uid = u; tid = t; } }
    List<Tweet> allTweets = new ArrayList<>();
    Map<Integer, Set<Integer>> followers = new HashMap<>();
    public void postTweet(int uid, int tid) { allTweets.add(new Tweet(uid, tid)); }
    public List<Integer> getNewsFeed(int uid) {
        Set<Integer> followed = followers.getOrDefault(uid, new HashSet<>());
        followed.add(uid);
        List<Integer> res = new ArrayList<>();
        for (int i = allTweets.size() - 1; i >= 0 && res.size() < 10; i--) {
            if (followed.contains(allTweets.get(i).uid)) res.add(allTweets.get(i).tid);
        }
        return res;
    }
    public void follow(int f1, int f2) { followers.computeIfAbsent(f1, k -> new HashSet<>()).add(f2); }
    public void unfollow(int f1, int f2) { if (followers.containsKey(f1)) followers.get(f1).remove(f2); }
}

Approach 3

Level III: Map + Heap (Pull-based Feed)

Intuition

Keep a User class containing a Set of followees and a LinkedList of tweets. For getNewsFeed, push the first tweet of each user in the followee list into a Max-Heap (sorted by timestamp), and then standard merge-k-sorted-lists logic.

⏱ Feed: O(F log F) where F is number of followees. Other ops: O(1).💾 O(U + T) for Users and Tweets.

java

class Twitter {
    private static int timestamp = 0;
    class Tweet { int id, time; Tweet next; Tweet(int i, int t) { id = i; time = t; } }
    class User {
        int id; Set<Integer> followed; Tweet head;
        User(int i) { id = i; followed = new HashSet<>(); followed.add(i); }
    }
    Map<Integer, User> userMap = new HashMap<>();
    public void postTweet(int uid, int tid) {
        userMap.putIfAbsent(uid, new User(uid));
        User u = userMap.get(uid);
        Tweet t = new Tweet(tid, timestamp++);
        t.next = u.head; u.head = t;
    }
    public List<Integer> getNewsFeed(int uid) {
        if (!userMap.containsKey(uid)) return new ArrayList<>();
        PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.time - a.time);
        for (int followeeId : userMap.get(uid).followed) {
            User followee = userMap.get(followeeId);
            if (followee != null && followee.head != null) pq.add(followee.head);
        }
        List<Integer> res = new ArrayList<>();
        while (!pq.isEmpty() && res.size() < 10) {
            Tweet t = pq.poll(); res.add(t.id);
            if (t.next != null) pq.add(t.next);
        }
        return res;
    }
    public void follow(int f1, int f2) { userMap.putIfAbsent(f1, new User(f1)); userMap.putIfAbsent(f2, new User(f2)); userMap.get(f1).followed.add(f2); }
    public void unfollow(int f1, int f2) { if (userMap.containsKey(f1) && f1 != f2) userMap.get(f1).followed.remove(f2); }
}

← Previous QuestionAll O(1) Data Structure

Next Question →Design Phone Directory

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.