百度竞品观察组二面

#牛客在线求职答疑中心# 有没有好兄弟分享一下育碧的intern gameplay programmer（c++）的面经啊，全网搜不到什么😭😭

自我介绍1.一个线程如何控制接口限频基于数据库（Mysql为例）的统计进行限流基于redis自增长及过期策略的限流基于内存（linkedlist为例）的限流基于木桶算法的限流2.红黑树 哪里用到了红黑树？java8 hashmap中链表转红黑树。epoll在内核中的实现，用红黑树管理事件块（文件描述符）。Java的TreeMap实现3.b+树 b树 使用场景数据库 文件系统4.为什么要有多线程？从计算机底层来说： 线程可以比作是轻量级的进程，是程序执行的最小单位,线程间的切换和调度的成本远远小于进程。另外，多核 CPU 时代意味着多个线程可以同时运行，这减少了线程上下文切换的开销。从当代互联网...

#我的实习求职记录#概述：3月28日投递，3月30日笔试(1/3)，4月15日发了一面（第一个面试），电话面，主要问项目和相关的八股，没有手撕，总共50分钟，最终感觉因为项目太少，亮点不够，4月22日发了感谢信面试流程：1.面试官介绍部门和组内方向（AI）2.自我介绍3.项目不是实验室的，而是开源的、通用的，为什么？4.进程线程协程的上下文是怎么切换的？  想讲到三者的区别再讲切换，然后到进程切换时被打断5.进程什么时候切换，用什么指令符？具体指令符不清楚，提了下schedule，就绪队列相关6.多个进程可以分配同一个cpu吗？不行，多CPU对应多进程，多核对应多线程7.电脑上的进程数为什么会远超过cpu核数？只答了时间片，应该再提一下优先级、阻塞和唤醒8.通过什么信号去通知进程切换到下一个进程？不知道，讲了下对信号的理解，建议我去看汇编（感觉可能是硬件中断、时钟中断)9.线程状态？简单八股10.线程与协程的区别？主要讲了下切换11.协程的通信，协程如何切换到下一个协程？讲了IO协程调度器，管道用于通知线程取任务12.线程下协程的内存管理？讲了下内核栈、用户栈13.能建立多少个长连接，与线程数和协程数是不是有关？只与协程数有关，重新讲了下协程调度器14.线程竞争获取协程的同步机制？对协程任务队列加锁15.问到这面试官说感觉已经没什么问题了（此时才30分钟不到），于是我主动讲了下hook16.怎么监听fd有事件发生？epoll，空闲线程epoll_wait17.服务器发送响应后又收到消息，都是用一个线程处理吗？一个协程18.协程一直阻塞怎么办？定时器，超时就取消事件19.项目问完了，问研究方向，有没有其他与AI相关的项目（实验室做的项目不太行），为什么不做AI相关的而是学C++开发，能讲讲研究生对C++的认知提升在哪些方面？20.反问对实习生重视哪些方面？主要注重工程能力和算法创新能力21.最后聊了下流程、实习时间相关的，以及给了我一些建议，对项目还算熟悉，需要丰富下简历，一个项目不够总结：第一次面试，有些紧张，答的不是很流畅和自信；面试管感觉很年轻，态度挺好的，主要按他对项目的疑问去考察，会有引导，看出我是第一次面试后也给了我一些建议；对于蚂蚁来说可能重视是否做过比较好的项目，我在这方面还是很不足的-

A 寻径指津 因为移动的代价都是1，所以是标准的bfs问题，但是与bfs不同的是四个方向的移动不是相邻的，而是一直移动到边界。 所以，我们只需要找到四个方向移动到达的位置，就可以用基本的bfs解决问题。 寻找往右走达到的点可以这么处理——对于第行的点，我们可以通过从第列往第列开始遍历，初始设置变量，如果碰到在位置为'#'，那么标记，如果碰到的不是'#'，那么位置往右走可以到达的位置就是，前者连单向边指向后者。 一行找连点的复杂度是，每行找完的复杂度就是，同样的原理对其它三个方向进行预处理连边。 连边完成以后进行bfs 参考代码 #include<bits/stdc++.h> us...