355. Design twitter

355_solution1.c

#include <stdbool.h>
#include <stdlib.h>

#define MAX_USERS 501 // userId is in [1, 500]
#define FEED_SIZE 10

typedef struct {
  int time;
  int id;
} Tweet;

typedef struct {
  Tweet *list;
  int size;
  int cap;
} TweetList;

typedef struct {
  int timestamp;
  TweetList tweets[MAX_USERS];          // userId -> tweets in post order
  bool following[MAX_USERS][MAX_USERS]; // follower -> followee
} Twitter;

static void swap(Tweet *a, Tweet *b) {
  Tweet t = *a;
  *a = *b;
  *b = t;
}

static void siftUp(Tweet *h, int i) {
  while (i > 0 && h[(i - 1) / 2].time > h[i].time) {
    swap(&h[(i - 1) / 2], &h[i]);
    i = (i - 1) / 2;
  }
}

static void siftDown(Tweet *h, int n, int i) {
  for (;;) {
    int min = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && h[l].time < h[min].time)
      min = l;
    if (r < n && h[r].time < h[min].time)
      min = r;
    if (min == i)
      return;
    swap(&h[min], &h[i]);
    i = min;
  }
}

static Tweet pop(Tweet *h, int *n) {
  Tweet top = h[0];
  h[0] = h[--*n];
  siftDown(h, *n, 0);
  return top;
}

Twitter *twitterCreate() { return calloc(1, sizeof(Twitter)); }

void twitterPostTweet(Twitter *obj, int userId, int tweetId) {
  TweetList *t = &obj->tweets[userId];
  if (t->size == t->cap) {
    t->cap = t->cap ? 2 * t->cap : 4;
    t->list = realloc(t->list, t->cap * sizeof(Tweet));
  }
  t->list[t->size++] = (Tweet){obj->timestamp++, tweetId};
}

// min-heap of size 10, ordered by timestamp: top is the oldest of the kept
// tweets
static void scan(const TweetList *t, Tweet *pq, int *n) {
  for (int i = 0; i < t->size; i++) {
    pq[*n] = t->list[i];
    siftUp(pq, (*n)++);
    if (*n > FEED_SIZE)
      pop(pq, n);
  }
}

int *twitterGetNewsFeed(Twitter *obj, int userId, int *retSize) {
  Tweet pq[FEED_SIZE + 1];
  int n = 0;

  scan(&obj->tweets[userId], pq, &n);
  for (int f = 1; f < MAX_USERS; f++) {
    if (f != userId && obj->following[userId][f])
      scan(&obj->tweets[f], pq, &n); // avoid scanning own tweets twice
  }

  // heap pops oldest first, so fill the result from the back
  int *res = malloc(FEED_SIZE * sizeof(int));
  *retSize = n;
  for (int i = n - 1; i >= 0; i--)
    res[i] = pop(pq, &n).id;
  return res;
}

void twitterFollow(Twitter *obj, int followerId, int followeeId) {
  obj->following[followerId][followeeId] = true;
}

void twitterUnfollow(Twitter *obj, int followerId, int followeeId) {
  obj->following[followerId][followeeId] = false;
}

void twitterFree(Twitter *obj) {
  for (int i = 0; i < MAX_USERS; i++)
    free(obj->tweets[i].list);
  free(obj);
}

355_solution2.c

#include <stdbool.h>
#include <stdlib.h>

#define MAX_USERS 501 // userId is in [1, 500]
#define FEED_SIZE 10

typedef struct {
  int time;
  int id;
} Tweet;

typedef struct {
  Tweet *list;
  int size;
  int cap;
} TweetList;

typedef struct {
  int timestamp;                        // global counter, ++ on every post
  TweetList tweets[MAX_USERS];          // userId -> tweets in post order
  bool following[MAX_USERS][MAX_USERS]; // follower -> followee
} Twitter;

typedef struct {
  int time;
  int id;
  int user;
  int idx;
} Entry;

static void swap(Entry *a, Entry *b) {
  Entry t = *a;
  *a = *b;
  *b = t;
}

static void siftUp(Entry *h, int i) {
  while (i > 0 && h[(i - 1) / 2].time < h[i].time) {
    swap(&h[(i - 1) / 2], &h[i]);
    i = (i - 1) / 2;
  }
}

