乐趣区

关于javascript:面试大厂手写代码这些就够了附-codepen-地址

jiezi

Offer 驾到，掘友接招！我正在参加 2022 春招系列流动 - 教训复盘，点击查看 流动详情 即算参赛

大家好，我是山月。这篇文章也可在我的博客面试路线图进行查看。

其中有一个高频问题是：我如何进行编程题目的练习？山月再次总结一份对于手写代码的练习路线。

为了保障代码可能失常运行，调试和测试。

以下所有的手写代码都贴在 我的 codepen 中

以下所有的手写代码都贴在 我的 codepen 中

以下所有的手写代码都贴在 我的 codepen 中

筹备工作

API 设计思考

作为一个工作过三年以上的老前端而言，都会明确一个事件: API 的设计比实现更为重要。

何解？

如 compose 函数罕用在各种中间件设计中，如 redux 等。redux 函数的实现极为简略，甚至一行就能实现，然而可能第一个想到 compose 的更不容易。

因而前端面试中的许多面试题以 ES API 与 lodash API 的模仿实现为主，因而在手写代码前需对 lodash 与 ES6+ 文档较为相熟。

代码标准

在面试过程中考查代码，除了能够考查候选人的逻辑能力，其次，可查看候选人的代码能力，比方

  1. 是否有统一的代码标准
  2. 是否有清晰可读的变量命名
  3. 是否有更简介的代码

对于优雅代码的养成能力能够查看 Clean Code concepts adapted for JavaScript.，在 Github 上领有 50+ K 的星星数。

比方对于命名优化

// BAD
// What the heck is 86400000 for?
setTimeout(blastOff, 86400000);

// GOOD
// Declare them as capitalized named constants.
const MILLISECONDS_PER_DAY = 60 * 60 * 24 * 1000; //86400000;

setTimeout(blastOff, MILLISECONDS_PER_DAY);

空间复杂度与工夫复杂度

  • 空间复杂度(Space Complexity) 形容该算法在运行过程中长期占用存储空间大小
  • 工夫复杂度(Time complexity) 形容该算法的运行工夫，罕用大 O 符号表述

该图片来自于文章 How to find time complexity of an algorithm?

  • O(1): Constant Complexity，常数复杂度，比方计算两次即可得出最终论断
  • O(logn): Logarithmic Complexity，最常见的是二分查找
  • O(n): Linear Complexity，个别为一个 for 循环，但半个或者两个 for 循环也视作 O(n)
  • O(n^2): 个别为嵌套的 for 循环，如冒泡排序

手写代码路线图

以下是我在诸多大厂面经中总结的代码题，我将依据难易水平、模块属性总结为不同的局部。

备注: 山月总结的所有大厂面试请点击此处

因而我把题目分为以下几类，能够依照我列出所有代码题的星星数及程序进行筹备，每天找三道题目进行编码，并且保持下来，三个月后面试大厂时的编码阶段不会出问题。

  1. ES API
  2. lodash API
  3. 编程逻辑题
  4. 算法与数据结构 (leetcode)

以下所有题目都能够在山月的仓库中找到，并且大部分代码题可在 codepen 上，找到我的题解测试并间接执行。

01 ES API

很多大厂面试题醉心于对于原生 API 的模仿实现，尽管大部分时候无所裨益，但有时能够更进一步加深对该 API 的了解。

例如，当你手写完结 Promise.all 时，对手写一个并发管制的 Promises 将会更加得心应手。

bind/call/apply ⭐⭐⭐⭐⭐️️️️

  • 实现 call/apply
  • 实现 bind
  • 实现 softBind

高频问题，中频实现。

Function.prototype.fakeBind = function(obj, ...args) {return (...rest) => this.call(obj, ...args, ...rest)
}

sleep/delay ⭐⭐⭐⭐⭐

  • 题目:【Q435】JS 如何实现一个 sleep/delay 函数
  • 代码:【Q435】JS 如何实现一个 sleep/delay 函数

sleep 函数既是面试中常问到的一道代码题，也是日常工作，特地是测试中罕用的一个工具函数。

const sleep = (seconds) => new Promise(resolve => setTimeout(resolve, seconds))

function delay (func, seconds, ...args) {return new Promise((resolve, reject) => {setTimeout(() => {Promise.resolve(func(...args)).then(resolve)
    }, seconds)
  })
}

Promise.all ⭐️⭐️⭐️⭐️⭐️

  • 代码: Promise.all
  • 题目: Promise.all

乍看简略，实现时方觉不易。

