本文介绍 算法工程师面试常见问题集锦

算法工程师面试常见问题集锦

本文由在当地较为英俊的男子金天大神原创，版权所有，欢迎转载，本文首发地址 https://jinfagang.github.io 。但请保留这段版权信息，多谢合作，有任何疑问欢迎通过微信联系我交流：jintianiloveu

算法工程师面试，将会遇到的问题无外乎三大类，第一类是数据结构类，比如让你写一个链表插入啊，让你用栈写一个队列啊之类的；第二类是大规模数据处理问题，比如让你在海量数据里面找出最小的第二个数等问题；第三类比较少，也就是智力问题了，比如一天中时针和分针会相遇多少次等问题。第一眼看上去有点复杂有点多，我来总结一下。

数据结构类问题

  • 寻找最大的k个数
    这个问题出现够频繁了，我在小米的面试，阿里的面试中都被问到了这个问题。大概有三种办法：
    1） 用快排的思想；
    2） 用堆排序；
    3） 用二分查找；
    4） 用二进制最高位来判断。
    此问题具体代码见这里。

  • 去除一个字符串中多余的空格，比如”what the fuck are you talking about?” -> “what the fuck are you talking about?”

这个问题其实很简单，但是容易出错，你在遍历字符串的时候，每次删除一个字符，字符串的长度在减少，所以正确的代码应该是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void remove_multiple_spaces(string &s) {
    // remove the multiple spaces in s
    // "you   and me a  are the  same" -> "you and me are the same"
    // first traverse the string,
    for (int i = 0; i < s.size(); ++i) {
        // if next char is space, and next next char is also space
        cout << s[i] << endl;
        if (s[i] == ' ' && s[i+1] == ' ') {
            // erase one space, erase one char, i--
            s.erase(i, 1);
            i--;
        }
    }
}

记住，这里有个i–。

  • 求解编辑距离。

编辑距离是我在面试阿里实习的时候遇到的一个问题，问题大概如下：有AB两个字符串，从A字符串到B字符串大概经过的转换如下：
1) 删除一个字符； 2） 插入一个字符； 3） 将一个字符修改为另一个字符；
求至少经过多少次编辑可以从A字符串变到B字符串？

这个问题其实也是够经典的，后来我才知道这个东西在NLP中用的比较多，也是最简单的对比句子相似度的方法。这个问题让我想起了LCS问题，也就是求取两个字符串的最长公共子序列问题，可以移步这里进行进一步探索。
回到编辑距离这个问题。我们假设字符串 “aagooohhk”, “goooobbk”, 假设从Ai到Bj的距离是D[i, j]， 那么D[i,j]和之前的D是什么关系呢，我们可以假设已经知道了D[i,j]，则在A上加上一个字符，B上加上一个字符，此时有2种情况：
1） 加上的字符时同一个字符；
2） 加上的字符不相同；
如果是同一个字符，那么编辑距离是一样的，因为这一步不需要操作，如果是不同的字符，就是一次替换操作。但是这个替换操作可以加载A上也可以加在B上，因此要求取一个最小值，总的来说可以得到一个递推公式：

1
D[i,j] = min(D[i-1][j]+1, D[i][j-1]+1, D[i-1][j-1] + (s1[i] == s2[j]?0:1))

这个公式就非常牛逼了。通过它就可以递推的得到编辑距离了。具体代码就不写了。

  • 最长单调递增子序列问题

哇塞这里出现的题目可谓是道道经典，很有可能就会被问到。这道题目是面百度的时候被问到的。其实题目也很简单，这个问题可以归结为LOS问题，Longest Ordered Sequence。比如 1 7 4 9 8 3 6, 最长的递增序列是1 4 8,也就是3.
其实题目也非常简单，借用求子数组最大和的思想来求解之。大概思路就是，首先挨个遍历一下，用一个last_len存储当前遍历的最长的长度，用result来存储最终的最大长度，每次更新result的时候都取result和last_len的最大值，last_seq_largest来存储本次最长递增序列的最后一个元素也就是最大的那个元素，每次和a[i] 进行比较。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int los(int a[], int n) {
    // get the longest ordered sequence
    int last_len = 0;
    int last_seq_largest = a[0];
    int result = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] > last_seq_largest) {
            last_len++;
            result = max(last_len, result);
        } else {
            last_seq_largest = a[i];
            last_len = 1;
        }
    }
    return result;
}

说到这个递增问题，还有第二问： 求删除最少的元素个数，使得一个数组先单调递增，在单调递减？
一种可行的方案是，上面我们不是可以求取一个最长的有序子序列吗，那么能够求递增也能够递减，这也就可以得到两个序列，一个最长的递增序列，一个最长的递减序列，这两个序列也有两种情况：
1） 两个序列有重叠区域，也就是说递增序列后面几个元素和递减序列前面几个元素相同，这种情况，只要把两个序列链接在一起，去除掉重复的部分就ok了；
2） 第二种情况也很好办，那就是两个序列没有重复的部分，那么毫无疑问，要删除最少的元素也就是这个序列最长，那么肯定是最长的递增序列和最长的递减序列链接在一起，这种情况直接连接即可。
那么删除的元素个数也就是连接之后的序列的长度与原始长度之差了。

….
….
…
…
…
…
…
…
…

收集面经不易，如果大家想要PDF的完整版本，可以添加我微信索要，只要9.9元让你面试打通关！直达任何你想去的公司！！wechat: jintianiloveu