前端面试重要问题总结（前端100问小结）（十）

第 91 题：介绍下 HTTPS 中间人攻击

题目讨论
https协议由 http + ssl 协议构成，具体的链接过程可参考SSL或TLS握手的概述

中间人攻击过程如下：

服务器向客户端发送公钥。
攻击者截获公钥，保留在自己手上。
然后攻击者自己生成一个【伪造的】公钥，发给客户端。
客户端收到伪造的公钥后，生成加密hash值发给服务器。
攻击者获得加密hash值，用自己的私钥解密获得真秘钥。
同时生成假的加密hash值，发给服务器。
服务器用私钥解密获得假秘钥。
服务器用加秘钥加密传输信息
防范方法：

服务端在发送浏览器的公钥中加入CA证书，浏览器可以验证CA证书的有效性

第 92 题：已知数据格式，实现一个函数 fn 找出链条中所有的父级 id

const value = '112'
const fn = (value) => {
...
}
fn(value) // 输出 [1， 11， 112]

const bfs = data => {
  const queue = [...data]
  let res = []
  while(queue.length) {
    let node = queue.shift()
    if (node.children) {
      for (let child of node.children) {
        queue.push(child)
      }
      res.push(node.id)
    }
  }
  return res
}

第 93 题：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log(m+n))。

nums1 = [1, 3]
nums2 = [2]

中位数是 2.0

nums1 = [1, 2]
nums2 = [3, 4]

中位数是(2 + 3) / 2 = 2.5

var findMedianSortedArrays = function(nums1, nums2) {
  let m = nums1.length
  let n = nums2.length
  let k1 = Math.floor((m + n + 1) / 2)
  let k2 = Math.floor((m + n + 2) / 2)

  return (findMedianSortedArraysCore(nums1, 0, nums2, 0, k1) + findMedianSortedArraysCore(nums1, 0, nums2, 0, k2)) / 2
};

const findMedianSortedArraysCore = (nums1, i, nums2, j, k)  => {
  // 如果数组起始位置已经大于数组长度-1
  // 说明已经是个空数组
  // 直接从另外一个数组里取第k个数即可
  if (i > nums1.length - 1) {
    return nums2[j + k - 1]
  }
  if (j > nums2.length - 1) {
    return nums1[i + k - 1]
  }
  // 如果k为1
  // 就是取两个数组的起始值里的最小值
  if (k === 1) {
    return Math.min(nums1[i], nums2[j])
  }
  // 取k2为(k/2)或者数组1的长度或者数组2的长度的最小值
  // 这一步可以避免k2大于某个数组的长度（长度为从起始坐标到结尾）
  let k2 = Math.floor(k / 2)
  let length1 = nums1.length - i
  let length2 = nums2.length - j
  k2 = Math.min(k2, length1, length2)

  let value1 = nums1[i + k2 - 1]
  let value2 = nums2[j + k2 - 1]

  // 比较两个数组的起始坐标的值
  // 如果value1小于value2
  // 就舍弃nums1前i + k2部分
  // 否则舍弃nums2前j + k2部分
  if (value1 < value2) {
    return findMedianSortedArraysCore(nums1, i + k2, nums2, j, k - k2)
  } else {
    return findMedianSortedArraysCore(nums1, i, nums2, j + k2, k - k2)
  }
}

第 94 题：vue 在 v-for 时给每项元素绑定事件需要用事件代理吗？为什么？

说一下我个人理解，先说结论，可以使用

事件代理作用主要是 2 个

1.将事件处理程序代理到父节点，减少内存占用率
2.动态生成子节点时能自动绑定事件处理程序到父节点

这里我生成了十万个 span 节点，通过 performance monitor 来监控内存占用率和事件监听器的数量，对比以下 3 种情况
1.不使用事件代理，每个 span 节点绑定一个 click 事件，并指向同一个事件处理程序

  <div>
      <span 
        v-for="(item,index) of 100000" 
        :key="index" 
        @click="handleClick">
        {{item}}
      </span>
    </div>

2.不使用事件代理，每个 span 节点绑定一个 click 事件，并指向不同的事件处理程序

 <div>
      <span 
        v-for="(item,index) of 100000" 
        :key="index" 
        @click="function () {}">
        {{item}}
      </span>
    </div>

