Skip to content
大纲

实现 add 方法,满足以下条件

分别满足以下条件

实现 add(1,2,3) 与 add(1)(2)(3) 结果相同

这是函数柯里化的一种基本表现形式

js
// 使用 curry 来实现
function curry(fn, ...rest) {
  return fn.length <= rest.length ? fn(...rest) : curry.bind(null, fn, ...rest)
}
const add = curry((a, b, c) => a + b + c)

// testing
console.log(add(1, 2, 3))
console.log(add(1)(2)(3))

思考

如何实现一个无限累加的 sum 函数?

点我查看详细
js
function sum(...args) {
  const f = (...rest) => sum(...args, ...rest)
  f.valueOf = () => args.reduce((x, y) => x + y, 0)
  return f
}

// TODO: 解析

实现大数加法

大数加法,这里要求要能支持很大的数字相加,超过了 JS 数据精度范围的(支持整数即可)

JS 中想要表达数值范围在-2^53 到 2^53 之间的所有整数,精度是没有问题的, 一旦数值超出这个范围,在数值末尾就会损失一定的精度

JS 能表达的最大安全整数 Number.MAX_SAFE_INTEGER 即 9007199254740991 (9_007_199_254_740_991)

解决方案

转成字符串,从个位遍历每一项,累加进位,可得到最终结果(是个字符串)

点我查看详细
js
function bigSum(a, b) {
  // 接收到的是数字,先将他们转换成字符串
  a = '' + a
  b = '' + b
  // 假如有一个为0, 直接返回不为0的一个
  if (a === '0' || b === '0') return a === '0' ? b : a
  // 获得a和b 较长的一个,以为较短的一个前面补0,直到a和b长度相等
  const len = Math.max(a.length, b.length)
  a = a.padStart(len, '0') // 000123
  b = b.padStart(len, '0') // 123456
  // 下面会用到的变量
  let t = 0 // 每次相加的结果
  let f = 0 // 是否进位
  let sum = '' // 最后的和
  // 从后向前遍历
  for (let i = len - 1; i >= 0; i--) {
    // 此次运算的结果 + 上次是否有进位
    t = parseInt(a[i]) + parseInt(b[i]) + f
    // 如果此次结果大于10, 说明下次可以进一位
    // f 只可能是1 或 0
    f = Math.floor(t / 10)
    // 这一次加的永远是这次的个位,如果此次结果>10,会在下次进一位
    sum = (t % 10) + sum
  }
  // 如果遍历结束,发现 f == 1 表示仍然可以进位, 就在sum最前面+1
  if (f) {
    sum = f + sum
  }
  return sum
}

// testing
let a = Number.MAX_SAFE_INTEGER // 9007199254740991
let b = 12
console.log(bigSum(a, b))

大数相乘,方案类似

实现一个异步的 sum/add

更多描述

这是一道字节跳动的面试题目,见面经 某银行前端一年半经验进字节面经,这是一道水平较高的题目,promise 串行,并行,二分,并发控制,层层递进。

请实现以下 sum 函数,只能调用 add 进行实现

js
/*
 * 请实现一个 sum 函数,接收一个数组 arr 进行累加,并且只能使用add异步方法
 * add 函数已实现,模拟异步请求后端返回一个相加后的值
 */
function add(a, b) {
  return Promise.resolve(a + b)
}

function sum(arr) {}

追加问题:如何控制 add 异步请求的并发次数

初级实现: 串行方式

初步想法,一个个累加就行了,可使用 reduce

点我查看详细
js
function add(a, b) {
  return Promise.resolve(a + b)
}

// 思路 1: 使用 reduce 实现
function sum(arr) {
  return arr.reduce(async (sum, item) => {
    return await add(await sum, item)
  }, Promise.resolve(0))
}

// 注意: 不能将 0 作为累加器的初始值
sum([1, 2, 3, 4])

// 思路 2: 返回 Promise
function sum(arr) {
  if (arr.length === 1) return arr[0]
  return arr.reduce((x, y) => Promise.resolve(x).then((x) => add(x, y)))
}
sum([1, 2, 3, 4]).then((res) => console.log(res))

// 思路 3: 使用 for await...of
async function sum(arr) {
  let result = 0
  // `for await...of` vs `for of`
  // for await (const num of arr) {
  for (const num of arr) {
    result = await add(result, num)
  }
  return result
}
sum([1, 2, 3, 4])

// 思路 4: https://github.com/mahaoming
async function sum(arr) {
  let res = 0
  if (arr.length === 0) return res
  if (arr.length === 1) return arr[0]

  let a = arr.pop()
  let b = arr.pop()
  arr.push(await add(a, b))
  return sum(arr)
}

以上方法有一个问题,在异步 sum 函数中,其中最为耗时的是 add(),因为他是一个异步 IO 操作,模拟的是服务器数据请求,假设 add 延时一秒,此时需要 N-1 秒,延时太长。

中级实现: 并行方式

关于上边的同步实现,有可能就会筛了一部分同学。面试官到了这里,就会继续增加难度。

接下来是并行的写法: 我们实现一个 chunk 函数,将数组两两分组,每两个计算一次,使用 chunk 二分,此时延时变为 logN 秒

关于 chunk 的 API 可以参考 lodash.chunk: _.concat(array, [values]),在平常工作中也会用到。

js
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
}

逻辑空赋值运算符(x ??= y)仅在 x 是空值(nullundefined)时对其赋值。

在通过 chunk 进行两两分组时,有可能最后一项为单数,此时直接返回数值即可,在最终得到结果后,迭代该函数继续二分,直到最后只有一个数值。

点我查看详细
js
// 并发
async function sum(arr) {
  if (arr.length === 1) return arr[0]
  const promises = chunk(arr, 2).map(([x, y]) =>
    // 注意此时单数的情况
    y === undefined ? x : add(x, y)
  )
  return Promise.all(promises).then((list) => sum(list))
}

此时使用的是 Promise.all,意味着不管 Promise.all 所接收的数组中有多少元素,将会同时进行处理。

此时面试官会进行扩展: 比如有 10000 个数据,那第一次就会发送 5000 个请求,网络拥堵了,我想控制成只能同时发送 10 个请求怎么办?

更进一步: 控制并行数

如果需要控制并行数,则可以先实现一个 Promise.map 用以控制并发,这也是在面试中经常考察的一个点。使用 Promise.map 来代替上一步的 Promise.all

关于 Promise.map 的 API 可以参考 bluebird: new Promise(function(function resolve, function reject) resolver) -> Promise

与上一步相同,使用 sum 迭代该函数继续二分,直到最后只有一个数值。

点我查看详细
js
// 并发
async function sum(arr) {
  if (arr.length === 1) return arr[0]
  const promises = chunk(arr, 2).map(([x, y]) =>
    // 注意此时单数的情况
    y === undefined ? x : add(x, y)
  )
  return Promise.all(promises).then((list) => sum(list))
}

关于 Promise.map 还有一个更简单的实现,可参考 async-pool

详细参见 async-pool 解析

参考