2016-10-26

关于前端常见算法面试题的一些思考

今天上班时间,读了 @JackPu 的新文章《前端面试中的常见的算法问题》。内容虽然看起挺基础,但可以有不少思考,同时也是一次挺好的复习。

其中,有几个问题,想出了一些不同的解决办法,做了下笔记,并且进行了简单的性能测试。关于排序,这次没有深看。接下来有空时,再研究一番。

判断回文(Palindromic Words)

结果是,使用循环来判断,性能远高于数组方法。接下来,在其他一些例子中也能看到,借用数组方法,往往很耗性能。

数组去重

ES 5 方法性能更好,高一倍以上。不过笔试、面试时,附上 的办法,肯定会更好。

统计一个字符串出现最多的字母

正则表达式的办法,临时想起来的,运行起来还是要慢,至少慢了一半。所以有时候还是要老老实实写代码,奇淫巧技少用。

不借助临时变量,进行两个整数的交换

三种方式均可。没有做性能测试。

斐波那契数列

联想到了三种方式:动态规划;尾递归;generator(算不上一个解决方案,只是临时想到的)。

上述三种方式中,动态规划最快,计算 fib(1000) 20000 次耗时 170 ms;尾递归耗时 200 ms 左右,generator 耗时 2800 ms 左右。

正数组的最大差值

出乎意料地,这次 Math 方法竟然败给看 for 循环。不用说,reduce 超级慢,比 Math 还慢近十倍。

声明:Math 只是在本案例中比 for 循环慢,实际上如果只是单独取数组中的最大值或最小值,Math 还是很厉害的。实测:随机生成一个长度为 20 的数组(100 以内的正整数),寻找最大值,运行 10^6 次,Math 完胜,不到 1s 搞定,for 循环直接卡死。所以还是得看具体情况。

对算法的了解还十分浅薄,错误肯定有,希望读者指教。还需要钻研更多。感谢 @JackPu 的文章带来的启发和思考。

补注:
本文在描述测试结果会进行一些对比,也会使用一些“失败”“不如”等字眼,但测试比较主要是满足好奇心。实际工作中,多数人应该不会碰到那么大的计算量,因此几乎不用担心(多数情况下),多关注其他方面的优化吧。
另外,请不要对某些说法(正数组的差值例子中所说 Math 败给 for 循环)产生刻板印象(我自己就是,这次之后总感觉 Math 是不是不给力。被自己误会到了囧),具体情况具体分析,另外,多操作,多做实验。
如果本文一些不严谨的说法给您的学习、工作造成负面影响,还请谅解。如有问题,欢迎随时和我联系。