图森未来后端一面面经

• 讲一讲实习经历
• 聊一聊 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，回答离线询问

这个是面过的几家里面最难的了。。。