简介

二面
1. 工作一年换工作的原因
2. 当前业务的dau（短视频自由流量到300w）信息流qps多少
3. 冒泡时间复杂度
4. 快排平均时间复杂度，最差情况
5. 归并排序时间复杂度
6. 哪些排序是稳定的，哪些是不稳定的
a. 稳定：插入、冒泡、归并、基数排序
b. 不稳定：快排、堆排、选择排序
7. 完全二叉树的叶子节点数量，500个节点
a. 妈的估算了一下，没有给出严格的说明，也没有说出完全二叉树和满二叉树的区别
b. 叶子节点只能出现在最后两层，叫做完全二叉树
i. 知识：n0（度为0，即叶子节点），n1（度为1，只有一个子树）n2（度为2）
ii. 在完全二叉树中，n1=0或1
iii. 引理：n0 = n2 + 1
1) 边数： 2n2 + n1 = n - 1 (除了节点，每个节点都有一根“天线”)
iv. 推理 n0 = n/2 or (n-1)/2
1) n = n0 + n1 + n2，n0 = n2 + 1
2) n = 2n0 + n1 - 1
3) n为偶数时，n1 = 1，n为奇数时 n1 = 0
4) 综合得到 n0 = (n+1)/2
5) / 在上式代表取整，不是除法
8. 代码题
a. 给了一个二维矩阵，每个数字都代表距离，求左上到右下的最短路径
i. 说了bfs、A*算法，没准备图论，申请换了一个
b. N=4，输出 1，2，3，4，12，13，14，23，24，123，124，234，N=3时同理
i. 点拨了一下使用bfs，没有get到，又提示使用队列
ii. 妈的，太菜了，面试有点紧张。知道思路后，一遍通过。
9. 项目相关问题
a. 向量索引建立的速度
i. 1亿索引占用多少内存
ii. 建立索引耗时多少
b. HNSW原理
i. 添加的时候逻辑是怎样的
ii. 搜索的时候逻辑是怎样的
iii. 高速通路是如何建立起来的
iv. 停止检索的条件
c. 实时索引实现介绍
i. 添加、删除、更新
10. 反问
给点建议。建议在现部门做的更深入一些，不知道是不是暗示不要跳槽，可恶。