3.使用事件代理

<div  @click="handleClick">
      <span 
        v-for="(item,index) of 100000"  
        :key="index">
        {{item}}
      </span>
    </div>

可以看到使用事件代理无论是监听器数量和内存占用率都比前两者要少

同时对比 3 个图中监听器的数量以及我以往阅读 vue 源码的过程中，并没有发现 vue 会自动做事件代理，但是一般给 v-for 绑定事件时，都会让节点指向同一个事件处理程序（第二种情况可以运行，但是 eslint 会警告），一定程度上比每生成一个节点都绑定一个不同的事件处理程序性能好，但是监听器的数量仍不会变，所以使用事件代理会更好一点

第 95 题：模拟实现一个深拷贝，并考虑对象相互引用以及 Symbol 拷贝的情况

题目讨论
一个不考虑其他数据类型的公共方法，基本满足大部分场景

function deepCopy(target, cache = new Set()) {
  if (typeof target !== 'object' || cache.has(target)) {
    return target
  }
  if (Array.isArray(target)) {
    target.map(t => {
      cache.add(t)
      return t
    })
  } else {
    return [...Object.keys(target), ...Object.getOwnPropertySymbols(target)].reduce((res, key) => {
      cache.add(target[key])
      res[key] = deepCopy(target[key], cache)
      return res
    }, target.constructor !== Object ? Object.create(target.constructor.prototype) : {})
  }
}

主要问题是

1.symbol作为key，不会被遍历到，所以stringify和parse是不行的
2.有环引用，stringify和parse也会报错

我们另外用getOwnPropertySymbols可以获取symbol key可以解决问题1，用集合记忆曾经遍历过的对象可以解决问题2。当然，还有很多数据类型要独立去拷贝。比如拷贝一个RegExp，lodash是最全的数据类型拷贝了，有空可以研究一下

另外，如果不考虑用symbol做key，还有两种黑科技深拷贝，可以解决环引用的问题，比stringify和parse优雅强一些

function deepCopyByHistory(target) {
  const prev = history.state
  history.replaceState(target, document.title)
  const res = history.state
  history.replaceState(prev, document.title)
  return res
}

async function deepCopyByMessageChannel(target) {
  return new Promise(resolve => {
    const channel = new MessageChannel()
    channel.port2.onmessage = ev => resolve(ev.data)
    channel.port1.postMessage(target)
  }).then(data => data)
}

无论哪种方法，它们都有一个共性：失去了继承关系，所以剩下的需要我们手动补上去了，故有Object.create(target.constructor.prototype)的操作

第二种方法

 const symbolName = Symbol();
  const obj = {
    objNumber: new Number(1),
    number: 1,
    objString: new String('ss'),
    string: 'stirng',
    objRegexp: new RegExp('\\w'),
    regexp: /w+/g,
    date: new Date(),
    function: function () {},
    array: [{a: 1}, 2],
    [symbolName]: 111
  }
  obj.d = obj;

  const isObject = obj => obj !== null && (typeof obj === 'object' || typeof obj === 'function');
  const isFunction = obj => typeof obj === 'function'
  function deepClone (obj, hash = new WeakMap()) {
    if (hash.get(obj)) {
      // 环处理
      return hash.get(obj);
    }
    if (!isObject(obj)) {
      return obj;
    }

    if (isFunction(obj)) {
      // function返回原引用
      return obj;
    }

    let cloneObj;

    const Constructor = obj.constructor;

    switch (Constructor) {
      case Boolean:
      case Date:
        return new Date(+obj);
      case Number:
      case String:
      case RegExp:
        return new Constructor(obj);
      default:
        cloneObj = new Constructor();
        hash.set(obj, cloneObj);
    }

    [...Object.getOwnPropertyNames(obj), ...Object.getOwnPropertySymbols(obj)].forEach(k => {
      cloneObj[k] = deepClone(obj[k], hash);
    })
    return cloneObj;
  }
  

  const o = deepClone(obj)
  console.log(o.objNumber === obj.objNumber);
  console.log(o.number === obj.number);
  console.log(o.objString === obj.objString);
  console.log(o.string === obj.string);
  console.log(o.objRegexp === obj.objRegexp);
  console.log(o.regexp === obj.regexp);
  console.log(o.date === obj.date);
  console.log(o.function === obj.function);
  console.log(o.array[0] === obj.array[0]);
  console.log(o[symbolName] === obj[symbolName]);

