前端日记

面试官：说说你对快速排序的理解？如何实现？应用场景？ 一、是什么快速排序（Quick Sort）算法是在冒泡排序的基础上进行改进的一种算法，从名字上看就知道该排序算法的特点是快、效率高，是处理大数据最快的排序算法之一 实现的基本思想是：通过一次排序将整个无序表分成相互独立的两部分，其中一部分中的数据都比另一部分中包含的数据的值小 然后继续沿用此方法分别对两部分进行同样的操作，直到每一个小部分不可再分，所得到的整个序列就变成有序序列 例如，对无序表49，38，65，97，76，13，27，49进行快速排序，大致过程为： 首先从表中选取一个记录的关键字作为分割点（称为“枢轴”或者支点，一般选择第一个关键字），例如选取 49 将表格中大于 49 个放置于 49 的右侧，小于 49 的放置于 49 的左侧，假设完成后的无序表为：{27，38，13，49，65，97，76，49} 以 49 为支点，将整个无序表分割成了两个部分，分别为{27，38，13}和{65，97，76，49}，继续采用此种方法分别对两个子表进行排序 前部分子表以 27 为支点，排序后的子表为{13，27，38}， ...

面试官：说说你对选择排序的理解？如何实现？应用场景？ 一、是什么选择排序（Selection sort）是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度，所以用到它的时候，数据规模越小越好 其基本思想是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置 然后再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾 以此类推，直到所有元素均排序完毕 举个例子，一个数组为 56、12、80、91、29，其排序过程如下： 第一次遍历时，从下标为 1 的位置即 56 开始，找出关键字值最小的记录 12，同下标为 0 的关键字 56 交换位置。此时数组为 12、56、80、91、20 第二次遍历时，从下标为 2 的位置即 56 开始，找出最小值 20，同下标为 2 的关键字 56 互换位置，此时数组为12、20、80、91、56 第三次遍历时，从下标为 3 的位置即 80 开始，找出最小值 56，同下标为 3 的关键字 80 互换位置，此时数组为 12、20、56、91、80 第四次遍历时，从下标为 ...

面试官：说说你对集合的理解？常见的操作有哪些？ 一、是什么集合（Set），指具有某种特定性质的事物的总体，里面的每一项内容称作元素 在数学中，我们经常会遇到集合的概念： 有限集合：例如一个班集所有的同学构成的集合 无限集合：例如全体自然数集合 在计算机中集合道理也基本一致，具有三大特性： 确定性：于一个给定的集合，集合中的元素是确定的。即一个元素，或者属于该集合，或者不属于该集合，两者必居其一 无序性：在一个集合中，不考虑元素之间的顺序，只要元素完全相同，就认为是同一个集合 互异性：集合中任意两个元素都是不同的 二、操作在ES6中，集合本身是一个构建函数Set，用来生成 Set 数据结构，如下： 1const s = new Set(); 关于集合常见的方法有： add()：增 delete()：删 has()：改 clear()：查 add()添加某个值，返回 Set 结构本身 当添加实例中已经存在的元素，set不会进行处理添加 1s.add(1).add(2).add(2); // 2只被添加了一次 体现了集合的互异性特性 delete()删除某个值，返回一个布尔 ...

面试官：说说常见的排序算法有哪些？区别？ 一、是什么排序是程序开发中非常常见的操作，对一组任意的数据元素经过排序操作后，就可以把他们变成一组一定规则排序的有序序列 排序算法属于算法中的一种，而且是覆盖范围极小的一种，彻底掌握排序算法对程序开发是有很大的帮助的 对与排序算法的好坏衡量，主要是从时间复杂度、空间复杂度、稳定性 时间复杂度、空间复杂度前面已经讲过，这里主要看看稳定性的定义 稳定性指的是假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变 即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的 二、有哪些常见的算法排序算法有： 冒泡排序 选择排序 插入排序 归并排序 快速排序 冒泡排序一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来 思路如下： 比较相邻的元素，如果第一个比第二个大，就交换它们两个 对每一对相邻元素作同样的工作，从开始第一对到结尾的最 ...

