面试经验总结

最近忙于找工作，总结下自己的面试经历，勉励自己不断学习不断进步吧。人，不管从事什么样的职业和做何种工作，都要保持一种不断探索和回头总结的习惯，好记性不如烂笔头。

面经1

一面

题

直接上题，如图，拿到这张卷子，第一反应是粗略扫了下三个题，第一题一看就会；第二题让我联想到了动态规划，最后也是用动态规划解出来的；第三题任意三个数之后为30，我首先联想到的是Hash，实际编码过程中遇到了问题，致使该题没能完全编码完成时间就到了。

晚上熄灯背靠枕头思索，恍然大悟，求一个数组中的任意三个数之和为某一个值，直接就可以用LeetCode 15 3sum实现，而且第三题的关键也就是这一步，只要这一步能想到这个算法，基于规则比较都不能算是这个题的难点。这让我不由得又开始厌恶自己起来，3sum这个题自己之前也刷了，为啥就想不起来，记性为何如此差。

第二天上午HR告诉我笔试通过了，第三题编码没做出来，这里也给各位同学一点建议，不管面试还是笔试过程中，一定要有一个好的代码规范，不一定要完完整整的编码出来，但是逻辑思路一定要清晰，一定要有自己的推理和思考。

解

如下答案都是自己独立想出的解法，没有运行也没有测试，重点在于思路，如果有问题，欢迎留言评论。

class C1st{
public:
    // 第一题：
    // 时间复杂度O(min(num1.size(), num2.size()))
    // 空间复杂度O(min(num1.size(), num2.size()))
    vector<int> getRepeateNum(const vector<int> num1, const vector<int> num2){
        // 传入的两个数组任意一个为空，返回空数组
        if(num1.empty() || num2.empty()){
            return {};
        }

        // 这是一个数组，存储符合条件的数
        vector<int> ret;

        int i = 0; 
        int j = 0;
        // 从0开始遍历num1和num2，比较两个数组的首元素是否相等，如果相等放入ret中
        // 否则首元素较小的数组向前走一步，直到遍历到任意一个数组的末尾
        while(i < num1.size() && j < num2.size()){
            if(num1[i] == num2[j]){
                ret.push_back(num1[i]);
                ++i;
                ++j;
            }else if(num1[i] < num2[j]){
                ++i;
            }else{
                ++j;
            }
        }

        return ret;
    }
};


class C2nd{
public:  
    /*
    第二题：
    1.  输入的矩阵N*M，可以采用动态规划思想，逆着考虑，把最后一行作为起点，第一行作为终点。
    2. 记F(i,j)为从matrix[i][j]到最后一行所有点的所有路径中和最小的路径的值，
       为了编码方便，下标都从0开始，0 <= i <= N-1, 0 <= j <= M-1，
       递推公式：
            F(N-1, j) = matrix[N-1][j],    0 <= j <= M-1;  
            F(N-2, j) = matrix[N-2][j] + min{F(N-1, k)}，    0 <= j, k<= M-1;
            F(i,j) = matrix[i][j] + min{ min{F(i+1, k), min{F(i+2, k)}}，   0 <= i <= N-3;  0 <= j,k<= M-1;  
    3. 最终结果为min{F{0, j}},   0 <= j <= M-1，实际编码过程中根据N是否为1，2和 >=3的值，
        选择上面不同的递推公式。
    4. 空间复杂度O(m*n) + O(n), 时间复杂度O(m*n)；
        如果使用下面的2的极致解法，空间复杂度为O(n)
    5. 功能：获取所有路径之和的最小值
    6. 不允许往回跳的情况下，matrix[i][j]，每一行的所有j(0 <= j <= M-1)可以理解
       成互为树的兄弟节点，matrix[i][j]表示从树的第i-1层任意节点到本层的j节点的代价，
       该题相当于求树的最小的路径，树中每个节点最少有m个子树，最多有2m个子树。
    7. 如果允许往回跳，整个拓扑结构成了一个图，有向图（可能有环存在），
       相当于求图的最小带权路径。
    */
    int getMinSum(const vector<vector<int>> matrix){
        if(matrix.empty() || matrix[0].empty()){
            return -1; // 非法返回-1
        }

        int n = matrix.size();
        int m = matrix[0].size();
        // 1. 二维数组;
        // 2. 如果追求极致这里也可把空间复杂度将为O(n)，使用数组temp1 = {F(i + 1, k)}
        //    和数组temp2 = {F(i + 2, k)}实现，0 <= i <= n-3,  0 <= k <= m-1.
        //    同步更新temp1和temp2即可
        vector<vector<int>> f(n, vector<int>(m));

        // 1. 用于存放 min{F(i, k)},  0 <= i <= n-1,  0 <= k <= m-1;  所有元素初始化为整形最大值
        // 2. 如果追求极致，这里空间复杂度可以降为O(1)，使用tmp1 = min{F(i + 1, k)}和
        //    tmp2 = min{F(i + 2, k)}实现，0 <= i <= n-3,  0 <= k <= m-1,
        //    同步更新tmp1和tmp2即可。
        vector<int> rowMin(n, 1 << 31 -1); 

        for(int j = 0; j < m; ++j){
            // 第一个递推公式
            f[n-1][j] = matrix[n-1][j];

            if(f[n-1][j] < rowMin[n-1]){
                rowMin[n-1] = f[n-1][j]
            }
        }

        for(int i = n-2; i >= 0; --i){
            for(int j = 0; j < m; ++j){
                // 1. 进行这一步的目的是处理过程中就把最小值计算出来，
                //    降低时间复杂度，利rowMin的O(n)空间换取O(m)的时间，与前面的两个1对应
                // 2. 如果追求极致，通过这里面更新temp1/temp2和tmp1/tmp2，
                //    在这种情况下时间复杂度为O(n*m)，空间复杂度为O(n)，与前面的两个2对应
                if(f[i][j] < rowMin[i]){
                    rowMin[i] = f[i][j]
                }

                if(i == n - 2){
                   // 第二个递推公式
                    f[i][j] = matrix[i][j] + rowMin(i + 1);
                }else{
                   // 第三个递推公式
                    f[i][j] = matrix[i][j] + min(rowMin(i + 1), rowMin(i + 2));
                }
            }
        }

        return rowMin[0];
    }
};