第 96 题：介绍下前端加密的常见场景和方法

题目讨论
首先，加密的目的，简而言之就是将明文转换为密文、甚至转换为其他的东西，用来隐藏明文内容本身，防止其他人直接获取到敏感明文信息、或者提高其他人获取到明文信息的难度。
通常我们提到加密会想到密码加密、HTTPS 等关键词，这里从场景和方法分别提一些我的个人见解。

场景-密码传输

前端密码传输过程中如果不加密，在日志中就可以拿到用户的明文密码，对用户安全不太负责。
这种加密其实相对比较简单，可以使用 PlanA-前端加密、后端解密后计算密码字符串的MD5/MD6存入数据库；也可以 PlanB-直接前端使用一种稳定算法加密成唯一值、后端直接将加密结果进行MD5/MD6，全程密码明文不出现在程序中。
PlanA
使用 Base64 / Unicode+1 等方式加密成非明文，后端解开之后再存它的 MD5/MD6 。

PlanB
直接使用 MD5/MD6 之类的方式取 Hash ，让后端存 Hash 的 Hash 。

场景-数据包加密

应该大家有遇到过：打开一个正经网站，网站底下蹦出个不正经广告——比如X通的流量浮层，X信的插入式广告……（我没有针对谁）
但是这几年，我们会发现这种广告逐渐变少了，其原因就是大家都开始采用 HTTPS 了。
被人插入这种广告的方法其实很好理解：你的网页数据包被抓取->在数据包到达你手机之前被篡改->你得到了带网页广告的数据包->渲染到你手机屏幕。
而 HTTPS 进行了包加密，就解决了这个问题。严格来说我认为从手段上来看，它不算是一种前端加密场景；但是从解决问题的角度来看，这确实是前端需要知道的事情。

Plan
全面采用 HTTPS

场景-展示成果加密

经常有人开发网页爬虫爬取大家辛辛苦苦一点一点发布的数据成果，有些会影响你的竞争力，有些会降低你的知名度，甚至有些出于恶意爬取你的公开数据后进行全量公开……比如有些食谱网站被爬掉所有食谱，站点被克隆；有些求职网站被爬掉所有职位，被拿去卖信息；甚至有些小说漫画网站赖以生存的内容也很容易被爬取。

Plan
将文本内容进行展示层加密，利用字体的引用特点，把拿给爬虫的数据变成“乱码”。
举个栗子：正常来讲，当我们拥有一串数字“12345”并将其放在网站页面上的时候，其实网站页面上显示的并不是简单的数字，而是数字对应的字体的“12345”。这时我们打乱一下字体中图形和字码的对应关系，比如我们搞成这样：

图形：1 2 3 4 5
字码：2 3 1 5 4

这时，如果你想让用户看到“12345”，你在页面中渲染的数字就应该是“23154”。这种手段也可以算作一种加密。
具体的实现方法可以看一下《Web 端反爬虫技术方案》。
参考
HTTPS 到底加密了什么？
Web 端反爬虫技术方案
可以说的秘密-那些我们该讨论的前端加密方法
前端加密那点事
关于反爬虫，看这一篇就够了

第 97 题：React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的？

问题描述

原问题标题“React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的？ ”

这里的n指的是页面的VDOM节点数，这个不太严谨。如果更严谨一点，我们应该应该假设
变化之前的节点数为m，变化之后的节点数为n。

React 和 Vue 做优化的前提是“放弃了最优解“，本质上是一种权衡，有利有弊。

倘若这个算法用到别的行业，比如医药行业，肯定是不行的，为什么？

React 和 Vue 做的假设是：

检测VDOM的变化只发生在同一层
检测VDOM的变化依赖于用户指定的key
如果变化发生在不同层或者同样的元素用户指定了不同的key或者不同元素用户指定同样的key，
React 和 Vue都不会检测到，就会发生莫名其妙的问题。