function pAll (_promises) {return new Promise((resolve, reject) => {
    // Iterable => Array
    const promises = Array.from(_promises)
    // 后果用一个数组保护
    const r = []
    const len = promises.length
    let count = 0
    for (let i = 0; i < len; i++) {
      // Promise.resolve 确保把所有数据都转化为 Promise
      Promise.resolve(promises[i]).then(o => { 
        // 因为 promise 是异步的，放弃数组一一对应
        r[i] = o;

        // 如果数组中所有 promise 都实现，则返回后果数组
        if (++count === len) {resolve(r)
        }
        // 当产生异样时，间接 reject
      }).catch(e => reject(e))
    }
  })
}

Array.isArray ⭐️⭐️⭐️⭐️⭐️

  • 题目: Array.isArray

面试常问，不过也足够简略。

Array.prototype.flat ⭐️⭐️⭐️⭐️⭐️

  • 题目:【Q443】实现一个数组扁平化的函数 flatten
  • 代码:【Q443】实现一个数组扁平化的函数 flatten

reduce 与 concat 几乎是绝配

function flatten (list, depth = 1) {if (depth === 0) return list
  return list.reduce((a, b) => a.concat(Array.isArray(b) ? flatten(b, depth - 1) : b), [])
}

留神，flatten 领有第二个参数 depth

Promise ⭐️⭐️⭐️⭐️

  • 题目: Promise

不说了，要实现真正的符合规范的 Promise，非常不容易。

Array.prototype.reduce ⭐️⭐️⭐️

  • 代码: Array.prototype.reduce
  • 题目: Array.prototype.reduce
const reduce = (list, fn, ...init) => {let next = init.length ? init[0] : list[0]
  for (let i = init.length ? 0 : 1; i < list.length; i++) {next = fn(next, list[i], i)
  }
  return next
}

该题目看起来简略，理论做起来有许多边界问题须要留神，如

  1. 回调函数中第一个 Index 是多少？
  2. 数组为稠密数组如何解决？

String.prototype.trim ⭐️⭐️⭐️

  • 题目: 如何去除字符串首尾空白字符

在正则表达式中，\s 指匹配一个空白字符，包含空格、制表符、换页符和换行符。等价于[\f\n\r\t\v\u00a0\u1680\u180e\u2000-\u200a\u2028\u2029\u202f\u205f\u3000\ufeff]。

const trim = str => str.trim || str.replace(/^\s+|\s+$/g, '')

个别在考查正则时会考查该 API

02 lodash API

throtle/debounce ⭐⭐⭐⭐⭐️️

  • 题目: 什么是防抖和节流，他们的利用场景有哪些

性能优化中缩小渲染的必要伎俩，代码也足够容易，面试题中常常会被提到。

function throttle (f, wait) {
  let timer
  return (...args) => {if (timer) {return}
    timer = setTimeout(() => {f(...args)
      timer = null
    }, wait)
  }
}
function debounce (f, wait) {
  let timer
  return (...args) => {clearTimeout(timer)
    timer = setTimeout(() => {f(...args)
    }, wait)
  }
}

cloneDeep ⭐⭐️⭐⭐⭐

  • 题目:【Q202】如何实现一个深拷贝 (cloneDeep)

深拷贝，无论在工作中的性能优化，还是面试中，都大受青眼。

应用 JSON 序列化反序列化无奈解决一些简单对象的拷贝问题，难点在于对不同的数据类型进行解决。

isEqual ⭐⭐⭐⭐⭐

  • 题目:【Q598】如何实现一个深比拟的函数 deepEqual

深比拟，在性能优化中也罕用到，比 cloneDeep 难度要低一些。

get ⭐️⭐️⭐️⭐️⭐️

  • 题目: 如何实现相似 lodash.get 函数
  • 代码: 如何实现相似 lodash.get 函数

在 ES6+ 中，应用可选链操作符 ?. 可进一步减小实现难度

function get (source, path, defaultValue = undefined) {// a[3].b -> a.3.b -> [a, 3, b]
  const paths = path.replace(/\[(\w+)\]/g, '.$1').replace(/\["(\w+)"\]/g, '.$1').replace(/\['(\w+)'\]/g, '.$1').split('.')
  let result = source
  for (const p of paths) {result = result?.[p]
  }
  return result === undefined ? defaultValue : result 
}

compose(flowRight) ⭐️⭐️⭐️⭐️⭐️

  • 题目:【Q181】如何实现 compose 函数，进行函数合成
const compose = (...fns) =>
  // 留神 f、g 的地位，如果实现从左到右计算，则置换程序
  fns.reduce((f, g) => (...args) => f(g(...args)))

