两道面试题

题目一

有一个数组,里面只存在 * 和 字母,比如 [‘*‘, ‘d’, ‘c’, ‘*‘, ‘e’, ‘*‘, ‘a’, ‘*‘]。现在需要把这个数组中的所有星号移动到左边,所有的字母移动到右边,所有字母的顺序不能改变。要求时间复杂度是 O(n),空间复杂度是 O(1)。

简化成代码模型,如下

1
2
3
4
5
6
7
8
9
var arr = ['*', 'd', 'c', '*', 'e', '*', 'a', '*'];

function parse(arr){
...
}

console.log(parse(arr));
// 期望结果
// [ '*', '*', '*', '*', 'd', 'c', 'e', 'a' ]

当时第一反应是,遍历 arr 数组得到 * 的个数 counter,并同时删除 *,最后在数组前面插入 counter 数量的 *,代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function parse(arr){
var counter = 0;
for(var i = 0; i < arr.length; i++){
if(arr[i] == '*'){
arr.splice(i, 1);
counter++;
i--;
}
}
while(counter > 0){
arr.unshift('*');
counter--;
}
return arr;
}

当时觉得这样是满足要求的,然而面试官说,spliceunshift 操作的时间复杂度是 O(n),后来又换个思路,重新实现了一遍,代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
function parse(arr){
var str = arr.join(''),
counter = 0;
str = str.replace(/\*/g, function(){
counter++;
return '';
})
while(counter > 0){
str = '*' + str;
counter--;
}
return str.split('');
}

题目二

假设有一个 10 人小组要出去 teambuilding,想随机均匀地分成 4 队,怎样实现?

简化成代码模型,如下

1
2
3
4
5
6
7
8
9
10
var arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var group = [[], [], [], []];

function parse(arr, group){
...
}

console.log(parse(arr, group));
// 期望结果
// [ [ 2, 7, 4 ], [ 0, 3, 1 ], [ 9, 6 ], [ 8, 5 ] ]

刚看到题目,没有细想,就用了一种比较复杂的办法实现:求出每组人数平均值(整数部分),在每个分组里放入这个数量的人(随机取出),剩余的人数再间隔地放入每个分组(按奇偶),代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function parse(arr, group){
var gLen = group.length,
eLen = Math.floor(arr.length / gLen);
for(var i = 0; i < gLen; i++){
for(var j = 0; j < eLen; j++){
var index = Math.floor(Math.random() * arr.length),
n = arr.splice(index, 1)[0];
group[i].push(n);
}
}
for(var i = 0; i < gLen && arr.length; i++){
if(i % 2 == 0){
var index = Math.floor(Math.random() * arr.length),
n = arr.splice(index, 1)[0];
group[i].push(n);
}
}
return group;
}

后来 sofish 说,其实不用这么麻烦的,你只要把每个分组想象成一个圈,往里面放人就行了。后来一想,确实,只要对所有人进行遍历就行了,代码如下

1
2
3
4
5
6
7
8
9
10
function parse(arr, group){
var aLen = arr.length,
gLen = group.length;
for(var i = 0; i < aLen; i++){
var index = Math.floor(Math.random() * arr.length),
n = arr.splice(index, 1)[0];
group[i % gLen].push(n);
}
return group;
}

这样下来,代码减少一半,复杂度降低一半。其实有时候就是多花两分钟思考的事,给我的教训就是,以后要多思考,而不是上来就写。

坚持原创技术分享,您的支持将鼓励我继续创作!