软件工程
通用数据结构和算法
分类
数据结构：数组、字符串、链表、队列、栈、二叉树、平衡树、前缀树
高级数据结构：B+树、LSM树、ART树、并发数据结构
算法：排序算法、查询算法、数值计算、字符串处理、数据压缩算法、递归思想
高级算法：网络flow、路径算法、大数据算法
向量
向量是数组的抽象和泛化，由一组元素
二叉树
先序preorder：中左右VLR
中序inorder：左中右LVR
后序postorder：左右中LRV
层次：广度优先
二叉搜索树BST
同时借鉴List和Vector两种数据结构。
BBST：平衡二叉搜索树。
BST的中序遍历是递增的。
查找
递归搜索，复杂度O(树的高度)
统一语义：无论查询成功与否，返回父结点位置。
插入
先通过查询函数进行定位，再在相应位置插入。
复杂度O(树的高度)
删除
先通过查找函数定位。
如果被删除结构没有左子树或者右子树，则直接将其与存在的子树交换即可。
否则，通过中序遍历找到其后继结点，与其交换后进行删除。
复杂度O(树的高度)
平等与等价
n个节点组成的二叉树，高度不低于logn到恰好为logn，则成为理想平衡。完全平衡二叉树CBT是其中一种。
高度渐进地不超过logn，则称为平衡二叉搜索树BBST。
平衡：上下可调，左右不变，zig（顺时针旋转）和zag操作（逆时针旋转）。
AVL树（Adelson-Velsky & E. Landis）
平衡因子：左子树和右子树高度差。
AVL树的平衡因子处处大于等于-1，小于等于1。
高度为3的AVL树至少包含fib(h+3)-1即12个节点。
插入可能导致所有的祖先失衡，删除只可能导入其父亲节点失衡。
插入
同时有多个失衡节点，最低者不低于X祖父。
g经单旋调整后恢复平衡，子树高度复原；更高祖先也必平衡。
4种情况：zizzig、zagzag、zigzag、zagzig。
删除
一字形：单旋
之字形：双旋
失衡传播：经过旋转平衡操作后，局部高度减1，导致更高祖先仍可能失衡。
3(祖孙三代结点）+4（四颗子树）按中序排序顺序重构
B树
B+通常用于数据库和文件系统中。B+树能够保持数据稳定有序，其插入和修改拥有较稳定的O(logn)复杂度。
红黑树
每个节点都是带有颜色属性的BST树。
颜色要求如下：
- 节点是红色或者黑色。
- 根是黑色。
- 所有叶子都是黑子（NIL节点）。
- 每个红色节点必须有两个黑色的子节点。
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
红黑树理论上在最坏情况下都是高效的，下限高。
如果查询远大于添加/删除，选用AVL数，否则红黑树更高效。
堆树/优先队列
堆的本质是完全二叉树，可用数组实现。
堆不能保证整棵树都是有序的，但将最大（最小）的节点放在最前面。
堆的插入和删除复杂度为0(log2n)。
散列表
向量按rank访问，链表按position访问，BST按key访问，散列按value访问。
待存放元素N，散列表（桶数组）长度M，直接应用数组大小R，必须满足N<M<<R。
装填因子(LoadFactor)：N/M。
散列函数实现关键：
- 确定性
- 快速：
- 满射
- 均匀
常用散列函数：
- 整数除余
- 不动点：hash(0)永远是0
- 零阶均匀：相邻关键码的散列地址也必须相邻
- MAD(Multiply-Add-Divide)法：(K*a+b) % M
- 平方取中法
- 折叠法：将key分割成等宽的若干段，取其总和作为地址。
- 位异或法（XOR）
- 伪随机数法：hash(key)=rand(key)=[rand(0)*a^key] % M
- 多项式法：适用于字符串。
散列函数：将关键码key转换为散列表元素桶entry。越随机，越无规律越好。
散列冲突排解：
- 多槽位法：每个key可容纳多个元素，浪费空间
- 独立链法：使用链表保存，地址不连续
- 地址开放法：线性试探
其他
- 包含1、2、3、4的不同二叉搜索树的多少颗？
现代软件工程
瀑布模型
适用于需求稳定，计划驱动（嵌入式）的场景。
极限编程ExtremeProgramming(XP)
五个原则：快速反馈、假设简单、增量变化、拥抱变化、高质量的工作
五个价值：沟通、简单、反馈、勇气、尊重
核心实践：结构编程、测试驱动、重构、短交付周期、持续集成、现场客户
敏捷
核心实践：
- 验收测试驱动ATDD/行为驱动开发BDD/领域驱动设计DDD/测试驱动开发TDD
- 看板/燃尽图/Scrum板/冲刺计划
- 持续集成CI/跨职能团队/用户故事
Scrum
Scrum 是用于开发、交付和持续支持复杂产品的一个框架，是一个增量的、迭代的开发过程，是敏捷的一种实现方式。
- 在这个框架中，整个开发过程由若干个短的迭代周期组成，一个短的迭代周期称为一个Sprint，每个Sprint的建议长度是一至四周。
- 在Scrum中，使用产品Backlog来管理产品的需求，产品backlog是一个按照商业价值排序的需求列表，列表条目的体现形式通常为用户故事
- Scrum团队总是先开发对客户具有较高价值的需求。在Sprint中，Scrum团队从产品Backlog中挑选最高优先级的需求进行开发
- 挑选的需求在Sprint计划会议上经过讨论、分析和估算得到相应的任务列表，我们称它为Sprint backlog
- 在每个迭代结束时，Scrum团队将递交潜在可交付的产品增量
看板
看板的核心原则在于限制在制品（WIP）（消灭库存），保证价值快速流动。
DevOps
DevOps是指开发和运维一起参与到整个软件生命周期过程的实践-从开发、测试、部署上线到维护。
核心实践：
- 软件过程模型：敏捷，去除迭代概念
- 自动化：自动化测试、自动化部署、自动化运维
- 持续交付/流水线
- 软件架构：微服务化
- 组织结构：全功能团队，去中心化
- 开发：特性开关，代码检视
- 发布：灰度发布（金丝雀，A/B测试）
- 文化：鼓励知识共享，鼓励开发和运维之间的沟通，充分授权
开源和第三方组件
Q：使用什么版本？
A：使用社区发布的最新稳定版本。
Q：从哪里获取源代码？
A：从中心仓获取。
Q：是否有公共的编译脚本？
A：暂时没有，各个服务自行编译。
Q：有漏洞怎么办？
A：报备即可。
Q：如何归档使用的软件列表？
A：暂无方案，正在规划dependency。