专栏首页灵魂画师牧码设计 Twitter:合并 k 个有序链表和面向对象设计

设计 Twitter:合并 k 个有序链表和面向对象设计

预计阅读时间: 10 分钟

「design Twitter」是 LeetCode 上第 335 道题目,让我们设计 Twitter 的一些功能。不仅题目很有意思,而且把合并多个有序链表的算法和面向对象设计(OO design)结合起来了,很有实际意义,本文就带大家来看看这道题。

至于 Twitter 的什么功能跟算法有关系,等我们描述一下题目要求就知道了。

PS:文末「阅读原文」按钮附大型系统设计学习资源的 Github 链接。

一、题目及应用场景简介

Twitter 和微博功能差不多,我们主要要实现这样几个 API:

举个具体的例子,方便大家理解 API 的具体用法:

这个场景在我们的现实生活中非常常见。拿朋友圈举例,比如我刚加到女神的微信,然后我去刷新一下我的朋友圈动态,那么女神的动态就会出现在我的动态列表,而且会和其他动态按时间排好序。只不过 Twitter 是单向关注,微信好友相当于双向关注。除非,被屏蔽...

这几个 API 中大部分都很好实现,最核心的功能难点应该是 getNewsFeed,因为返回的结果必须在时间上有序,但问题是用户的关注是动态变化的,怎么办?

这里就涉及到算法了:如果我们把每个用户各自的推文存储在链表里,每个链表节点存储文章 id 和一个时间戳 time(记录发帖时间以便比较),而且这个链表是按 time 有序的,那么如果某个用户关注了 k 个用户,我们就可以用合并 k 个有序链表的算法合并出有序的推文列表,正确地 getNewsFeed 了!

具体的算法等会讲解。不过,就算我们掌握了算法,应该如何编程表示用户 user 和推文动态 tweet 才能把算法流畅地用出来呢?这就涉及简单的面向对象设计了,下面我们来由浅入深,一步一步进行设计。

二、面向对象设计

根据刚才的分析,我们需要一个 User 类,储存 user 信息,还需要一个 Tweet 类,储存推文信息,并且要作为链表的节点。所以我们先搭建一下整体的框架:

之所以要把 Tweet 和 User 类放到 Twitter 类里面,是因为 Tweet 类必须要用到一个全局时间戳 timestamp,而 User 类又需要用到 Tweet 类记录用户发送的推文,所以它们都作为内部类。不过为了清晰和简洁,下文会把每个内部类和 API 方法单独拿出来实现。

1、Tweet 类的实现

根据前面的分析,Tweet 类很容易实现:每个 Tweet 实例需要记录自己的 tweetId 和发表时间 time,而且作为链表节点,要有一个指向下一个节点的 next 指针。

class Tweet {
    private int id;
    private int time;
    private Tweet next;

    // 需要传入推文内容(id)和发文时间
    public Tweet(int id, int time) {
        this.id = id;
        this.time = time;
        this.next = null;
    }
}

2、User 类的实现

我们根据实际场景想一想,一个用户需要存储的信息有 userId,关注列表,以及该用户发过的推文列表。其中关注列表应该用集合(Hash Set)这种数据结构来存,因为不能重复,而且需要快速查找;推文列表应该由链表这种数据结构储存,以便于进行有序合并的操作。画个图理解一下:

除此之外,根据面向对象的设计原则,「关注」「取关」和「发文」应该是 User 的行为,况且关注列表和推文列表也存储在 User 类中,所以我们也应该给 User 添加 follow,unfollow 和 post 这几个方法:

3、几个 API 方法的实现

三、算法设计

实现合并 k 个有序链表的算法需要用到优先级队列(Priority Queue),这种数据结构是「二叉堆」最重要的应用。

如果你对优先级队列不太了解,可以理解为它可以对插入的元素自动排序。乱序的元素插入其中就被放到了正确的位置,可以按照从小到大(或从大到小)有序地取出元素。

PriorityQueue pq
# 乱序插入
for i in {2,4,1,9,6}:
    pq.add(i)
