饿了么二面

面试题目

2016.05.24

擦！把自己美团二面的给不小心删掉了 wtf!
饿了么一面总体上自我感觉还行，大部分题目是可以答得上，也幸运地进入到了二面当中，在二面来临之前，我是不知道二面面试官是什么个尿性的，下午正在睡着午觉呢，突然面试官就打了一个电话过来，把我吓醒了，说加一下微信，wtf，怎么又是微信的方式来进行面试啊。好吧，进入面试内容。

面试官说，有三道题目，每道题目限时10分钟

Question 1

有一个多维数组，需要转换成一维数组。

注意：题目的答题时间是5-10分钟。如果超过10分钟没有完成，请停止答题，提交表单。

答题代码：
var a = [1, [2, [3, 4]], 5, [6]];

var flatten = function(array) {
// 你需要补充的代码
}

console.log(flatten(a)); // 输出 [1, 2, 3, 4, 5, 6]

这题的话，一开始思考就是可以用递归的方式去解决，就是去不断的判断是否为 数组类型，是的话，就递归处理，我的代码具体如下

var a = [1, [2, [3, 4]], 5, [6]];
var result = [];
var flatten = function(arr) {
    arr.forEach(function(item) {
        if (item instanceof Array) {
            flatten(item);
        } else {
            result.push(item);
        }
    })
    return result;
}
console.log(flatten(a));

问：然后，写完之后，面试官问我，如果flatten执行两次，会出问题吧？该如何解决

的确，result设置为了 全局变量，flatten执行两边之后，由于result没有清空的话，会一直加在result 的后面

我一开始的解决方案是说把result放在 function当中，结果too young too simple，果然是要思考完毕再做相关的回答会比较好，因为没有注意到我是用递归的方式来实现的，如果把result都放在funcrion当中，那么每次result都会被清空，最后是得不到正确答案的。

后来面试官问我解决方法，我自己想了想，这个问题主要是有一个全局变量很蛋疼，那么关键就是不要使用到全局变量，然后每次又可以使用的时候清空，道理是懂的，就是每次传给flatten函数的数组为 空数组，那么我的思路如下

var a = [1, [2, [3, 4]], 5, [6]];
var f = function(arr, result) {
    arr.forEach(function(item) {
        if (item instanceof Array) {
            f(item, result);
        } else {
            result.push(item);
        }
    })
    return result;
}
var flatten = function(arr) {
    return f(arr, []);
}
console.log(flatten(a));

Question 2

好吧，第一题也就这么过去了，没有问特别，然后直接又扔了第二题的链接给我，题目如下

将 1-1000 放在一个含有 1001 个元素的数组中，只有唯一的一个元素重复，其他均出现一次。

请把这个重复的元素找出来，要求所有的元素只能访问一次，空间复杂度 O(1)。

如果无法理解O(1)的空间复杂度，做一个简单的解释：
    只能使用常量个空间，使用的空间不能和数组的长度有关系，比如如果使用另外一个长度和给定数组长度一样的数组，则空间复杂度是 O(n)。

注意：题目的答题时间是5-10分钟。如果超过10分钟没有完成，请停止答题，提交表单。

使用下面的代码开始答题：

// 这个方法生成了1001个元素的数组，只有一个元素是重复的。
var getArray = function() {
    var count = 1000;
    var array = [];

    for (var i = 1; i <= count; i++) {
        array.push(i);
    }

    var special = Math.floor(Math.random() * (count + 1));
    array.push(special);
    console.log('重复数字为：' + special);

    return array.sort(function() {
        return Math.random() - 0.5;
    });
};

var findNumber = function(array) {
    //你要实现的代码写在这里。
};

console.log('找到的重复数字为：' + findNumber(getArray()));

这种题目的话，首先是要理清思路，因为规定了空间复杂度为 O(1)，那么，因为以前有印象就是找出偶数个的，使用 异或 的方式，所以这题应该也是差不多的方式，我的大致思路是这样的，假设没有重复元素，那么在一个for循环后，得到异或结果是 a^b，现在是因为插入了一个重复的元素，假设重复元素是 b，那么，第一遍异或的结果就应该为 a^b^b，现在第二遍异或，第二遍异或，应当除重复元素，得到一个 a^b写的结果，再将结果与第一次循环的结果进行异或，即 (a^b^b)^(a^b) = b，通过这种方式，就可以获得重复的值

// 这个方法生成了1001个元素的数组，只有一个元素是重复的。
var getArray = function() {
    var count = 1000;
    var array = [];
    for (var i = 1; i <= count; i++) {
        array.push(i);
    }
    var special = Math.floor(Math.random() * (count + 1));
    array.push(special);
    console.log('重复数字为：' + special);
    return array.sort(function() {
        return Math.random() - 0.5;
    });
};
var findNumber = function(array) {
    //你要实现的代码写在这里。
    // 采取异或，只有一个重复的疑惑会为0
    var result = 0;
    for (var i = 0, len = array.length; i < len; i++) {
        result ^= array[i];
    }
    for (var j = 1, l = array.length; j < l; j++) {
        result ^= j;
    }
    return result;
};
console.log('找到的重复数字为：' + findNumber(getArray()));

Question 3
第三个问题，我到现在都还不知道要怎么解决，当时在面试的时候，没有想出要要怎么进行解决，想了十分钟，没有思路，先来看一下题目吧

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

如果你没有思路同时满足O(n)和O(1)，请满足空间复杂度O(1)的条件，只满足时间复杂度  O(n) 不得分。

如果无法理解时间复杂度和空间复杂度，做一个简单的解释：
1. O(n)的意思是只能对数组做单层 for 循环，可以进行多次。
2. O(1)的意思是只能使用常量个空间，使用的空间不能和数组的长度有关系，比如如果使用另外一个长度和给定数组长度一样的数组，则空间复杂度是 O(n)。

注意：题目的答题时间是5-10分钟。如果超过10分钟没有完成，请停止答题，提交表单。

使用下面的代码开始答题：
var a = ['*', 'd', 'c', '*', 'e', '*', 'a', '*'];

var sort = function(array) {
//请补充此处代码
};

console.log(sort(a));// 应该返回['*', '*', '*' ,'*', 'd', 'c', 'e', 'a']

的确是没有什么思路啊，不过我的想法是，使用排序的思想，将*号看作是最小的，其他都不改变，但是暂时也是没有想到到底要怎么去解决，等待解决ing......

目前想到了一种做法，就是如下

var a = ['*', 'd', 'c', '*', 'e', '*', 'a', '*'];
var sort = function(arr) {
    var result = arr.join('').replace(/\*/gi, '');
    for (var i = 0, l = arr.length - result.length; i < l; i++) {
        result = '*' + result;
    }
    return result.split('');
}
console.log(sort(a))