贰.1.5 实战：字节跳动前端面试2道算法题

笔者在写作本书期间，曾经受邀参加字节跳动北京地区的“WEB前端高级工程师”岗位的面试。面试官是一位前端小姐姐，女程序员在其他公司很少见，所以觉得字节跳动的极客文化很有特色。一番流程性的自我介绍之后，小姐姐提了两道笔试算法题。
贰.1.5.1 多维数组扁平化
题目
原数组[[0],[2,3,4],1,[1,[2,3]]]，写一段代码，将该数组扁平化，输出[0,2,3,4,1,1,2,3]
分析
如果读过本书壹.1.1 新版 ECMAScript 特性分析，就会发现 ES10 最新的特性Array.prototype.flat()可以完美解题，但是考虑到这个新特性是2019年（面试时）才出来不久，很多浏览器没有支持这个特性，所以也要考虑用原生JavaScript代码来实现这个扁平化数组的功能。
既然是处理数组，那就要熟悉JavaScript数组对象的各种方法，并恰当的利用它们来实现我们的目的。
解法一
请认真阅读注释，很多关键性提示都在注释里面详细指出了。
1
(() => {
2
    //题目中给的测试数据
3
    let sourceArr = [[0], [2, 3, 4], 1, [1, [2, 3]]];
4
    //结果数组，用来保存最终输出的数据
5
    let resultArr = [];
6
​
7
    (function doFunc(arr) {
8
        //若无子数组，直接把arr的数据导入结果数组resultArr
9
        if (!hasChildArray(arr)) {
10
            //用concat方法，将resultArr与arr合并后再返回给resultArr
11
            resultArr = resultArr.concat(arr);
12
        }
13
        //若有子数组
14
        else {            
15
            for (let i = 0, l = arr.length; i < l; i++) {
16
                //如果子元素类型是数字
17
                if (typeof arr[i] == "number") {
18
                    resultArr.push(arr[i]); //放入结果数组中保存起来
19
                }
20
                //否则，如果子元素类型是数组
21
                else if (Array.isArray(arr[i])) {
22
                    doFunc(arr[i]); //递归调用
23
                }
24
            }
25
        }
26
    })(sourceArr);
27
​
28
    console.log(resultArr); //>> [0, 2, 3, 4, 1, 1, 2, 3]
29
​
30
    /**
31
     * 定义一个工具性子函数，判断参数中传来的数组是否有子数组
32
     * @param   {Array}   数组
33
     * @return  {Boolean} true:有;false:没有
34
     */
35
    function hasChildArray(arr) {
36
        /*
37
        arr.some() 方法测试数组arr中是不是有元素通过了被提供的函数callback
38
        的测试。它返回的是一个Boolean类型的值。只要数组中有元素通过callback的
39
        测试就会返回true；所有元素都没有通过callback的测试，返回值才会为false。
40
        */
41
        return arr.some(function callback(item) {
42
            //判断arr中的子元素item是否数组
43
            if (Array.isArray(item)) {
44
                return true; //返回true表明通过了测试，让外层some也返回true
45
            }
46
        });
47
    }
48
})();
Copied!
解法二
这个解法是后来补充的，面试时并没有想出来，后来觉得挺简洁的，所以分享出来。
1
(() => {
2
    //题目中给的测试数据
3
    let sourceArr = [[0], [2, 3, 4], 1, [1, [2, 3]]];
4
    //结果数组，用来保存最终输出的数据
5
    let resultArr;
6
​
7
    (function doFunc(arr) {
8
        resultArr = arr.toString().split(",");//利用toString和split取巧得到扁平数组
9
        resultArr = resultArr.map(item=>Number(item));//将数组项由字符串转换为数字
10
    })(sourceArr);
11
})();
Copied!
贰.1.5.2 二叉树&完整路径和
经过上面的数组算法题热身之后，小姐姐比较满意，还想继续验证一下笔者在数据结构和算法这块儿的基本功，于是喝了一口茶之后，她紧接着出了一个更开放性的、二叉树有关的题。
题目
对于给定的二叉树，判断是否存在一条完整路径（从根节点开始，到叶节点结束的连线），其路径上节点的值之和为target，输出布尔值。举例：下面的树，是否存在一条完整路径，该路径上各个节点之和target=7？
1
      6
2
    /   \
3
   2     3
4
  /\    /
