笔试生涯第一次全A四道题都偏模拟

部门做的业务是AOI和POI相关的高并发LBS，面试前复习了一下八股和项目，还看了几个京东零售的面经，结果全程在问我高并发点、线、面计算之类的（可能是因为我是地信专业简历上带了个GIS项目），怎么和别人的面经不一样啊呜呜呜1.自我介绍（本人一段GIS后端的单体项目实习，完全没有接触过高并发下的LBS，还有两个项目，一个RAG，一个仿12306）2.详细说一下你们的空间查询是怎么做的3.也就是画了一个围栏之后，查围栏里面的点，那你知道怎么判断一个点在不在围栏内吗，包含函数的原理是什么4.那你了解空间索引吗5.那Geohash或者四叉树你了解过吗6.墨卡托投影呢7.（假设场景）如果在高并发场景下，...

T1 大分讨,不过没太讨论清楚T2 不会ML，oh noT3 先容斥变成求解长为m,取值[1,v] 总和为k的数组，考虑用如下的生成函数描述总和为k的个数：[x^k] (\frac{x *(1-x^v)}{1- x})^m= [x^{k - m}] (1-x^v)^m  \cdot  (1-x)^{-m}前者二项式系数展开，后者牛顿二项式系数展开，枚举前一项x的系数为x^{iv}, 可得：ans = \sum_{i = 0, r = k - m - iv}^{iv \leq k - m} (-1)^i C(m, i) C(m + r - 1,r)最后ans <-   v^n - ans 即可, 注意n根据费马小定理要对P - 1取模，或者直接传i64复杂度O(\sum m + log P)T4, 一个基环树，考虑将答案拆为3部分：1. 链， 2. 若干次整个环， 3 部分环我们先通过dfs求得基环树的环和链，用倍增维护链上的父节点和其他信息，复杂度O(nlogn)1.如果k > 链长，直接跳到根节点，进入2部分否则，倍增上跳的过程中求和即可，O(log n)2/3 若环长为len，还剩k步，则我们走x = k / len个整环，y = k % len 一部分长的环于是贡献就是 x(x+1)/2 * all(circle) + (x + 1) * getcir(p, p + y - 1), 求解这部分是O(1)的总复杂度是O(nlogn + qlogn)可惜T4 赛后才调完

自我介绍 AI项目拷打（问的问题都不会，拉完了）黑马点评项目拷打（问的都会，全挡出去了）然后就是八股（比较简单基础）List集合有哪些，区别是什么慢SQL是如何优化的MySQL的隔离级别回表，覆盖索引和索引下推索引失效的情况Redis的数据类型和结构缓存击穿/穿透/雪崩悲观锁和乐观锁后面就是闲聊你能实习多久，多久到岗位你怎么看待ai，平时有用过ai吗你怎么看待互联网的各个岗位反问总体来说面试强度不大，有点简单，30分钟结束战斗，面试官人也很好，但是总感觉像KPI我问面试官什么时候能出结果，面试官说很快会出结果，结果后面来了一句一到两周吧更新:两小时后约二面