业务开发算法50讲

业务开发算法50讲 / 从算法的工程实践开始,提升问题解决能力

黄清昊 EMQ X存储工程师,LeetCode高赞答主
  • 课程目录
  • 课程介绍
  • 在线阅读:开篇词|真实世界的算法,和你想的不一样

    让我们一起来探索工程实战中每天都存在的算法问题吧!

  • 先导篇|诶,这个 git diff 好像不是很直观?

    你知道每天都在用的 git diff 背后,是什么算法吗?

  • 01|动态数组:按需分配的vector为什么要二倍扩容?

    数组的关键词是:相同类型、连续内存、顺序存储

  • 02|双向链表:list如何实现高效地插入与删除?

    链表:删除、插入、遍历操作频繁,而不适用于随机访问索引频繁

  • 03|双端队列:并行计算中的工作窃取算法如何实现?

    work stealing 工作窃取算法,核心用到的数据结构是什么?

  • 04|栈:函数调用的秘密究竟是什么?

    我们熟悉的stack overflow中,栈帧完美运用了栈LIFO的特性。

  • 05|HashMap:一个优秀的散列表是怎么来的?

    散列函数的本质,就是将一个更大且可能不连续空间,映射到一个空间有限的数组里,从而借用数组基于下标O(1)快速随机访问数组元素的能力。

  • 06|TreeMap:红黑树真的有那么难吗?

    红黑树,本质是2-3树在二叉树上的一种模拟,通过旋转操作完成2-3节点的合并和分裂,从而在不改变二叉树节点结构的前提下,保证二叉树的有序性和平衡性。

  • 07|堆:如何实现一个高效的优先队列?

    在JDK中的PQ实现里,并没有和我们想象中一般的树那样采用节点+指针来实现树状数据结构,而是用了内存上连续的数组来模拟。

  • 08|外部排序:如何为TB级数据排序?

    许多算法问题都不能只简单地考虑内存中可以存储,甚至单机磁盘可以存储的情况了,今天学习外排算法思想,给你一些解决此类问题的启发。

  • 09|二分:如何高效查询Kafka中的消息?

    相比简单的内存中的二分查询,Kafka中的二分查询考虑了更多的“现实”问题。这也是我们在工程中遇到算法问题和平时做算法题的算法的一个很大的差异。

  • 10|搜索算法: 一起来写一个简单的爬虫?

    BFS和DFS,作为两种最暴力、也相当常用的搜索策略,最大的特点就是无差别地去遍历搜索空间的每一种情况,但凡是可以抽象成图上的问题,基本上都可以考虑用BFS、DFS去做。

  • 11|字符串匹配:如何实现最快的grep工具

    BM算法,最大的特点就是利用了对目标串的预处理,用空间换时间,避免了许多不必要的比较。

  • 12|拓扑排序:Webpack是如何确定构建顺序的?

    什么叫拓扑?每个节点只出现一次,且保证如果存在路径P从A指向B,那么A在序列中一定出现在B之前。

  • 13|哈夫曼树:HTTP2.0是如何更快传输协议头的?

    HPACK是HTTP/2.0 为了降低HTTP payload大小从而提高传输效率的杀招,应用了静态表、动态表和哈夫曼编码三种技术,把冗余的HTTP头信息大大压缩。

  • 14|调度算法:操作系统中的进程是如何调度的?

    不同的调度算法有不同的使用场景,很难说哪个算法一定比另一个更好,只是在公平性、效率、吞吐量、等待时间等因素间做了不同的取舍。

  • 15|LRU:在虚拟内存中页面是如何置换的?

    通过分页和虚拟内存的抽象,操作系统解放了用户对内存管理和容量的心智负担。当缓存的数据越来越多,如何选择一个合适的页面或缓存内容来替换,就是缓存置换算法的用武之地。

  • 16|日志型文件系统:写入文件的时候断电了会发生什么?

    写文件写到一半断电了,或者因为各种各样的原因系统崩溃了,系统重启之后文件是否还能被正常地读写呢?如果不能的话,我们应该怎么办呢?

  • 17|选路算法:Dijkstra是如何解决最短路问题的?

    网络路由算法,核心就是在动态变化的网络中,基于探测和寻找最快传输路径的想法,帮助路由器建立路由表,让每个数据包都可以快速且正确地传播到正确目的地。

  • 18|选路算法:链路状态算法是如何分发全局信息的

    在Dijkstra算法的基础上,动态的链路状态算法具体如何解决网络路由问题?

  • 19|选路算法:距离矢量算法为什么会产生无穷计算问题?

    距离矢量算法背后的Bellman-Ford本质就是对所有边无差别的松弛操作,迭代地进行很多轮,本地的、非中心化的算法。

  • 20|滑动窗口:TCP是如何进行流量控制和拥塞控制的?

    TCP协议不止考虑了包的可靠传输,同时也兼顾了效率,更提供了对流量控制和拥塞避免的能力,滑动窗口和拥塞窗口的设计就是为了这两个目的。

  • 21|分而治之:MapReduce如何解决大规模分布式计算问题

    我们今天学习谷歌的三驾马车之一:MapReduce算法。

  • 22|PageRank:谷歌是如何计算网页排名的

    谷歌三驾马车之二 PageRank 算法,利用网页之间的链接关系,通过迭代的方式计算网页的权重,帮助谷歌获得了更好的搜索质量打败竞争对手。

  • 23|Raft:分布式系统间如何达成共识?

    Raft,复杂问题拆解成多个明确清晰的子问题,分而治之。

  • 24|UUID:如何高效生成全局的唯一ID?

    生成分布式唯一ID的两种思路:引入额外的系统生成ID、在业务侧本地通过规则约束独立生成ID。

  • 25|一致性哈希:如何在集群上合理分配流量?

    在请求和服务有状态时,我们要想办法把有状态的请求稳定的指向同一台机器,保证上下文的连续性,同时起到均衡的效果。

  • 26|B+ Tree:PostgreSQL 的索引是如何建立的?

    B+树,整个结构更矮胖,加上磁盘的预读特性,每次都可以加载一整个节点中全部的键,到内存做二分查找,这样只需要通过3~5次的磁盘IO就可以查询加了索引的字段,非常高效。

  • 27|LSM Tree:LevelDB的索引是如何建立的?

    modern LSM tree的实现,分为内存和磁盘上的数据结构两部分,内存memtable、immutable memtable用通用的有序集合存储即可,磁盘SSTable就是一段段连续按key有序存储的段。

  • 28|MVCC:如何突破数据库并发读写性能瓶颈?

    事务隔离等级,就是某个事务对其他事务修改数据结果的可见性情况。为了处理脏读、不可重复读、幻读,由弱到强,定义了读未提交、读已提交、可重复读和串行化四个隔离等级。

  • 29|位图:如何用更少空间对大量数据进行去重和排序?

    bitmap,位图,本质上是一种通过二进制位来记录状态的数据结构。常用于大量数据去重和排序、内存资源敏感、需要标记状态等场景下。

  • 30|布隆过滤器:如何解决Redis缓存穿透问题?

    布隆过滤器,通过对每个元素进行某种散射式的Hash,把状态记录在Bitmap中,在大量数据中判断某个元素是否存在,高效且成本低。

  • 31|跳表:Redis是如何存储有序集合的?

    跳表,本质上说,是高层的链表,和线性索引的原理很像,通过为原始的链表增加不同层的索引,起到和平衡二分搜索树一样快速搜索的效果。

  • 32|时间轮:Kafka是如何实现定时任务的?

    时队列的三种底层实现方式:JDK中的DelayedQueue、借助Redis中ZSET的实现、Kafka中时间轮的实现。

  • 33|限流算法:如何防止系统过载?

    计算机的世界里到处都是trade off,魔法并不存在,要始终铭记在权衡方案时,如果我们在某些方面获得了一些好处,那就一定要警觉在另一些方面是否付出了一些代价,以及代价是否可承受。

  • 34|前缀树:Web框架中如何实现路由匹配?

    前缀树,采用了独特的树状存储结构,是一种高效的有序集合的实现,在节点中存储的是某个串的一个组成单元,对于字符串来说通常就是一个字符。

  • 结束语|在技术的世界里享受思维的乐趣

    在技术的世界里享受思维的乐趣,这是我对你最大的祝愿,希望这个专栏可以帮助你更快地实现这个目标。

  • 期末测试|来赴一场满分之约!

    特别给你准备了一套算法结课测试题,快来挑战一下吧!

  • 特别策划|面试:BAT面试三关准备方法大揭秘

    大厂面试核心考察的就是你的潜力,主要就三关:算法、计算机基础知识、领域知识。

  • 即学即练|基础数据结构篇:复习卡 & 算法题特训

    必知必会算法题 & 一键直达复习卡,学练结合,欢迎参与~

  • 即学即练|基础算法思想篇:复习卡 & 算法题特训

    必知必会算法题 & 一键直达复习卡,学练结合,欢迎参与~

  • 即学即练|操作系统篇:复习卡 & 算法题特训

    必知必会算法题 & 一键直达复习卡,学练结合,欢迎参与~

  • 即学即练|计算机网络篇:复习卡 & 算法题特训

    必知必会算法题 & 一键直达复习卡,学练结合,欢迎参与~

  • 即学即练|分布式篇:复习卡一键直达

    分布式篇,你学得如何啦?

  • 即学即练|工程实战篇:复习卡一键直达

    工程实战篇,你掌握了多少?

