八股文-字节备考

倒置二叉树
二叉树遍历
实现一个单例类
二叉排序树实现插入算法
手写一个智能指针实现，线程安全的智能指针
找出一个字符串s包含字符串t的最小重复字符串 - 最小覆盖子串
一个n的数组，有一些随机数据，怎么抽出m长度的数据，保证数组的数据唯一，方法可能有很多，面试官会探讨最优方法
给一个任意整数组，剔除一个元素后，得出最大乘积例如：[4]int{2,3,4,-4} 最大乘积 24 情况A：奇数个负数；情况B：偶数（包括0）个负数,子情况：没有非负数；
怎么从一对数里面最快找到最大值和最小值 - 数组中最大数对和的最小值
给出一个字符串N “ABBCDB”（大小英文字母组成），按照一下任意一个规则，一：从头部删除一个字母，并追加到新字符串尾；二：从尾删除一个字母，并追加到新字符串尾；期望最后得到一个字典排序最小的字符串 - 选择每一步操作中字典序较小的方式？
有一个任意的整形数组，[]int，从数组取出任意一个元素是的它是符合下面条件的，一：它的左边都比它小，二它的右边都比它大。

// 计算每个位置左边的最大值
leftMax[0] = arr[0]
for i := 1; i < n; i++ {
   leftMax[i] = max(leftMax[i-1], arr[i-1])
}

// 计算每个位置右边的最小值
rightMin[n-1] = arr[n-1]
for i := n - 2; i >= 0; i-- {
   rightMin[i] = min(rightMin[i+1], arr[i+1])
}

// 检查每个位置是否满足条件
for i := 0; i < n; i++ {
   if arr[i] > leftMax[i] && arr[i] < rightMin[i] {
      return arr[i]
   }
}

10000个整数的升序数组，无重复数，找出最接近目标数的下标

// 如果查找失败，判断最接近目标数的元素是array[left]还是array[right]
if (abs(array[left] - target) < abs(array[right] - target)) {
   // 如果array[left]更接近，返回left
   return left;
} else {
   // 如果array[right]更接近，返回right
   return right;
}

2根燃烧速度不同的香，每根1小时可燃完，如何测算出15分钟的时间

同时点燃A的两端和B的一端，这样A的燃烧速度是B的两倍。
当A燃尽时，表示过去了半小时，此时B还剩下半小时的长度。
立即点燃B的另一端，这样B的燃烧速度变成原来的两倍，也就是每15分钟燃尽一半的长度。
当B燃尽时，表示又过去了15分钟，这样您就测算出了15分钟的时间。

1、什么是链表，链表有什么特点，使用链表有什么好处链表和数组有什么区别
2、说说你常用的排序算法，并说出他的时间复杂度和空间复杂度
3、说说你知道的的查找算法有哪些，并如何实现的
4、说说快速排序和堆排序的实现过程
5、说出二分查找的实现过程和时间空间复杂度
第一个，最基本的二分查找算法：

// 因为我们初始化 right = nums.length - 1
// 所以决定了我们的「搜索区间」是 [left, right]
// 所以决定了 while (left <= right)
// 同时也决定了 left = mid+1 和 right = mid-1
// 
// 因为我们只需找到一个 target 的索引即可
// 所以当 nums[mid] == target 时可以立即返回
int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

第二个，寻找左侧边界的二分查找：

// 因为我们初始化 right = nums.length
// 所以决定了我们的「搜索区间」是 [left, right)
// 所以决定了 while (left < right)
// 同时也决定了 left = mid + 1 和 right = mid
// 
// 因为我们需找到 target 的最左侧索引
// 所以当 nums[mid] == target 时不要立即返回
// 而要收紧右侧边界以锁定左侧边界
int left_bound(int[] nums, int target) {
    int left = 0;
    int right = nums.length; // 注意
    
    while (left < right) { // 注意
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    // 判断 target 是否存在于 nums 中
    // 如果越界，target 肯定不存在，返回 -1
    if (left < 0 || left >= nums.length) {
        return -1;
    }
    // 为什么返回 left 而不是 right？
    // 都是一样的，因为 while 终止的条件是 left == right。
    // 判断一下 nums[left] 是不是 target
    return nums[left] == target ? left : -1;
}

// 两边都闭的「搜索区间」
int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 判断 target 是否存在于 nums 中
    // 如果越界，target 肯定不存在，返回 -1
    if (left < 0 || left >= nums.length) {
        return -1;
    }
    // 判断一下 nums[left] 是不是 target
    return nums[left] == target ? left : -1;
}

