Seeker

同样是一道面试题，来自有道前端的面试。

写一个函数处理大数据的相加问题，所谓的大数据是指超出了整型，长整型之类的常规数据类型表示范围的数据。实现语言不限。

我是用js实现的，说一下我自己的思路：

1、首先这个题目最重要的环节在考虑怎么存储大数据？用什么数据类型保存呢？最简单可行的方式是String
2、确定了使用何种类型保存数据之后这个题目就明朗了。首先判断两个传入字符串的长度，取最短的len循环，两者从低位开始对应位相加，同时注意保存进位。在短的数据处理完后，将进位交给较长串的剩余部分处理。

详细实现看一下代码，完整实例见jsfiddle

var strAdd = function(srcA, srcB) {
    var i, temp, tempA, tempB, len, lenA, lenB, carry = 0;
    var res = [],
        arrA = [],
        arrB = [],
        cloneArr = [];
    arrA = srcA.split('');
    arrB = srcB.split('');
    arrA.reverse();
    arrB.reverse();
    lenA = arrA.length;
    lenB = arrB.length;
    len = lenA > lenB ? lenB : lenA;
    for (i = 0; i < len; i++) {
        tempA = parseInt(arrA[i], 10);
        tempB = parseInt(arrB[i], 10);
        temp = tempA + tempB + carry;
        if (temp > 9) {
            res.push(temp - 10);
            carry = 1;
        } else {
            res.push(temp);
            carry = 0;
        }
    }
    cloneArr = lenA > lenB ? arrA : arrB;
    for (; i < cloneArr.length; i++) {
        tempA = parseInt(cloneArr[i], 10);
        temp = tempA + carry;
        if (temp > 9) {
            res.push(temp - 10);
            carry = 1;
        } else {
            res.push(temp);
            carry = 0;
        }
    }
    return (res.reverse()).join('');
};

以上。

PS：其实吧，这个面试题被我改编了下，原始的面试题主考官提示了用字符串保存大数据的，这个其实降低难度了~~
//===============================================

百度面试时问的一道题目，蛮常规的，但是当时自己的回答挺差劲的。现在总结记录下~

题目：要求写一个函数，去掉给定数组中的重复值。
如：
传入数组 a = [0, 8, 5, 4, 78, 8, 90, 4, 'a', 'b', 'a'];
要求返回：[0,4,5,8,78,90,a,b]

对于这个题目，在面试之后也想了好多次，不过一直没能想出一个时间复杂度较低的方法。昨天下午在宿舍看《JavaScript语言精粹》看到一个书中的一段代码有所触发，于是在jsfiddle上测试了，成功。代码如下(完整版参见jsfiddle)

var getNR = function(src) {
    src = src || [];
    var res = {};
    var curr = [];
    var i, j = 0,temp, name;
    for (i = 0; i < src.length; i++) {
        temp = src[i];
        if (res[temp]) {
            //do noting
        } else {
            res[temp] = 1;
        }
    }
    for (name in res) {
        if (res.hasOwnProperty(name)) {
            curr[j++] = name;
        }
    }
    return curr;
};

总结一下我的思路：

思路一：将目标数组进行排序，然后依序删除重复的数组，但这样在删除重复元素的同时也改变数组原有元素的属性，明显是不符合要求的，del。
思路二：新建一个数组b，将a中的元素push到b中，但是在push之前检查该元素是否存在。这个时间复杂度是n*n,最简单也是最笨的办法。
思路三：跟思路二类似，不过充分利用了js对象的属性，新建一个空对象，将a中的元素作为属性添加到该对象中，在添加之前检测该属性是否已存在。全部添加完后将该对象的属性依序放到数组中，return

美团面试的题目中有一道这个题目的变种：

要求在Array类上添加一个方法，对于任意数组调用该方法后，去除该数组中的重复元素。

这个变种题考查的知识点多了些，还包括原型，this的理解等。

//===============================================

去某公司（公司名不说了，人这套题说不定还要用）面试，现场30分钟做了一套题，其中有一道是这样的：

要求用js写一个函数，对传入的形如下网址字符串，返回对应的对象。
如：
若传入字符串a=’?name=zhiyelee&blog=www.tsnrose.com’;
则返回 b={‘name’:'zhiyelee’,'blog’:'www.tsnrose.com’}

当时由于时间比较短，实现的有些问题，回来后想了一下，总结如下：
我想到了两种思路，一种是使用正则表达式，第二种是使用字符串的split函数。

1、使用正则表达式处理

我首先想到的是使用正则表达式处理，可能是感觉这个更有挑战性写起来也最简洁，不过当时怀疑这种方法的效率会低于直接使用字符串函数处理的效率。这个效率我们在下文会验证~
这个方法的思路很简单，就是使用正则表达式每次匹配出一个‘***=###’串，然后循环最后取出所有。
代码如下

var getNRReg = function(str) {
    var res = {};
    var reg = /(\w+)=(\w+)/g;
    while ((a = reg.exec(str))) {
        res[a[1]] = a[2];
    }
    return res;
};

2、使用字符串函数处理

这种想法思路也比较常规，不过写起来肯定要比使用正则表达式处理麻烦一些。
我的思路首先用‘&’将原串分割成多个字串，每个字串的样式如‘***=###’，然后再对字串应用split(‘=’)。（此种方法没有使用正则，当然我们可以使用正则split(/&|=/)
代码如下

var getNRSplit = function(str) {
    var temp, res = {},
        i, ret;
    str = str.slice(1);
    temp = str.split('&');
    for (i = 0; i < temp.length; i++) {
        ret = temp[i].split('=');
        res[ret[0]] = ret[1];
    }
    return res;
}

这两种方法的效率问题

众所周知正则表达式的效率有点低，因此最初认为第一种方案的效率肯定要低于第二种方案的效率，于是实测了下，结果不然：

执行1000000次的耗时情况：
getNRReg执行耗时 4399ms
getNRSplit执行耗时 6116ms

完整源代码查看： jsfiddle ，可以自行测试~

update: 2011-08-05 10:10
----------
感谢 @simon4545 提供的思路，效率比上面的两种都要高。split确实也很消耗性能的，直接substring会更好。
这个一直没重新整理，最近项目中用到，顺便整理贴出来。

var getUrlData = function(){
	var srcUrl = window.location.search;
	var searchStr = decodeURIComponent(srcUrl.substr(1));
	var temp = searchStr.split('&');
	var len = temp.length;
	var index,argName,argValue,currArg,retArr = {};
	for (var i = 0 ; i < len ;i++){
		currArg = temp[i];
		index = currArg.indexOf('=');
		if(index > 0){
			argName = currArg.substring(0,index);
			argValue = currArg.substring(index+1);
			retArr[argName] = argValue;

		}else{
			return -1;
		}
		return retArr;
	}

};

ps:
最后附上新浪微博2011-06-15 在北邮宣讲会前端岗位的一道笔试题：

用正则表达式完成删除与某个字符相邻且相同的字符，比如“fdaffdaaklfjk”字符串处理之后成为“fdafdakljk”。

我的答案见 jsfiddle
//===============================================