45讲

你将获得

  • 35 类算法实战应用场景
  • 6 大领域常用算法知识体系
  • 源码剖析+手写实现,深入细节
  • 清晰图解+论文精读,吃透算法

讲师介绍


课程介绍

之前花很多时间学的算法和数据结构,好像就是为了应对面试关,对日常的开发工作没有什么帮助。

入职之后,没什么机会和需求要手写一些基础的数据结构,往往做着 CURD 的活;算法的存在感,最多就是调用调用 JDK 的包、STL 的函数,算法就像是只存在于那些开箱即用的中间件和基础库中而已,和我们的日常开发没什么关系。

而且学习算法的过程相当痛苦,不只是学习曲线比较陡峭,主要还是平时可能完全用不到这些知识,边学边忘,没有连续的时间投入和充分的刻意练习。偶尔想起来做一做 LeetCode,发现刚学完的知识点根本记不住,不理解大厂面试为什么问这么多算法题。

其实纠结面试的算法值不值得学,是本末倒置了。算法,在开发者日常工作中无处不在,真正的价值在于,能解决工程实战中存在的真实问题。所以越是薪资高的大厂,越会通过算法题考察面试者的思考问题和解决问题的能力。

这个专栏将从实际工程问题的视角,为你呈上一堂实用、精彩的算法课。

