数据结构和算法

  1. 常见的数据结构和算法及其实用场景。时间复杂度和空间复杂度

数组

插入和查找的时间复杂度分别为O(logn)、O(1)

  • 是由相同类型的元素的集合所组成的数据结构,分配一块连续的内存来存储。利用元素的索引(index)可以计算出元素对应的存储地址。
  • 在某些语言中,数组类型可以由散列表、链表、搜索树或其它数据结构来实现。
  • 数组设计之初是在形成上依赖内存分配而成的,所以必须在使用前预先请求空间。所以,数组有以下特性:
  1. 请求空间以后大小固定,不能再改变(数据溢出问题);
  2. 在内存中有空间连续性的表现,中间不会存在其它程序需要调用的数据,为此数组的专用内存空间;
  3. 在旧式编程语言中,程序不会对数组的操作做下界判断,也就有潜在的越界操作的风险
  • 因为简单数组强烈依赖计算机硬件之内存,所以不适用于现代的程序设计。欲使用可变大小、硬件无关的数据类型,Java等程序设计语言均提供了更高级的数据结构:ArrayList、Vector等动态数组。

线性表

插入和查找的时间复杂度分别为O(1)、O(logn)

不是按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针
链表
单向链表、双向链表、循环链表
队列

是一系列节点的集合。集合可以为空,不然的话,树含有一个根节点及根节点下面的若干个子树。
术语:

  1. 节点的度:一个节点含有的子树的个数称为该节点的度;
  2. 树的度:一棵树中,最大的节点的度称为树的度;
  3. 叶节点或终端节点:度为零的节点;
  4. 非终端节点或分支节点:度不为零的节点;
  5. 父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
  6. 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
  7. 兄弟节点:具有相同父节点的节点互称为兄弟节点;
  8. 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
  9. 深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0;
  10. 高度:对于任意节点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0;
  11. 堂兄弟节点:父节点在同一层的节点互为堂兄弟;
  12. 节点的祖先:从根到该节点所经分支上的所有节点;
  13. 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
  14. 森林:由m(m=0)棵互不相交的树的集合称为森林;

二叉树

每个节点最多含有丙个子树的树

完全二叉树

平衡二叉树(AVL树)

二叉查找树

霍夫曼树(最优二叉树) 带权路径最短的二叉树

B树

一种一般化的bst,一个节点可以拥有最少两个子节点。对读写操作进行优化的自平衡树,能够保持数据有序。B树在查找数据、顺序访问、插入数据和删除的操作的时间复杂度都是O(logn)。B树减少定位记录时所经历的中间过程,从而加快存取速度。常应用在数据库和文件系统的实现上。

红黑树

等同于 2-3-4树。红黑树是每个节点都带有颜色属性的二叉查找树。颜色为黑色或红色。

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色(叶子是NIL节点)。
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

自平衡二叉查找树。

典型用途是实现关联数组。O(logn)时间内完成查找、插入和删除。

B+树

PHP

  1. php7有哪些性能上的提升?为什么会有性能上的提升
  2. php数组的实现方式
  3. php内核
  4. 框架的实现方式,常用框架的异同,依赖注入,懒加载等
  5. session不同的保存方案,如redis,mysql应该如何配置php.ini。将session保存于mysql配置方式跟redis有很大差别。

Mysql

  1. 索引
  2. sql的优化方法
  3. mysql的实现原理
  4. 分表、分库的策略,及其关查询实现方法
  5. 主从同步的原理
  6. 不同存储引擎的差异
  7. 锁,读锁,写锁,行锁,表锁

这个相关部分看完<<高效MySql>>基本上能应付日常的需求

Nginx

  1. 负载均衡的配置
  2. 热更新的实现原理
  3. 反向代理

Redis

  1. 防止缓存穿透、缓存雪崩的解决方案

  2. 持久化

  3. 主从同步

  4. 高可用–哨兵,集群

  5. 锁方案 DLM(Distributed Lock Manager)

  6. 数据结构及其实现方法

计算机网络

  1. TCP/UDP实现细节,差异比较
  2. 封包、解包
  3. HTTP协议其常见的状态码

Linux

  1. 理解什么是负载,其值跟什么因素有关,如何去定位是什么原因导致负载上升
  2. 进程(process)、线程(thread)、协程