static void siftDown(Entry *h, int n, int i) {
  for (;;) {
    int max = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && h[l].time > h[max].time)
      max = l;
    if (r < n && h[r].time > h[max].time)
      max = r;
    if (max == i)
      return;
    swap(&h[max], &h[i]);
    i = max;
  }
}

static void push(Entry *h, int *n, Entry e) {
  h[*n] = e;
  siftUp(h, (*n)++);
}

static Entry pop(Entry *h, int *n) {
  Entry top = h[0];
  h[0] = h[--*n];
  siftDown(h, *n, 0);
  return top;
}

Twitter *twitterCreate() { return calloc(1, sizeof(Twitter)); }

void twitterPostTweet(Twitter *obj, int userId, int tweetId) {
  TweetList *t = &obj->tweets[userId];
  if (t->size == t->cap) {
    t->cap = t->cap ? 2 * t->cap : 4;
    t->list = realloc(t->list, t->cap * sizeof(Tweet));
  }
  t->list[t->size++] = (Tweet){obj->timestamp++, tweetId};
}

int *twitterGetNewsFeed(Twitter *obj, int userId, int *retSize) {
  Entry pq[MAX_USERS]; // max-heap, at most one entry per user
  int n = 0;

  for (int user = 1; user < MAX_USERS; user++) {
    if (user != userId && !obj->following[userId][user])
      continue;
    const TweetList *t = &obj->tweets[user];
    if (t->size > 0) {
      int idx = t->size - 1;
      push(pq, &n, (Entry){t->list[idx].time, t->list[idx].id, user, idx});
    }
  }

  int *res = malloc(FEED_SIZE * sizeof(int));
  *retSize = 0;
  while (n > 0 && *retSize < FEED_SIZE) {
    Entry e = pop(pq, &n);
    res[(*retSize)++] = e.id;
    if (e.idx > 0) {
      Tweet next = obj->tweets[e.user].list[e.idx - 1];
      push(pq, &n, (Entry){next.time, next.id, e.user, e.idx - 1});
    }
  }

  return res;
}

void twitterFollow(Twitter *obj, int followerId, int followeeId) {
  obj->following[followerId][followeeId] = true;
}

void twitterUnfollow(Twitter *obj, int followerId, int followeeId) {
  obj->following[followerId][followeeId] = false;
}

void twitterFree(Twitter *obj) {
  for (int i = 0; i < MAX_USERS; i++)
    free(obj->tweets[i].list);
  free(obj);
}

355_solution1.cpp

#include <functional>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

class Twitter {
private:
  int timestamp = 0;
  unordered_map<int, vector<pair<int, int>>>
      tweets; // userId -> {timestamp, tweetId}
  unordered_map<int, unordered_set<int>> following; // userId -> followeeIds

public:
  Twitter() {}

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

  vector<int> getNewsFeed(int userId) {
    // min-heap of size 10, ordered by timestamp: top is the oldest of the kept
    // tweets
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    auto scan = [&](int uid) {
      auto it = tweets.find(uid);
      if (it == tweets.end())
        return;
      for (auto &t : it->second) {
        pq.push(t);
        if (pq.size() > 10)
          pq.pop();
      }
    };

    scan(userId);
    for (int f : following[userId]) {
      if (f != userId)
        scan(f); // avoid scanning own tweets twice
    }

    // heap pops oldest first, so fill the result from the back
    vector<int> res(pq.size());
    for (int i = (int)pq.size() - 1; i >= 0; i--) {
      res[i] = pq.top().second;
      pq.pop();
    }
    return res;
  }

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

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

355_solution2.cpp

#include <array>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

class Twitter {
private:
  int timestamp = 0; // global counter, ++ on every postTweet
  unordered_map<int, vector<pair<int, int>>>
      tweets; // userId -> list of {timestamp, tweetId}
  unordered_map<int, unordered_set<int>>
      following; // userId -> set of followeeIds

public:
  Twitter() {}

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