黄清昊老师不仅会和你讨论基础的数据结构和算法思想,更会着重帮你掌握这些算法是如何运行在真实的物理机器上的、是如何解决实际业务系统中的问题的,以及是如何在各个稳定运行的中间件、分布式系统、基础库中实现的。在这个过程中,你的思考问题和解决问题的能力都会得到锻炼,希望能真正帮助到有类似疑惑的你。

课程设计

专栏主要分为偏基础和偏实战的两部分,共 6 个模块,为你精讲开发工作中真正用得上的算法。

正式学习之前,将通过一个简单、有趣、常用的文本差分算法为先导,探索那些就在开发者身边却常常被熟视无睹的算法,体验思维的乐趣。

  • 数据结构篇、算法思想篇

这两个模块,包含了工程中常用的基础数据结构和算法思想,比如双向链表、动态数组、哈希表、红黑树、二分搜索、深度优先搜索、贪心算法等,由浅入深,推演算法的来历和特点,分析源码实现思路,不只是了解算法知识,更要理解工业级的算法实现是如何运行在真实的物理机上的。

  • 操作系统篇、计算机网络篇

这两个模块,会带你学习两门非常重要的计算机基础课——操作系统和计算机网络中会用到的基础算法,同样会结合真实的网络库、操作系统的源码进行讲解。这样当你了解许多经典算法的发明背景和应用场景时,再结合操作系统和计算机网络的基础知识,你可以对算法有更深入的理解。

  • 分布式篇、工程实践篇

学习高流量、高并发、高可用的现代互联网应用中各种算法的应用,解析 Redis、MySQL 和 MapReduce 等系统或者论文的经典源码。深入理解在各场景下如何拆解问题、应用算法,目的是升级编程思维,帮助你排查真实业务开发中的各种问题,做出良好的架构设计。

最后将挑选出几个有趣的算法,在高手番外篇中不定期奉上。


课程目录


特别放送

免费领取福利


限时活动推荐


订阅须知

随机推荐

朗适RS100功能是否出色?深度评测教你怎么选?

狮王小狮王儿童氟防蛀牙膏 20g怎么样?评测教你怎么选?

狮王小狮王儿童氟防蛀牙膏 20g使用感受如何?小白买前必看!

雀巢超启能恩奶粉3段760g*4罐评测数据怎样?评测报告来了!

雀巢超启能恩奶粉3段760g*4罐选购哪种好?评测报告分享?

蒙牛纯甄草莓果粒常温酸奶200g×10实际效果怎样?用户反馈评测结...