系統設計

1type Post = { id: number; author: number; time: number };
2 
3class FeedService {
4  private outbox = new Map<number, Post[]>(); // each author's posts, oldest first
5  private inbox = new Map<number, Post[]>();  // precomputed feeds, oldest first
6 
7  constructor(
8    private followers: number[][], // followers[a]: who follows a
9    private following: number[][], // following[u]: whom u follows
10    private strategy: "push" | "pull" | "hybrid",
11    private threshold = 1000,
12  ) {}
13 
14  private isCelebrity(author: number): boolean {
15    return this.followers[author].length >= this.threshold;
16  }
17 
18  publish(post: Post): void {
19    const own = this.outbox.get(post.author) ?? [];
20    own.push(post);
21    this.outbox.set(post.author, own);
22    if (this.strategy === "pull") return;
23    if (this.strategy === "hybrid" && this.isCelebrity(post.author)) return;
24    for (const f of this.followers[post.author]) {
25      const feed = this.inbox.get(f) ?? [];
26      feed.push(post);
27      this.inbox.set(f, feed);
28    }
29  }
30 
31  readFeed(user: number, k: number): Post[] {
32    const lists: Post[][] = [];
33    if (this.strategy !== "pull") lists.push(this.inbox.get(user) ?? []);
34    for (const a of this.following[user]) {
35      if (this.strategy === "pull" || (this.strategy === "hybrid" && this.isCelebrity(a))) {
36        lists.push(this.outbox.get(a) ?? []);
37      }
38    }
39    const head = lists.map((list) => list.length - 1);
40    const feed: Post[] = [];
41    while (feed.length < k) {
42      let best = -1;
43      for (let i = 0; i < lists.length; i++) {
44        if (head[i] >= 0 && (best < 0 || lists[i][head[i]].time > lists[best][head[best]].time)) best = i;
45      }
46      if (best < 0) break;
47      feed.push(lists[best][head[best]--]);
48    }
49    return feed;
50  }
51}