面试知识点

算法和数据结构

• 常用算法

  • 排序算法

    • 各种排序算法的时间复杂度，是否稳定

    • 内部排序

      • 快速排序 nlgn 不稳定

      • 冒泡排序 n2 稳定

      • 堆排序 nlgn 不稳定

        • 大小堆

      • 归并排序

      • 选择排序 n2 不稳定 5 3 5 2 4

      • 插入排序 n2 稳定

      • 希尔排序 不稳定

    • 手写冒泡

    • 手写快排

    • 外部排序

  • 查找算法

    • 顺序查找

    • 二分（手写）

      • 递归

      • 非递归

    • 二叉搜索树

    • 平衡搜索树

      • 红黑树

    • 多路搜索树

      • B tree

      • B+tree

  • 一致性hash

    • 减少数据迁移

    • [0,2的32次方 - 1]

    • 虚拟节点

    • 客户端实现

  • 动态规划dp

    • 最长公共子序列

    • 和最大的连续子序列

    • M*N棋盘问题

  • 字符串处理

• 数据结构

  • 数组

  • 链表

  • 队列

  • 栈

  • 堆

  • 树

    • 二叉树

    • 红黑树

  • 图

  • hashtable

• 常见算法题

  • 剑指offter

    • 单链表反转 stack O(n)

    • 数组中找出只出现过一次的数字

  • leetcode

  • 外部排序 10亿个整数，随机生成，可重复，求最大的前1万个

  • M*N个方格走法问题 排列组合/动态规划

  • 最长回文

操作系统

• select poll epoll

  • epoll的原理

• 进程

• 线程

• golang中 协程为什么快

• 锁

• 信号量

• 堆栈

  • 栈

    • 由操作系统分配

    • 初始化时分配

    • 私有

  • 堆

    • 运行时，程序自己申请

• Linux

  • grep http://pic002.cnblogs.com/images/2010/165814/2010110910285741.png

    网络

    • TCP 相关

      • 三次握手

      • 四次挥手

      • 可靠性保证

      • 包结构

      • 拥塞控制

      • SYN 洪流攻击

        • syn cookie

        • 增大backlog

        • 降低重试的timeout

    • UDP

    • HTTP相关

      • 结构

      • 常见状态码

        • 1XX

        • 2XX

        • 3XX 301 302 307区别

        • 4XX

        • 5XX

      • 浏览器跨域

      • cookie session

    • HTTPS过程原理

    • 网络层的一般过程

    • 链路层

      • ARP

        • mac缓存表

        • ARP广播

        • ARP欺骗

    数据库

    • 索引

      • 联合索引

      • B+tree

        • 叶子节点链表的好处

        • 页分裂

      • 聚簇索引

    • 分库分表策略

    • 分区

    • 锁

      • 表锁

      • 行锁

      • gap锁

    • 事务

      • ACID

        • 原子性

        • 一致性

        • 隔离性

          • uncommitted read

          • committed read（MVCC）

          • repetable read （MVCC）

          • serializable

          • 如何避免幻读

        • 持久性

      • MVCC（参见高M 第一章 1.4节）

        • 每起一个事务，系统版本号+1

        • 创建版本号 和 删除版本号

        • select update insert delete的操作

    • 集群

      • 主从同步

        • 三个线程

          • log dump

          • IO线程

          • SQL线程

        • binlog的格式

          • row

          • statement

          • mixed

        • 主从延迟 https://jingyan.baidu.com/article/2c8c281d9614760008252a1e.html

          • mysql5.6以前 都是单线程重放relayLog

          • mysql5.6 一个库一个线程

          • mysql5.7 使用GTID 将并行的事务化为一组，组与组之间并行执行

    NoSql

    • redis

      • 常用命令

      • 底层数据结构

      • 数据持久化

      • rehash过程

      • GC

        • LRU

        • LFU

      • 集群

        • 主从复制

        • 哨兵

        • Cluster

          • 3.0之后加入

      • redis热点key问题

      • 单线程原理

    • memcache

    面向对象设计

    • 封装 继承 多态

    • 面向对象基本原则

      • SOLID

    • 设计模式

      • 创建

        • 工厂模式

        • 抽象工厂模式

        • 单例模式

        • 构建者模式

      • 行为

        • 观察者模式

        • 策略模式（算法簇模式）

      • 结构

        • 适配器模式

        • 装饰器模式

        • 注册器模式

    系统设计

    • feed流

    • 短链系统

    • 订单过期

    语言问题

    PHP

    • 生命周期

    • ZendVM

    • 内存管理 GC

    • 数组实现

    • 线程安全

    • 502 504 产生的原因

    项目问题

    架构

    • 分布式相关

      • CAP

      • 两阶段提交

      • 分布式事务

      • 冗余数据一致性

    • https://blog.csdn.net/s465564/article/details/77880868

    • 分布式应用服务器

    • 分布式缓存服务器

    • 分布式数据服务器

    • 高可用

    • 伸缩性

    • 拓展性

    • 负载均衡LB

      • nginx

        • 轮询（默认）

        • weight

        • ip_hash

        • url_hash 第三方

        • fair 第三方

      • 4层负载

        • LVS

        • F5

        • HAproxy

    优化问题

    • 优化接口速度

      • 压缩请求 zip/br

      • 请求数量的权衡

      • 前端和客户端缓存

    • 限流

      • 令牌桶

      • 漏斗

    通用问题

    • 项目中遇到的难点，怎么解决？

    • 自己有那些优点和缺点？你认为你的优势是什么？

    • 工作中你觉得最不爽的事情是什么