shuffle ⭐️⭐️⭐️⭐️⭐️

  • 题目:【Q447】如何实现一个数组洗牌函数 shuffle
  • 相干:【Q645】随机生成六位数的手机验证码(反复 / 不可反复)
  • 代码:【Q447】如何实现一个数组洗牌函数 shuffle

对于实现一个简略的 shuffle，可能极其简略。

const shuffle = (list) => list.sort((x, y) => Math.random() - 0.5)

如果不借助 Array.prototype.sort，可由以下代码实现

function shuffle (list) {
  const len = list.length
  let result = [...list]
  for (let i = len - 1; i > 0; i--) {const swapIndex = Math.floor(Math.random() * (i + 1));
    [result[i], result[swapIndex]] = [result[swapIndex], result[i]]
  }
  return result
}

生产实践中很多场景会应用到 shuffle，如 随机生成不反复六位数的手机验证码

sample ⭐️⭐️⭐️⭐️⭐️

  • 题目:【Q436】如何实现一个 sample 函数，从数组中随机取一个元素

Math.random() 函数返回一个浮点, 伪随机数在范畴从 0 到小于 1，用数学示意就是 [0, 1)，能够利用它来实现 sample 函数

Array.prototype.sample = function () { return this[Math.floor(Math.random() * this.length)] }

sampleSize ⭐️⭐️⭐️⭐️⭐️

  • 题目:【Q677】如何实现一个 sampleSize 函数，从数组中随机取 N 个元素

能够依据 shuffle 来实现一个简略的 sampleSize

const shuffle = (list) => list.sort((x, y) => Math.random() - 0.5)
const sampleSize = (list, n) => shuffle(list).slice(0, n)

maxBy ⭐⭐⭐⭐⭐

  • 题目:【Q628】实现一个函数 maxBy，依据给定条件找到最大的数组项

keyBy ⭐⭐⭐⭐

  • 题目:【Q678】实现一个函数 keyBy

groupeBy ⭐⭐⭐⭐

  • 题目:【Q679】实现一个函数 groupBy

chunk ⭐️⭐️⭐️⭐️

  • 题目:【Q643】如何实现 chunk 函数，数组进行分组
function chunk (list, size) {const l = []
  for (let i = 0; i < list.length; i++) {const index = Math.floor(i / size)
    l[index] ??= [];
    l[index].push(list[i])
  }
  return l
}

chunk ⭐️⭐️⭐️⭐️

  • 题目:【Q399】实现一个 once 函数，记忆返回后果只执行一次
const f = x => x

const onceF = once(f)

//=> 3
onceF(3)

//=> 3
onceF(4)

template ⭐⭐⭐⭐️️️️️

  • 题目:【Q660】实现一个 render/template 函数，能够用以渲染模板
  • 代码:【Q660】实现一个 render/template 函数，能够用以渲染模板

难度略微大一点的编程题目。

const template = '{{user["name"] }}，明天你又学习了吗 - 用户 ID: {{user.id}}';

const data = {
  user: {
    id: 10086,
    name: '山月',
  }
};

//=> "山月，明天你又学习了吗 - 用户 ID: 10086"
render(template, data);

留神:

  1. 留神深层嵌套数据
  2. 留神 user['name'] 属性

pickBy/omitBy ⭐⭐⭐⭐

camelCase ⭐️⭐⭐⭐

  • 题目: 驼峰命名

difference ⭐️⭐️⭐️

  • 题目:【Q655】实现 intersection，取数组交加

03 编程逻辑题

对于编程逻辑题，指在工作中常会遇到的一些数据处理

FizzBuzz，是否能被 3 或 5 整除 ⭐️⭐️⭐️⭐️⭐️

  • 题目: FizzBuzz，是否能被 3 或 5 整除

输出一个整数，如果可能被 3 整除，则输入 Fizz

如果可能被 5 整除，则输入 Buzz

如果既能被 3 整数，又能被 5 整除，则输入 FizzBuzz

//=> 'fizz'
fizzbuzz(3)

//=> 'buzz'
fizzbuzz(5)

//=> 'fizzbuzz'
fizzbuzz(15)

//=> 7
fizzbuzz(7)

这道题尽管很简略，但在面试中依然有大部分人无奈做对

实现 Promise.map 用以管制并发数 ⭐️⭐️⭐️⭐️⭐️

  • 题目: Promise.map
  • 代码: Promise.map

用以 Promise 并发管制，面试中常常会有问到，在工作中也常常会有波及。在上手这道问题之前，理解 [Promise.all]() 的实现将对实现并发管制有很多的帮忙。