  vector<int> getNewsFeed(int userId) {
    priority_queue<array<int, 4>> pq;
    vector<int> res;

    auto users = following[userId];
    users.insert(userId);

    for (int user : users) {
      if (!tweets[user].empty()) {
        int idx = tweets[user].size() - 1;
        auto [time, tweetid] = tweets[user].back();
        pq.push({time, tweetid, user, idx});
      }
    }

    while (!pq.empty() && res.size() < 10) {
      auto [time, tweetid, user, idx] = pq.top();
      pq.pop();
      res.push_back(tweetid);
      if (idx > 0) {
        auto [ntime, ntweetid] = tweets[user][idx - 1];
        pq.push({ntime, ntweetid, user, idx - 1});
      }
    }

    return res;
  }

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

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

/**
 * 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);
 */

355_solution1.go

package heaps

import "container/heap"

type tweet struct{ time, id int }

// min-heap ordered by timestamp
type tweetHeap []tweet

func (h tweetHeap) Len() int           { return len(h) }
func (h tweetHeap) Less(i, j int) bool { return h[i].time < h[j].time }
func (h tweetHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *tweetHeap) Push(x any)        { *h = append(*h, x.(tweet)) }

func (h *tweetHeap) Pop() any {
    old := *h
    x := old[len(old)-1]
    *h = old[:len(old)-1]
    return x
}

type Twitter struct {
    timestamp int
    tweets    map[int][]tweet          // userId -> tweets in post order
    following map[int]map[int]struct{} // userId -> followeeIds
}

func Constructor() Twitter {
    return Twitter{tweets: map[int][]tweet{}, following: map[int]map[int]struct{}{}}
}

func (this *Twitter) PostTweet(userId int, tweetId int) {
    this.tweets[userId] = append(this.tweets[userId], tweet{this.timestamp, tweetId})
    this.timestamp++
}

func (this *Twitter) GetNewsFeed(userId int) []int {
    // min-heap of size 10: top is the oldest of the kept tweets
    pq := &tweetHeap{}

    scan := func(uid int) {
        for _, t := range this.tweets[uid] {
            heap.Push(pq, t)
            if pq.Len() > 10 {
                heap.Pop(pq)
            }
        }
    }

    scan(userId)
    for f := range this.following[userId] {
        if f != userId {
            scan(f) // avoid scanning own tweets twice
        }
    }

    // heap pops oldest first, so fill the result from the back
    res := make([]int, pq.Len())
    for i := len(res) - 1; i >= 0; i-- {
        res[i] = heap.Pop(pq).(tweet).id
    }
    return res
}

func (this *Twitter) Follow(followerId int, followeeId int) {
    if this.following[followerId] == nil {
        this.following[followerId] = map[int]struct{}{}
    }
    this.following[followerId][followeeId] = struct{}{}
}

func (this *Twitter) Unfollow(followerId int, followeeId int) {
    delete(this.following[followerId], followeeId)
}

355_solution2.go

package heaps

import "container/heap"

type tweet struct{ time, id int }

type entry struct{ time, id, user, idx int }

// max-heap ordered by timestamp
type entryHeap []entry

func (h entryHeap) Len() int           { return len(h) }
func (h entryHeap) Less(i, j int) bool { return h[i].time > h[j].time }
func (h entryHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *entryHeap) Push(x any)        { *h = append(*h, x.(entry)) }

func (h *entryHeap) Pop() any {
    old := *h
    x := old[len(old)-1]
    *h = old[:len(old)-1]
    return x
}

type Twitter struct {
    timestamp int                      // global counter, ++ on every PostTweet
    tweets    map[int][]tweet          // userId -> tweets in post order
    following map[int]map[int]struct{} // userId -> followeeIds
}

func Constructor() Twitter {
    return Twitter{tweets: map[int][]tweet{}, following: map[int]map[int]struct{}{}}
}

func (this *Twitter) PostTweet(userId int, tweetId int) {
    this.tweets[userId] = append(this.tweets[userId], tweet{this.timestamp, tweetId})
    this.timestamp++
}

func (this *Twitter) GetNewsFeed(userId int) []int {
    pq := &entryHeap{}
    res := []int{}

    push := func(user, idx int) {
        t := this.tweets[user][idx]
        heap.Push(pq, entry{t.time, t.id, user, idx})
    }

    if n := len(this.tweets[userId]); n > 0 {
        push(userId, n-1)
    }
    for user := range this.following[userId] {
        if n := len(this.tweets[user]); user != userId && n > 0 {
            push(user, n-1)
        }
    }

    for pq.Len() > 0 && len(res) < 10 {
        e := heap.Pop(pq).(entry)
        res = append(res, e.id)
        if e.idx > 0 {
            push(e.user, e.idx-1)
        }
    }

    return res
}

func (this *Twitter) Follow(followerId int, followeeId int) {
    if this.following[followerId] == nil {
        this.following[followerId] = map[int]struct{}{}
    }
    this.following[followerId][followeeId] = struct{}{}
}

func (this *Twitter) Unfollow(followerId int, followeeId int) {
    delete(this.following[followerId], followeeId)
}

355_solution1.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

class Twitter {
    private int timestamp = 0;
    private final Map<Integer, List<int[]>> tweets = new HashMap<>(); // userId -> {timestamp, tweetId}
    private final Map<Integer, Set<Integer>> following = new HashMap<>(); // userId -> followeeIds