class C3rd{
public:
    /*
    第三题：
    1. 把牌转换为分数数组，2～9(2~9), J(10),T(10),Q(10),K(10),A(1), 目的是计算是否有牛
    2. str中某个牌若出现过，则在vec中相应置为true，数组下标2～9对应牌2～9，
       下标10对应牌T，同理，11(J), 12(Q), 13(K), 14(A)。vec的目的是便于规则比较
    */
    void string2Array(vector<int> & scores, vector<int> & vec, int& sum, string & str){
        for(int i = 0; i < str.size(); ++i){
            switch(str[i])
            {
                case 'T' :
                    vec[10] = true;
                    scores.push_back(10);
                    sum += 10;
                    break;            
                case 'J' :
                    vec[11] = true;
                    scores.push_back(10);
                    sum += 10;
                    break;
                case 'Q' :
                    vec[12] = true;
                    scores.push_back(10);
                    sum += 10;
                    break;
                case 'K' :
                    vec[13] = true;
                    scores.push_back(10);
                    sum += 10;
                    break;
                case 'A' :
                    vec[14] = true;
                    scores.push_back(1);
                    sum += 1;
                    break;  
                default:
                    vec[str[i] - '0'] = true;
                    scores.push_back(str[i] - '0');
                    sum += str[i] - '0';
                    break;              
            }
        }

        // 排序的目的是hasCow内求任意三个数之和=30需要
        sort(scores.begin(),scores.end());
    }


    // 这里有点类似于leetcode的15题3sum
    bool hasCow(vector<int> & nums, int & sum){
        if(nums.size() < 3)
            return -1;

        int n = nums.size();
        for(int k = 0; k < n - 2; ++k)
        {
            int sum1 = sum - nums[k];
            int i =  k + 1;
            int j = n - 1;
            while(i < j){
                if(nums[i] == sum1 - nums[j]){
                    // 有牛
                    return true;
                }else if(nums[i] < sum - nums[j]){
                    ++i;
                }else{
                    --j;
                }
            }
        }

        // 没牛
        return false;
    }


    // 都无牛或者都有牛且牛的值相等时执行该规则比较
    int ruleCompare(vector<int> &v1, vector<int> & v2){
        if(v1.size() != v2.size())
            return -2;
        int i = v1.size() - 1;
        while(i >= 2){
            if(v1[i] && v2[i]){
                // 都出现过，比较下一张牌
                --i;
            }else if(!v1[i] && !v2[i]){
                // 都没出现过，比较下一张牌
                --i;
            }else{
                // 否则，谁出现过谁就大
                return v1[i] ? 1 : -1;
            }
        }

        // 一样大
        return 0;
    }

