深信服算法岗一面

第一题
树的直径有哪些解法
两次dfs和树形dp，讲了一下树形dp的思路

因为我的简历写的比较少，所以面试官问我一些个人信息和擅长哪方面。
我说：ACM大一下打到大三，然后去考研。dp写的多一点，还有思维之类的。
第二题
cf的D题，n个数的数组，有正有负，问区间和小于x的有多少。
我只想到了O(n²)，面试官提示用树状数组或者线段树。
每次加入树状数组时，查询一下 x - 当前数的数量。

第三题
面试官：看你考研，问道考研题
如何判断一个链表是否有环

搜的时候存走过的点，有重复得就有环
面试官问能不能优化一下空间，我没想出来
结果是用快慢指针