高级前端面试手写扁平数据结构转Tree

目录
  • 前言
  • 什么是好算法,什么是坏算法
    • 时间复杂度
    • 计算方法
    • 空间复杂度
    • 计算方法:
  • 不考虑性能实现,递归遍历查找
  • 不用递归,也能搞定
  • 最优性能
  • 小试牛刀

前言

招聘季节一般都在金三银四,或者金九银十。最近在这五六月份,陆陆续续面试了十几个高级前端。有一套考察算法的小题目。后台返回一个扁平的数据结构,转成树。

我们看下题目:打平的数据内容如下:

let arr = [
    {id: 1, name: '部门1', pid: 0},
    {id: 2, name: '部门2', pid: 1},
    {id: 3, name: '部门3', pid: 1},
    {id: 4, name: '部门4', pid: 3},
    {id: 5, name: '部门5', pid: 4},
]

输出结果

[
    {
        "id": 1,
        "name": "部门1",
        "pid": 0,
        "children": [
            {
                "id": 2,
                "name": "部门2",
                "pid": 1,
                "children": []
            },
            {
                "id": 3,
                "name": "部门3",
                "pid": 1,
                "children": [
                    // 结果 ,,,
                ]
            }
        ]
    }
]

我们的要求很简单,可以先不用考虑性能问题。实现功能即可,回头分析了面试的情况,结果使我大吃一惊。

10%的人没思路,没碰到过这种结构

60%的人说用过递归,有思路,给他个笔记本,但就是写不出来

20%的人在引导下,磕磕绊绊能写出来

剩下10%的人能写出来,但性能不是最佳

感觉不是在招聘季节遇到一个合适的人真的很难。

接下来,我们用几种方法来实现这个小算法

什么是好算法,什么是坏算法

判断一个算法的好坏,一般从执行时间和占用空间来看,执行时间越短,占用的内存空间越小,那么它就是好的算法。对应的,我们常常用时间复杂度代表执行时间,空间复杂度代表占用的内存空间。

时间复杂度

时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的次数。

随着n的不断增大,时间复杂度不断增大,算法花费时间越多。 常见的时间复杂度有

  • 常数阶O(1)
  • 对数阶O(log2 n)
  • 线性阶O(n)
  • 线性对数阶O(n log2 n)
  • 平方阶O(n^2)
  • 立方阶O(n^3)
  • k次方阶O(n^K)
  • 指数阶O(2^n)

计算方法

  • 选取相对增长最高的项
  • 最高项系数是都化为1
  • 若是常数的话用O(1)表示

举个例子:如f(n)=3*n^4+3n+300 则 O(n)=n^4

通常我们计算时间复杂度都是计算最坏情况。计算时间复杂度的要注意的几个点

  • 如果算法的执行时间不随n的增加而增长,假如算法中有上千条语句,执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 举例如下:代码执行100次,是一个常数,复杂度也是O(1)。
    let x = 1;
    while (x <100) {
     x++;
    }
  • 有多个循环语句时候,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的方法决定的。举例如下:在下面for循环当中,外层循环每执行一次,内层循环要执行n次,执行次数是根据n所决定的,时间复杂度是O(n^2)。
  for (i = 0; i < n; i++){
         for (j = 0; j < n; j++) {
             // ...code
         }
     }
  • 循环不仅与n有关,还与执行循环判断条件有关。举例如下:在代码中,如果arr[i]不等于1的话,时间复杂度是O(n)。如果arr[i]等于1的话,循环不执行,时间复杂度是O(0)。
    for(var i = 0; i<n && arr[i] !=1; i++) {
    // ...code
    }

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间的大小。

计算方法:

  • 忽略常数,用O(1)表示
  • 递归算法的空间复杂度=(递归深度n)*(每次递归所要的辅助空间)

计算空间复杂度的简单几点