    public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[] {timestamp++, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        // min-heap of size 10, ordered by timestamp: top is the oldest of the kept tweets
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        scan(userId, pq);
        for (int f : following.getOrDefault(userId, Set.of()))
            if (f != userId)
                scan(f, pq); // avoid scanning own tweets twice

        // heap pops oldest first, so fill the result from the back
        Integer[] res = new Integer[pq.size()];
        for (int i = res.length - 1; i >= 0; i--)
            res[i] = pq.poll()[1];
        return List.of(res);
    }

    private void scan(int uid, PriorityQueue<int[]> pq) {
        for (int[] t : tweets.getOrDefault(uid, List.of())) {
            pq.offer(t);
            if (pq.size() > 10)
                pq.poll();
        }
    }

    public void follow(int followerId, int followeeId) {
        following.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        following.getOrDefault(followerId, new HashSet<>()).remove(followeeId);
    }
}

355_solution2.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

class Twitter {
    private int timestamp = 0; // global counter, ++ on every postTweet
    private final Map<Integer, List<int[]>> tweets = new HashMap<>(); // userId -> list of {timestamp, tweetId}
    private final Map<Integer, Set<Integer>> following = new HashMap<>(); // userId -> set of followeeIds

    public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[] {timestamp++, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        // {time, tweetId, user, idx}, newest first
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        List<Integer> res = new ArrayList<>();

        Set<Integer> users = new HashSet<>(following.getOrDefault(userId, Set.of()));
        users.add(userId);

        for (int user : users) {
            List<int[]> list = tweets.get(user);
            if (list != null && !list.isEmpty()) {
                int idx = list.size() - 1;
                int[] t = list.get(idx);
                pq.offer(new int[] {t[0], t[1], user, idx});
            }
        }

        while (!pq.isEmpty() && res.size() < 10) {
            int[] e = pq.poll();
            res.add(e[1]);
            int idx = e[3];
            if (idx > 0) {
                int[] t = tweets.get(e[2]).get(idx - 1);
                pq.offer(new int[] {t[0], t[1], e[2], idx - 1});
            }
        }

        return res;
    }

    public void follow(int followerId, int followeeId) {
        following.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        following.getOrDefault(followerId, new HashSet<>()).remove(followeeId);
    }
}

355_solution1.js

class Heap {
  // cmp(a, b) < 0 means a comes out first
  constructor(cmp) {
    this.cmp = cmp;
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  push(val) {
    const h = this.data;
    h.push(val);
    let i = h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.cmp(h[p], h[i]) <= 0) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  }

  pop() {
    const h = this.data;
    const top = h[0];
    const last = h.pop();
    if (h.length === 0) return top;
    h[0] = last;
    let i = 0;
    for (;;) {
      let best = i;
      const l = 2 * i + 1,
        r = 2 * i + 2;
      if (l < h.length && this.cmp(h[l], h[best]) < 0) best = l;
      if (r < h.length && this.cmp(h[r], h[best]) < 0) best = r;
      if (best === i) return top;
      [h[best], h[i]] = [h[i], h[best]];
      i = best;
    }
  }
}

class Twitter {
  constructor() {
    this.timestamp = 0;
    this.tweets = new Map(); // userId -> [timestamp, tweetId][]
    this.following = new Map(); // userId -> Set of followeeIds
  }

  postTweet(userId, tweetId) {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId).push([this.timestamp++, tweetId]);
  }