但是React 认为， 前端碰到上面的第一种情况概率很小，第二种情况又可以通过提示用户，让用户去解决，因此
这个取舍是值得的。 没有牺牲空间复杂度，却换来了在大多数情况下时间上的巨大提升。
明智的选择！

基本概念

首先大家要有个基本概念。
其实这是一个典型的最小编辑距离的问题，相关算法有很多，比如Git中
，提交之前会进行一次对象的diff操作，就是用的这个最小距离编辑算法。
leetcode 有原题目,
如果想明白这个O(n^3)， 可以先看下这个。

对于树，我们也是一样的，我们定义三种操作，用来将一棵树转化为另外一棵树：

• 删除 删除一个节点，将它的children交给它的父节点
• 插入 在children中 插入一个节点
• 修改 修改节点的值

事实上，从一棵树转化为另外一棵树，我们有很多方式，我们要找到最少的。
直观的方式是用动态规划，通过这种记忆化搜索减少时间复杂度。

算法

由于树是一种递归的数据结构，因此最简单的树的比较算法是递归处理。

详细描述这个算法可以写一篇很长的论文，这里不赘述。
大家想看代码的，这里有一份
我希望没有吓到你。

确切地说，树的最小距离编辑算法的时间复杂度是O(n^2m(1+logmn)),
我们假设m 与 n 同阶， 就会变成 O(n^3)。

第 98 题：（京东）写出如下代码的打印结果

function changeObjProperty(o) {
  o.siteUrl = "http://www.baidu.com"
  o = new Object()
  o.siteUrl = "http://www.google.com"
} 
let webSite = new Object();
changeObjProperty(webSite);
console.log(webSite.siteUrl);

function changeObjProperty(o) {
o.siteUrl = "http://www.baidu.com"
o = new Object() // 形参 o 的指向发生改变，指向堆内存中一个新的对象
o.siteUrl = "http://www.google.com"
}
let webSite = new Object();
changeObjProperty(webSite);
console.log(webSite.siteUrl); //"http://www.baidu.com"

函数的形参是值传递的

第 99 题：（bilibili）编程算法题

用 JavaScript 写一个函数，输入 int 型，返回整数逆序后的字符串。如：输入整型 1234，返回字符串“4321”。要求必须使用递归函数调用，不能用全局变量，输入函数必须只有一个参数传入，必须返回字符串。

function fun(num){
    let num1 = num / 10;
    let num2 = num % 10;
    if(num1<1){
        return num;
    }else{
        num1 = Math.floor(num1)
        return `${num2}${fun(num1)}`
    }
}
var a = fun(12345)
console.log(a)
console.log(typeof a)

第 100 题：（京东）请写出如下代码的打印结果

function Foo() {
    Foo.a = function() {
        console.log(1)
    }
    this.a = function() {
        console.log(2)
    }
}
Foo.prototype.a = function() {
    console.log(3)
}
Foo.a = function() {
    console.log(4)
}
Foo.a();
let obj = new Foo();
obj.a();
Foo.a();

function Foo() {
    Foo.a = function() {
        console.log(1)
    }
    this.a = function() {
        console.log(2)
    }
}
// 以上只是 Foo 的构建方法，没有产生实例，此刻也没有执行

Foo.prototype.a = function() {
    console.log(3)
}
// 现在在 Foo 上挂载了原型方法 a ，方法输出值为 3

Foo.a = function() {
    console.log(4)
}
// 现在在 Foo 上挂载了直接方法 a ，输出值为 4

Foo.a();
// 立刻执行了 Foo 上的 a 方法，也就是刚刚定义的，所以
// # 输出 4

let obj = new Foo();
/* 这里调用了 Foo 的构建方法。Foo 的构建方法主要做了两件事：
1. 将全局的 Foo 上的直接方法 a 替换为一个输出 1 的方法。
2. 在新对象上挂载直接方法 a ，输出值为 2。
*/

obj.a();
// 因为有直接方法 a ，不需要去访问原型链，所以使用的是构建方法里所定义的 this.a，
// # 输出 2

Foo.a();
// 构建方法里已经替换了全局 Foo 上的 a 方法，所以
// # 输出 1