【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