首页 > 其他 > 详细

面试经验总结

时间:2019-06-26 13:42:16      阅读:71      评论:0      收藏:0      [点我收藏+]

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

面经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;
}

三面

没问技术,主要是职业规划,从毕业到现在的每个工作和每个空档期都干了些啥,为什么转行等等,从本科毕业到现在的每个时间节点问的很细,最后问我期望薪资,我说年薪30+,然后问我之前的薪资。

面经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到了后,说几位面试官对我比较认可,说我学习能力强,潜力大,然后问我期望薪资,我说年薪30+,然后HR说他要回头反馈给用人部门,他说因为他也要看用人部门对我的一个评估,说因为目前有几个候选人,然后就是说了下薪资福利,公积金缴纳情况等。

面经3

一面

首先是自我介绍,然后问项目,接着问之前工作中遇到的难题和我是怎么去解决和处理的,再就是是下面的编程题,题做完后问了下C++ STL里面的容器以及底层实现,对每种容器进行不同操作的时间复杂度空间复杂度,Vector在容量分配上的缺点,如何避免,问我建堆和调整堆的时间复杂度。

最后问了下如何删除一个链表的节点,我问了下是给我一个值还是给我一个节点,如果给我一个值我就只能遍历链表进行删除;如果是给我一个节点,在不是尾节点的情况下,我只需要O(1)的时间,把下一个节点的值赋给当前节点,然后当前节点指向下下一个节点,如果是尾节点我只能利用快慢指针遍历进行删除。

输入m,n(正整数),表示矩阵行、列,输出如下形式矩阵:

0 2 3 9 10
1 4 8 11 16
5 7 12 15 17
6 13 14 18 19

