大厂实习面试

一小时0实习0八股，纯思维题。一题都没答上来。1. 有一个函数，函数入参是 lsn，lsn 随机（可能会非常非常大）。返回值 ret 需要满足条件，0<=lsn<=ret 的入参 lsn 全部出现过，>ret 的 lsn 可能出现过也可能还没出现。给出满足条件的最大的 ret，时间复杂度 O(1)2. 核心问题：实现两个函数，Refresh 和 Consume。实现 Refresh，刷新数组中某一个值；实现 Consume，每次调用Consume都能获取到数组当前的最大值的下标。数组长度可能很大，时间复杂度必须小于堆排序和快排。3. 有 n 个怪物，每个怪物血量不同。第一次可以击杀 k 个，之后每次只能击杀 1 个与已 killed 的怪物其相邻的怪物，最终成绩是第一次击杀的 k 个怪物总血量+最后一个击杀的怪物的血量，给出最终成绩最大值。

之前的帖子因意外又没了，基于之前的重新补上，顺便加一点工作后的感悟。不过内容是基于25年秋招，那时候AI还没现在这么强大，仅供参考，能吸收到一些就可以了，务必不要无脑照搬。我个人在25届的秋招中收获了几家的offer，经过抉择以及多方问询后加入了腾讯，选择在TEG进行后台开发。修订后的内容主要分三部分： 面向现在正在秋招的 / 还在准备实习的非应届 / 还不着急准备实习秋招的面向现在正在秋招的同学的一些建议0 算法题相关 对面试，hot100足以，而且现在一堆题单帮你缩小范围，其实hot100都不用全刷完，但不要花太多时间去找题单，而是要先去刷题。找个你能看得懂的题解，自己去实现，逐步理解即可...

有三个项目三个实习，但全程几乎没问任何实习、项目、八股。1. 如何让一个数字快速对 512 取模？可以与（512-1）做按位与。2. 如果是任意数字呢，在不用取模和除法的条件下，实现 n%m？可以使用 n 不断减去 m，但这样复杂度很高，因此可以用二分优化。3. 还有更好的办法么？感觉想不出更好的方法，如果 m 是 2 的整数次幂可以用刚刚类似的方法。4. 代码写一下吧（还有很多额外的限制记不清楚了，比如不能用任何超过 32 位长度的类型）写的二分但是没有写完，写到一半面试官说算了这个问题过吧（感觉想要的不是二分而是更好的办法）5. 一个三万个节点的链表如何找到第两万大？一开始想错了说要放到数组用 select 算法，后来反应过来说直接对链表用 select ，说了一遍过程。6. 这样会破坏原始链表结构，有办法不破坏么可以把每次下一阶段需要的链表额外存下来，但最坏情况下需要额外的三万空间。7.这样会使得使用的空间更多，有更好的办法么？可以用优先队列，只用两万的空间，然后说了一下用优先队列的方案，核心就是两万了以后，再加进来的时候和堆顶元素对比下就行，不会超过两万。8.  空间还能比两万更少么？（尝试说了一些，没有答到点上，面试官直接说算了）9. 你知道内存池的作用么，为什么需要内存池？八股直接回答10.如果让你实现内存池你会怎么实现，要求能动态调整池大小？（回答了一些自己的思路，基本就是链表，想了很多种优化加上去。）11. 用 c++实现你刚刚说的思路，不一定能运行伪代码就可以。（c++大概写了一下但是写的很差被找出来很多问题，比如这是内存池里面链表的维护不能用 new）反问环节:1. 假如我能被录取，希望我承担什么工作？答: 这个问题问的太早了。

1. 算法1: 求一个数的阶乘然后找到第一个不为0的数字2. 算法2: 用递归实现二分查找3. HashMap的原理4. HashMap为什么不是线程安全的5. 假如HashMap在扩容的时候有另一个线程来读取会发生什么6. ConcurrentHashMap7. rpc的调用过程，工作流程8. 工作中有没有什么跟网络相关经历9. 进程线程的区别10. 线程之间是如何进行同步的11. 工作中有没有用到多线程编程的地方12. 线程池工作流程13. caffine采用的过期策略（lru + lfu）为什么14. raft共识算法15. 如果QPS从70w变成了700w还有哪些角度可以优化？16. 本地缓存更新和读写的时候是否有读写锁？优化？17. 是否观察过cpu核心利用率？线程数量？