6. Design Twitter

package twitter

import (
    "container/heap"
    "sync"
    "sync/atomic"
)

// Tweet представляет опубликованное сообщение.
type Tweet struct {
    ID   int
    Time int64
}

// User инкапсулирует твиты пользователя и граф его подписок.
type User struct {
    mu        sync.RWMutex
    id        int
    following map[int]struct{}
    tweets    []Tweet // плоский срез, новые твиты в конце
}

func newUser(id int) *User {
    return &User{
        id:        id,
        following: make(map[int]struct{}),
        tweets:    make([]Tweet, 0, 32),
    }
}

// heapNode хранит состояние обхода ленты конкретного автора.
type heapNode struct {
    tweet Tweet
    uid   int
    index int // индекс следующего твита для просмотра в tweets автора
}

// maxTweetHeap реализует интерфейс heap.Interface для поиска самых свежих твитов.
type maxTweetHeap []heapNode

func (h maxTweetHeap) Len() int           { return len(h) }
func (h maxTweetHeap) Less(i, j int) bool { return h[i].tweet.Time > h[j].tweet.Time } // Max-Heap
func (h maxTweetHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *maxTweetHeap) Push(x any)        { *h = append(*h, x.(heapNode)) }
func (h *maxTweetHeap) Pop() any {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[0 : n-1]
    return item
}

// Twitter координирует пользователей и глобальное время.
type Twitter struct {
    mu      sync.RWMutex
    users   map[int]*User
    clock   atomic.Int64 // монотонный генератор логического времени
}

func Constructor() Twitter {
    return Twitter{
        users: make(map[int]*User),
    }
}

func (t *Twitter) getOrCreateUser(userId int) *User {
    t.mu.RLock()
    u, ok := t.users[userId]
    t.mu.RUnlock()
    if ok {
        return u
    }

    t.mu.Lock()
    defer t.mu.Unlock()
    // Double-check locking
    if u, ok = t.users[userId]; ok {
        return u
    }
    u = newUser(userId)
    t.users[userId] = u
    return u
}

// PostTweet публикует твит от имени пользователя.
func (t *Twitter) PostTweet(userId int, tweetId int) {
    u := t.getOrCreateUser(userId)
    timestamp := t.clock.Add(1)

    u.mu.Lock()
    u.tweets = append(u.tweets, Tweet{ID: tweetId, Time: timestamp})
    u.mu.Unlock()
}

// GetNewsFeed формирует ленту из 10 самых свежих твитов.
func (t *Twitter) GetNewsFeed(userId int) []int {
    u := t.getOrCreateUser(userId)

    // Собираем снимок списка авторов: сам пользователь + подписки
    u.mu.RLock()
    authors := make([]int, 0, len(u.following)+1)
    authors = append(authors, userId)
    for fid := range u.following {
        authors = append(authors, fid)
    }
    u.mu.RUnlock()

    // Инициализируем кучу
    h := make(maxTweetHeap, 0, len(authors))

    for _, aid := range authors {
        author := t.getOrCreateUser(aid)
        author.mu.RLock()
        n := len(author.tweets)
        if n > 0 {
            // Берем самый последний (самый свежий) твит
            lastTweet := author.tweets[n-1]
            h = append(h, heapNode{
                tweet: lastTweet,
                uid:   aid,
                index: n - 2, // указатель на предыдущий твит
            })
        }
        author.mu.RUnlock()
    }

    heap.Init(&h)

    result := make([]int, 0, 10)

    // Извлекаем до 10 твитов
    for h.Len() > 0 && len(result) < 10 {
        top := heap.Pop(&h).(heapNode)
        result = append(result, top.tweet.ID)

        if top.index >= 0 {
            author := t.getOrCreateUser(top.uid)
            author.mu.RLock()
            if top.index < len(author.tweets) {
                prevTweet := author.tweets[top.index]
                heap.Push(&h, heapNode{
                    tweet: prevTweet,
                    uid:   top.uid,
                    index: top.index - 1,
                })
            }
            author.mu.RUnlock()
        }
    }

    return result
}

// Follow подписывает followerId на followeeId.
func (t *Twitter) Follow(followerId int, followeeId int) {
    if followerId == followeeId {
        return
    }
    u := t.getOrCreateUser(followerId)
    t.getOrCreateUser(followeeId) // гарантируем существование цели

    u.mu.Lock()
    u.following[followeeId] = struct{}{}
    u.mu.Unlock()
}

// Unfollow отписывает followerId от followeeId.
func (t *Twitter) Unfollow(followerId int, followeeId int) {
    if followerId == followeeId {
        return
    }
    u := t.getOrCreateUser(followerId)

    u.mu.Lock()
    delete(u.following, followeeId)
    u.mu.Unlock()
}

[ Кэш-линия L1: 64 байта ]
| Tweet 0 (16B) | Tweet 1 (16B) | Tweet 2 (16B) | Tweet 3 (16B) |