第三个，寻找右侧边界的二分查找：

// 因为我们初始化 right = nums.length
// 所以决定了我们的「搜索区间」是 [left, right)
// 所以决定了 while (left < right)
// 同时也决定了 left = mid + 1 和 right = mid
// 
// 因为我们需找到 target 的最右侧索引
// 所以当 nums[mid] == target 时不要立即返回
// 而要收紧左侧边界以锁定右侧边界
int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    // 判断 target 是否存在于 nums 中
    // left - 1 索引越界的话 target 肯定不存在
    if (left - 1 < 0 || left - 1 >= nums.length) {
       return -1;
    }
    // 又因为收紧左侧边界时必须 left = mid + 1
    // 所以最后无论返回 left 还是 right，必须减一
    // 判断一下 nums[left - 1] 是不是 target
    return nums[left - 1] == target ? (left - 1) : -1;
}

// 两边都闭的「搜索区间」
int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 最后改成返回 left - 1
    //  if (left - 1 < 0 || left - 1 >= nums.length) {
    //      return -1;
    //  }
    //  return nums[left - 1] == target ? (left - 1) : -1;
    // 由于 while 的结束条件为 right == left - 1，所以你把上述代码中的 left - 1 都改成 right 也没有问题，
    // 这样可能更有利于看出来这是在「搜索右侧边界」
    // 最后改成返回 right
    if (right < 0 || right >= nums.length) {
        return -1;
    }
    return nums[right] == target ? right : -1;
}

6、哈希表知道吗，哈希表实现原理，如何处理哈希冲突
7、一颗二叉树从右边看过去，把看到的节点打印出来
8、0-1背包问题
9、判断两个字符串是否相等
10、快排的实现过程

数组排序
打乱一个数组
矩阵的最小路径和
二叉树寻找树的深度
将10进制整型转化为16进制字符串
用栈实现队列，用队列实现栈
栈和队列的区别，如何用栈实现队列

升序链表合并
如何判断链表有环
去除链表中值为0的节点
从数组中取出几个最小的值
翻转一个单向链表（编程实现）
在一个有序数组中查找一个数（编程实现）
设计一种算法，实现用单向链表查询倒数第k个元素

1.网上原题：二叉树最近公共祖先节点
面试题目：二叉树最近公共祖先节点；两个节点可能相同，也可能为空，也可能只有一个节点在树上

2.网上原题：每次上1个台阶或2个台阶，求上n楼的方案问题
面试题目：斐波那契数列的非递归实现

写一个Top K的算法
100w字符统计使用次数
100首歌，怎么生成随机列表
100W条字符串选出重复最多的十条
100W个整数中如何查找不重复的数
100W的手机号码怎么存储最省空间

1、N个数，找第K大数
2、找出两个子view最近的共同父view（算法）
3、给一个数组，求如何划分数组，使得abs（sum【A】 - sum【B】）最小，leetcode原题
4、给个有序数组，将数组非重复部分排在前面，不占用额外空间，输出数组
6、红黑树的特点是什么，什么情况下使用hashmap，什么情况下使用红黑树
7、一个包含0-9的数组，只有一个数字是两次出现，如何在O(n)时间，O(1)空间下找出这个数字
8、一个Int型是有4个字节，a = 1， b = 2，怎样不使用第三个变量，使得a，b变量交换值。

1、给定一个二叉树和一个数字n，判断二叉树中是否有一个路径上的数字之和等于给定的数字n
2、二叉树翻转（递归和迭代）
3、两条链表是否含有交叉
4、写一个迭代器
5、100万个16位整数，内存不限，找出Top K。
6、找出一个数组的长度 Top2 的连续升序子数组，并按长度降序输出
例如：
输入：[2, 1, 4, 5, 8, 3, 7, 10, 2, 5], k = 2
输出：[1, 4, 5, 8], [3, 7, 10]
7、给定一个序列，求最长递增子序列有几个（动态规划）
8、算法写个3sum(leetcode)
9、排序算法
10、实现一个单链表反转

