前端内参
搜索文档…
贰.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 本篇结语

由此可见,在一线互联网公司面试,碰到数据结构和算法这块儿的面试题是避免不了的,而且考的是触类旁通,题目都是基础数据结构和算法的变体,所以更要扎扎实实把最常见的数据结构和算法题研究熟悉,你一定可以顺利通过技术面试。
最近更新 1yr ago