2021校招
2021-03-30 11:18:41 # 面试 # 校招 # summary

国内实习

由于个人原因，导致暑期可能无法在国内实习，所以就找了少数几个日常实习，暑期实习只面了一个微软。由于我是有全职经验再回学校读书的，所以可能面试内容倾向于项目经验多一点。

微软(offer)

岗位：C+AI Summer Intern

一面

面试官小哥人很好，基本上都在交流项目，全程45分钟，聊了37分钟的项目和经历，算法题是比较常规的，而且只描述了思路，并没有实际coding。

聊项目经验的事情就先pass了，算法题目是力扣84. 柱状图中最大的矩形，这道题我还没有写题解，写完后会更新上来，这里先简要描述一下思路。

解法1： 以每个柱形为高，向左向右分别延伸，直到找到第一个比它矮的indexL和indexR，indexR-indexL即为“以当前柱形为高的最大矩形面积”，遍历所有柱形。时间复杂度为O(n^2)。

解法2：“左侧第一个更矮”和“右侧第一个更矮”，这个算法看起来很熟悉，这里我们可以使用单调栈来进行处理，从左到右过滤一次，从右到左过滤一次，找出每个位置左右第一个更矮的位置。这一步是O(n)的，然后从前至后再扫描一遍数组即可。整体复杂度O(n)。

二面

二面的面试官出了两道很有意思的题目，我都没有回答上来，这里记录一下。

  1. 从一个数组中找出最大和最小两个数字，要求尽可能少的比较次数（不考虑空间问题）。提示：$\frac{3}{2}n$次。（加减常数也不要考虑了）

解法：维持两个变量max 和min ，min 标记最小，max标记最大，每次比较相邻两个数，较大者与max比较，较小者与min比较，找出最大最小值，每2个元素比较了3次，总计比较次数为1.5N次。

  1. 从一个数组中找出最小的两个数字，要求尽可能少的比较次数（不考虑空间问题）。提示：$n+log_2^n$次。（加减常数就不要考虑了）

解法：将数字两两为一组进行比较，每一组筛选出较大的数字和较小的数字，然后将较小的那一组数字进行下一轮的比较，然后进行同样的操作，最终可以选出最小的那个数字，此时，我们总计比较了($1 + 2 + 4 + ….. + \frac{n}{2}$)次，也就是n次。然后第二小的数字，一定是和最小的那个数字比较过，从和最小的数字比较过的数字中找到最小的数字，即为第二小的数字。

算法题：传统的LCS。dp解法，这里就不展开讲了。

Lead面

目测是凉了，因为本人是Java选手，C++面经确实一点也没复习，痛了痛了。

  1. 基础题：

以下代码中二者有什么区别？ a[10]是从栈上分配内存，new是从堆上分配内存。大致明白想考的依图，这样可以聊到C++的内存结构，还有一系列的内容。但是奈何没复习，就直接pass了，不给自己挖坑了。

1
2
int a[10];
int* a = new int[10];
  1. 算法题：

题目：给出一棵二叉树，给出其中的两个节点，计算两个节点之间的距离。

思路：先按照传统的LCA来找到p和q的Lowest Ancestor，再从LCA出发，找到p和q的depth，进行相加。special case就是p和q可能是LCA本身，这里做个判断即可。实现语言为Java。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {};
    TreeNode(int val) {this.val = val;}
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.righr = right;
    }
}

public class Solution {
    TreeNode lowestAncestor = null;
    public int distance(TreeNode root, TreeNode p, TreeNode q) {
        // Find the LCA of p and q.
        LCA(root, p, q);
        
        // Return the distance of these two nodes.
        if (lowestAncestor == p) {
            return findDepth(p, q);
        } else if (lowestAncestor == q) {
            return findDepth(q, p);
        } else {
            return findDepth(lowestAncestor, p) + findDepth(lowestAncestor, q);
        }
    }
    
    private boolean LCA(TreeNode root, TreeNode p, TreeNode q) {
        if (lowestAncestor != null) {
            return false;
        }
        
        if (root == null) {
            return false;
        }
        
        int left = LCA(root.left, p, q) ? 1 : 0;
        int right = LCA(root.right, p, q) ? 1 : 0;
        int mid = root == p || root == q ? 1 : 0;
        
        if (left + mid + right > 1) {
            lowestAncestor = root;
        }
        
        return (left + mid + right) > 0;
    }
    
    private int findDepth(TreeNode root, TreeNode node) {
        if (root == null) {
            return -1;
        }
        
        if (root == node) {
            return 0;
        }
        
        int l = findDepth(root.left, node), r = findDepth(root.right, node);
        return Math.max(l, r) + 1;
    }
}

问：进一步，是否可以将TreeNode优化一下，变成支持子节点可以指向父节点的，可以有什么优化么？

答：可以用一个hashset记录p的所有ancestors，然后q依次向上去查找ancestor，直到找到第一个ancestor在p所记录的hashset中。

（算法题结束）

  1. 设计题：

这题是真没见过，记录一下给大家提个醒吧。

题目：给出a，b，c三个大小的水桶，给出一个正整数n，两个问题：（1）写程序判断是否能倒出n升水？（2）如果能倒出，怎么倒？

答：这是真没见过，见过一次就好了。这题应该用state machine来进行思考，每个水桶的初始状态是一个tuple(a,b,c)，目的是倒出n升水，每一个state都会有一些合法的transition，把这些transition依次遍历，然后递归进行遍历。这里需要用一个set来记录当前路径上的所有state，如果出现了state“回溯”，则也放弃这条分支。直到找到n升水的解决办法。

注意，这里的n升水，n一定是小于（a,b,c）三者中的最大值的，因为多余的那部分可以用最大的那个桶给直接倒出来，倒$/frac{n}{c}$次。

字节（offer）

腾讯（offer）

Prev
2021-03-30 11:18:41 # 面试 # 校招 # summary
Next