【面试】深信服长沙C++

0. 面试官说主要面算法，其他的就不面了，还被面试官看到了我博客上的(21年别人总结的)深信服C++面经，好尴尬啊啊啊。

1. 自我介绍

2. 问了一下实习时间，听到面试官长叹一口气…

3. 求一棵树的直径

   • 答了dfs的做法

4. 问擅长哪些方面

5. 刚才提到的树的直径，用DP来解一下

   • 一时间没答上来，口胡了经过根节点的路径和不经过根节点的路径
   • 所以面试官说先放一放，后面再想

6. 给一个链表，判断里面是不是有环

   • 先答了 dfs 加 O(n) 的空间用来标记是否被访问过
   • O(1) 空间就是快慢指针

7. 给长1e5的数组，值域有正有负，求区间和等于x的区间的个数

   • O(nlogn) 的时间复杂度，qz[i] - qz[j]，遍历 i，找 map[qz[j]] 的个数

8. 给定一棵树，每两个节点之间有一个权重，问树上最长异或路径

   • 以 1 为根，对于每个节点 u，得到 1 到 u 的路径异或和，对得到的值建立 01 字典树，遍历每个值并在这个 01 字典树上找最大

9. 描述 kmp 的 next 数组是怎么构成的

10. 再想一下刚才DP求树的直径

    • 以 1 为根
    • dp[u] 表示从 u 到叶子的最长路径
    • dp[u] = max(dp[vi]) + 1; (vi 是 u 的各个孩子)
    • maxlen[u] = max(dp[vi] + dp[vj] + 2); (vi, vj 是 u 的两个孩子)

11. 反问有什么问题

    • 语言，招聘条件的疑惑

12. 面试官的问题说需要和组内商量一下实习时间的问题