概念
常见问题
抽象和接口的区别
从设计层面来说,抽象是对类的抽象,是一种模板设计,接口是行为的抽象,是一种行为的规范。
前后端分离下的 SEO (Search Engine Optimization)
前后端分离无法提供搜索引擎可收录的页面, 需要搜索引擎蜘蛛有执行 JavaScript 能力
- 对于 SPA 页面, 自行提交 sitmap, 让蜘蛛主动去爬.
- 在
noscript
标签中写入当前页面的关键点. 不支持 JavaScript 的蜘蛛到这里会采集到这里面的信息. - 后端根据 spider UA 来判断, 返回不同的页面.
什么情况下使用多线程
- 缩短应用的完成任务的时间
- 若多个线程都是 CPU 密集型, 那么不能获得性能上的提升.
- 若都是 IO 密集型, 也不能提升性能.
- 最好在大量 CPU 计算和大量 IO 共存的使用使用
- 多 CPU 时使用
如何保证多线程下变量的一致性
- 锁机制
- CAS
口述树的几种遍历方式
- 先序遍历: 根左右
- 中序遍历: 左根右
- 后序遍历: 左右根
- 层序遍历: 从上往下一层层
- 深度优先遍历: 遍历到叶节点再返回
MySQL 与 Redis 区别, 使用场景
- MySQL
- 关系型数据库
- 持久化, 每次请求访问都存在着 I/O 操作. 功能强大, 速度慢
- 数据类型多
- 储存结构数据
- Redis
- 非关系型数据库
- 主要储存于内存中, 会往磁盘备份数据. 读取速度快
- 数据类型少
- 缓存, 锁
(3) 数组和链表的区别, 使用场景
- 数组
- 在内存中连续存储的
- 节省内存
- O(1) 找到需要的元素
- 长度固定, 超过元素数量上限需要扩容
- 数据使用少的时候会浪费内存
- 增加删除插入数据效率比较低, 需要移动大量的元素
- 链表
- 在内存中跳跃存储的, 动态申请内存
- 插入删除元素都简单 O(1)
- 查找元素慢 O(n)
- 动态使用内存, 不需要扩容
快排时间复杂度, 空间复杂度(递归实现)
(2) 堆排时间复杂度, 空间复杂度
快排原理
选取一个基数值, 小于基数的放在基数的左侧, 大于基数的放在右侧. 然后对左右侧递归调用, 即完成排序.
时间复杂度: O(NlogN), 最差 O(n2) 空间复杂度: O(logN), 每个栈中都使用了常量, 空间使用依据栈的深度得来, 所以是 O(logN), 最差 O(n2)
建堆时间复杂度
协程原理
协程可以理解为用户态的线程, 开发者自行控制程序切换时机, 而不是像进程和线程那样把控制权交给操作系统. 协程没有线程,进程切换的时间和资源开销. 协程是非抢占式调度, 当前协程切换到其它协程是由自己控制; 线程则是时间片用完抢占时间片调度.
(2) 锁有哪些类型?
- 公平锁/非公平锁
- 可重入锁: 又名递归锁, 指在同一个线程在外层方法获取锁的时候, 在进入内层方法时会自动获取锁.
- 独享锁/共享锁
- 互斥锁/排他锁
- 乐观锁/悲观锁
- 自旋锁
什么是 CAS (乐观锁)
- CAS (compare and swap ) 比较并替换, 比较和替换是线程开发时用到的一种技术.
- CAS 是原子操作, 保证并发安全, 而不是保证并发同步.
- CAS 是 CPU 的一个指令.
- CAS 是非阻塞的, 轻量级的乐观锁.
- 优点: 非阻塞的轻量级乐观锁, 通过 CPU 指令实现, 在资源竞争不激烈的情况下性能高, 相比 synchronized 重量级, synchronized 会进行行比较复杂的加锁,解锁和唤醒操作.
- 缺点
- ABA 问题, 当内存中的值 A 变为 B 再变为 A 时, 甲进程会认为这个值没有改变过. 可以通过版本号来实现控制.
- 自旋时间长, 消耗 CPU 资源, 如果资源竞争激烈, 多线程自旋长时间消耗资源.
(2) 什么是死锁? 死锁的场景? 死锁的本质? 如何避免死锁?
-
什么是死锁: 死锁指的是线程之间都占有对方想要的资源, 又等待对方手里的资源, 形成互相等待的局面一直持续下去
- 四个必要条件
- 互斥
- 持有并等待
- 不抢占
- 环路等待
- 死锁的场景
- 如何避免死锁
- 破坏环路等待条件: 锁队列
- 破坏持有并等待条件: 一次性获取所有锁
- 破坏不抢占条件: 获取不到后续的锁的时候, 主动释放手里的锁
- 破坏互斥条件: 使用 CAS 无锁结构
- 检测死锁: 存在死锁时干掉相关进程
同步和异步的概念
任务串行执行需要等待结果叫同步
任务并行执行不需要等待结果叫异步
描述堆的结构
优先队列的完全二叉树
- 必须是完全二叉树
- 用数组表示
- 任一节点的值是其子树所有节点的最大值或最小值
- 任意节点是其左右子树的最大(最小)值
- 编号为n的节点, 左子树为 2n, 右子树为 2n+1. 父节点 (int)(n / 2)
堆排序实现策略
堆排序是指利用最大堆或最小堆来进行排序, 排序过程就是构建堆的过程
平均时间复杂度: O(nLogN)
- 步骤
- 创建一个堆 H[0, … , n-1]
- 把堆首 (最大值) 和堆尾互换
- 把堆的尺寸缩小1, 并调用 shift_down(0), 目的是把新的数组顶端数据调整到相应位置;
- 重复步骤2, 直到堆的尺寸为1.
比较快排和堆排序时间复杂度最好最坏情况, 空间复杂度
快排: 最好 O(nLogN), 最差 O(n**2), 当为线性表的时候出现最差的情况 堆排序: 时间复杂度: O(nLogN)
(4) 线程池 (原理)
b树是什么
是一种多路平衡查找树.
I/O多路复用有哪些方法? 使用过哪些?
进程间通信方式? 共享储存如何实现?
管道 Pipe
将一个程序的输出交给另一个程序进行处理
- 匿名管道
常见的 Linux 命令 |
其实就是匿名管道
缺点: 速度慢, 容量优先, 只有父子进程能通信
- 命名管道
mkfifo pipe_name
可以创建一个命名管道, 一个进程往管道输入数据, 则会阻塞等待别的进程从管道读取数据, 如果管道数据没有人读取, 那么写进程一直会阻塞
缺点: 任何进程间都能通信, 但是速度慢
消息队列
这里的消息队列不是指常见的 RabbitMQ, Redis 等.
消息队列提供了一种从一个进程向另一个进程发送一个数据块的方法. 每个数据块都被认为含有一个类型, 接收进程可以独立地接收含有不同类型的数据结构. 我们可以通过发送消息来避免命名管道的同步和阻塞问题. 但是消息队列和命名管道一样, 每个数据块有最大长度限制.
如果频繁的发送接收消息, 那么进程需要频繁的读取队列中的数据到内存, 相当于间接地从一个进程拷贝到另一个进程, 这需要花费时间.
缺点: 受到系统限制, 且要注意第一次读的时候, 要考虑上一次没有读完数据的问题
共享内存
共享内存
这个通信方式可以很好的结局拷贝所消耗的时间了. 创建进程时, 两个不同进程的虚拟内存指向同一块物理内存中, 这样就完成了内存共享机制了.
共享内存有多进程竞争内存的问题.
缺点: 速度快, 容量可控. 但是存在进程安全的问题.
信号量 kill -l
最常见的信号量使用就是 Linux 上的 kill
命令了.
信号量的本质是一个 计数器
, 用来实现及昵称之间的互斥与同步. 例如信号量初始值是1, 然后 a 进程来访问内存1的时候, 我们就把信号量设置为0, 然后进程 b 也要来访问内存1的时候,看到信号量的值为0就知道已经被其它进程在访问了, 这个时候进程b就会访问不了内存1.
所以说, 信号量也是进程之间的一种通信方式.
缺点: 不能传递复杂消息, 只能用来同步.
Socket
Socket 套接字进行通信.
Socket 是一种通信机制, 凭借这种机制, 客户/服务器系统的开发工作既可以在本地单机上进行, 也可以跨网络进行.
套接字包含三个属性: 域(domain), 类型(type), 协议(protocol)
域
域是指 Socket 通信中使用的网络介质. 最常见的域就是 AF_INET
, 是指 Internet 网络.
类型
Socket (某方面类似于标准的输入/输出流) 通过的是一个有序, 可靠, 双向字节流的连接.
协议
Socket 既可以实现网络间不同主机间的通信, 还可以实现同一主机不同进程间的通信, 且建立的通信是双向的通信. Socket 进程通信和网络通信使用的是同一套接口, 只是地址结构和一些参数不同.
I/O多路复用, 线程, 进程间有什么关系?
多线程保证线程安全?
线程安全实现的其他方法?
一般什么情况下使用锁?
读操作是否需要上锁? 如何实现?
需要, 多线程情况下, 读锁是用来限制写操作的.
一般通过一个 32 位数字来实现, 前 16 位储存读锁数量, 用 (S»16) 可以获取到读锁数量. 后16位储存写锁数量, 用 (S & 0x0000FFFF) 来获取写锁数量.
有无一种机制读时不上锁, 写时上锁?
hash冲突如何解决? php中的hash冲突使用哪种方法解决?
- 开放定址法(再散列法): 冲突时, 将哈希结果加上偏移值再次使用同一个哈希函数hash
- 再哈希法: 构建多个不同的哈希函数, 当发生冲突时, 使用其它的哈希函数
- 链地址法: 哈希表的元素储存链表的头指针, 重复元素会成为链表的一部分
- 建立公共溢出区: 将哈希表分为基本表和溢出表两部分, 凡是和基本表发生冲突的元素, 一律填入溢出表.
什么时候会使用到堆栈
了解哪些树?二叉平衡树概念?二叉搜索树?二叉排序树?二叉平衡树基于什么衍生出来?二叉排序树缺点?
图遍历方法? 分别解释如何遍历
从文件打开到编辑代码并执行操作系统做了哪些事 (OS启动核心进程,创建子进程后获取CPU时间片,通过查询文件并执行os的I/O操作打开文件进行编辑后编译执行,最后执行I/O操作输出执行结果。)
什么是临界区?
面向对象特性?
怎么理解多态?
编译器实现重载的原理是什么?
各种数据结构的稳定性和时间空间复杂度
线程的状态转换
线程池的核心数?
进程必须运行在端口上吗?
端口用来区标识发送方和接收方的应用层.
多进程可以监听同一个端口, 例如 Nginx 的多个 worker 进程监听的就是同一个端口, 通过 fork 进程来实现的.
UDP 可以多进程同时监听同个端口.
完全二叉树和满二叉树的概念和区别
满二叉树: 除叶子节点外的界都都有两个子节点 完全二叉树: 除了最后一层不满, 其它层都满了, 最后一层所有元素都堆在左侧 完美二叉树: 树的每一层节点都满了
(3) 负载均衡的加权轮询算法怎么实现, 以及其它算法
什么是算法的稳定性?
排序算法中, 指值相等的元素在排序前后不会变化顺序.
并行和并发的区别?
线程的生命周期有哪些状态?怎么转换?
wait 和 sleep 有什么区别?什么情况下会用到 sleep?
怎么停止线程?
怎么控制多个线程按序执行?
谈谈对面向对象的理解,谈谈对多态的理解。
搜索引擎。
rpc接口的超时时间时如何设置得?
orm 框架给你带来的哪些的好处?
- 默认防注入
- 查询条件动态构造
- 容易接入缓存
总结概括一下多态是在做什么?
Reactor 模式是什么
服务器有哪些中断信号?
对一个关闭的socket发起写的请求会发生什么中断?
守护进程是什么?
网络io模型。
布隆过滤器,什么时候用?优点是什么?
布隆过滤器使用多次hash的结果储存在位上的方式来记录数据是否存在, 查找时如果判断不存在那么一定不存在, 判断存在时可能会有误判. 一般在大量数据需要进行判断是否存在时使用, 比如说记录 id 是否存在于数据库中, 就可以使用布隆过滤器来记录, 不存在的 id 肯定不存在, 误判的 id 也只是到达数据库进行一次查询.
优点: 极少的空间储存大量的是否存在数据 缺点: 有误判, 而且删除很麻烦