![文远知行 研发工程师 一面](https://imgs.xnip.cn/cj/jy2/2024-07-26/db1f604b-6347-4cca-be6c-d21a384fe910.jpg)
2024/07/26 14:00 (40分钟)
场景题:黄灯时间和道路限速的关系
要考虑到两个场景,一个是距离较长时刹车停下来,另一个是距离较短时不刹车直接过去,而黄灯时间则需要保证后者不会闯红灯,可以得到两种情况的临界距离是 v0^2/2a,黄灯时间不能少于这个距离下不刹车通过的时间,即 v0/2a
编程题:平面上n个点,求最多选出多少个点,使得点集中没有x1<=x2且y1<=y2的点对
选出的点集排一下序,一定是x严格递增时y是严格递减的,那么问题就转换成先对x排序后,选出y的最长下降子序列,复杂度nlogn