另外，最受欢迎的 Promise 库 bluebird 对 Promise.map 进行了实现，在我的项目中大量应用。

异步的 sum/add ⭐️⭐️⭐️⭐️⭐️

编码题中的集大成者，出自头条的面经，promise 串行，并行，二分，并发管制，层层递进。

  • 题目:【Q644】实现一个异步的 sum/add

如何应用 JS 实现一个公布订阅模式 ⭐️⭐️⭐️⭐️⭐️

  • 题目:【Q613】如何应用 JS 实现一个公布订阅模式
  • 代码:【Q613】如何应用 JS 实现一个公布订阅模式

如何实现有限累加的 sum 函数 ⭐️⭐️⭐️⭐️⭐️

  • 题目:【Q421】如何实现有限累加的一个函数
  • 代码:【Q421】如何实现有限累加的一个函数

实现一个 sum 函数如下所示：

sum(1, 2, 3).valueOf() //6
sum(2, 3)(2).valueOf() //7
sum(1)(2)(3)(4).valueOf() //10
sum(2)(4, 1)(2).valueOf() //9
sum(1)(2)(3)(4)(5)(6).valueOf() // 21

这还是字节、快手、阿里一众大厂最为偏爱的题目，实际上有一点技巧问题。

这还是字节、快手、阿里一众大厂最为偏爱的题目，实际上有一点技巧问题。

这还是字节、快手、阿里一众大厂最为偏爱的题目，实际上有一点技巧问题。

这是一个对于懒计算的函数，应用 sum 收集所有累加项，应用 valueOf 进行计算

  • sum 返回一个函数，收集所有的累加项，应用递归实现
  • 返回函数带有 valueOf 属性，用于对立计算
function sum (...args) {const f = (...rest) => sum(...args, ...rest)
  f.valueOf = () => args.reduce((x, y) => x + y, 0)
  return f
}

统计数组中最大的数 / 第二大的数 ⭐️⭐️⭐️⭐️⭐️

  • 题目: 统计数组中最大的数 / 第二大的数
  • 代码: 统计数组中最大的数 / 第二大的数

求最大的一个值：

function max (list) {if (!list.length) {return 0}
  return list.reduce((x, y) => x > y ? x : y)
}

求最大的两个值：

代码见 找出数组中最大的两个值 – codepen

function maxTwo (list) {
  let max = -Infinity, secondMax = -Infinity
  for (const x of list) {if (x > max) {
      secondMax = max
      max = x
    } else if (x > secondMax) {secondMax = x}
  }
  return [max, secondMax]
}

如果求 TopN，可应用大顶堆、小顶堆实现，见另一个问题

统计字符串中呈现次数最多的字符 ⭐️⭐️⭐️⭐️⭐️

  • 题目:【Q644】统计字符串中呈现次数最多的字符及次数
  • 代码:【Q644】统计字符串中呈现次数最多的字符及次数
function getFrequentChar (str) {const dict = {}
  for (const char of str) {dict[char] = (dict[char] || 0) + 1
  }
  const maxBy = (list, keyBy) => list.reduce((x, y) => keyBy(x) > keyBy(y) ? x : y)
  return maxBy(Object.entries(dict), x => x[1])
}

以下计划一边进行计数统计一遍进行大小比拟，只须要 1 次 O(n) 的算法复杂度

function getFrequentChar2 (str) {const dict = {}
  let maxChar = ['', 0]
  for (const char of str) {dict[char] = (dict[char] || 0) + 1
    if (dict[char] > maxChar[1]) {maxChar = [char, dict[char]]
    }
  }
  return maxChar
}

对以下数字进行编码压缩 ⭐️⭐️⭐️⭐️⭐️

  • 题目:【Q412】对以下字符串进行压缩编码
  • 代码:【Q412】对以下字符串进行压缩编码

这是一道大厂常考的代码题

  • Input: ‘aaaabbbccd’
  • Output: ‘a4b3c2d1’，代表 a 间断呈现四次，b 间断呈现三次，c 间断呈现两次，d 间断呈现一次

有以下测试用例

//=> a4b3c2
encode('aaaabbbcc')

//=> a4b3a4
encode('aaaabbbaaaa')

//=> a2b2c2
encode('aabbcc')

如果代码编写正确，则可持续深刻：

  • 如果只呈现一次，不编码数字，如 aaab -> a3b
  • 如果只呈现两次，不进行编码，如 aabbb -> aab3
  • 如果进行解码数字抵触如何解决

编写函数 encode 实现该性能

代码见【Q412】对以下字符进行压缩编码 – codepen