while pq not empty:
    # 每次取出第一个(最小)元素
    print(pq.pop())

# 输出有序:1,2,4,6,9

借助这种牛逼的数据结构支持,我们就很容易实现这个核心功能了。注意我们把优先级队列设为按 time 属性从大到小降序排列,因为 time 越大意味着时间越近,应该排在前面:

这个过程是这样的,下面是我制作的一个 GIF 图描述合并链表的过程。假设有三个 Tweet 链表按 time 属性降序排列,我们把他们降序合并添加到 res 中。注意图中链表节点中的数字是 time 属性,不是 id 属性:

至此,一个简化的 Twitter 时间线功能就设计完毕了。

四、最后总结

本文运用简单的面向对象技巧和合并 k 个有序链表的算法设计了一套简化的时间线功能,这个功能其实广泛地运用在许多社交应用中。

我们先合理地设计出 User 和 Tweet 两个类,然后基于这个设计之上运用算法解决了最重要的一个功能。可见实际应用中的算法并不是孤立存在的,需要和其他知识混合运用,才能发挥实际价值。

当然,实际应用中的社交 App 数据量是巨大的,考虑到数据库的读写性能,我们的设计可能承受不住流量压力,还是有些太简化了。而且实际的应用都是一个极其庞大的工程,比如下图,是 Twitter 这样的社交网站大致的系统结构:

我们解决的问题应该只能算 Timeline Service 模块的一小部分,功能越多,系统的复杂性可能是指数级增长的。所以说合理的顶层设计十分重要,其作用是远超某一个算法的。

最后,Github 上有一个优秀的开源项目,专门收集了很多大型系统设计的案例和解析,而且有中文版本,上面这个图也出自该项目。对系统设计感兴趣的读者可以点击「阅读原文」查看。

PS:本文前两张图片和 GIF 是我第一次尝试用平板的绘图软件制作的,花了很多时间,尤其是 GIF 图,需要一帧一帧制作。如果本文内容对你有帮助,点个赞分个享,鼓励一下我呗!

本文分享自微信公众号 - 牧码啦(mumalo),作者:labuladong

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Linus 在 Google 分享了 Git 的设计思路,顺带怼了一大波人(视频)

    去年在微博上,看到了有位技术博主整理翻译了一个关于 Linux 创始人 Linus 的演讲视频:「Git 的特点和设计思路」。

    灵魂画师牧码
  • 画解算法:67. 二进制求和

    https://leetcode-cn.com/problems/add-binary/

    灵魂画师牧码
  • 3道题彻底搞定:套路解决递归问题

    相信不少同学和我一样,在刚学完数据结构后开始刷算法题时,遇到递归的问题总是很头疼,而一看解答,却发现大佬们几行递归代码就优雅的解决了问题。从我自己的学习经历来看...

    灵魂画师牧码
  • 欧迪办公为新品牌启用升级版域名:BizBox

    Office Depot公司(欧迪办公)成立于1986年,总部位于美国佛罗里达州,年销售额150多亿美元,全球员工近52000人,为43个国家和地区的客...

    躲在树上的域小名
  • Flask第一篇——URL详解

    用户2149234
  • Debug 远程调试

    大家都知道debug本地调试,就是再自己的代码上打一个断点,然后debug运行就可以本地调试,那么远程调试就是,代码再虚拟机上运行。自己可以看到虚拟机上运行的...

    斯文的程序
  • Jaeger 1.8.2 发布 开源分布式追踪系统

    Jaeger 是 Uber 开源的分布式追踪系统,灵感来自于 Dapper 和 OpenZipkin ,现已加入 CNCF 基金会。它可以用于监视基于微服务的体...

    Debian社区
  • [日常] 面试知识点总结(持续更新)

    陶士涵
  • 思考,快与慢

    吐槽:GitBook editor 有个二B的设计-当它莫名检测出文件被外星人修改后,会弹个无法取消的对话框-检测出外部修改,ignore? discard? ...

    tyrchen
  • Python Django添加superuser

    用户1258909

扫码关注云+社区

领取腾讯云代金券