仅仅只复制单个变量,空间复杂度为O(1)。举例如下:空间复杂度为O(n) = O(1)。

   let a = 1;
   let b = 2;
   let c = 3;
   console.log('输出a,b,c', a, b, c);

递归实现,调用fun函数,每次都创建1个变量k。调用n次,空间复杂度O(n*1) = O(n)。

    function fun(n) {
       let k = 10;
       if (n == k) {
           return n;
       } else {
           return fun(++n)
       }
    }

不考虑性能实现,递归遍历查找

主要思路是提供一个递getChildren的方法,该方法递归去查找子集。 就这样,不用考虑性能,无脑去查,大多数人只知道递归,就是写不出来。。。

/**
 * 递归查找,获取children
 */
const getChildren = (data, result, pid) => {
  for (const item of data) {
    if (item.pid === pid) {
      const newItem = {...item, children: []};
      result.push(newItem);
      getChildren(data, newItem.children, item.id);
    }
  }
}
/**
* 转换方法
*/
const arrayToTree = (data, pid) => {
  const result = [];
  getChildren(data, result, pid)
  return result;
}

从上面的代码我们分析,该实现的时间复杂度为O(2^n)。

不用递归,也能搞定

主要思路是先把数据转成Map去存储,之后遍历的同时借助对象的引用,直接从Map找对应的数据做存储

function arrayToTree(items) {
  const result = [];   // 存放结果集
  const itemMap = {};  //
  // 先转成map存储
  for (const item of items) {
    itemMap[item.id] = {...item, children: []}
  }
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;
    const treeItem =  itemMap[id];
    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }
  }
  return result;
}

从上面的代码我们分析,有两次循环,该实现的时间复杂度为O(2n),需要一个Map把数据存储起来,空间复杂度O(n)

最优性能

主要思路也是先把数据转成Map去存储,之后遍历的同时借助对象的引用,直接从Map找对应的数据做存储。不同点在遍历的时候即做Map存储,有找对应关系。性能会更好。

function arrayToTree(items) {
  const result = [];   // 存放结果集
  const itemMap = {};  //
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;
    if (!itemMap[id]) {
      itemMap[id] = {
        children: [],
      }
    }
    itemMap[id] = {
      ...item,
      children: itemMap[id]['children']
    }
    const treeItem =  itemMap[id];
    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }
  }
  return result;
}

从上面的代码我们分析,一次循环就搞定了,该实现的时间复杂度为O(n),需要一个Map把数据存储起来,空间复杂度O(n)

小试牛刀

方法 1000(条) 10000(条) 20000(条) 50000(条)
递归实现 154.596ms 1.678s 7.152s 75.412s
不用递归,两次遍历 0.793ms 16.499ms 45.581ms 97.373ms
不用递归,一次遍历 0.639ms 6.397ms 25.436ms 44.719ms

从我们的测试结果来看,随着数量的增大,递归的实现会越来越慢,基本成指数的增长方式。

以上就是高级前端面试手写扁平数据结构转Tree的详细内容,更多关于扁平数据结构转Tree的资料请关注我们其它相关文章!

(0)