    // 入口
    int compareTwoScore(const string str1, const string str2){
        if(str1.size() != 5 || str2.size() != 5){
            return -2; // 输入非法
        }

        vector<int> score;
        int mod1 = -1, sum1 =0;
        int mod2 = -1, sum2 = 0;

        // 1. 数组下标2～9对应牌2～9，下标10对应牌T，同理，11(J), 12(Q), 13(K), 14(A)
        // 2. 对应的牌出现过则设置为true，主要是两副牌都没牛的情况下，逆序遍历v1和v2比较两幅牌的大小
        vector<bool> v1(14, false), v2(14, false);

        string2Array(score, v1, sum1, str1);
        bool hasCow1 = true;
        if(getModWhenHasCow(score, 30)){
            mod1 = (sum1 - 30) % 10;
        }else if(getModWhenHasCow(score, 20)){
            mod1 = (sum1 - 20) % 10;
        }else if(getModWhenHasCow(score, 10)){
            mod1 = (sum1 - 10) % 10;
        }else{
            mod1 = sum1;
            hasCow1 = false;
        }

        score.clear();
        string2Array(score, v2, sum2, str2);
        bool hasCow2 = true;
        if(getModWhenHasCow(score, 30)){
            mod2 = (sum2 - 30) % 10;
        }else if(getModWhenHasCow(score, 20)){
            mod2 = (sum2 - 20) % 10;
        }else if(getModWhenHasCow(score, 10)){
            mod2 = (sum2 - 10) % 10;
        }else{
            mod2 = sum2;
            hasCow2 = false;
        }

        if(hasCow1 && !hasCow2){
            // str1有牛str2没牛
            return 1;
        }else if(!hasCow1 && hasCow2){
            // str2有牛str1没牛
            return -1;
        }else if(hasCow1 && hasCow2){
            // 两个都有牛
            if(mod1 == mod2){
                // 余下二张牌分数之和相等，执行规则比较
                return ruleCompare(v1, v2);
            }else if(0 == mod1){
                // str1牛牛
                return 1;
            }else if(0 == mod2){
                // str2牛牛
                return -1;
            }else{
                return mod1 > mod2 ? 1 : -1;
            }
        }else{
            // 都无牛的情况下，执行规则比较
            return ruleCompare(v1, v2);
        }

        return -2; // never to be run, jut for ignore debug warn info
    }
};

二面

首先是自我介绍，然后问了下项目，最后出了个题：现有一棵二叉搜索树T，有N个线程都向T中插入节点，如何保证多线程安全性和并发性的对树T进行操作。

题与解

分析：因为是二叉搜索树，所以新插入的节点肯定是位于树中的某节点（该节点的左孩子为空或者右孩子为空，或者左右孩子均为空），我提出的思路是给树的每个节点添加两把锁leftMutex，rightMutex。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    Mutex leftMutex;
    Mutex rightMutex;
    TreeNode(int x) : val(x), left(NULL), right(NULL){
        leftMutex.init();
        rightMutex.init();
    }
};

TreeNode* T;  // 全局树的根节点
Mutex mutex;  // 控制T=NULL的情况 
mutex.init();

// 递归实现，也可以用非递归实现，利用while找到插入的位置，然后在加锁互斥
bool insertNode(TreeNode* T, int val){
    if(!T){
        mutex.lock();
        if(!T){
            T = new TreeNode(val);
            mutex.unlock();
        }else{
            mutex.unlock();
            insertNode(T, val);
        }
    }else if(!T->left && val < T->val){
        // 插入左孩子
        T->leftMutex.lock();
        if(!T->left){
            T->left = new TreeNode(val);
            T->leftMutex.unlock();
        }else{
            T->leftMutex.unlock();
            insertNode(T->left, val);
        }
    }else if(!T->right && val > T->val){
        // 插入右孩子
        T->rightMutex.lock();
        if(!T->right){
            T->right = new TreeNode(val);
            T->rightMutex.unlock();
        }else{
            T->rightMutex.unlock();
            insertNode(T->right, val);
        }
    }else if(val > T->val){
        insertNode(T->right, val);
    }else{
        insertNode(T->left, val);
    }
    
    return true;
}

三面

这一面不是HR面，没问技术，主要是职业规划，从毕业到现在的每个工作和每个空档期都干了些啥，为什么转行等等，从本科毕业到现在的每个时间节点问的很细，最后问我期望薪资，我作答后，然后问我之前的薪资。这一面面完后，HR加了我微信。

面经2

一面

题与解答

首先是自我介绍，然后问我为什么转行，踏入互联网的动机是什么。接着就是问项目，问的很细。最后出了一个题：输入一个字符串，写代码实现，把字符串中的所有字母A放在最前面，C放在最后，其他字符放在中间。

首先想到的就是荷兰国旗问题，使用三个指针实现，不过我用这种方法实际编码的时候，没写出来，于是我赶紧换了次一点的空间复杂度为O(n)的方法实现了，然后和面试官讲了可以用三个指针的办法进行优化，在纸上画图描述了下三个指针的思路。

