2018年6月前端面试经历(中)

12,952 阅读5分钟

前言

上一篇文章,写了一些出去面试会考到的笔试题,不是很全(哈哈哈,基本上都是靠脑子记的,有些都忘记了~)

传送门在这里:2018年6月前端面试经历(上)~~~

这篇我会写出一些我碰到的算法题,解法不统一,希望大家能多多的提供自己的想法和代码~

算法题

1)快速排序

思路:
- 随机选择数组中的一个数 A,以这个数为基准
- 其他数字跟这个数进行比较,比这个数小的放在其左边,大的放到其右边
- 经过一次循环之后,A 左边为小于 A 的,右边为大于 A 的
- 这时候将左边和右边的数再递归上面的过程

const Arr = [85, 24, 63, 45, 17, 31, 96, 50];
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1)[0];
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    // 递归
    return quickSort(left).concat([pivot], quickSort(right));
}

console.log(quickSort(Arr));

ps:
这是阮老师的一个快排写法,网上对于这个的争论很多,第一说了阮老师不应该用splice去取值,应该用下标,还有就是不应该每次都从新开俩个新数组。
其实我觉得算法题重要的是思路,实现的方式有很多,不一定说谁对谁错,效率越好的算法的确是我们想要的,但是更多的理解一些不同的实现思路,我觉得也是可以的~。

这里是不同的声音: 面试官:阮一峰版的快速排序完全是错的

2)二分排序法

二分查找法主要是解决「在一堆有序的数中找出指定的数」这类问题,不管这些数是一维数组还是多维数组,只要有序,就可以用二分查找来优化。

二分查找是一种「分治」思想的算法,大概流程如下:

  • 数组中排在中间的数字 A,与要找的数字比较大小
  • 因为数组是有序的,所以: a) A 较大则说明要查找的数字应该从前半部分查找 b) A
  • 较小则说明应该从查找数字的后半部分查找
  • 这样不断查找缩小数量级(扔掉一半数据),直到找完数组为止
题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

function Find(target, array) {
    let i = 0;
    let j = array[i].length - 1;
    while (i < array.length && j >= 0) {
        if (array[i][j] < target) {
            i++;
        } else if (array[i][j] > target) {
            j--;
        } else {
            return true;
        }
    }
    return false;
}

//测试用例
console.log(Find(10, [
    [1, 2, 3, 4], 
    [5, 9, 10, 11], 
    [13, 20, 21, 23]
    ])
);

3)解析url后的参数

function parseParam(url) {
  let obj = {};
  let arr = url.split("?");
  if (arr.length == 1) { //判断没有问号
    return "无参数"
  }
  let total = arr[1].split("&");
  for (let i = 0; i < total.length; i++) {
    let single = total[i].split("=");
    if (single[0] == '') { //判断有?但是没有参数
      return '无参数'
    }
    if (!single[1]) {
      obj[single[0]] = true;
    } else {
      if (obj[single[0]]) {
        let concat
        if (!Array.isArray(obj[single[0]])) { //判断是否数组
          concat = [obj[single[0]]]
        } else {
          concat = obj[single[0]];
        }
        concat.push(single[1]);
        concat = new Set(concat);
        concat = Array.from(concat) //数组去重
        obj[single[0]] = concat
      } else {
        obj[single[0]] = decodeURI(single[1]) //进行转码
      }
    }
  }
  return obj
}

var url = 'http://www.baidu.com/?user=huixin&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled';

var params = parseParam(url)

console.log(params)

4)实现一个简单的模版引擎:

列:我叫a,年龄b,性别c; let data = { name: '小明', age: 18, } 没有定义的返回undefined


let template = '我是{name},年龄{age},性别{sex}';
    let data = {
        name: '小明',
        age: 18,
    }
    const  reg= /({([a-zA-Z]+)})/g;
    var r= '',regrounp={};
    while( r = reg.exec(template) ){
        Object.defineProperty(regrounp,r[2],{
            enumerable:true,
            value:r[2]
        })
    }

    var render = (template,regrounp)=>{
        var result='';
        for( key in regrounp){
            if(data[key] == undefined){
                result  = (result || template).replace(new RegExp(`{${regrounp[key]}}`,"g"),undefined);
            }else{		
                result  = (result || template).replace(new RegExp(`{${regrounp[key]}}`,"g"),data[key]);
            }
        }
        return result
    }
    let newtemple = render(template, regrounp);
    console.log(newtemple) // 结果: 我是小明,年龄18,性别undefined
  

这里不试不知道,{}这样声明的对象,可以直接枚举,Object.defineProperty声明出的对象,如果不定义enumerable:true的话,是不能用for-in 枚举的。