1.算法整数反转
2.判断两个二叉树是否相等
3.写一个二叉树的层序遍历
4.N个数，找第K大数，经典题，leetcode原题
5.一颗二叉树从右边看过去，把看到的节点打印出来
6.一个乱序的整型数组，输出数组中没出现的最小的整数
7.一个正整数数组找出连续和为K的整数倍的最短序列
8.求double类型的n次方，double pow(double base ， int n) 注意边界问题
9.实现单链表的逆序，普通的修改链接指针的逆序方式之外是否还有其他方式实现逆序。
10只描述思路：10T大小的文件，每行为一个单词，找出词频最高的前k个单词
11.求二叉树的直径，即一个叶子节点到另一个叶子节点的最大长度

给一个数组，用二分法查找某个元素是否在里面，在就返回0，不在就返回-1

旋转链表
给定一个单链表，旋转链表，将链表每个节点向后移动 k 个位置，
如果是尾节点，则把它移动到最前面；其中 k 是正数。
要求：时间复杂度O(n)，空间复杂度O(1)
例如：
输入: 1->2->3->4->5->NULL, k = 1 输出: 5->1->2->3->4->NULL
输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL
输入: 1->2->3->4->5->NULL, k = 7 输出: 4->5->1->2->3->NULL

视频一面：

如何检测内存泄露，分配和释放配对
如何进行FD回收
虚函数表存放的位置
内存池原理，内存池上初始化Class，new placement
熟悉哪些架构模式，MQ，Proxy，Master-Slave，etc
迭代器何时失效
视频二面：
TCP滑动窗口
RTT测量-Ping/Pong协议
HTTP报文格式以及Status Code
HTTPS与HTTP区别
TCP与UDP区别
SSL握手细节处理上
程序编译链接的流程
服务器如何处理空置连接
视频三面：

两条链表是否含有交叉
写一个迭代器
100万个16位整数，内存不限，找出Top K。

1.讲出mysql常用的三个引擎，他们的区别以及应用场景（讲了myisam,innodb,memory）
2.TCP建立连接后，出现网络连接断开，发送方会进行哪些行为
3.讲讲智能指针，share_ptr的原理，是否线程安全，为什么，底层实现讲一下
4.map,hash_map的底层实现
5.vector扩容机制，使用时有哪些注意事项
6.Mysql特性与隔离级别
7.项目中如何解决分布式架构下的数据一致性问题
8.算法写个3sum(leetcode)

自己比较擅长的技术点？一个比较有代表性的项目，项目中体现技术能力的点。
哈希函数的实现，比如key为一个字符串或者一个整数，哈希冲突后怎么解决
多线程并发读写共享变量时，需要加锁，如果不加会怎么样？是否会导致程序崩溃
dns包的类型，怎么构造一个dns查询请求的回包，可以伪造吗？怎么实现。可以假装为淘宝服务器，伪造http回包吗？
编程方面：
实现单链表的逆序。普通的修改链接指针的逆序方式之外是否还有其他方式实现逆序。
实现LRU

1 redis RDB AOF 存储的优劣，BGSAVE 时候新的数据怎么存储
2 redis有序集合的底层实现
3 tcp 的重传机制，拥塞状态算法，快速恢复算法
4 cup内存分配算法 c++内存碎片问题
5 算法题：求二叉树的直径，即一个叶子节点到另一个叶子节点的最大长度

1、最有挑战性项目是哪个，用到了哪些关键技术
2、redis用过那些数据结构如何实现的
3、redis持久化有哪些方式
4、集群如何实现负载均衡如何保证集群方式得队列请求顺序分发
5、线程同步有哪些方式
6、io多路复用有没有用过 select与epoll区别
最后算法题是leetcode 11题盛最多水的容器

redis的持久化机制、主从复制
redis是单线程还是多线程输出数据的，为什么？
描述redis的数据类型、 redis如何利用多核能力，如何解决并发读写的脏数据问题
redis基本数据结构，集群实现方式，redis的锁实现，数据同步，高可用性

TCP的三次握手，TCP四次挥手，状态变更
tcp粘包，怎么发生解决，http怎么解决
HTTPS与HTTP区别，TCP与UDP区别
tcp建立连接的过程是怎样的；http请求包包含哪些部分
upd和tcp的区别，udp可以建连接么，http底层是tcp还是udp，为什么
tcp断开连接，谁会处于timewait状态？tcp出现过多的TIME_WAIT一般是什么原因引起的，