function encode (str) {const l = []
  let i = 0
  for (const s of str) {
    const len = l.length
    const lastChar = len > 0 ? l[len - 1][0] : undefined
    if (lastChar === s) {l[len - 1][1]++
    } else {l.push([s, 1])
    }
  }
  return l.map(x => x.join('')).join('')
}

测试通过

> encode('aaab')
< "a3b1"

然而面试官往往会持续深刻

  1. 如果只呈现一次，不编码数字，如 aaab -> a3b
  2. 如果只呈现两次，不进行编码，如 aabbb -> aab3
  3. 如果进行解码，碰到数字如何解决？

以下是除数字外的进一步编码

function encode (str) {const l = []
  let i = -1;
  let lastChar
  for (const char of str) {if (char !== lastChar) {
      lastChar = char
      i++
      l[i] = [char, 1];
    } else {l[i][1]++
    }
  }
  return l.map(([x, y]) => {if (y === 1) {return x}
    if (y === 2) {return x + x}
    return x + y
  }).join('')
}

LRU Cache ⭐️⭐️⭐️⭐️⭐️

  • 代码:【Q249】应用 js 实现一个 lru cache

实现一个函数用来对 URL 的 querystring 进行编码与解码 ⭐️⭐️⭐️⭐️⭐️

  • 题目:【Q440】实现一个函数用来对 URL 的 querystring 进行编码

JSONP 的原理是什么，如何实现 ⭐️⭐️⭐️⭐️

  • 题目:【Q439】JSONP 的原理是什么，如何实现

JSONP，全称 JSON with Padding，为了解决跨域的问题而呈现。尽管它只能解决 GET 跨域，尽管当初基本上都应用 CORS 跨域，但依然要晓得它，毕竟 面试会问。

JSONP 基于两个原理:

  1. 动态创建 script，应用 script.src 加载申请跨过跨域
  2. script.src 加载的脚本内容为 JSONP: 即 PADDING(JSON) 格局
function jsonp ({url, onData, params}) {const script = document.createElement('script')

  // 一、为了防止全局净化，应用一个随机函数名
  const cbFnName = `JSONP_PADDING_${Math.random().toString().slice(2)}`

  // 二、默认 callback 函数为 cbFnName
  script.src = `${url}?${stringify({ callback: cbFnName, ...params})}`

  // 三、应用 onData 作为 cbFnName 回调函数，接收数据
  window[cbFnName] = onData;

  document.body.appendChild(script)
}

// 发送 JSONP 申请
jsonp({
  url: 'http://localhost:10010',
  params: {id: 10000},
  onData (data) {console.log('Data:', data)
  }
})

应用 JS 如何生成一个随机字符串 ⭐️⭐️⭐️⭐️⭐️

  • 题目:【Q619】应用 JS 如何生成一个随机字符串
const random = (n) => Math.random().toString(36).slice(2, 2 + n)

给数字增加千位符 ⭐️⭐️⭐️

  • 代码: 如何给数组增加千位符

千位符替换可由正则 /(\d)(?=(\d\d\d)+(?!\d))/ 进行匹配

function numberThousands (number, thousandsSeperator = ',') {return String(number).replace(/(\d)(?=(\d\d\d)+(?!\d))/g, '$1' + thousandsSeperator)
}

04 算法与数据结构 (leetcode)

Leetcode 简略与中级难度题目 200/100 道，以简略题目为主。间接刷就得了。

在我的题库中也收集了在诸多大厂面经中总结出的多道算法题，总结如下

输入 100 以内的菲波那切数列

  • 题目: 输入 100 以内的菲波那切数列

TopK 问题

  • 题目:【Q288】如何求数组中的 TOP k

典型的二叉堆问题

  1. 取数组中前 k 个数做小顶堆，堆化
  2. 数组中的其它数逐个与堆顶元素比拟，若大于堆顶元素，则插入该数

工夫复杂度 O(nlg(k))

求正序增长的正整数数组中，其和为 N 的两个数

  • 题目:【Q681】求正序增长的正整数数组中，其和为 N 的两个数

求给定数组中 N 个数相加之和为 sum 所有可能汇合

  • 题目:【Q673】求给定数组中 N 个数相加之和为 sum 所有可能汇合

求给定数组中 N 个数相加之和为 sum 所有可能汇合，请补充以下代码

function fn(arr, n, sum) {}

如何判断两个链表是否相交

  • 题目:【Q061】如何判断两个链表是否相交

经典问题

最终

代码编程题在面试过程中呈现频率很高，且能很大水平考查候选人的代码能力与代码格调。

退出移动版