我的博客

分治思想解决设计题

算法设计

利用分治思想可以解决许多面试常见的设计题。问一：有一个文件，里面存放着大量的 url，文件很大以至于无法完全加载进内存，要求找出其中重复出现的 url。如果文件不大，我们肯定会创建一个 HashSet，依次遍历 url，如果它没出现在 HashSet 中就将其加入，否则我们就找到了一个重复的 url。其实，我们现在也可继续用 Hash 的方法，不同的是现在要在磁盘上作 Hash。...

Posted by John Mactavish on August 30, 2021

双指针模板

常用算法与数据结构模板系列（十五）

双指针不是某一种算法，而是一类算法，原则上使用两个变量作为指针操作数组、链表等的算法都可称为双指针。根据问题的不同，双指针采用不同的更新策略，就形成了不同的模板。今天就来大概地总结一下这些模板。前后双指针 “原地删除数组中特定元素”问题例如 27.移除元素：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不...

Posted by John Mactavish on August 20, 2021

Python X 算法题

写算法题的知识点

赋值语句 Python 的赋值语句值得考量。看下面的例子： >>> a = [-1, -1] >>> i = 0 >>> a[i] = i = i + 1 >>> a, i ([1, -1], 1) >>> i = a[i] = i - 1 >>> a, i ([0, -1], 0...

Posted by John Mactavish on August 17, 2021

缓存与数据库间的一致性

缓存系统学习系列（二）

缓存系统可以加速数据操作。但它毕竟只是中间层，数据的持久化与强一致性等还得依靠数据库。那么，系统中的数据便分散在了两处，缓存与数据库间便出现了一致性问题。只读数据不会出问题。而数据的并发读写、写写则会带来麻烦。缓存系统与数据库各自都有措施来保证自身操作的原子性，但两者的组合却不是原子的。我们当然可以考虑引入分布式锁来保证组合操作的原子性，但这也会影响系统吞吐量，这不是今天讨论...

Posted by John Mactavish on August 5, 2021

缓存穿透、击穿与雪崩

缓存系统学习系列（一）

文章转自“程序员囧辉”的知乎文章略有修改与补充缓存穿透描述：访问一个缓存和数据库都不存在的 key，此时会直接打到数据库上，并且因为查不到数据，没法回写缓存，所以下一次同样会打到数据库上。此时，缓存起不到作用，请求每次都会走到数据库，流量大时数据库可能会被打挂。此时缓存就好像被“穿透”了一样，起不到任何作用。解决方案：接口校验。在正常业务流程中可能...

Posted by John Mactavish on August 4, 2021

排序算法总结

常用算法与数据结构模板系列（十四）

如果你已经很熟悉了，只是需要看下总结的图，那么这就是喽。冒泡排序（Bubble Sort）它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为更大的元素会经由交换慢慢“浮”到数列的一端。通过一个优化策略————在发现某次循环没有交换时提前退出，冒泡排序...

Posted by John Mactavish on July 31, 2021

设计满足要求的数据结构

常用算法与数据结构模板系列（十三）

这里总结了 LeetCode 上出现的“设计满足要求的数据结构”类题目。这些题目的解法通常是组合使用常用的数据结构；只要有了思路，实现并不难，所以本文主要讲解思路。 155. 最小栈设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素...

Posted by John Mactavish on July 21, 2021

秒杀系统设计

后端业务学习

Posted by John Mactavish on July 15, 2021

分布式数据库主键 id 生成方案

分布式 id 生成策略

对于传统的关系型数据库，数据以表的形式给出。表中经常有一个列或多列的组合，其值能唯一地标识表中的每一行。这样的一列或多列称为表的主键，通过它可强制表的实体完整性。但并不是唯一的一列就能成为主键，主键还有其他要求。主键必不为空，因此“电子邮箱地址”等可选字段不适合作为主键。其次，主键最好不要变动以维护表的稳定，因而“用户名”等可修改的字段也不合适。总的来说，主键最好与业务无关以摆脱易变的...

Posted by John Mactavish on July 14, 2021

基于K近邻的手写数字字母识别

KNN实验

摘要：本次实验是基于K近邻（K Nearest Neighbors，简称KNN）算法的手写数字字母识别，主要目的是辨认出生活中复杂多样的手写字体。实验的主要方法，也就是K近邻法，是一种常用的基本分类和回归方法。我们同时处理了KNN的两种实现方案：暴力法与KD树（K Dimensional Tree，简称KD树），对比了它们在时间开销上的区别。实验结果显示，在运用KNN进行手写数字字母识别时，...

Posted by John Mactavish on July 3, 2021