相关推荐

  • 2019年度web前端面试题总结(主要为Vue面试题)

    毕业之后就在一直合肥小公司工作,没有老司机.没有技术氛围,在技术的道路上我只能独自摸索.老板也只会画饼充饥,前途一片迷茫看不到任何希望.于是乎,我果断辞职,在新年开工之际来到杭州,这里的互联网公司应该是合肥的几十倍吧.... 刚来3天,面试了几家公司,有些规模比较小,有些是创业公司,也有些已经发展的不错了:今天把最近的面试题目做个汇总,也给自己复个盘,由于我的技术栈主要为Vue,所以大部分题目都是Vue开发相关的. 1. 谈谈你对MVVM开发模式的理解 MVVM分为Model.View.View

  • JS前端面试必备——基本排序算法原理与实现方法详解【插入/选择/归并/冒泡/快速排序】

    本文实例讲述了JS前端面试必备--基本排序算法原理与实现方法.分享给大家供大家参考,具体如下: 排序算法是面试及笔试中必考点,本文通过动画方式演示,通过实例讲解,最后给出JavaScript版的排序算法 插入排序 算法描述: 1. 从第一个元素开始,该元素可以认为已经被排序 2. 取出下一个元素,在已经排序的元素序列中从后向前扫描 3. 如果该元素(已排序)大于新元素,将该元素移到下一位置 4. 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置 5. 将新元素插入到该位置后 6. 重复

  • JS一次前端面试经历记录

    本文实例讲述了JS一次前端面试经历.分享给大家供大家参考,具体如下: 最近公司在做一些战略调整,部门有不少老员工前辈们都陆陆续续的离职或者被离职了.而我所在的团队--网易菠萝,也被归并到游戏运营中心了.因为产品策划还没有出来.暂时没什么需求做,闲得有点e-g-g疼的,每天从早到晚都是待在公司看看书.刷刷知乎等.我真是命途多舛啊,还没有真正步入社会,就见证了一个上百人的事业部说没落就没落.甚至已看破红尘,连参加省公务员考试的计划都做好了.这可不是开玩笑的哈,已经在报名费和复习资料上花了两三百块啦,

  • JS中的算法与数据结构之二叉查找树(Binary Sort Tree)实例详解

    本文实例讲述了JS中的算法与数据结构之二叉查找树(Binary Sort Tree).分享给大家供大家参考,具体如下: 二叉查找树(Binary Sort Tree) 我们之前所学到的列表,栈等都是一种线性的数据结构,今天我们将学习计算机中经常用到的一种非线性的数据结构--树(Tree),由于其存储的所有元素之间具有明显的层次特性,因此常被用来存储具有层级关系的数据,比如文件系统中的文件:也会被用来存储有序列表等. 在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的

  • 「中高级前端面试」JavaScript手写代码无敌秘籍(推荐)

    1. 实现一个new操作符 new操作符做了这些事: 它创建了一个全新的对象. 它会被执行[[Prototype]](也就是__proto__)链接. 它使this指向新创建的对象.. 通过new创建的每个对象将最终被[[Prototype]]链接到这个函数的prototype对象上. 如果函数没有返回对象类型Object(包含Functoin, Array, Date, RegExg, Error),那么new表达式中的函数调用将返回该对象引用. function New(func) { va

  • 高级前端面试手写扁平数据结构转Tree

    目录 前言 什么是好算法,什么是坏算法 时间复杂度 计算方法 空间复杂度 计算方法: 不考虑性能实现,递归遍历查找 不用递归,也能搞定 最优性能 小试牛刀 前言 招聘季节一般都在金三银四,或者金九银十.最近在这五六月份,陆陆续续面试了十几个高级前端.有一套考察算法的小题目.后台返回一个扁平的数据结构,转成树. 我们看下题目:打平的数据内容如下: let arr = [ {id: 1, name: '部门1', pid: 0}, {id: 2, name: '部门2', pid: 1}, {id:

  • JS前端面试手写apply和bind实例

    目录 前言 apply && bind apply && bind 作用 相同点 VS 不同点 轻松手写 手写实现 apply 手写实现 bind 总结 前言 面试官问:“聊一聊你理解的 apply 和 bind.” 于是我便开始开始介绍起这两个知识点,最后顺带提了它们的实现代码. 这不提倒还好,一提就出了大事,一下子给面试官找到了面试题目. 面试官紧接着说:“既然你提到了代码,那就手写一下它俩吧.” 我一下子不知所措.虽然我了解过 apply 和 bind 手写代码,但是

  • 面试手写实现Promise.all

    目录 前言 常见面试手写系列 Promise.resolve 简要回顾 源码实现 Promise.reject 简要回顾 源码实现 Promise.all 简要回顾 源码实现 Promise.allSettled 简要回顾 源码实现 Promise.race 简单回顾 源码实现 结尾 前言 (ಥ﹏ಥ)曾经真实发生在一个朋友身上的真实事件,面试官让他手写一个Promise.all,朋友现场发挥不太好,没有写出来,事后他追问面试官给的模糊评价是基础不够扎实,原理性知识掌握较少... 当然整场面试失利

  • JS前端html2canvas手写示例问题剖析

    目录 前言 感性认识 第一步:解析 dom 树 第二步:按层叠规则分组(重点) 第三步:创建画布 第四步:渲染 另一种方法(html->svg->canvas) 结语 前言 这两天把 html2canvas 这玩意抽丝剥茧了一下,搞了个勉强能跑的小 demo,麻雀虽小五脏俱全,来看看实现的效果吧(跟基金一样的绿,离离原上谱)

  • 手写实现JS中的new

    目录 1 new 运算符简介 2 new 究竟干了什么事 3 模拟实现 new 运算符 4 补充 ⚠ 预备知识: 了解原型和原型链 了解this绑定 1 new 运算符简介 MDN文档:new 运算符创建一个用户定义的对象类型的实例或具有构造函数的内置对象的实例. class Person { constructor(name) { this.name = name; } } // 创建自定义对象类型的实例 const person = new Person('小明') // 创建具有构造函数的

  • JS前端面试数组扁平化手写flat函数示例

    目录 前言 题目 实现扁平化的方法 封装 flatten 1. ES6 flat 2. toString 3. 使用正则替换 4. 循环递归 4.1 循环 + concat + push 4.2 增加参数控制扁平化深度 4.3 巧用 reduce 4.4 使用 Generator 函数 5. 使用堆栈 stack 避免递归 6.while 循环+ some方法 前言 由于上半年参加了校招的技术面试, 前前后后面了20多个人了, 每次面试都会让应聘者手写一下数组扁平化flat(),但是发现居然没有

  • 前端面试JavaScript高频手写大全

    目录 1. 手写instanceof 2. 实现数组的map方法 3. reduce实现数组的map方法 4. 手写数组的reduce方法 5. 数组扁平化 5. 1 es6提供的新方法 flat(depth) 5.2 利用cancat 6. 函数柯里化 7. 浅拷贝和深拷贝的实现 7.1浅拷贝和深拷贝的区别 8. 手写call, apply, bind 8.1 手写call 8.2 手写apply(arguments[this, [参数1,参数2.....] ]) 8.3 手写bind 9.

  • JavaScript前端面试扁平数据转tree与tree数据扁平化

    目录 一.写在前面 二.正文部分 2.1 扁平数据转为 tree 数据 2.2 tree 数据转为扁平数据 2.3 完整测试 demo 三.写在后面 一.写在前面 有时我们拿到的数据的数据结构可能不是理想的,那么此时就要求前端程序员,具有改造数据的能力.例如拿到扁平的数据, 但我们要应用在 tree 树形组件或 Cascader 级联选择器组件中,这样的组件要求数据结构是非扁平的的具有层级递进关系的 tree 结构. 总之就是说,提供数据的接口给到的数据,未必符合要求,而当我们又无法令他人为为我

  • 手写 Vue3 响应式系统(核心就一个数据结构)

    目录 前言 响应式 总结 前言 响应式是 Vue 的特色,如果你简历里写了 Vue 项目,那基本都会问响应式实现原理.而且不只是 Vue,状态管理库 Mobx 也是基于响应式实现的.那响应式是具体怎么实现的呢?与其空谈原理,不如让我们来手写一个简易版吧. 响应式 首先,什么是响应式呢? 响应式就是被观察的数据变化的时候做一系列联动处理.就像一个社会热点事件,当它有消息更新的时候,各方媒体都会跟进做相关报道.这里社会热点事件就是被观察的目标.那在前端框架里,这个被观察的目标是什么呢?很明显,是状态

随机推荐