最后问我有没有什么问题需要问的，我问了下面向这个职位的主要工作内容和技术栈。

class CStrSort{
public:
    int getCharCount(string & str, const char ch){
        int count = 0;
        for(int i = 0; i < str.size(); ++i){
            if(ch == str[i]){
                ++count;
            }
        }

        return count;
    }
    
    string strSort1(string str, const char start, const char end){
        if(str.size() <= 1){
            return str;
        }

        string ret;
        int cntA = getCharCount(str, start);
        int cntC = getCharCount(str, end);

        // 面试官追问我了下，说string好像没有append操作
        // 我肯定的说有，并解释了含义，说自己经常用
        ret.append(cntA, start);
        for(int i = 0; i < str.size(); ++i){
            if(str[i] != start && str[i] != end){
                ret += str[i];
            }
        }

        ret.append(cntC, end);
        return ret;
    }
    
    
    // i之前全是start, k之后全是end, j进行扫描
    string strSort2(string str, const char start, const char end){
        if(str.size() <= 1){
            return str;
        }
        
        int i = 0;
        int j = 0;
        int k = str.size() - 1;
        while(j <= k){
            if(str[j] == start){
                // 交换
                str[j] ^= str[i];
                str[i] ^= str[j];
                str[j] ^= str[i];
                ++i;
                ++j;
            }else if(str[j] == end){
                str[j] ^= str[k];
                str[k] ^= str[j];
                str[j] ^= str[k];
                ++j;
                --k;
            }else{
                ++j;
            }
        }
        
        return str;
    }
};

二面

这一面没有自我介绍，也没有深挖项目细节，感觉这一面主要是在挖掘我的技术广度，回忆了下，问的问题大致涉及如下：

1. Http，我讲了请求和响应的组成，并说之前工作经常接触，把1到5开头的状态码含义，然后说了下301，302，500，403，404，200的含义；
2. 问我熟悉shell和linux不，我说之前工作经常用，可以熟练运用；
3. 问我会不会gdb，问我自己平时遇到程序崩溃的时候怎么定位的，我举了个例子，访问空指针发生段错误时，通过gdb进入调试，问我怎么监视一个变量（watch），如何查看堆栈（bt），如何调试指定线程（thread threadnumber）等；
4. 问我了解curl命令不，我说实际没去研究，但是知道有这个命令，是用来抓去网页内容的；
5. 问我多线程下怎么定位死锁，我说我会着重关注临界区和线程之间同步的点；
6. 问我会看top命令不，我解释了大致都有哪些参数及其含义；
7. 问我进程地址空间的构成，堆和栈区别，问动态库、共享内存、mmap位于进程地址空间中的哪个位置；
8. 问我知道消息队列不，我说开源的有kafka，RabbitMQ，我说我自己实际没看过源代码，也没用过，但是我在自己的项目中封装和模拟了一个消息队列的实现；
9. 还问了Rpc；
10. 问我UML，我说自己经常用，然后解释哪些项目用过，我说从我的githuub都能看到；
11. 问我熟悉mysql不，然后我说自己在项目中完全设计过mysql数据库，然后说了是哪个项目，说在我的github能够看到；
12. 问熟悉redis不，我说没有看过源码，然后继续说了下redis与mysql的区别，然后罗列了redis key的类型和含义，说了下RDB和AOF，redis配置文件和redis集群；
13. 问我熟悉PHP，Python不，我说我用PHP自己写过一个前后端的项目，然后说用Python写过爬虫项目，说Python也经常在用，最后说我主要还是C++;
14. 问IPC，我罗列共享内存，MMAP，管道，TCP，并说自己实际都编码用过。

三面

没有自我介绍，问我和前两位面试官聊的怎么样，我说面试官挺亲和的，聊的挺投缘的。问我听说过zookeeper，Hdfs没，我说实际没用过也没去深入研究过，但是知道有这么个东西，并说了两个都是干啥的，然后说自己简单搭建过Hadoop；然后问我最近关注的开源技术都有哪些，我说linux内核源码，libevent，stl，redis。然后补充了下说还没看redis源码，只是通过网上视频、博客和教程，说后面也会慢慢关注下源码；还问了我对行业和公司有什么要求没，我说没具体限制。问我住哪里，要不要搬家，我说找工作了肯定得重新找房子。

HR面

三面后，公司小姐姐给我重新倒了杯水，说不好意思，HR忙还没赶过来，让我等会；最后HR到了后，说几位面试官对我比较认可，说我学习能力强，潜力大，然后问我期望薪资，我作答后，然后HR说他要回头反馈给用人部门，他说因为他也要看用人部门对我的一个评估，说因为目前有几个候选人，然后就是说了下薪资福利，公积金缴纳情况等，最后加了微信。