专栏首页BFE.dev前端刷题日记Facebook面试题: 用递归和迭代手写Array.prototype.flat()
原创

Facebook面试题: 用递归和迭代手写Array.prototype.flat()

题目来源: bigfrontend.dev/problem/imp…

手写 Array.prototype.flat() 看似简单,但是Facebook面试一轮通常有两道题目,也就是说要在15分钟之内写出bugfree的代码,加上现场的紧张已经还要求清晰的思路表达,还是有挑战的。

题目

我们需要实现flat()来去掉括号,层数由第二个参数来指定

const arr = [1, [2], [3, [4]]];
flat(arr)
// [1, 2, 3, [4]]
flat(arr, 1)
// [1, 2, 3, [4]]
flat(arr, 2)
// [1, 2, 3, 4]
复制代码

递归

用recursion比较简单了,便利数组做如下操作即可:

  1. 如果碰到了array,就先用flat() 去掉它的括号,然后收集结果
  2. 如果碰到的不是array,就收集结果

用以上想法就可以简单地得到以下代码。

function flat(arr, depth = 1) {
  const result = []
  for (let item of arr) {
    if (Array.isArray(item) && depth > 0) {
      result.push(...flat(item, depth - 1))
    } else {
      result.push(item)
    }
  }
  return result
}
复制代码

用reduce重写

有一个result,有一个for loop,那就可以用reduce玩一点花样出来。 不过这个并不没什么卵用,不是本质上的变化。

function flat(arr, depth = 1) {
  return arr.reduce((result, item) => {
    if (Array.isArray(item) && depth > 0) {
      result.push(...flat(item, depth - 1))
    } else {
      result.push(item)
    }
    return result
  }, [])
}

复制代码

迭代

刷过面试题都知道,遇到递归就要尝试一下用迭代来写,可以说必考了。

我们先手写一下去掉括号的过程。左边是目标array,右边是结果array。

[1, [2], [3, [4]]]  => []
复制代码

从左往右,碰到了1,不是array,直接放入结果

[[2], [3, [4]]] => [1]
复制代码

下一个是 [2],是array,去掉括号,重新放回原来的数组。

[2, [3, [4]]] => [1]
复制代码

下一个是2,不是array,放入结果

[[3, [4]]] => [1,2]
复制代码

重复上述过程,我们得到以下中间结果。

[3, [4]] => [1,2]
[[4]] => [1,2,3]
[4] => [1,2,3]
[] => [1,2,3,4]
复制代码

接下来得考虑depth的问题,我们不能见到括号就去掉,所以每个element需要有自己的step,相当于给原数组的element增加了一个depth属性,我们用 [element, depth]来表示。

假设depth是1: 初始状态下所有元素都是depth:1

[[1, 1], [[2], 1], [[3, [4]], 1]] => []
复制代码

下一个element是1,不是array,所以放入结果

[[[2], 1], [[3, [4]], 1]] => [1]
复制代码

下一个element是[2],是array,depth是1,那么它的所有元素的depth设为0,然后重新放回

[[2, 0], [[3, [4]], 1]] => [1]
复制代码

下一个element是2, 不是array,放入结果

[[[3, [4]], 1]] => [1, 2]
复制代码

下一个是 [3,[4]], depth是1,把其中元素放回,depth设为0

[[3,0],[[4],0]] => [1, 2]
复制代码

下一个是3,直接放入结果

[[[4],0]] => [1, 2, 3]
复制代码

下一个是 [4],depth是0,因为是0,所以这个括号没法去掉,把[4]放入结果

[] => [1,2,3,[4]]
复制代码

大功告成。

把上述过程转换微代码,就比较容易了。以下是迭代的解法。

function flat(arr, depth = 1) {
  const result = []
  const stack = [...arr.map(item => ([item, depth]))]
  
  while (stack.length > 0) {
    const [head, depth] = stack.shift()
    if (Array.isArray(head) && depth > 0) {
      stack.unshift(...head.map(item => ([item, depth - 1])))
    } else {
      result.push(head)
    }
  }
  return result
}
复制代码

这里还有一个performance的问题。我们用到了shift/unshift, 实际上是不太好的,因为shift/unshift会触发所有元素的index发生变化。更好的办法是用 push/pop,这样我们得到了一个逆序的结果,最后reverse一下就好。

function flat(arr, depth = 1) {
  const result = []
  const stack = [...arr.map(item => ([item, depth]))]
  
  while (stack.length > 0) {
    const [top, depth] = stack.pop()
    if (Array.isArray(top) && depth > 0) {
      stack.push(...top.map(item => ([item, depth - 1])))
    } else {
      result.push(top)
    }
  }
  
  return result.reverse()
}
复制代码

通过撒花! 如果你有兴趣可以去 BFE.dev 实际挑战一下。

希望能帮助到你!接下来JSer还会带来更多前端面试代码题解析,欢迎关注。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BFE.dev前端刷题 33. 实现Promise.allSettled()

    和Promise.all()不同,Promise.allSettled()即使是遇到rejection也会等待所有的promise到最后。所以我们只需要用一个a...

    JSer
  • BFE.dev前端刷题#108. 用队列(Queue)实现栈(Stack)

    如果我们要pop4的话,因为这是一个队列,我们只能把1 dequeue掉。所以为了要得到4,我们必须要把其余的1,2,3给dequeue掉。dequeue掉的元...

    JSer
  • BFE.dev前端刷题 104. 按层遍历DOM树

    可以看到我们只需要不停的从左边取出元素,然后将其子元素从右边不停放入即可。这用queue实现。

    JSer
  • 微服务之SpringCloud基础

    用户1112962
  • 不要钱还免安装!Photoshop杀手火了,网友:作者是上帝么?

    Adobe这家公司,虽然不时搞出一些惊艳的玩意,但大家对Photoshop一直是又爱又怨:

    量子位
  • SVG - 动画制作

    SVG - 动画制作 HTML5学堂:SVG - 动画制作。上一篇文章讲解了SVG的基本属性,大家能够利用SVG的基本属性进行绘制图像,那么如何让绘制好的图像动...

    HTML5学堂
  • 服务化最佳实践

    建议将服务接口、服务模型、服务异常等均放在 API 包中,因为服务模型和异常也是 API 的一部分,这样做也符合分包原则:重用发布等价原则(REP),共同重用原...

    WindWant
  • cobbler自动安装系统(Centos7.X)

    环境: [root@kickstart ~]# cat /etc/redhat-release CentOS Linux release 7.4.1708 (C...

    863987322
  • 你可能需要的Kafka面试题与部分答案整理

    场景:数据比较集中且实时要求不是太高,如果同步处理,假如业务高峰需要4台服务支撑,那么在业务高峰过了之后,就会出现资源闲置,如果引入消息队列的话,将数据放到消息...

    大数据真好玩
  • NodeJS学习三之API

    版权声明:本文为吴孔云博客原创文章,转载请注明出处并带上链接,谢谢。 https://blog.csdn.net/wkyseo/articl...

    空空云

扫码关注云+社区

领取腾讯云代金券