Python技术迷

我把领导的私密聊天记录同步到了全员群,结果...领导当天就被老板约谈

手滑年年有,哎,这回轮到行政同事了:刚上岗就把领导私聊里那句“老板真抠、我都想走了”,一键同步进了500人全员群。群里安静得像服务器宕机,我觉得空气都能听见CPU风扇转。

Image

网友们看完笑疯:有人说“这叫公开透明,领导省了复盘会”;有人补刀“建议下次同步前先跑个单元测试”;还有人更狠:“老板:谢谢你让我少养一个想跳槽的。”

我觉得最惨的还是当事人,明明只是点错按钮,结果领导被约谈、自己连辞职信标题都想好了。最后领导扛住了,只私下说:这种错,一次就够。话说回来,这种同步功能也真香,文件、消息不怕丢,换手机也不断档,前提是别把它当‘群发核弹’按钮。

算法题:设计推特

哎你们这个“设计推特”啊,我跟你说,每次看到都像在公司群里看同事发消息:一分钟发 3 条,领导还要我“按时间倒序”把最近 10 条捞出来……我人都麻了。然后你发现问题本质其实就俩字:时间线。谁发了啥、谁关注了谁、我刷的时候把关注的人(包括我自己)最近的内容按时间排一下,取前 10。

我当年第一次写这个题,脑子里想着“那我给每个人维护一条全局链表不就完了?”结果写着写着就走偏了,跟自己较劲:要不要用平衡树,要不要上数据库索引(我真有病)。后来一想,题里就要你接口能跑,别整花活:每个用户存自己发过的推,再加个关注集合;刷 feed 的时候,把“我关注的这些人”各自的最新一条先塞进堆里,像合并 K 个有序链表那样,一次弹出一条再补一条,弹够 10 条就收工。

关键点有俩:

  • 得有个 timestamp,每发一次推就 time += 1,保证全局顺序(不要用真实时间,面试官电脑时间乱你就哭)
  • Python 里用 heapq 是小根堆,所以我们把时间取负数,当大根堆用

然后代码我给你写个“能直接过”的版本,比较干净,但也不装:

from collections import defaultdict
import heapq

classTwitter:
def__init__(self):
        self.time = 0# 全局时间戳,越大越新
        self.following = defaultdict(set)  # user -> set(followee)
        self.tweets = defaultdict(list)    # user -> list of (time, tweetId)

defpostTweet(self, userId: int, tweetId: int) -> None:
        self.time += 1
        self.tweets[userId].append((self.time, tweetId))

deffollow(self, followerId: int, followeeId: int) -> None:
if followerId == followeeId:
return
        self.following[followerId].add(followeeId)

defunfollow(self, followerId: int, followeeId: int) -> None:
if followerId == followeeId:
return
        self.following[followerId].discard(followeeId)

defgetNewsFeed(self, userId: int):
# 关注的人 + 自己
        people = set(self.following[userId])
        people.add(userId)

        heap = []
# 每个人先塞“最后一条”
for u in people:
            arr = self.tweets[u]
if arr:
                idx = len(arr) - 1
                t, tid = arr[idx]
# 堆元素:(-time, tweetId, user, idx)
                heapq.heappush(heap, (-t, tid, u, idx))

        res = []
while heap and len(res) < 10:
            neg_t, tid, u, idx = heapq.heappop(heap)
            res.append(tid)
# 把这个人的上一条补进去
            idx -= 1
if idx >= 0:
                t, tid2 = self.tweets[u][idx]
                heapq.heappush(heap, (-t, tid2, u, idx))

return res

你看这个逻辑就很像我刷短视频:先把关注的博主“最新一条”都摆桌上(堆),我每看完一条,就让那个博主“再端上一条更老的”,端到我看够 10 条我就溜了,绝不深情,算法也一样现实。

复杂度也挺符合直觉:假设你关注了 F 个人,每个人发过的推你不需要全扫,只要在堆里最多弹 10 次,每次 log F,所以刷一次大概是 O((F + 10) log F)(前面建堆要塞 F 条)。这就是为啥别把所有推全合并排序,那种写法一到大数据就像周五晚高峰打车,直接红温。