  getNewsFeed(userId) {
    // min-heap of size 10, ordered by timestamp: top is the oldest of the kept
    // tweets
    const pq = new Heap((a, b) => a[0] - b[0]);

    const scan = (uid) => {
      for (const t of this.tweets.get(uid) ?? []) {
        pq.push(t);
        if (pq.size() > 10) pq.pop();
      }
    };

    scan(userId);
    for (const f of this.following.get(userId) ?? [])
      if (f !== userId) scan(f); // avoid scanning own tweets twice

    // heap pops oldest first, so fill the result from the back
    const res = new Array(pq.size());
    for (let i = res.length - 1; i >= 0; i--) res[i] = pq.pop()[1];
    return res;
  }

  follow(followerId, followeeId) {
    if (!this.following.has(followerId)) this.following.set(followerId, new Set());
    this.following.get(followerId).add(followeeId);
  }

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

355_solution2.js

class Heap {
  // cmp(a, b) < 0 means a comes out first
  constructor(cmp) {
    this.cmp = cmp;
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  push(val) {
    const h = this.data;
    h.push(val);
    let i = h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.cmp(h[p], h[i]) <= 0) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  }

  pop() {
    const h = this.data;
    const top = h[0];
    const last = h.pop();
    if (h.length === 0) return top;
    h[0] = last;
    let i = 0;
    for (;;) {
      let best = i;
      const l = 2 * i + 1,
        r = 2 * i + 2;
      if (l < h.length && this.cmp(h[l], h[best]) < 0) best = l;
      if (r < h.length && this.cmp(h[r], h[best]) < 0) best = r;
      if (best === i) return top;
      [h[best], h[i]] = [h[i], h[best]];
      i = best;
    }
  }
}

class Twitter {
  constructor() {
    this.timestamp = 0; // global counter, ++ on every postTweet
    this.tweets = new Map(); // userId -> list of [timestamp, tweetId]
    this.following = new Map(); // userId -> set of followeeIds
  }

  postTweet(userId, tweetId) {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId).push([this.timestamp++, tweetId]);
  }

  getNewsFeed(userId) {
    // [time, tweetId, user, idx], newest first
    const pq = new Heap((a, b) => b[0] - a[0]);
    const res = [];

    const users = new Set(this.following.get(userId));
    users.add(userId);

    for (const user of users) {
      const list = this.tweets.get(user);
      if (list?.length) {
        const idx = list.length - 1;
        pq.push([...list[idx], user, idx]);
      }
    }

    while (pq.size() > 0 && res.length < 10) {
      const [, tweetId, user, idx] = pq.pop();
      res.push(tweetId);
      if (idx > 0) pq.push([...this.tweets.get(user)[idx - 1], user, idx - 1]);
    }

    return res;
  }

  follow(followerId, followeeId) {
    if (!this.following.has(followerId)) this.following.set(followerId, new Set());
    this.following.get(followerId).add(followeeId);
  }

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

355_solution1.py

import heapq
from collections import defaultdict
from typing import List


class Twitter:
    def __init__(self):
        self.timestamp = 0
        self.tweets: dict[int, list[tuple[int, int]]] = defaultdict(list)  # userId -> (timestamp, tweetId)
        self.following: dict[int, set[int]] = defaultdict(set)  # userId -> followeeIds

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.timestamp, tweetId))
        self.timestamp += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        # min-heap of size 10, ordered by timestamp: top is the oldest of the kept tweets
        pq: list[tuple[int, int]] = []

        def scan(uid: int) -> None:
            for t in self.tweets.get(uid, []):
                heapq.heappush(pq, t)
                if len(pq) > 10:
                    heapq.heappop(pq)

        scan(userId)
        for f in self.following.get(userId, ()):
            if f != userId:
                scan(f)  # avoid scanning own tweets twice

        # heap pops oldest first, so reverse at the end
        res = [heapq.heappop(pq)[1] for _ in range(len(pq))]
        return res[::-1]

    def follow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)

355_solution2.py

import heapq
from collections import defaultdict
from typing import List


