![文远知行研发工程师二面](https://imgs.xnip.cn/cj/jy2/2024-08-02/4a9eb960-3f33-4b42-942a-db628fde87b1.jpg)
时间:2024/07/29 17:00(60分钟)
八股:vector底层(答到size达到capacity时扩容就差不多了),为什么扩容是1.5到2倍(时间和空间的tradeoff),push_back复杂度(均摊常数)
手撕:给定一个红绿灯的位置坐标和高度,给若干障碍物凸多边形柱体顶点坐标和高度,每次询问对于一辆车的位置和高度判断其是否能看到红绿灯
这个问题感觉就是我说了我比较擅长计算几何后给我的题目,思路是以红绿灯为光源,把柱体投影到车的高度面上,判断车是否在阴影里,为了方便我写的是枚举每条边投影成若干梯形,需要实现判断点在凸多边形内的函数,写完之后盘了一下优化点,写了蛮久,个人感觉面试写到这个程度已经挺好了