大厂面经分享|后端开发岗面试真题

前言

在当下激烈的面试竞争环境下，大厂面试一直是程序员小伙伴津津乐道的话题，每一场面试的过程以及考题，都是大家茶余饭后的焦点。

今天力扣君分享一个之前在面试大厂过程中，面试官出的几道技术面试题，供大家品鉴～

面经自述

面试企业：哔哩哔哩

简历响应时间：1 天

面试题目数：3 题

除去 3 道编程题，其他都是选择题：SQL，二叉树。编程第一道相当于是送分题，后面两道题都是二叉树，感觉 B 站偏爱二叉树，和其他公司笔试感觉不一样的是，B 站用的是和力扣一样的核心代码模式；这一点，感觉做起来很舒服。

题目概述

题目一：

给定一个二叉树根节点 root，每个节点都有一个权值，你最多可以将某个节点与其父节点交换一次。每一层节点的权值之和看作该层的权值和，取这些权值和最大的一个，问最大能达到多少？

分析：

很明显考的是层序遍历，考虑一个点: 交换节点有几种情况、交换后对某一层的权值和的贡献最大能达到多少。就可以解决了。

题目二：

给你一个二叉搜索树根节点 root，按照从下往上的顺序遍历这棵树，如果以 node 为根节点的子树不是二叉平衡树(左右子树高度相差大于 1)，则删除距离节点 node 最近的那棵子树。

要求：被删除的那棵树也必须是平衡二叉树，且成为一棵新的树。

继续在原树上进行删除操作，直到所有的子树都是平衡二叉树。并要求对删除后的所有子树根节点按照节点数量从小到大排序，节点数量相同的按照根节点值从小到大排序。

分析：

利用 DFS 可以很轻松的获取到左右子树的高度，重点是：先删除高度更大的那棵子树、可能需要对一棵子树进行两次删除操作。

题目还给了例图，不然会很蒙圈，重现一下：

例如给定这棵树：

首先，发现以 3 为根节点的子树不平衡，可以删除节点 5， 4 中的任意一个节点来达到平衡，但是题目规则要求是距离节点 3 最近的子树，因此会删除以 5 为根节点的子树。

得到如下的结果：

附上代码：

public class Solution {
  
  class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
  }
  
  // 用于保存节点记录
  class Record{
    TreeNode node;
    int nodeCount;
    public Record(TreeNode node, int nodeCount) {
      this.node = node;
      this.nodeCount = nodeCount;
    }
  }


  List<Record> records;
  
  int nodes;


  public TreeNode[] delete(TreeNode root) {
    if (root == null) {
      return null;
    }
    records = new ArrayList<>();
    nodes = 0;
    dfs(root, 0);
    records.add(new Record(root, nodes));
    
    Collections.sort(records, new Comparator<Record>() {
      @Override
      public int compare(Record o1, Record o2) {
        int dif = o1.nodeCount - o2.nodeCount;
        if (dif != 0) {
          return dif;  
        }
        return o1.node.val - o2.node.val;
      }
    });
    TreeNode[] res = new TreeNode[records.size()];
    int i = 0;
    for (Record record : records) {
      res[i++] = record.node;
    }
    return res;
  }


  private int dfs(TreeNode root) {
    TreeNode left = root.left;
    TreeNode right = root.right;
    int leftDep = left != null ? dfs(left) : 0;
    int leftNodeCount = nodes;
    nodes = 0;
    int rightDep = right != null ? dfs(right) : 0;
    int rightNodeCount = nodes;
    
    int dif;
    while ((Math.abs((dif = leftDep - rightDep))) > 1) {
      // 删除一棵子树时, 更新该子树的高度, 并清除节点计数
      if (dif > 1) {
        records.add(new Record(left, leftNodeCount));
        leftNodeCount = 0;
        leftDep = 0;
        root.left = null;
      } else {
        records.add(new Record(right, rightNodeCount));
        rightNodeCount = 0;
        rightDep = 0;
        root.right = null;
      }
    }
    // 每次递归, 利用 nodes 保存当前节点计数
    nodes = leftNodeCount + rightNodeCount + 1;
    return Math.max(leftDep, rightDep) + 1;
  }
}

写在最后：

能进一线互联网大厂工作，也是每个程序员生涯的梦想，为的不仅仅是大厂的种种福利、工作环境和高薪，更为的是大厂的工作氛围，能加入到大牛的圈子，能跟众多大牛一起交流学习，对技术的提升进阶，也为了从大厂出来后的工作履历可以给日后的生涯走向提供更多的选择。也恭喜这位同学上分成功～

如果大家也有面试经历，不妨分享分享，评论留言少 BUG ！点赞转发不脱发！