class Twitter:
    def __init__(self):
        self.timestamp = 0  # global counter, += 1 on every postTweet
        self.tweets: dict[int, list[tuple[int, int]]] = defaultdict(list)  # userId -> list of (timestamp, tweetId)
        self.following: dict[int, set[int]] = defaultdict(set)  # userId -> set of followeeIds

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.timestamp, tweetId))
        self.timestamp += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        pq = []  # (-time, tweetId, user, idx): negate for a max-heap
        res = []

        for user in self.following.get(userId, set()) | {userId}:
            if self.tweets.get(user):
                idx = len(self.tweets[user]) - 1
                time, tweet_id = self.tweets[user][idx]
                pq.append((-time, tweet_id, user, idx))
        heapq.heapify(pq)

        while pq and len(res) < 10:
            _, tweet_id, user, idx = heapq.heappop(pq)
            res.append(tweet_id)
            if idx > 0:
                time, tweet_id = self.tweets[user][idx - 1]
                heapq.heappush(pq, (-time, tweet_id, user, idx - 1))

        return res

    def follow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)

355_solution1.rs

use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap, HashSet};

struct Twitter {
    timestamp: i32,
    tweets: HashMap<i32, Vec<(i32, i32)>>, // userId -> (timestamp, tweetId)
    following: HashMap<i32, HashSet<i32>>, // userId -> followeeIds
}

impl Twitter {
    fn new() -> Self {
        Self { timestamp: 0, tweets: HashMap::new(), following: HashMap::new() }
    }

    fn post_tweet(&mut self, user_id: i32, tweet_id: i32) {
        self.tweets.entry(user_id).or_default().push((self.timestamp, tweet_id));
        self.timestamp += 1;
    }

    fn get_news_feed(&self, user_id: i32) -> Vec<i32> {
        // min-heap of size 10, ordered by timestamp: top is the oldest of the kept tweets
        let mut pq = BinaryHeap::new();

        let mut scan = |uid: i32| {
            for &t in self.tweets.get(&uid).into_iter().flatten() {
                pq.push(Reverse(t));
                if pq.len() > 10 {
                    pq.pop();
                }
            }
        };

        scan(user_id);
        for &f in self.following.get(&user_id).into_iter().flatten() {
            if f != user_id {
                scan(f); // avoid scanning own tweets twice
            }
        }

        // into_sorted_vec is ascending on Reverse, i.e. newest first
        pq.into_sorted_vec().into_iter().map(|Reverse((_, id))| id).collect()
    }

    fn follow(&mut self, follower_id: i32, followee_id: i32) {
        self.following.entry(follower_id).or_default().insert(followee_id);
    }

    fn unfollow(&mut self, follower_id: i32, followee_id: i32) {
        if let Some(set) = self.following.get_mut(&follower_id) {
            set.remove(&followee_id);
        }
    }
}

355_solution2.rs

use std::collections::{BinaryHeap, HashMap, HashSet};

struct Twitter {
    timestamp: i32,                        // global counter, += 1 on every post_tweet
    tweets: HashMap<i32, Vec<(i32, i32)>>, // userId -> list of (timestamp, tweetId)
    following: HashMap<i32, HashSet<i32>>, // userId -> set of followeeIds
}

impl Twitter {
    fn new() -> Self {
        Self { timestamp: 0, tweets: HashMap::new(), following: HashMap::new() }
    }

    fn post_tweet(&mut self, user_id: i32, tweet_id: i32) {
        self.tweets.entry(user_id).or_default().push((self.timestamp, tweet_id));
        self.timestamp += 1;
    }

    fn get_news_feed(&self, user_id: i32) -> Vec<i32> {
        let mut pq = BinaryHeap::new(); // (time, tweetId, user, idx)
        let mut res = Vec::new();

        let followees = self.following.get(&user_id).into_iter().flatten();
        let users: HashSet<i32> = followees.copied().chain([user_id]).collect();

        for user in users {
            if let Some(list) = self.tweets.get(&user).filter(|l| !l.is_empty()) {
                let idx = list.len() - 1;
                let (time, tweet_id) = list[idx];
                pq.push((time, tweet_id, user, idx));
            }
        }

        while res.len() < 10 {
            let Some((_, tweet_id, user, idx)) = pq.pop() else { break };
            res.push(tweet_id);
            if idx > 0 {
                let (time, tweet_id) = self.tweets[&user][idx - 1];
                pq.push((time, tweet_id, user, idx - 1));
            }
        }

        res
    }

    fn follow(&mut self, follower_id: i32, followee_id: i32) {
        self.following.entry(follower_id).or_default().insert(followee_id);
    }

    fn unfollow(&mut self, follower_id: i32, followee_id: i32) {
        if let Some(set) = self.following.get_mut(&follower_id) {
            set.remove(&followee_id);
        }
    }
}