下载APP
登录
关闭
讲堂
算法训练营
Python 进阶训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
程序员的算法能力测试
2018-12-11 极客时间
写留言
精选留言(39)
2018-12-12基本上每期必跟，回想大学时期抱着《算法导论》啃着的时候，每天晚上都要挠掉几万根头发，最后《算法导论》也没有撸完。这次跟着作者一起看，经常能get到以前没有意识到的内容，课程真的很赞，收获很多。
下面来回答一下题目：
第一题：
我的理解是散列表、跳表、堆结合使用
需求1：根据猎头ID快速查找、删除及更新：散列表快速定位ID，删除及更新操作则依赖于跳表（为）
需求2：查找积分在某个区间内的猎头ID列表：使用用积分构建的跳表或是红黑树，都可以解决这个问题
需求3：查找积分从小到大在第X位的猎头ID信息：这个可以用堆来解决，构建一个大顶堆（堆大小为X），堆顶即为第X位
需求4：查找积分从小到大在排名在第X位-第Y为的猎头ID信息：这个也可以用堆来解决，构建一个大顶堆（大小为Y），出Y-X+1次堆即可
第二题：
很明显分而治之，在每个库中查到金额最大的K个订单，重要的是如何合并数据——直接使用小顶堆（大小为K）即可
PS：这题思路点拨好像关系不大
第三题：
有两个策略：非阻塞的处理方式，直接拒绝请求；阻塞请求，将请求进行排队，等到有空闲线程时，再依次进行出队
这里需要注意的是第二种，队列如何设计实现，我们都知道队列可以有两种实现：如果是链表，它可以支持无限排队，那么此时需要考虑阻塞的长度，会影响响应时间；而数组类型的，队列长度优先，当数组满时请求会被拒绝。
当然链表也是可以设置一直阈值的，重要的是限定长度是多少，这个需要好好思考
第四题：hash + 二分查找
自定义一个hash函数，将IP前3段转换为Int值，比如[202.102.133.0] 为 202 \* 256 ^ 2 + 102 * 256 + 133即可，对应值为山东东营，这样的对应关系由hash存储；这样在传入IP后，直接根据自定义的hash函数，再根据存储的hash数据定位即可
第五题：
考虑到图片数据量，可以使用多台服务器，然后使用hash做负载均衡
需求1：包含的信息，很明显使用散列表存储即可
需求2：根据关键字搜索：可以使用倒排索引结构来存储（这个好像课程中还没有讲到，或者忘记了。。。）
需求3：避免重复相同的图片：按照hash负载均衡至指定服务器后，在哈希表中判断是否存在即可避免重复存储
第六题：
首先设置合适的初始大小；
其次设置合适的装载因子，以及动态扩容时扩容的大小；
然后设计一个散列冲突时的解决方法：比如使用链表、当链表很长时，使用红黑树
最后，设置一个散列冲突比较低的散列函数，个人觉得这是最重要的，也是最基础的
时间有点赶，只是粗略的回答了一下，在这就抛转引玉了展开 8
2018-12-12光写业务的程序员不是一个好的工程媛 6- 2018-12-12一直在写业务，以为业务写好了就万事大吉，结果一次碰到了，时间空间转化的问题，其实有现成的算法了，可我竟然不知道，掉坑里了，怕了好久才爬出来，所以这个专栏给我启发很大啊 3
2018-12-12作为一个测试从业者，也想提升自己的编程水平，希望有所收获，期待！ 2
2018-12-121.使用redis有序集合，所有四个操作，都可以使用zset相关命令 只要一次操作就可以解决（既然zset已经提供了基于跳表的有序集合实现，直接用就可以了）
2.从10个库上通过order by limit k，找到排序好的前k个数，然后集合到一台机器上，进行汇总得到前k个数，汇总方法有以下两种:
a.随机选择+partition（随机选择找到第k大个的数，在进行partition）
b.小顶堆
3.常见两种工作线程池设计方法:
a.生产线程产生任务，扔到队列里，工作线程去抢，这种情况下生产线程无需关心是否有空闲线程，如果任务挤压严重，就是否考虑是工作线程不足还是机器吞吐量不够了（加工作线程或者加机器），当然为了减小锁冲突开销，可以才用一个工作线程双队列的方式（incoming+worker queue），生产线程进行简单轮询往工作线程队列中投递任务（类似actor 模式）。这种方式应该是最常见方式
b.我们采用协程方式，当没有空闲线协程时，主协程会通过条件变量等待一定时间来等待空闲协程，如果超时还没有空闲协程那丢弃。
4.ip存储本来就在有序排序了，果断二分查找，二分查找需要数据支持随机访问，因为ip存储采用分块存储，所以连续内存应该没问题（如果不支持随机访问，就要跳表）
5.采用倒排索引存储，通过关键字->｛玫瑰花，月季花｝这种方式，花集合采用set方式，避免重复。对于关键字查询，不同关键字拿到不同的set，最后进行set的交集即为结果
6.采用murmurhash散列函数，通过哈希因子进行合理rehash操作，当然毕竟rehash操作浪费性能，所以如果是恶意哈希冲突攻击，肯定是前面服务引入风控进行流量抵御（比如根据ip，重复key，user等进行频率限制）展开 1
2018-12-12真的需要重构我的思维，先学完申哥的数学课，再来上算法课，完美 1- 2018-12-12我不懂数据结构，也没有写过代码，但就是很喜欢数据结构与算法之美，重构一下我的大脑，蟹蟹 1
2018-12-12除了在大学认真学过一些基础的数据结构和算法外，实际工作中用到的机会比较少，但是我觉得它其实是我们很多思路的基础，不懂数据结构和算法，你的想法就会受限，就会觉得这个方法不可行，那个方法又太难，最后只能采用比较原始的语法来解决问题，比如，使用for 循环结合SDK内置的 hashmap、arraylist 等数据结构来处理。这样，就永远得不到提升。希望通过本课程能够重拾数据结构和算法，开拓自己的视野，提高自己的能力。 1
2019-02-23需要学习学习了
2019-02-21算法和数据结构是基础
2018-12-14这个是要先有数据结构的基础再看，还是可以没基础直接学。我跨考考研的- 2018-12-13已经订阅了专栏，每个问题在专栏里老师都有讲解，非常的棒，在这里我就不献丑了，非常推荐大家订阅~
2018-12-131. 类似redis，跳表存积分->ID，hash存ID->积分
2018-12-13听说评论给优惠券，我又可以买买买了
2018-12-13这个专栏确实是不错的，给了很多启发
2018-12-13数据结构难啃，但是，能不啃吗？肯定不行，还是得一步一个脚印。- 2018-12-13订阅了专栏,跟着专栏提高自己的数据结构和算法！
2018-12-13一直在学习这个 写的很不错 浅显易懂
2018-12-12算法对于程序员是很重要的！加强学习😊- 2018-12-12牛逼