2021秋招提前批-百度自动驾驶高精地图部门-面试总结
Published:
百度自动驾驶，高精地图部门定位方向:
- 部门概况：主要面向自动驾驶中高精地图的构建和定位两个方向，定位主要是对多种传感器的使用来实现车辆位置的精确定位，目前已经可以实现 20cm 左右的精度。定位团队大概 20 多人，高精地图团队大概 40~50 人左右。整个百度自动驾驶相关的人员在 1000 人以上。
一面
- 自我介绍
- 介绍一个自己的项目或者工作
数据结构堆的构建时间复杂度，删除插入时间复杂度
- 初始化堆$N\cdot log(N)$, 删除和插入$log(N)$
C++ 水平怎么样，写过一些相关的代码？
- 了解水平，OJ 水平，大型项目没写过。
Hash 表的原理，冲突处理
- hash 函数根据 key 将数据分布到不同的 hash 桶中，在负载因子较小的时候可以实现 O(1)的时间复杂度。冲突处理方式有链表链接，当负载因子到达一定阈值的时候扩展 hash 表。具体的扩容算法可以查看这里
有序表和无序表的区别
- 好像只在 C++里有这个区别，map 和 unordered_map？ C++中 map 默认按照 key 递增排序，实现上为红黑树（一种非严格意义的平衡二叉树），搜索时间 O(log(N))； unodered_map 使用哈希表实现，平均搜索时间 O(1)，最坏搜索时间 O(N)。
- python 里好像都是 dictionary
算法题 动态规划讲思路
- 题目：一个人去打靶，每次命中 1~10 环的概率是一样的（都是 1/10),那么打靶 5 次得分 45 分的概率是多少？
- 动态规划 初始化：$dp[0][x]=1/10 , x\in [1,10], \quad dp[0][y]=0 , y\in [11,50]$
- 状态转移方程：$dp[i][j]= \sum_{k=1}^{10}{dp[i-1][j-k]* (1/10)} , j \in [i,50]$，
- 除去初始化一次，总共外层循环 4 次，内层循环从 1~50。返回 dp[4][45]。
- 通过状态压缩可以空间复杂度 O(2* target),时间复杂度 O(M*target),其中 M 是总共打靶的次数，target 是目标分数。
- 算法题 写代码
- 题目给定两个线段，用四个点表示，求解两个线段的交点坐标
- 题目比较简单主要是各种边缘 case。核心思路是根据两个点算出直线的斜率和截距，然后计算交点是否在两个线段中间。设交点坐标为（a,b） ,给定的四个点坐标是（x1,y1）（x2,y2）（x3,y3）（x4,y4）, 如果满足 $ a>= min(x1,x2) ~ and ~ a<= max(x1,x2) ~ and ~ b>=min(y1,y2) ~ and ~ b<=max(y1,y2) ~ and ~ a>= min(x3,x4) ~ and ~ a<= max(x3,x4) ~ and ~ b>=min(y3,y4) ~ and ~ b<=max(y3,y4) $则点 (a，b)在两个线段中。
- 边缘 case 包括，直线斜率为无穷大，两直线平行（没有交点）或者重合（无数个交点），或者交点在线段外面。
二面
二面是部门的经理，问的都是比较开放的问题。
你对自己未来的职业规划是怎样的，对行业的选择。（面试官语重心长的表示个人的行业选择对未来的职业规划有很大的影响）
讲一下自己简历的 ORB-SLAM2 相关的那个项目
介绍一下你在腾讯医疗 AI 实验室做的工作
如果让你去构建学校周围的高精地图你会怎么做？
- 先利用 SLAM 技术得到当前传感器和周围物体的相对位置关系，然后使用北斗等卫星导航系统得到当前传感器的地球绝对坐标，然后根据相对坐标和换算出周围环境中的点在地球坐标系下的坐标。然后使用点云分割等技术构建三维物体或者 mesh 表示，然后渲染地图。
如果让你实现微信摇一摇这个功能，前后端你应该怎么设计，怎么从众多用户中找出附近的人。
- 分级查询，按照国家，省，市，区县，街道等不同级别过滤大部分用户，然后计算附近的距离然后返回 topK 的结果。
- 预设网格，标记点，客户端定时发送位置信息到服务器，注册到相应的标记点的用户池里。摇一摇用户查询时，直接返回其标记点的用户池或加上其附近 K 个标记点的用户池，再做一下排序。
怎么识别微信群中聊天是否包含反动违法或者谣言等信息？
- 针对反动违法等内容构建关键词条，构建 embedding 语义库，然后对每条群里的消息进行快速 embedding 然后和语义库中敏感词进行语义相似度匹配，高于阈值的消息进行更细粒度的检查或者人工审核。所有关键词都低于阈值则可以安全放行
- 针对谣言信息，感觉目前技术无法做到即时和实用。
你对自动驾驶有兴趣吗
聊了一下自动驾驶这个领域的未来，前景，目前的现状和困难，和国内外厂商的对比和趋势。