数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

不定期福利第三期 | 测一测你的算法阶段学习成果

王争 2018-12-21
专栏最重要的基础篇马上就要讲完了,不知道你掌握了多少?我从前面的文章中挑选了一些案例,稍加修改,组成了一套测试题。
你先不要着急看答案,自己先想一想怎么解决,测一测自己对之前的知识掌握的程度。如果有哪里卡壳或者不怎么清楚的,可以回过头再复习一下。
正所谓温故知新,这种通过实际问题查缺补漏的学习方法,非常利于你巩固前面讲的知识点,你可要好好珍惜这次机会哦!

实战测试题(一)

假设猎聘网有 10 万名猎头顾问,每个猎头顾问都可以通过做任务(比如发布职位),来积累积分,然后通过积分来下载简历。假设你是猎聘网的一名工程师,如何在内存中存储这 10 万个猎头 ID 和积分信息,让它能够支持这样几个操作:
根据猎头的 ID 快速查找、删除、更新这个猎头的积分信息;
查找积分在某个区间的猎头 ID 列表;
查询积分从小到大排在第 x 位的猎头 ID 信息;
查找按照积分从小到大排名在第 x 位到第 y 位之间的猎头 ID 列表。

相关章节

题目解析

这个问题既要通过 ID 来查询,又要通过积分来查询,所以,对于猎头这样一个对象,我们需要将其组织成两种数据结构,才能支持这两类操作。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(42)

  •         
    老师是高手,把这么多其他人甚至课本上讲的蹩脚难懂的知识,娓娓道来,深入浅出。
    买了这门课一开始没怎么看,最近两天有空就看,觉得是一种享受!
    2018-12-21
    40
  • 陈阿票
    基本上一下子都知道用什么数据结构和算法去解决,但是实际代码我肯定写不出来,心里总有一种纸上谈兵的感觉。
    2018-12-21
    1
    32
  • alic
    这门课程以后也会反复看的,希望老师也不要因为掉队人多了就松懈了,加油。
    2018-12-22
    10
  • 渔人
    第二题,前K大的订单,您的描述有些简略,不容易理解,我重复描述一下,您看对不对哈。 10个库,取前K大的订单, 第一次从各个库中分别取出最大的订单,组成一个数量为10的大顶堆。另外维护一个数组,刚开始是空的。 这时从大顶堆中弹出堆顶元素(堆中最大值),将堆顶元素写入数组,然后在该元素所在的库中按序拿出第二个元素写入大顶堆填上空缺,大顶堆会重新平衡,堆顶元素可能会变。 这时重复上面的步骤,继续弹出堆顶写入数组,并在弹出元素所在库中按序拿下一个值填入大顶堆,大顶堆又会重新平衡,接着继续弹出堆顶元素写入数组····直到数组的长度为K时,整个过程结束。

    大顶堆的大小一直为10,堆每次平衡后,就将堆顶搞出来,重新写入一个值,周而复始,取K次堆顶就是前K大的集合了。
    @ban
    2019-01-28
    4
  • jiemoon
    老师,像那个猎头的题目,用多个数据结构的话,更新操作会出现数据不一致的情况?

    作者回复: 加个锁?主要还是看操作是不是对数据一致性敏感吧

    2018-12-21
    3
  • 恋恋
    认真看了老师六个实战题目和详细解析,我觉得每道题可以当做一个小项目来练手了。同时也真实感受到基础的重要性!

    作者回复: 是的,好好写写,收获会很大。

    2019-02-08
    2
  • 怀特
    实战测试题一:
    其实算法问题,可以笼统的归纳为:数据以及数据之上的索引。
    有的数据是自带索引的,比如数组其实自带了下标的索引
    如果数据没有索引,就需要自建索引。如果我们自己建,那就是采取各种数据结构来构造一个索引;否则,比如据库的索引,也是建了与数据分离的索引的数据结构。
    从这个角度讲:
    1、根据id来查找猎头信息: 猎头信息存储到数组中就可以,这样很快
    2、根据积分来查找猎头信息:可以旁边建立基于积分的数组来作为索引,节点数据就是猎头id
    这样:
    1、猎头信息存储在数组中
    2、自建一个索引,分别是 积分+id的有序数组
    注意积分变化时维护自建索引的有效性,就可以了。
    这样没有用高深的数据结构,可能会费一些内存和费一些cpu,但实现简单,基本够用了,比较通用。
    2019-01-09
    2
  • RAY
    学习的老师的这门课程,总有种相见恨晚的感觉,真正体悟到了算法之美。举重若轻,方为大师,老师真可谓大师。

    作者回复: 哈哈哈 过奖了

    2018-12-25
    2
  • 挨踢菜鸟
    老师,我想问一下,您除了讲数据结构之外,本专栏之后还会讲一些其他的吗,比如设计模式之类的,看您的课程真是一种享受,非常期待您其他的专栏
    2018-12-23
    1
    2
  • 传说中的成大大
    实战测试1:
         本来想的用树来维护通过ID的增删改查, 用积分做成一个hash表 每个hash下标对应多个猎头ID, 也可以用跳表实现增删改查

    实战测试2:
    维护一个大小为k的小顶堆 每次读一个库的数据 然后维护这个小顶堆

    实战测试3:
          维护一个优先队列,根据优先级来判定 突然到来的线程请求是否该执行,也就是该线程是否在优先队列优先级高的区域

    实战测试4:
           能想到二分法

    实战测试5:
            不会

    实战测试6:
            不会
    以上题目是未看过任何答案和提示想出来的

    看了解答 除了测试6没多大印象以外,其他的都能有很深刻的印象

    学习目标: 最开始学习数据结构和算法的目标就是说要掌握好树和图,但是实际上却发现了更多需要我去掌握的数据结构和算法
    实施情况, 坚持了三个月 每一篇文章都认真仔细的学习了 ,总得来说收获颇多,尤其是了解很多以前都不了解的数据结果和算法,扩充了自己的知识面

    接下来的目标还是以本位为测试基准,优先针对性的复习,然后再把课程过一遍,坚持自己的学习初衷 我一定要把数据结果和算法学好!
     还是谢谢老师

    2018-12-21
    2
  • Phoenix
    老师,第二题,我有另一条思路,想请老师教导和指点
    正如老师所说,数据库最大性能瓶颈就是在IO,所以反复执行DB的IO操作是低效的
    我想法是要高效实现第二题的要求,又尽量对数据库的IO操作,有以下思路
    1 借助桶排序的思想,将订单按金额从小到大的规则分布在10个库中
    2 要查找金额最大的前k订单,就先从第10个库中检索订单,满足K数量就直接返回
    3 不满足k数量,在从第9个库中查找,以此类推,直到满足k数量,返回结果
    2019-02-28
    1
  • ban
    把取出来的10个订单放到优先级队列中,取出最大值(也就是大顶堆堆顶数据),就是全局金额最大的订单。然后再从这个全局金额最大订单对应的数据库中,取出下一条订单(按照订单金额从大到小排列的),然后放到优先级队列中。一直重复上面的过程。

    老师这段话我看到好多遍,想了好多次一直没搞懂,为什么取出最大金额的数据库查到下一条订单放到队列能理解,但是下次重复这个过程还是从队列中取出最大金额的下一个订单,这样每次最大的金额不是同一个吗,取出的订单还是同一个?

    还有另外一个问题就是全部取出来后怎么判断这个队列是 top k的订单金额?

    第二次回复,求老师讲解,自己研究好久没搞透
    2018-12-22
    1
  • 才才
    还得看好几遍,还得练习
    2018-12-21
    1
  • 刘哲
    老师讲的非常好,但是我们不能光凭老师的文章去看懂数据结构,还要自己实战,搜索文章学习才行
    2019-09-22
  • DFighting
    看了这些题目,怎么说呢,有点知其然,不知其所以然的感觉。应该是没有实际应用过的缘故吧,这个彩蛋很好,适合动手实践实践,不然过段时间又忘了

    作者回复: 知其所以然看里面的文章链接呢,毕竟是测试题,限于篇幅,不可能讲解太多。

    2019-08-07
  • 不去彼岸
    实战测试题二:
    如果k的值很大,用归并排序merge的方法时间复杂度会很高,是不是可以用二分查找的思想
    取每个库中第k位的金额,然后根据这些金额中的最大金额max与最小金额min,得到中间值mid,再用这个中间值去各个库中查大于这个值的数量,加起来就是这个中间值的排名ki,ki>k则说明中间值比要找的金额大,递归查找(min,mid)中间值的排名,ki<k,递归查找(mid,max)中间值的排名,这样时间复杂度就是10*logn 也就是O(logn)
    2019-04-25
  • 路上的始终
    涉及到一定的需求场景时虽然不能立刻写出代码,但是有很多思路,能写伪代码
    2019-04-24
  • 天空只能仰望?
    哈哈,第二遍刷过来很多例子多写了一遍,还是有很多的印象,测试相关题目不一定想到的都是最优解但是也都能联想到相关数据结构和问题解决办法,感谢老师👨‍🏫!
    2019-04-20
  • H.L.
    题目2: 从10个库中分别取n条数据,放在内存中,再构建一个堆,不断的删堆顶,从内存中的数据放到堆,再堆化,如果其中一个库在内存中没数据了,就触发一次sql操作,取下一批数据回来放到内存
    2019-04-12
  • 小智e
    最近在找实习,恶补基础知识,正在努力追赶老师的步伐,感觉超值的课程
    2019-03-25
收起评论
42
返回
顶部