5
-1  3  0
Copied!
分析
这个题目出得确实很开放，如果对树、二叉树的概念不熟悉，会有点无从下手，好在我们已经经过二叉树相关的学习训练了。开放性命题需要做一些假设，把前提条件确定了，才能解题。先确定树、结点的数据结构，有什么样的数据结构，就有后面什么样的算法。二叉树的遍历，离不开递归。
解法一
笔者多年的OOP经（毒）验（素）派上用场了，首先就会想到用两个类定义树和结点，然后写一个递归遍历树，代码如下：
1
(() => {
2
  //定义结点的数据结构
3
  class Node {
4
    /**
5
     * 构造函数
6
     * @param {Number}  value   当前结点的值
7
     * @param {Node}    left    当前结点的左子结点
8
     * @param {Node}    right   当前结点的右子结点
9
     */
10
    constructor(value, left, right) {
11
      this.value = value;
12
      this.left = left;
13
      this.right = right;
14
    }
15
  }
16
  //定义二叉树的数据结构
17
  class BTree {
18
    /**
19
     * 构造函数
20
     */
21
    constructor() {
22
      //结点列表，存放所有结点
23
      this.list = [];
24
    }
25
    /**
26
     * 添加根结点
27
     * @param {Node} node 被添加的结点
28
     */
29
    addRoot(node) {
30
      if (node != null) {
31
        this.list.push(node);
32
      }
33
    }
34
    /**
35
     * 添加子结点
36
     * @param {Node}    pNode  父结点
37
     * @param {Node}    node   当前结点
38
     * @param {Boolean} isLeft 是否左侧添加，如果为false则是右侧添加
39
     */
40
    addChildNode(pNode, node, isLeft) {
41
      this.list.push(node);
42
      if (isLeft) {
43
        pNode.left = node;
44
      } else {
45
        pNode.right = node;
46
      }
47
    }
48
    /**
49
     * 根据数组中的索引(下标）返回node
50
     * @param {Number} index 索引(下标）
51
     */
52
    getNode(index) {
53
      return this.list[index];
54
    }
55
  }
56
​
57
  //创建示例中的二叉树
58
  let bTree = new BTree();
59
  //第一层 根结点
60
  bTree.addRoot(new Node(6, null, null));
61
  //第二层
62
  bTree.addChildNode(bTree.getNode(0), new Node(2, null, null), true);
63
  bTree.addChildNode(bTree.getNode(0), new Node(3, null, null), false);
64
  //第三层
65
  bTree.addChildNode(bTree.getNode(1), new Node(-1, null, null), true);
66
  bTree.addChildNode(bTree.getNode(1), new Node(3, null, null), false);
67
  bTree.addChildNode(bTree.getNode(2), new Node(0, null, null), true);
68
​
69
  /**
70
   * 主逻辑函数
71
   * @param {Node}    node    树的结点
72
   * @param {Number}  target  题目要求的目标值
73
   */
74
  function hasPathSum(node, target) {
75
    //若根节点无子结点
76
    if (!node.left && !node.right) {
77
      //直接判断根结点额值是否等于target
78
      return node.value == target;
79
    } 
80
    //若有子结点
81
    else {
82
      //如有左结点 左侧递归
83
      if (!!node.left)
84
          return hasPathSum(node.left, /*关键*/ target - node.value);
85
      //如有右结点 右侧递归
86
      if (!!node.right)
87
          return hasPathSum(node.right, /*关键*/ target - node.value);
88
    }
89
  }
90
​
91
  console.log(hasPathSum(bTree.getNode(0), 7)); //>> true
92
})();
Copied!
看到笔者很快交出了答案，面试官小姐姐嘴角露出了一丝微笑。经过大概1分钟的review之后，她说：“二叉树BTree和结点Node本质上可以是相同的数据结构的，根结点其实就可以代表一棵树了，你可仔细想想。你的答题虽然实现了目的，但是不需要定义2个类来分别放树和结点，能否精简一下呢？”
的确，她说的对，完全可以精简。如果要求树和结点的数据结构一样，那可以考虑用数组的形式来表示它们，用多维数组来代表一颗二叉树即可，于是有了第二种解法。
解法二
1
(() => {
2
  //用多维数组代表题中示例的树，这个数组是按“前序遍历”后排序
3
  let arrSouce = [6, [2, [-1], [3]], [3, [0]]];
4
​
5
  /**
6
   * 定义二叉树的结点。根结点和树的数据结构一样，
7
   * 因此只需要定义一个结点(Node)的数据结构即可
8
   */
9
  class Node {
10
    /**
11
     * 构造函数
12
     * @param {Number}  value 当前结点的值
13
     * @param {Node}    left  左子结点
14
     * @param {Node}    right 右子结点
15
     */
16
    constructor(value, left, right) {
17
      if (value != undefined) {
18
        this.value = value;
19
        if (left != undefined) this.left = left;
20
        if (right != undefined) this.right = right;
21
      }
22
    }
23
  }
24
​
25
  /**
26
   * 创建一个树
27
   * @param {Array} arr 一个代表二叉树的多维数组
28
   */
29
  function makeBTree(arr) {
30
    if (arr) {
31
      if (arr.length == 1) {
32
        return new Node(arr[0]);
33
      }
34
      //递归，创建二叉树
35
      return new Node(arr[0], makeBTree(arr[1]), makeBTree(arr[2]));
36
    }
37
  }
38
​
39
  //创建示例中的二叉树，简洁多了！
40
  let bTree = makeBTree(arrSouce);
41
​
42
  /**
43
   * 主逻辑函数，与第一种解法里代码一样
44
   * @param {Node}    node    树的结点
45
   * @param {Number}  target  题目要求的目标值
46
   */
47
  function hasPathSum(node, target) {
48
    //若根节点无子结点
49
    if (!node.left && !node.right) {
50
      //直接判断根结点额值是否等于target
51
      return node.value == target;
52
    } 
53
    //若有子结点
54
    else {
55
      //如有左结点 左侧递归
56
      if (!!node.left)
57
          return hasPathSum(node.left, /*关键*/ target - node.value);
58
      //如有右结点 右侧递归
59
      if (!!node.right)
60
          return hasPathSum(node.right, /*关键*/ target - node.value);
61
    }
62
  }
63
​
64
  console.log(hasPathSum(bTree, 7)); //>> true
65
})();
Copied!
面试官小姐姐很满意，在填写面试评估的那一栏里写下了“通过技术面试”。
贰.1.5.3 本篇结语
由此可见，在一线互联网公司面试，碰到数据结构和算法这块儿的面试题是避免不了的，而且考的是触类旁通，题目都是基础数据结构和算法的变体，所以更要扎扎实实把最常见的数据结构和算法题研究熟悉，你一定可以顺利通过技术面试。
​

贰、数据结构与算法 - 以前

贰.1.4 二叉树的遍历

下一个 - 贰、数据结构与算法

贰.1.6 分治法、动态规划与贪心算法的区别

最近更新 1yr ago

复制链接

内容