vector<vector<int>> printNum(int m, int n){
  if(m < 0 || n < 0){
    return -1; // 非法返回-1
  }
  if(m == 0 || n == 0){
    return {}; // 返回空数组
  }
  vector<vector<int>> ret(m, vector<int>(n,0));
  int i = 0;
  int j = 0;
  bool down = true;
  // 只要(i,j) != (m-1, n-1),就一直循环
  while(i != m-1 || j != n-1){
    if(down){
      // 左下循环
      while(i+1 >= 0 && i+1 < m && j-1 < n && j - 1 >= 0){
        ret[i+1][j-1] = ret[i][j] + 1;
        ++i;
        --j;
      }
      
      if(i+1 >= 0 && i+1 < m && j < n && j >= 0){
        // 下
        ret[i+1][j] = ret[i][j] + 1;
        ++i;
      }else if(i >= 0 && i < m && j+1 < n && j+1 >= 0){
        // 右
        ret[i][j+1] = ret[i][j] + 1;
        ++j;
      }
      // 转向
      down = false;
    }else{
     // 右上循环
      while(i-1 >= 0 && i-1 < m && j+1 < n && j + 1 >= 0){
        ret[i-1][j+1] = ret[i][j] + 1;
        --i;
        ++j;
      }
      
      if(i >= 0 && i < m && j+1 < n && j+1 >= 0){
        // 右
        ret[i][j+1] = ret[i][j] + 1;
        ++j;
      }else if(i+1 >= 0 && i+1 < m && j < n && j >= 0){
        // 下
        ret[i+1][j] = ret[i][j] + 1;
        ++i;
      }
      down = true;
  }
  
  return ret;
}

二面

题与解

首先是自我介绍,然后是项目,然后是算法题编码:给定任意两个字符串,实现字符串的乘法,返回结果字符串,如:输入str1 = "132875678946569349",str2 = "892346567895",下面是我当时的编码。

class stringMult{
public:
    // 判断字符串是否全是0
    bool isZero(string& str){
      for(int i = 0; i < str.size(); ++i){
        if(str[i] != '0'){
          return false;
        }
      }

      return true;
    }

    //反转字符串
    void reverseString(string& str){
        for(int i = 0; i <= str.size() - 1 / 2; ++i){
            char tmp = str[i];
            str[i] = str[str.size() - 1 - i];
            str[str.size() - 1 - i] = tmp;
        }
    }

    string getOneRet(string & str, char ch, int count){
      string ret;
      int carry = 0;
      for(int i = str.size() - 1; i >= 0; --i){
        // 进位保存
        int tmp = ((str[i] - '0')* (ch - '0') + carry) / 10;
        // 余数位
        int cur = ((str[i] - '0')* (ch - '0') + carry) % 10;
        ret.push_back(cur);
        carry = tmp;
      }

      if(carry){
        ret.push_back(carry);
      }

      reverseString(ret);
      if(count){
        // 乘法都会偏移,把低位补齐方便后面对所有的string相加
        ret.append(count, '0');
      }
      return ret;
    }
                   
    // 乘法入口
    string stringMulti(string str1, string str2){
     if(str1.empty()){
       return str2;
     }
     
     if(str2.empty()){
        return str1;   
     }
     
     if(isZero(str2) || isZero(str1)){
       return "0";
     }
     
     // 位数短的放在乘法的第二行,减少计算次数
     string tmp;
     if(str1.size() < str2.size()){
       tmp = str1;
       str1 = str2;
       str2 = tmp;
     }

      vector<string> vec; // 存储str2的每个字符与str1相乘的结果,最后总体相加
      int count = 0;
      for(int i = str2.size() - 1; i >= 0; --i){
        string oneRet = getOneRet(str1, str2[i], count);
        vec.push_back(oneRet);
        ++count;
      }

      string ret;
      int maxLen = vec.back().size();
      int carry = 0;
      for(int i = 0; i < maxLen; ++i){
        int sum = 0;
        for(int j = 0; j < vec.size(); ++j){
          if(i < vec[j].size()){
            sum += vec[j] - '0';
          }
        }

        int tmp = (sum + carry) / 10;
        int cur = (sum + carry) % 10;
        ret.push_back(cur);
        carry = tmp;
      }

      if(carry){
        ret.push_back(carry);
      }

      reverseString(ret);
      return ret;
    }
}

编码完成后,又出了一算法题,n个骰子,每个骰子掷1次,求和为某个值val的概率。这道题只让说出思路,没让编码,我首先讲了下分母为\(6^n\),这个当时我真没想出啥好方案,就说了一个暴力的解法,思考了两分钟后还没想出更优方案,面试官说没关系,然后就结束这场面试了,说HR之后会联系我,其实当我没想出更好的方案时,我就以为我已经凉了,但是也不清楚HR会不会真的联系我,如果联系了我会续写后面的经验贴。

不过讲实话,剑指offer 67道题,我基本都看了,没看的超不过10道,并且掷骰子这个题刚好就是我没看的那个,看的一个没问到,没看的偏偏要遇见,看起来以后不能放过一条漏网之鱼。

三面

果不其然,周六二面后,周一收到三面通知,由于我人在北京,三面需要到上海,来回报销路费,于是周二去了上海,从15点开始,约进行了1.5小时,首先还是自我介绍,然后依然是问项目,接着又是做算法题:给定一个矩阵m,h表示高,w表示宽,矩阵中值为0表示当前格子可以走,值为1表示当前格子不可以走,求从(0, 0)到(h-1, w-1)的最短路径,即求所有可行路径中格子最小的路径。

拿到这个题,首先想到的就是深度优先搜索,下面是当时写的,写完后,检查了一遍,然后给面试官过代码解释了下。面试官让我优化,我自己思考了好一阵子,得出一个思路,深度优先搜索的过程中 ,按深搜顺序存储当前路径中所有格子的行和列号index(i,j),当找到一条可行路径后, 逆序遍历路径,把路径中的(i,j)到(h-1, w-1)的格子数填入prevRet(i,j)中,这样, 当下一次深搜时先判断prevRet(i,j)是否有值, 如果有直接获取该值,同时逆序遍历路径中的格子继续填入prevRet(i,j),避免很多重复的计算。把优化的思路和面试官解释清楚后,面试官说思路没问题,没让我重新编码。

接着面试官问我如何测试我自己写的这个接口,然后我说需要编写测试用例,给定输入和输出,看接口的输出与结果是否一致,然后大致列了几条:

  • h和w不合法的情况,输出-1;
  • 只有1行或者只有1列的情况下,矩阵中1的个数大于等于1必须返回0,否则返回行元素个数或列元素个数;
  • 任何情况下的输入,输出值不大于矩阵中0的个数;
  • 如果输入矩阵太大,int可能存不下结果值,接口内部需要能够应对这种情况,给出合理提示;
  • 如果输入矩阵很大,因为处理过程中申请了visit,内存可能不够,接口内部需要能够应对这种情况,给出合理提示;

与面试官解释下测试用例后,面试官让我再想想还有没有其他情况,我想了一会实在想不出,然后面试官问我写的这几条是想到一个写一个,还是按什么思路写的,我当然说是条理性写的。

最后面试官问我转行的初衷,都修了什么课程,有没有学操作系统,我说操作系统,linux内核,算法,机器学习等都有修,估计是看我跨专业才问的。我继续补充说对虚拟内存管理,进程地址空间,中断,调度,进程线程切换,上下文保存与恢复,同步与互斥机制等都清楚。

面试官最后又问我是否能够全职,问我有什么问题需要问他,我回答当然是全职,然后问了下:主要工作内容,主要技术栈,在招的这个岗位的团队大小。面试官回答我的问题后,就让我等一下,估计是去请HR了。

题与解

// 走迷宫
class maze{
public:
    void dfs(vector<vector<int>> &m, int &h, int &w, int row, int col, int &one){
        if(row > h || col > w || visit[row][col] || m[row][col]){
            return;
        }
        
        if(row == h && col == w && !visit[row][col] && !m[row][col]){
            ret = min(ret, one + 1);
            return;
        }
        ++one;
        visit[row][col] = true;
        dfs(m, h, w, row - 1, col, one);
        dfs(m, h, w, row + 1, col, one);
        dfs(m, h, w, row, col - 1, one);
        dfs(m, h, w, row, col + 1, one);
        --one;
        visit[row][col] = false;
    }
    
    int getMinPath(vector<vector<int>> m, int h, int w){
        if(h <= 0 || w <= 0){
            return -1; // 输入非法
        }
        
        // 初始化为整形最大值
        ret = 1 << 31 -1;
        visit = vector<vector<bool>>(h, vector<bool>(w, false));
        
        // 记录路径中可行的格子数
        int onePath = 0;
        dfs(m, h-1, w-1, 0, 0, onePath);
        return ret;
    }
    
private:
    vector<vector<bool>> visit; // 记录访问标志
    int ret; // 存放结果
    
    // 按深搜顺序存储当前路径中所有格子的行和列号(i,j)
    // 当找到一条可行路径后, 逆序遍历路径,
    // 把路径中的(i,j)到(h-1, w-1)的格子数填入prevRet[i][j],
    // 这样, 当下一次深搜时先判断prevRet[i][j]是否有值, 如果有直接获取该值,
    // 同时逆序遍历路径中的格子继续填入prevRet[i][j]
    vector<pair<int, int>> index;
    vector<vector<int>> prevRet(h, vector<int>(w, 0));
};

HR面

HR到了后,问我现在是否住北京,买的几点票,我掐着面试时间买的返程票,然后就说那我也快一点(怕我赶不上车),然后就问我昨晚住的哪里(因为我是前一天晚上去的上海),我说住复旦大学同学那里,问我职业规划,问我是否打算长住北京,问我什么时候可以到岗,问我之前的薪资,问我目前是否有offer,问我期望薪资,说公司劳动强度大,问我怎么看待能否承受,问我是否打算继续面,还是说从offer中选一个。我一一回答后,问了几个问题:薪资福利组成结构,公积金缴纳情况,餐补房补啥的,来回路费报销方式,HR也一一作答。

最后HR说需要商讨下,如果有消息会通知我,然后我就打道回北京了,高铁上坐我旁边的妹子挺文静(好吧,主要是身材好),最后快到站时要对方微信,没要到(好吧,我什么时候脸皮变这么厚了我,从小长到大很少这样主动搭讪,虽然没要到,不过脸没红,也没让我很尴尬,为了自己的脱单大计,为了生活,为了尽早摆脱老爸老妈的催婚之言,我只能豁出我这个脸皮偏了),就到此结贴吧,一路走来,绕了很多弯路,"常将有日思无日,莫把无时当有时",继续努力吧。

面试经验总结

原文:https://www.cnblogs.com/icoty23/p/11089276.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!