文章选自 |《数据结构与算法之美》
乔布斯说，一个天才员工可以顶的上 50 个平庸的员工。我要说，在软件开发行业里，一个优秀靠谱的工程师，可以顶的上 100 个普通的工程师。但是，普通的业务开发，有时候并不能区分一个工程师是普通还是优秀。但是，面对一些稍微复杂的技术问题，这个区分就会非常明显。
今天，我就从《数据结构和算法之美》中挑选了几个涉及算法和数据结构的真实软件开发场景的问题。你可以测试一下，你是否是一名足够优秀的软件开发工程师？
实战测试题（一）
假设猎聘网有 10 万名猎头顾问，每个猎头顾问都可以通过做任务（比如发布职位），来积累积分，然后通过积分来下载简历。假设你是猎聘网的一名工程师，如何在内存中存储这 10 万个猎头 ID 和积分信息，让它能够支持这样几个操作：
根据猎头的 ID 快速查找、删除、更新这个猎头的积分信息；
查找积分在某个区间的猎头 ID 列表；
查询积分从小到大排在第 x 位的猎头 ID 信息；
查找按照积分从小到大排名在第 x 位到第 y 位之间的猎头 ID 列表。
点击查看答案：
17 | 跳表：为什么Redis一定要用跳表来实现有序集合？
实战测试题（二）
电商交易系统中，订单数据一般都会很大，我们一般都分库分表来存储。假设我们分了 10 个库并存储在不同的机器上，在不引入复杂的分库分表中间件的情况下，我们希望开发一个小的功能，能够快速地查询金额最大的前 K 个订单（K 是输入参数，可能是 1、10、1000、10000，假设最大不会超过 10 万）。
如果你是这个功能的设计开发负责人，你会如何设计一个比较详细的、可以落地执行的设计方案呢？
为了方便你设计，我先交代一些必要的背景，在设计过程中，如果有其他需要明确的背景，你可以自行假设。
数据库中，订单表的金额字段上建有索引，我们可以通过 select order by limit 语句来获取数据库中的数据；
我们的机器的可用内存有限，比如只有几百 M 剩余可用内存。希望你的设计尽量节省内存，不要发生 Out of Memory Error。
点击查看答案：
12 | 排序（下）：如何用快排思想在O(n)内查找第K大元素？
18 | 散列表（上）：Word文档中的单词拼写检查功能是如何实现的？
22 | 哈希算法（下）：哈希算法在分布式系统中有哪些应用？
实战测试题（三）
我们知道，CPU 资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致 CPU 频繁切换，处理性能下降。所以，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。
当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？
点击查看答案：
实战测试题（四）
通过 IP 地址来查找 IP 归属地的功能，不知道你有没有用过？没用过也没关系，你现在可以打开百度，在搜索框里随便输一个 IP 地址，就会看到它的归属地。
这个功能并不复杂，它是通过维护一个很大的 IP 地址库来实现的。地址库中包括 IP 地址范围和归属地的对应关系。比如，当我们想要查询 202.102.133.13 这个 IP 地址的归属地时，我们就在地址库中搜索，发现这个 IP 地址落在[202.102.133.0, 202.102.133.255]这个地址范围内，那我们就可以将这个 IP 地址范围对应的归属地“山东东营市”显示给用户了。
在庞大的地址库中逐一比对 IP 地址所在的区间，是非常耗时的。假设在内存中有 12 万条这样的 IP 区间与归属地的对应关系，如何快速定位出一个 IP 地址的归属地呢？
点击查看答案：
15 | 二分查找（上）：如何用最省内存的方式实现快速查找功能？
实战测试题（五）
假设我们现在希望设计一个简单的海量图片存储系统，最大预期能够存储 1 亿张图片，并且希望这个海量图片存储系统具有下面这样几个功能：
存储一张图片及其它的元信息，主要的元信息有：图片名称以及一组 tag 信息。比如图片名称叫玫瑰花，tag 信息是{红色，花，情人节}；
根据关键词搜索一张图片，比如关键词是“情人节 花”“玫瑰花”；
避免重复插入相同的图片。这里，我们不能单纯地用图片的元信息，来比对是否是同一张图片，因为有可能存在名称相同但图片内容不同，或者名称不同图片内容相同的情况。
我们希望自助开发一个简单的系统，不希望借助和维护过于复杂的三方系统，比如数据库（MySQL、Redis 等）、分布式存储系统（GFS、BigTable 等），并且我们单台机器的性能有限，比如硬盘只有 1TB，内存只有 2GB，如何设计一个符合我们上面要求，操作高效，且使用机器资源最少的存储系统呢？
点击查看答案：
21 | 哈希算法（上）：如何防止数据库中的用户信息被脱库？
22 | 哈希算法（下）：哈希算法在分布式系统中有哪些应用？
实战测试题（六）
我们知道，散列表的查询效率并不能笼统地说成是 O(1)。它跟散列函数、装载因子、散列冲突等都有关系。如果散列函数设计得不好，或者装载因子过高，都可能导致散列冲突发生的概率升高，查询效率下降。
在极端情况下，有些恶意的攻击者，还有可能通过精心构造的数据，使得所有的数据经过散列函数之后，都散列到同一个槽里。如果我们使用的是基于链表的冲突解决方法，那这个时候，散列表就会退化为链表，查询的时间复杂度就从 O(1)急剧退化为 O(n)。
如果散列表中有 10 万个数据，退化后的散列表查询的效率就下降了 10 万倍。更直观点说，如果之前运行 100 次查询只需要 0.1 秒，那现在就需要 1 万秒。这样就有可能因为查询操作消耗大量 CPU 或者线程资源，导致系统无法响应其他请求，从而达到拒绝服务攻击（DoS）的目的。这也就是散列表碰撞攻击的基本原理。
如何设计一个可以应对各种异常情况的工业级散列表，来避免在散列冲突的情况下，散列表性能的急剧下降，并且能抵抗散列碰撞攻击？
点击查看答案：
18 | 散列表（上）：Word文档中的单词拼写检查功能是如何实现的？
这六个实际软件开发中的问题，你是否都能顺利解决呢？欢迎订阅我的专栏《数据结构和算法之美》，专门为工程师量身打造的算法私教课，这些问题的答案都在里面。在专栏中，我不仅深入浅出、全面细致地讲解每一种数据结构和算法的特点、适合解决的问题、应用场景，还列举了大量类似上面这六个案例的真实软件开发场景，真枪实弹地给你展示数据结构和算法是如何应用到实际的软件开发中的。让你不仅仅学会、学懂，还能真的学有所用。
腾讯大规模云原生技术实践案例集
本案例集详细阐释了 QQ、腾讯会议、和平精英、小红书、斗鱼、微盟等十多个亿级用户产品背后的大规模云原生...
评论