none

0%

手撸面试常问的几个底层算法

发表于 更新于

继承

寄生组合式继承

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function Parent() {
    this.name = 'Liliya'
}
Parent.prototype.getName = function () {
    return this.name
}

function Child() {
    Parent.call(this)
}

function extend(sup, sub) {
    function F() {}
    F.prototype = Parent.prototype
    sub.prototype = new F()
    sub.prototype.constructor = sub
    return sub
}

const Class = extend(Parent, Child)

const child = new Class()
child.getName()

instanceof

1
2
3
4
5
6
7
8
9
10
function instanceOf(instance, Constructor) {
    let proto = instance.__proto__
    while (proto) {
        if (proto === Constructor.prototype) {
            return true
        }
        proto = proto.__proto__
    }
    return false
}

bind

1
2
3
4
5
6
Function.prototype.bind = function (ctx, ...args1) {
    const f = this
    return function (...args2) {
        return f.call(ctx, ...args1, ...args2)
    }
}

call

1
2
3
Function.prototype.call = function (ctx, ...args) {
    return this.bind(ctx, ...args)()
}

apply

1
2
3
Function.prototype.apply = function (ctx, args) {
    return this.bind(ctx, ...args)()
}

map

1
2
3
4
5
6
7
Array.prototype.map = function (callback) {
    const result = []
    for (let i = 0, len = this.length; i < len; i++) {
        result.push(callback(this[i], i, this))
    }
    return result
}

forEach

1
2
3
4
5
Array.prototype.forEach = function (callback) {
    for (let i = 0, len = this.length; i < len; i++) {
        callback(this[i], i, this)
    }
}

reduce

1
2
3
4
5
6
7
8
9
10
11
12
Array.prototype.reduce = function (callback, defaultValue) {
    const useDefault = defaultValue !== void 0
    let result = useDefault ? defaultValue : this[0],
        next,
        len = this.length,
        i = useDefault ? 0 : 1
    for (; i < len; i++) {
        next = this[i]
        result = callback(result, next, i, this)
    }
    return result
}

Promise

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
class Promise {
  static PENDING = 'pending'
  static FULFILLED = 'fulfilled'
  static REJECTED = 'rejected'

  constructor(executor) {
    this.state = Promise.PENDING
    this.value = void 0
    this.resean = void 0
    this.onFulfilledCallbak = []
    this.onRejectedCallbak = []
    const resolve = (value) => {
      if (this.state === Promise.PENDING) {
        this.state = Promise.FULFILLED
        this.value = value
        this.onFulfilledCallbak.forEach((fn) => fn())
      }
    }
    const reject = (resean) => {
      if (this.state === Promise.PENDING) {
        this.state = Promise.REJECTED
        this.resean = resean
        this.onRejectedCallbak.forEach((fn) => fn())
      }
    }
    try {
      executor(resolve, reject)
    } catch (e) {
      reject(e)
    }
  }

  static resolve(value) {
    return new Promise((resolve) => {
      resolve(value)
    })
  }

  static reject(reason) {
    return new Promise((_, reject) => {
      reject(reason)
    })
  }

  resolvePromise(p1, p2, resolve, reject) {
    if (p1 === p2) {
      reject(new TypeError('circular reference'))
    }
    let called = false
    if (p2 !== null && (typeof p2 === 'function' || typeof p2 === 'object')) {
      try {
        const then = p2.then
        if (typeof then === 'function') {
          then.call(
            p2,
            (value) => {
              if (called) return
              called = true
              this.resolvePromise(p1, value, resolve, reject)
            },
            (err) => {
              if (called) return
              called = true
              reject(err)
            }
          )
        } else {
          if (called) return
          called = true
          resolve(p2)
        }
      } catch (e) {
        if (called) return
        called = true
        reject(e)
      }
    } else {
      if (called) return
      called = true
      resolve(p2)
    }
  }

  then(onFulfilled, onRejected) {
    onFulfilled = typeof onFulfilled === 'function' ? onFulfilled : (_) => _
    onRejected =
      typeof onRejected === 'function'
        ? onRejected
        : (_) => {
            throw _
          }
    const promise = new Promise((resolve, reject) => {
      if (this.state === Promise.FULFILLED) {
        setTimeout(() => {
          try {
            this.resolvePromise(
              promise,
              onFulfilled(this.value),
              resolve,
              reject
            )
          } catch (e) {
            reject(e)
          }
        })
      } else if (this.state === Promise.REJECTED) {
        setTimeout(() => {
          this.resolvePromise(promise, onRejected(this.resean), resolve, reject)
        })
      } else {
        this.onFulfilledCallbak.push(() => {
          setTimeout(() => {
            this.resolvePromise(
              promise,
              onFulfilled(this.value),
              resolve,
              reject
            )
          })
        })
        this.onRejectedCallbak.push(() => {
          setTimeout(() => {
            this.resolvePromise(
              promise,
              onRejected(this.resean),
              resolve,
              reject
            )
          })
        })
      }
    })
    return promise
  }

  catch(onRejected) {
    return this.then(null, onRejected)
  }
  finally(onFinished) {
    onFinished = typeof onFinished === 'function' ? onFinished : (_) => _
    return this.then((val) => {
      onFinished()
      return val
    }).catch((err) => {})
  }
}