面试官：说说你对栈、队列的理解？应用场景？ 一、栈栈（stack）又名堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表 表尾这一端被称为栈顶，相反地另一端被称为栈底，向栈顶插入元素被称为进栈、入栈、压栈，从栈顶删除元素又称作出栈 所以其按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据，具有记忆作用 关于栈的简单实现，如下： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class Stack { constructor() { this.items = []; } /** * 添加一个（或几个）新元素到栈顶 * @param {*} element 新元素 */ push(element) { this.items.push(element) } /** * 移除栈顶的元素 ...

面试官：说说你对数据结构的理解？有哪些？区别？ 一、是什么数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合 前面讲到，一个程序 = 算法 + 数据结构，数据结构是实现算法的基础，选择合适的数据结构可以带来更高的运行或者存储效率 数据元素相互之间的关系称为结构，根据数据元素之间关系的不同特性，通常有如下四类基本的结构： 集合结构：该结构的数据元素间的关系是“属于同一个集合” 线性结构：该结构的数据元素之间存在着一对一的关系 树型结构：该结构的数据元素之间存在着一对多的关系 图形结构：该结构的数据元素之间存在着多对多的关系，也称网状结构 由于数据结构种类太多，逻辑结构可以再分成为： 线性结构：有序数据元素的集合，其中数据元素之间的关系是一对一的关系，除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的 非线性结构：各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生关联 二、有哪些常见的数据结构有如下： 数组 栈 队列 链表 树 图 堆 散列表 数组在程序设计中，为了处理方便， 一般情 ...

面试官：说说你对算法中时间复杂度，空间复杂度的理解？如何计算？ 一、前言算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别 衡量不同算法之间的优劣主要是通过时间和空间两个维度去考量： 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述 通常会遇到一种情况，时间和空间维度不能够兼顾，需要在两者之间取得一个平衡点是我们需要考虑的 一个算法通常存在最好、平均、最坏三种情况，我们一般关注的是最坏情况 最坏情况是算法运行时间的上界，对于某些算法来说，最坏情况出现的比较频繁，也意味着平均情况和最坏情况一样差 二、时间复杂度时间复杂度是指执行这个算法所需要的计算工作量，其复杂度反映了程序执行时间「随输入规模增长而增长的量级」，在很大程度上能很好地反映出算法的优劣与否 一个算法花费的时间与算法中语句的「执行次数成正比」，执行次数越多，花费的时间就越多 算法的复杂度通常用大O符号 ...

面试官：说说你对树的理解？相关的操作有哪些？ 一、是什么在计算机领域，树形数据结构是一类重要的非线性数据结构，可以表示数据之间一对多的关系。以树与二叉树最为常用，直观看来，树是以分支关系定义的层次结构 二叉树满足以下两个条件： 本身是有序树 树中包含的各个结点的不能超过 2，即只能是 0、1 或者 2 如下图，左侧的为二叉树，而右侧的因为头结点的子结点超过2，因此不属于二叉树： 同时，二叉树可以继续进行分类，分成了满二叉树和完成二叉树： 满二叉树：如果二叉树中除了叶子结点，每个结点的度都为 2 完成二叉树：如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布 二、操作关于二叉树的遍历，常见的有： 前序遍历 中序遍历 后序遍历 层序遍历 前序遍历前序遍历的实现思想是： 访问根节点 访问当前节点的左子树 若当前节点无左子树，则访问当前节点的右子 根据遍历特性，递归版本用代码表示则如下： 123456const preOrder = (root) => { if(!root){ return } ...

面试官：说说微信小程序的实现原理？ 一、背景 网页开发，渲染线程和脚本是互斥的，这也是为什么长时间的脚本运行可能会导致页面失去响应的原因，本质就是我们常说的 JS 是单线程的 而在小程序中，选择了 Hybrid 的渲染方式，将视图层和逻辑层是分开的，双线程同时运行，视图层的界面使用 WebView 进行渲染，逻辑层运行在 JSCore 中 渲染层：界面渲染相关的任务全都在 WebView 线程里执行。一个小程序存在多个界面，所以渲染层存在多个 WebView 线程 逻辑层：采用 JsCore 线程运行 JS 脚本，在这个环境下执行的都是有关小程序业务逻辑的代码 二、通信 小程序在渲染层，宿主环境会把wxml转化成对应的JS对象 在逻辑层发生数据变更的时候，通过宿主环境提供的setData方法把数据从逻辑层传递到渲染层，再经过对比前后差异，把差异应用在原来的Dom树上，渲染出正确的视图 当视图存在交互的时候，例如用户点击你界面上某个按钮，这类反馈应该通知给开发者的逻辑层，需要将对应的处理状态呈现给用户 对于事件的分发处理，微信进行了特殊的处理 ...

面试官：说说你对微信小程序的理解？优缺点？ 一、是什么2017年，微信正式推出了小程序，允许外部开发者在微信内部运行自己的代码，开展业务 截至目前，小程序已经成为国内前端的一个重要业务，跟 Web 和手机 App 有着同等的重要性 小程序是一种不需要下载安装即可使用的应用，它实现了应用“触手可及”的梦想，用户扫一扫或者搜一下即可打开应用 也体现了“用完即走”的理念，用户不用关心是否安装太多应用的问题。应用将无处不在，随时可用，但又无需安装卸载 注意的是，除了微信小程序，还有百度小程序、微信小程序、支付宝小程序、抖音小程序，都是每个平台自己开发的，都是有针对性平台的应用程序 二、背景⼩程序并⾮凭空冒出来的⼀个概念，当微信中的 WebView 逐渐成为移动 Web的⼀个重要⼊⼝时，微信就有相关的 JS-SDK JS-SDK 解决了移动⽹⻚能⼒不⾜的问题，通过暴露微信的接⼝使得 Web 开发者能够拥有更多的能⼒，然⽽在更多的能⼒之外，JS-SDK的模式并没有解决使⽤移动⽹⻚遇到的体验不良的问题 因此需要设计⼀个⽐较好的系统，使得所有开发者在微信中都能获得⽐较好的体验： 快速的加载 更 ...