【2023校招】智加科技-自动驾驶软开面经
0x00 本人情况
- 本人2023应届毕业生,本硕计算机科班出身,ACM铜牌底层选手,硕士研究方向为计算机视觉,后专注高性能计算领域,在某大厂和某造车新势力有过两段hpc实习经历,期间做过商汤openppl的开源项目。因为曾在自动驾驶部门实习,所以对做自动驾驶的一些公司比较熟悉,个人也比较看好自动驾驶这个行业风口,而智加科技在重卡自动驾驶是行业翘楚,所以最后选择了智加科技。由于时间过得比较久,一些问题也记不太清了,只把部分有印象的问题写下来供大家参考,也希望未来能与更加优秀的同学一起共事~
0x01 一面
- 面试官自我介绍,非常nice,紧张心情立马缓解了很多
- 自我介绍,追问了一些过往的实习经历,根据项目经历提问
- 操作系统的基本原理,包括Linux进程地址空间(mm_struct),系统调用的过程(中断,CPU状态切换,上下文保存与恢复,汇编语言具体是怎么进行系统调用的)等
- C++基础知识,包括多态virtual的原理和作用,智能指针相关概念等等
- coding两道题 Q1 Q2
- 反问:自动驾驶哪些业务场景中需要强调高性能,强调了内存方面,继续谈论了一下STL中的allocator
0x02 二面
- 相隔一周得知一面通过,约二面又安排了下一周,可见智加科技投递的人数非常多,面试官资源比较紧张。
- 面试官简单自我介绍
- 自我介绍,实习经历和项目经历介绍,为什么要从高性能计算转自动驾驶开发
- 多线程相关知识,线程同步的方法 进程间通信方式 Linux进程地址空间 哪些情况使得栈溢出
- 介绍一些Google C++ style(简历中的实习talk分享)
- coding两道题 Q3 Q4
- 反问
0x03 三面
- 隔了两周约上了三面,期间是因为智加公司年会要出去玩所以只能往后排期哈哈哈,三面面试官是北京区的技术总监,三面也是纯技术面
- 自我介绍
- 实习中是如何对推理引擎的算子做优化的,优化一个算法的流程和逻辑
- 介绍一些Google C++ style
- 进程和线程的区别,回答了os对二者抽象的定义,以及Linux内核实现上task_struct的相关定义
- 哪些情况可能使得程序crash掉
- 进程间通信方式
- coding两道题Q5 Q6
- 反问:反问系统/算法流程优化的过程,强调了profiling的重要性;重型卡车和乘用车自动驾驶分别的特点和落地难度;
0x04 代码题
- 智加面试很强调coding能力,三次面试一共做了6道题(牛客网),包括STL,数据结构(树,链表,栈等),数学,设计题,一部分原创一部分题库,题库的一般要求当场AC,所以也反映了一定debug能力和心理素质,好在和ACM不同,WA的时候是可以看见样例的,所以可以面向样例编程。但是有的题目无法进行cout,所以还是得加强一下调试能力
- 下面是Q1-Q6的题目以及写出的代码,不保证结果完全正确,大家可以自己分析,如果有更好的思路可以打到评论区哈
- Q1. 手写简易版SharedPtr
// SimpleSharedPtr // copy constructor(lvalue/rvalue) // operator=(lvalue/rvalue) // destructor // void reset(T* pointer) template<typename T> class SimpleSharedPtr{ public: SimpleSharedPtr():obj(nullptr), ref(nullptr){} SimpleSharedPtr(const SimpleSharedPtr& other){ ref = other.ref; obj = other.obj; (*ref)++; } SimpleSharedPtr(SimpleSharedPtr&& other){ ref = other.ref; //swap obj = other.obj; other.ref = nullptr; other.obj = nullptr; } SimpleSharedPtr& operator = (const SimpleSharedPtr& other){ if(other.obj == obj){ //指向同一个对象 return *this; } if(obj != nullptr){ (*ref)--; //原先的引用计数减少1 if((*ref) == 0){ delete obj; delete ref; } } ref = other.ref; // 赋值 obj = other.obj; (*ref)++; } SimpleSharedPtr& operator = (SimpleSharedPtr&& other){ if(other.obj == obj){ return *this; } if(obj != nullptr){ (*ref)--; if((*ref) == 0){ delete obj; delete ref; } } ref = other.ref; obj = other.obj; other.ref = nullptr; other.obj = nullptr; } ~SimpleSharedPtr(){ if(ref == nullptr){ return; } (*ref)--; if((*ref) == 0) { delete obj; obj = nullptr; delete ref; ref = nullptr; } } void reset(T* pointer){ if(obj == pointer) return; if(obj != nullptr){ (*ref)--; if((*ref) == 0){ delete obj; delete ref; } } obj = pointer; ref = new int(1); } private: T* obj; int* ref; };
- Q2. 二叉树层次遍历
#include<iostream> #include <queue> using namespace std; struct TreeNode { TreeNode* left; TreeNode* right; int value; TreeNode(int v):value(v){} }; void levelTraverse(TreeNode* root) { if(root == nullptr) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* fr = q.front(); q.pop(); cout<<fr->value<<" "; if(fr->left) q.push(fr->left); if(fr->right) q.push(fr->right); } cout<<endl; } // 每层打印一行 void levelTraverse2(TreeNode* root) { if(root == nullptr) return; queue<TreeNode*> q; q.push(root); int cur = 1; int nxt = 0; while (!q.empty()) { for(int i=0; i<cur; ++i) { TreeNode* fr = q.front(); q.pop(); cout<<fr->value<<" "; if(fr->left) q.push(fr->left), nxt++; if(fr->right) q.push(fr->right), nxt++; } cout<<endl; cur = nxt; nxt = 0; } cout<<endl; } // 前序建立二叉树 void build(TreeNode* &T){ int x; cin>>x; if(x == -1){ return; } T = new TreeNode(x); build(T->left); build(T->right); } int main(){ TreeNode* T; build(T); levelTraverse(T); levelTraverse2(T); return 0; }
- Q3. pow(2 + sqrt(3), 1000) 向下取整 不使用任何浮点数计算, 求结果的整数部分(结果取模)
/* 不使用任何浮点运算 法1: 直接使用二项式定理,只取k是偶数的部分 计算量大 可能需要高精度支持 法2: (2 + k3)^1000 = a + b*k3 (2 - k3)^1000 = a - b*k3 ==> (0.3)^1000 = 0.00..01 (2 + k3)^1000 + (2 - k3)^1000 = 2a (2 + k3)^1000 = 2a - 1 // 整数部分 求a (2, k3) * (2, k3) ==> (7, 4*k3) // a = 7, answer = 2a - 1 = 13 递归求实部 */ #include<iostream> #include <queue> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; struct node{ ll real; ll vir; // sqrt(3) node(){real = 0; vir = 0;} node(ll r, ll v):real(r), vir(v){} node operator * (const node& b){ // 不使用任何浮点运算 node t; t.real = (real*b.real + vir*b.vir*3) % mod; t.vir = (real*b.vir + vir*b.real) % mod; return t; } }; // 快速幂 不使用任何浮点运算 node pow_node(node x, int n){ node ans(x.real, x.vir); n--; while (n) { if(n & 1) ans = ans * x; x = x * x; n >>= 1; } return ans; } int main(){ int n; while(cin>>n){ node x(2, 1); // 2 + 1 * sqrt(3) node ans = pow_node(x, n); int res = ans.real + ans.real - 1;// 2a - 1 cout<<res<<endl; } return 0; }
- Q4. 栈的压入、弹出序列
/* 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。 假设压入栈的所有数字均不相等。 例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列, 但4,3,5,1,2就不可能是该压栈序列的弹出序列。 下面答案写得比较复杂,均摊时间复杂度也是O(N), leetcode有原题可以查一下简单的做法 */ class Solution { public: bool IsPopOrder(vector<int> pushV, vector<int> popV) { unordered_map<int, int> mp; unordered_set<int> on_stack; stack<int> stk; for(int i=0; i<pushV.size(); i++) mp[pushV[i]] = i; int max_pos = 0; for(auto x : popV){ if(mp.count(x) == 0) return false; if(!on_stack.count(x)){ int pos = mp[x]; on_stack.insert(x); for(int j=max_pos; j<pos; j++){ if(on_stack.count(pushV[j]) == 0) { on_stack.insert(pushV[j]); stk.push(pushV[j]); } } max_pos = max(max_pos, pos); } else{ if(x == stk.top()) { stk.pop(); } else return false; } } return stk.size() == 0; } };
- Q5 将给定的链表向右转动k个位置,k是非负数
/** * struct ListNode { * int val; * struct ListNode *next; * }; * *转动链表 将给定的链表向右转动k个位置,k是非负数。 例如: 给定1->2->3->4->5->null , k=2, 返回4->5->1->2->3->null。 */ class Solution { public: /** * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* rotateRight(ListNode* head, int k) { if(!head) return head; int len = 0; ListNode* p = head; while(p) { p = p->next; len++; } k = k % len; k = len - k; int idx = 1; p = head; while(idx < k){ p = p->next; idx++; } ListNode* new_head = p->next; p->next = nullptr; ListNode* ret = new_head; if(!new_head) return head;// while(new_head->next){ new_head = new_head->next; } new_head->next = head; return ret; } };
- Q6 设计LFU缓存结构 面试时只要求写出如何设计数据结构以及get set关键代码思路
/* 设计LFU缓存结构 一个缓存结构需要实现如下功能。 set(key, value):将记录(key, value)插入该结构 get(key):返回key对应的value值 但是缓存结构中最多放K条记录,如果新的第K+1条记录要加入,就需要根据策略删掉一条记录,然后才能把新记录加入。这个策略为:在缓存结构的K条记录中,哪一个key从进入缓存结构的时刻开始,被调用set或者get的次数最少,就删掉这个key的记录; 如果调用次数最少的key有多个,上次调用发生最早的key被删除 这就是LFU缓存替换算法。实现这个结构,K作为参数给出。 */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * lfu design * @param operators int整型vector<vector<>> ops * @param k int整型 the k * @return int整型vector */ int idx = 0; int capacity; unordered_map<int, int> ump_kv; // key-val unordered_map<int, int> ump_kc; // key-count unordered_map<int, int> ump_kid; // key-id map<int, set< pair<int, int> > > mp_cidk; // count - { <id1, key1>, <id2,key2>,...} int get(int key){ int origin_cnt = ump_kc[key]; //之前的cnt ump_kc[key]++; //cnt++ int origin_id = ump_kid[key]; //之前操作id ump_kid[key] = ++idx; // 更新id mp_cidk[origin_cnt].erase(pair(origin_id, key)); mp_cidk[ump_kc[key]].insert(pair(ump_kid[key], key)); return ump_kv[key]; } void set(int key, int val){ if(ump_kv.count(key) != 0){ ump_kv[key] = val; int origin_cnt = ump_kc[key]; //之前的cnt int origin_id = ump_kid[key]; //之前操作id ump_kc[key]++; ump_kid[key] = ++idx; mp_cidk[origin_cnt].erase(pair(origin_id, key)); mp_cidk[ump_kc[key]].insert(pair(ump_kid[key], key)); return; } else{ if(ump_kv.size() < capacity){ ump_kv[key] = val; ump_kc[key] = 1; ump_kid[key] = ++idx; mp_cidk[1].insert(pair(ump_kid[key], key)); } else{ int out_cnt = mp_cidk.begin()->first; int out_id = (mp_cidk.begin()->second).begin()->first; int out_key = (mp_cidk.begin()->second).begin()->second; mp_cidk[out_cnt].erase(pair(out_id, out_key)); if(mp_cidk[out_cnt].size() == 0) mp_cidk.erase(out_cnt); set(key, val); //删除了一个空间之后必然可以插入成功,重新试一次即可 } } } vector<int> LFU(vector<vector<int> >& operators, int k) { // write code here } };
0x05 写在最后
- 非常感谢和我一起在ad部门实习的同学,在他的推荐下我投递了智加科技,最后获得offer也是一种缘分吧~ 智加的三轮技术面试体验非常棒,非常纯粹的技术面试。对于每个候选人都有HR全流程跟踪,想问什么都可以及时得到反馈,给HR小姐姐点赞!技术上推荐大家学好C/C++基础知识,可以阅读一下STL相关源码,熟练掌握操作系统原理,有时间多读一下深入理解Linux内核,当然coding能力也是非常重要的。如果有对智加感兴趣的同学也可以私信我详聊,祝大家找到心仪的offer~
附上智加科技面经大合集 https://www.nowcoder.com/discuss/967001
#面经笔经##智加科技秋招##自动驾驶##2023届校招##软件开发#