小马智行：pony ai（hr面后挂了）
说实话，拿到虾皮后，我有点懈怠了，对待后面的面试都不是很积极。
今天是群里的一位姑娘问我，有没有面过小马智行的，所以我决定还是将经验贴写写
岗位：仿真相关的
面试工具：zoom
笔试是有一个专门的链接，无自动补全和锁紧，就是一个txt在线编辑，写代码的时候需要屏幕共享
一面：
自我介绍
项目经验
笔试题目：
第一题：
我忘了，真不好意思，但是应该挺简单的，（被我忘记的应该都简单）
第二题：
假设有给定一个数组[1,2,3...n]这个数据是等差数列单调递增的，从1到n的
请问：
这个数组有多少个子数组和为奇数：
举例：
[1,2,3,4,5]
[1],[3],[5],[1,2][2,3],[3,4],[4,5],[2,3,4],[1,2,3,4,5]就是所有的子数组
解法：
我是按照子数组的元素个数分开算的
子数组元素个数为1，也就是只有一个数的时候，有一半和为奇数，1，3，5
子数组元素个数为2，全部为奇数，[1,2],[2,3],[3,4]
从元素个数为3的时候，就开始稳定了：
a.元素个数为奇数个，奇偶的数量各占一半
b.元素个数为偶数个，没有奇数
最后问我时间复杂度，我说n，他说，这个能不能简化到1呢，我想了想，说了说公式，他表示可以了
2面：
自我介绍
项目经验
第一题：
假设给你一个deque[3,2,9,0,1,7,6,5,4]，我们每次取出队头的两个元素，将较大的元素放在最后，较小的元素还是放在队头
请问，经过k（k巨大）次调整后，第m个元素为什么？
解法：
将小的放在前，大的放在后，我给你演示下这个过程
前4次调整，
3,2,9,0,1,7,6,5,4
2,9,0,1,7,6,5,4,3
2,0,1,7,6,5,4,3,9
0,1,7,6,5,4,3,9,2
0,7,6,5,4,3,9,2,1
其实细心的同学应该发现了，当队列中的最小值0提到前面后，除0外的整个序列就已经确定好了，是一个链表环
0（最小值）永远在第一位，剩下的，永远是1,7,6,5,4,3,9,2在循环
所以当最小值到达队首的时候，整个序列就开始了稳定的循环，假设为总体为n个元素，用k = k %（n-1）就大大缩减了，模拟过程的次数
3面：
自我介绍
项目经验
第一题：
假设给你一个01矩阵，和初始位置，终点位置，请问你怎么做到最少的拐弯次数到达终点，（0代表可以经过，1代表有障碍物），不存在向后走
0 0 0 0 E
0 1 0 1 0
0 S 1 0 0
0 0 0 0 0
这个跟平时做的不一样，大多人首先想的应该回事，通过bfs广搜来做，但是广搜找的是路径最短，而不是转弯次数最短
可能这个时候会想到，我用一个矩阵来记录每个点的最小转弯次数就行了（本人也是这么做的）
面试官给我举了这个例子,假设为2n * 2n的方阵：
1 1 1 1 0 0 0 0 E
1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 1
0 S 0 0 0 1 1 1 1
将方针分成了4个小方阵（每个方阵 n 个点），左上跟右下全部为1，只有一条路能通过
这个时候，如果左下的方阵比较顽皮，他可以做到让我们不断更新节点，时间复杂度能达到 n^4，所以不太行
解法为：
我们每次不只是更新相邻4个点的信息，更要更新一行或者一列节点的信息，因为一行或者一列都是不用再额外转向的
好吧，大写的服！
为了掩饰尴尬，面试官说你这个bfs做法也可以，均摊到非极端矩阵的复杂度也不很高
。。。。。。
文化面（hr面）
自我介绍
说你在百度做了什么
你在百度实习的时候，遇到最大的困难是什么？
为什么没在百度留用呢？
你对自动驾驶有了解吗？回答了百度apollo
在前面的面试中，你对我们有什么印象？
你实习待过的两家公司区别是什么？（外企和百度）
然后给我介绍了一下小马的文化。
有什么要问我的吗？
手头有意向吗？当时为什么会选择投递这两家公司吗？
