前端笔试经

排序
请完善下面代码，以写出一个平均时间复杂度低于 $图片说明$ 的排序算法（空间复杂度不作要求）：

function sort(a) {
    // 请在这里补充代码，sort 的形式参数你可以随便加
    let start = 0;
    let size = a.length;
    let min = a[0];
    let max = a[0];
    for (let i = 1; i < size; i++) {
        if (a[i] < min) {
            min = a[i];
        } else if (a[i] > max) {
            max = a[i];
        }
    }
    if (min != max) {
        let bucket = new Array(size);
        for (let i = 0; i < size; i++) {
            bucket[i] = new Array();
        }
        let interpolation = 0;
        for (let i = 0; i < size; i++) {
            interpolation = Math.floor(
                ((a[i] - min) / (max - min)) * (size - 1)
            );
            bucket[interpolation].push(a[i]);
        }
        for (let i = 0; i < size; i++) {
            if (bucket[i].length > 1) {
                sort(bucket[i]);
            }
            for (let j = 0; j < bucket[i].length; j++) {
                a[start++] = bucket[i][j];
            }
        }
    }
    return a;
}

选择了桶排序算法，平均时间复杂度为 $图片说明$ 参考：排序算法

缓存
请完善下面代码，输出第 n (n=0,1,2,3,4…) 个斐波那契数，要求 n 为 50 时，能够在 2 秒内返回结果。
```
function fibonacci(n){
 // 请补充代码
 let phi = (1 + Math.sqrt(5)) / 2;
 return Math.round(Math.pow(phi, n) / Math.sqrt(5));
}
```
用递归调用，浏览器会爆掉的，所以选了时间复杂度的公式法：
，用 performance 函数测了一下，时间不超过 0.1s
Promise
请完善 light 函数的代码，要求运行代码之后，1秒钟后打印 red，打印 red 之后的 2 秒钟后打印 green，打印 green 的 3 秒钟后打印 yellow

function light(timer, fn) {
    // 请补充代码
    let promise =  new Promise(function(resolve, reject) {
        setTimeout(() => resolve(fn), timer*1000);
    })

    return promise.then(fn);
}

测试用例：

function red() {
    console.log(new Date())
    console.log('red');
}
function green() {
    console.log(new Date())
    console.log('green');
}
function yellow() {
    console.log(new Date())
    console.log('yellow');
}

light(1, red).then(function() {
    return light(2, green);
}).then(function() {
    return light(3, yellow);
})

第 3-5 行代码只是定义了一个 Promise ，这里还得用一次 .then方法

Hack
请想办法使 a === 1 && a === 2 && a === 3 为 true：
注意，只要能运行成功一次即可，如果运行第二次报错也没关系。
提示：getter。

// 请补充代码
let i = 0;

Object.defineProperty(window, 'a', {
    get: function() {
        return ++i;
    }
});

解释一下，这里Object.defineProperty()直接给 window 对象定义了一个新属性 a，第 3 个参数是属性描述符，有两种形式——数据描述符和存取描述符，而且只能出现其中一种，这里用的是后者，用 getter 方法所描述的属性是可继承的，所以每次 window 调用 a 属性时，都会执行一次 get，而 ++i 的返回值是 i+1 之后的值，所以该表达式为 true。
5. 深拷贝
请实现深拷贝，它能深拷贝含有数组、普通对象、日期、简单函数的对象：

// 测试用例
const o1 = {
    date: new Date(2020,0,1),
    fn: function(){ return 'fn' },
    array: [1,2,3],
    obj: {
        nested: {
        name: 'frank',
        date2: new Date(2020,0,1),
        fn2: function(){ return 'fn2' }
        }
    }   
}

常用的浅拷贝方法是 ES6 提出的 Object.assign() 和 spread operator，
深拷贝有 JSON.parse(JSON.stringify())，还可以使用 lodash的_.cloneDeep()函数，不过使用前者时对象里不能出现Date，函数，undefined，Infinity，正则，。。。，后者遇到函数直接 return
html spec 提到了一种 deep clone 的算法——structured clone：

This specification used to define a "structured clone" algorithm, and more recently a StructuredClone abstract operation. However, in practice all known uses of it were better served by separate serialization and deserialization steps, so it was removed.

《JavaScript 高级程序设计》里也提到了这种算法，并且给出了支持的数据类型，
所以我用了history.state这个 API来实现：

function clone(o) {
    // 请补充代码
    const oldState = history.state;
    history.replaceState(o, null);
    const clonedObj = history.state;
    history.replaceState(oldState, null);
    return clonedObj;
}

同样，它也不能处理函数，而且执行次数太多 Chrome 会无响应，但是它是推荐的解法
关于深拷贝和浅拷贝可以看一下这篇博客。

#前端工程师##笔试题目##笔经#