腾讯日常实习后台一面

自我介绍（今天临时赶的三百字介绍，主要讲实习经历，其他全带过）

然后问实习经历，在公司主要做什么

接着问简历，项目用到了redis，之前我准备了redis集群，特点，缓存穿透等

结果被问到的是：

redis哈希的底层数据结构是什么 =》SDS和哈希表，其中SDS结构中存储了字符串大小，方便扩容，并且字符串里可以有\0；会存空间大小，不会有缓冲区溢出。

在链表结构中，每个结点都有前驱和后继指针，list结构里存了头结点、尾结点、链表长度。缺点是不连续，无法很好利用缓存。改进=》ziplist压缩列表，是连续的。list,hash,zset都用listpack作为底层数据结构。在表头存了：到尾结点的偏移；一共多少个结点。每个结点存了：前一个结点的长度。当前结点的长度。当前结点的数据。

压缩列表存在的问题：查询复杂度高，要从前往后遍历；插入和修改数据的时候 如果分配的空间变化 那么会有连锁更新

改进：1.listpack采用块结构，每个块可以独立地存储一部分元素

2.quicklist 将多个 listpack 关联在一起，用双向链表的形式构建列表。通过这种方式，quicklist 在插入、删除时，仅需操作相关 listpack 而无需移动其他块

哈希结构：表里面存了 大小（有多少个桶），sizemask（用于确定索引计算方法），已有的结点数量（当已存储的元素数量相对哈希表大小达到一定比例，会进行扩展，以保持性能）。

哈希冲突怎么解决=》 链地址法，每个桶对应一个链表；开放寻址法，通过线性探测找到下一个可用的位置；动态扩展法，通过rehash来增加哈希表的大小

rehash过程：创建新表；对于原来的每个key-value，计算新的位置，移动。全部移动好以后，把引用指向新哈希表。

问了简历上另一个项目，我介绍了一遍，因为之前保研自我介绍的时候准备过，所以背得挺好

因为我提到了NEO4J，所以问了如何找到两点之间的最短路径，我只想到了迪杰斯特拉

常用算法：

Floyd-Warshall 算法，创建一个距离矩阵，初始时对每对点初始化为无穷大，只有直接相连的点的距离为边的权重。

通过三重循环更新距离矩阵，对于每对点 (i, j)，检查是否存在点 k，使得从 i 到 j 的最短路径可以经过 k。

该算法的时间复杂度为 O(V^3)，其中 V 是图中点的数量。

具体实现：

用二维矩阵表示图。

for (int k = 0; k < numberOfVertices; k++) {  
            for (int i = 0; i < numberOfVertices; i++) {  
                for (int j = 0; j < numberOfVertices; j++) {  
                    if (distance[i][k] != INF && distance[k][j] != INF) { // 防止溢出  
                        distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);  
                    }  
                }  
            }  
        }  

迪杰斯特拉，从源点出发，利用优先队列（通常用堆实现）来维护当前已知的最短路径。

不断扩展已知最短路径，到未访问的相邻节点更新其最短路径。

具体实现：用int数组来存起点到每个点的最短距离；用map表示边，每个点连接着多条边，每条边都有一个target；用优先队列来找出对于当前最近的边。

接着就写代码

第一题是让我说思路 题目是判断点是否在凸多边形里 其中多边形的每个点坐标都按顺序给出来了

我想了半天 想到画一个射线 然后对每条边求交点 但时间复杂度是O(n)

面试官提到有O(logn)的方法 我实在没想出来 他就说先一直二分 最后把问题转换成判断点在直线的哪一侧 这就要用叉乘来判断是顺时针还是逆时针的

第二题是反转链表 直接用头插入法解决

第三题是求树最大深度 我直接用递归 一开始差点翻车后来检查了一下改好了

面试官说递归复杂度太高，应该用栈，我就讲了下深度优先遍历的思路

 public int maxDepth(TreeNode root) {  
        if (root == null) {  
            return 0;  
        }  

        Stack<TreeNode> stack = new Stack<>();  
        Stack<Integer> depthStack = new Stack<>();  
        stack.push(root);  
        depthStack.push(1); // 根节点深度为 1  

        int maxDepth = 0;  

        while (!stack.isEmpty()) {  
            TreeNode node = stack.pop();  
            int depth = depthStack.pop();  

            // 更新最大深度  
            maxDepth = Math.max(maxDepth, depth);  

            // 先压入右子节点，这样左子节点会优先遍历  
            if (node.right != null) {  
                stack.push(node.right);  
                depthStack.push(depth + 1);  
            }  
            if (node.left != null) {  
                stack.push(node.left);  
                depthStack.push(depth + 1);  
            }  
        }  

        return maxDepth;  
    }

反问

我问工作内容（想知道现在什么算风口） 工作强度

感觉他们组还挺累的 时不时有ddl 但期待二面