关于mysql的sql调优方式
MongoDB与MySQL的区别
mysql的事物实现原理，数据库事务原则？
mysql的innodb存储格式，为什么索引要用B+树
为什么最终选择用规则库的方式做，是否在解析规则的时候存在性能瓶颈？

负载策略和一致性哈希
什么是懒汉，什么是饿汉
多线程下怎样保证共享属性的安全性；
如何检测内存泄露，分配和释放配对
如何排查内存泄漏，回答的使用Valgrind工具。
流量控制和拥塞控制，阻塞io和非阻塞io有什么区别
五层网络模型，传输层有哪些协议
最得意的一个项目，所使用的网络模型以及底层接口。
内存对齐，字节对齐，大小端，网络序和字节序
网络编程相关，select epoll区别与优缺点，水平触发和边缘触发
etcd和zookeep间的区别，什么是raft算法，redis中的数据如何淘汰？

乐观锁与悲观锁的区别，乐观锁的实现；
死锁产生条件，怎么解决；同步锁有哪些；
ping过程是用什么协议，请求过程是怎样的
进程kill不掉怎么办，进程的地址空间包含哪些
服务端进程中间挂掉和服务不可用，这对客户端来说，感知有什么不一样

一面：
1、C++多态是怎样实现的
2、C++11中智能指针底层实现
3、Tcp创建和关闭的过程
4、Stl容器底层数据结构
5、Mysql索引的数据结构，什么是事务
6、分布式锁是怎么实现的
7、Ssl握手过程
8、协程的原理
9、什么是死锁，死锁的条件，怎么避免死锁
10、实现单链表翻转

二面
1、画出当前项目的架构图
2、讲解项目的业务流程（会针对项目的业务进行提问）
3、限流算法有哪些
4、堆和栈在进程和多线程中有什么区别
5、算法题：给定一段时间的股票价格数组double a[n]，找出i和j(其中i<=j<n), 使得(a[i]-a[j])/a[i]表达式的值最大

三面
1、字符串“abcdef”占用多少字节，int类型占用多少字节，指针占用多少字节？
2、 http是tcp/ip哪一层，https数据传输使用对称加密还是非对称加密？为什么？
3、怎么判断机器的大小端
4、流量控制和拥塞控制的方法和用途
5、单核cpu下，下面代码n的结果？
Int n=0;
线程T1和线程T2分别执行下面代码
While(n<10)
{
n=n+1;
}
6、怎么从一对数里面最快找到最大值和最小值
7、实现二叉搜索树插入节点

1 设计社区黑名单系统，如何针对发表不当言论的用户筛选和处理(包含用户小号和大号）
2 mysql索引的存储结构，为什么不用跳表，而redis的zset使用跳表两者有什么差异
3 两个有序数组怎么快速找到相同字符串
4 https和http的一次请求
5 tcp为什么使用3次握手建立连接，2次握手有什么问题
6 mysql语句中索引命中规则
7 redis数据结构
8 B+树和B树以及B-树的差异和使用场景

指针与引用的区别
typedef与define的区别
红黑树与平衡二叉树的区别
mysql索引为什么用b+树
跳表的时间复杂度
归并排序是否稳定，时间复杂度
tcp的可靠性是怎么实现的
tcp三次握手换成两次是不是可以
对端关闭连接，本端怎么判断？
read出错怎么处理
对端关闭连接，本端写会出现什么问题
redis的数据结构
zset的底层实现
zset的范围查询命令是什么
有没有用过消息队列

TCP握手与挥手，TIMEWAIT的出现原因、情况。
TCP协议的“粘包”
MySQL的隔离级别，MySQL是
如何解决的幻读。MySQL的间隙锁、next-key lock等。
C++ STL里的Hash表，还有它是如何扩容的。对比Redis是如何扩容的。
一致性哈希

1.浏览器输入网址经过哪些过程，如果出现502是什么原因，要如何排查
2.进程间通信有哪些
3.死锁，如何避免死锁，什么是自旋锁，自旋锁的优点
4.IO多路复用
5.TCP四次挥手过程中time_wait状态发生在哪里
6.https是使用什么加密方式
7.场景题：有刚注册的账号，频繁发广告贴，如何处理
8.算法题：两个有序数组的交集