图森未来后端一面面经
- 讲一讲实习经历
- 聊一聊 Kubernetes（实习经历中有用到）
- 聊项目：你觉得你的项目亮点是什么
- [手撕] 算法题（一）：求方程 x^5 + x = 1 的近似解，精确到六位小数。
- sol: f(x) = x^5 + x - 1，在区间 [0, 1] 上二分
- [口胡] 算法题（二）：一个长度为 n 的数组 a[n]，给出一个数 sum，求数组和大于等于 sum 的子数组的个数（n < 1e5）
- sol：
- 区间 (j, i] 的区间和可以用前缀和 p(i) - p(j) 表示，这里要 p(i) - p(j) >= sum，则 p(j) <= sum - p(i)
- 所以对于每个 i 要找到满足 p(j) <= sum - p(i) 的 j 有几个
- 于是可以把所有的 p(i) 和 sum - p(i) 离散化，树状数组，然后扫一遍前缀和数组，每次 O(log n) 加一个值进来，然后 O(log n) 查询
- 时间复杂度 O(n log n)
- [口胡] 算法题（三）：一个长度为 n 的数组 a[n]，给出一个数 sum，求数组和大于等于 sum 的子数组的最短长度（n < 1e5）
- sol：
- 承接前一题，其实就是要找到满足 p(j) <= sum - p(i) 的最大 j
- 把所有的 p(i) 和 sum - p(i) 按照从小到大排序，如果是 p(i) 就加入按照 i 排列的大根堆，如果是 sum - p(i) 就从堆顶取一个 i，回答离线询问
这个是面过的几家里面最难的了。。。
#实习##面经##Java工程师#
