百度作业帮提前批：数据挖掘/机器学习算法工程师一面面经

写在前面

之前在牛客网上投递了百度作业帮的数据挖掘/机器学习算法工程师岗位，今天下午进行了视频面试，用的是牛客网的系统，牛客网的系统还是不错的，点赞。面试之前在牛客网上搜过面经，我们学校的一个同学面过，说上来就是编程题，好吧，就是这样，可能我俩是同一个面试官吧，面试官还是我们学校的，-_-

题目一

题目描述

给定两个矩形，每个矩形给你左上角的坐标和右下角的坐标。然后判断两个矩形是否相交，输出相交矩形的左上角坐标和右下角坐标，如果不想交或者相交为一条线的话，输出{-1, -1, -1, -1}。假设坐标原点为(0, 0)，两个矩形都在第四向限。

题目意思大概就是上面，面试的过程中就题目和面试官反复确认了下。

解题思路

题目比较简单，在草稿纸上画出示意图就可以看出坐标间的关系，就可以编写代码求解了，这个题目主要是题意不清楚的地方和面试官确认了好几次。

解题代码

下面是我在视频面中的代码：

public static void main(String[] args) {
    int[] matrix1 = {x1, y1, x2, y2};
    int[] matrix2 = {x3, y3, x4, y4};
    
    // x方向
    if(matrix2[0] >= matrix1[2] || matrix2[2] <= matrix1[0]) {
         return new int[] {-1, -1, -1, -1};
    }
    // y方向
    if (matrix2[3] >= matrix1[1] || matrix1[3] >= matrix2[1]) {
        return new int[] {-1, -1, -1, -1};
    }
    int[] ans = {x5, y5, x6, y6};
    ans[0] = Math.max(matrix1[0], matrix2[0]);
    ans[1] = Math.min(matrix1[1], matrix2[1]);
    ans[2] = Math.min(matrix1[2], matrix2[2]);
    ans[3] = Math.max(matrix1[3], matrix2[3]);
    return ans;
}

写了一个类似伪代码的代码，最后面试官确认没有问题。

题目二

题目描述

给定n，代表生成括号的对数，请编写代码生成所有可能的并且有效的括号组合。

示例

1
2
3

1   ()
2   ()() (())
3   ((())), (()()), (())(), ()(()),()()()

解题思路

这个题目在面试官说完，题意是很好理解的，感觉是一个比较简单的题目，考虑一会儿后，我觉得是用递归来做，但是具体没有想清楚，然后就开始边编写代码边思考。

后面下来查了下，是Leetcode的一个原题https://leetcode.com/problems/generate-parentheses/description/，我不知道为啥一年前我是用c++来做的，没有印象了。

递归是没错的，我们可以在递归的时候保存剩余左括号数目left和剩余右括号数目right，如果为负或者left > right，这不是有效的括号组合。当left==0且right==0时，那么添加结果就可以了。具体见下面代码，代码是按照leetcode上写的。

解题代码

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        helper(n, n, "", res);
        return res;
    }
    
    void helper(int left, int right, String str, List<String> res) {
        if (left < 0 || right < 0 || left > right) {
            return;
        }
        if (left == 0 && right == 0) {
            res.add(str);
            return;
        }
        helper(left - 1, right, str + "(", res);
        helper(left, right - 1, str + ")", res);
    }
}

总结一下

总的来说，这次面试出的题目并不是很难，第二个题目是一年前做的，忘记了解题思路，思考错误了一个点，我说要去保存未匹配的左括号数量。其实直接保存左右括号的值就可以了。这次面试感觉有点紧张，思路不是很清晰。

在视频编写代码的过程中，犯了一些小错误，比如拼写错误，变量没有定义就使用等，主要之前还没这样视频面共享写代码过。以后写代码还是要严谨，可以多花一点时间思考。不确定的地方可以和面试官沟通，确定后就主要是自己思考解题思路，并写出严谨的代码。