腾讯日常实习后台一面

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

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

接着问简历，项目用到了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 但期待二面

#我的实习求职记录##面经#