这里有一片很好的文章 推荐 编写一个简单的JavaScript模板引擎

5)如何快速让字符串变成已千为精度的数字

function exchange(num) {
    num += ''; //转成字符串
    if (num.length <= 3) {
        return num;
    }

    num = num.replace(/\d{1,3}(?=(\d{3})+$)/g, (v) => {
        console.log(v)
        return v + ',';
    });
    return num;
}

console.log(exchange(1234567));

6) 实现 JS 对象的深拷贝

深拷贝就是在拷贝数据的时候,将数据的所有引用结构都拷贝一份。简单的说就是,在内存中存在两个数据结构完全相同又相互独立的数据,将引用型类型进行复制,而不是只复制其引用关系。

分析下怎么做 深拷贝

  • 首先假设深拷贝这个方法已经完成,为 deepClone
  • 要拷贝一个数据,我们肯定要去遍历它的属性,如果这个对象的属性仍是对象,继续使用这个方法,如此往复
function deepClone(o1, o2) {
    for (let k in o2) {
        if (typeof o2[k] === 'object') {
            o1[k] = {};
            deepClone(o1[k], o2[k]);
        } else {
            o1[k] = o2[k];
        }
    }
}
// 测试用例
let obj = {
    a: 1,
    b: [1, 2, 3],
    c: {}
};
let emptyObj = Object.create(null);
deepClone(emptyObj, obj);
console.log(emptyObj.a == obj.a);
console.log(emptyObj.b == obj.b);

递归容易造成爆栈,尾部调用可以解决递归的这个问题,Chrome 的 V8 引擎做了尾部调用优化,我们在写代码的时候也要注意尾部调用写法。递归的爆栈问题可以通过将递归改写成枚举的方式来解决,就是通过for或者while来代替递归。

7) 求斐波那契数列(兔子数列) 1,1,2,3,5,8,13,21,34,55,89...中的第 n 项

 下面的代码中count记录递归的次数,我们看下两种差异性的代码中的count的值:
 let count = 0;
 function fn(n) {
    let cache = {};
    function _fn(n) {
        if (cache[n]) {
            return cache[n];
        }
        count++;
        if (n == 1 || n == 2) {
            return 1;
        }
        let prev = _fn(n - 1);
        cache[n - 1] = prev;
        let next = _fn(n - 2);
        cache[n - 2] = next;
        return prev + next;
    }
    return _fn(n);
}

let count2 = 0;
function fn2(n) {
    count2++;
    if (n == 1 || n == 2) {
        return 1;
    }
    return fn2(n - 1) + fn2(n - 2);
}

console.log(fn(20), count); // 6765 20
console.log(fn2(20), count2); // 6765 13529

8)算法的效率

算法的好坏可以通过算法复杂度来衡量,算法复杂度包括时间复杂度和空间复杂度两个。时间复杂度由于好估算、好评估等特点,是面试中考查的重点。空间复杂度在面试中考查得不多。

常见的时间复杂度有:

  • 常数阶 O(1)
  • 对数阶 O(logN)
  • 线性阶 O(n)
  • 线性对数阶 O(nlogN)
  • 平方阶 O(n^2)
  • 立方阶 O(n^3)
  • !k次方阶 O(n^k)
  • 指数阶 O(2^n)

随着问题规模 n 的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

一般做算法复杂度分析的时候,遵循下面的技巧:

  • 看看有几重循环,一般来说一重就是O(n),两重就是 O(n^2),以此类推
  • 如果有二分,则为O(logN)
  • 保留最高项,去除常数项

题目:分析下面代码的算法复杂度

let i =0; // 语句执行一次 
while (i < n) { // 语句执行 n 次 
  console.log(`Current i is ${i}`); //语句执行 n 次
  i++; // 语句执行 n 次
}
根据注释可以得到,算法复杂度为1 + n + n + n = 1 + 3n,去除常数项,为O(n)。

算法题其实还有很多,比如二叉树的增删改查等,推荐大家晚上空出时间都去看看~还是挺有意思的~

延伸资源:

在 JavaScript 中学习数据结构与算法

我接触过的前端数据结构与算法


彩蛋

hr面试

1)你觉得你是什么样的人?

2)为什么离职?

3)你最不满意以前领导的什么地方?

4)你平时周末都干什么?

5)你做的最喜欢的项目是什么?为什么?

6)喜欢什么样的团队?


预告:跟新完了这篇,下一篇是面试官的面试了,由于我的技术栈是react,所以接下来的主题是围绕着react