2020 字节跳动面试题一面解析

最近有文章漏出了一位实习生面试字节跳动今日头条的前端面试题，总共四轮面试，现在就跟大家一起来探讨一下这些面试题，为疫情后的工作做些准备。

1. 算法：实现 36 进制转换

首先新建一个 Stack 类，用于定义基本操作方法

class Stack {constructor() {
        this.count = 0;
        this.items = {};}

    push(element) {this.items[this.count] = element;
        this.count++;
    }

    pop() {if (this.isEmpty()) {return undefined;}
        this.count--;
        const result = this.items[this.count];
        delete this.items[this.count];
        return result;
    }

    peek() {if (this.isEmpty()) {return undefined;}
        return this.items[this.count - 1];
    }

    isEmpty() {return this.count === 0;}

    size() {return this.count;}

    clear() {this.items = {};
        this.count = 0;
    }

    toString() {if (this.isEmpty()) {return '';}
        let objString = `${this.items[0]}`;
        for (let i = 1; i < this.count; i++) {objString = `${objString},${this.items[i]}`;
        }
        return objString;
    }
}

然后定义一个转换方法，用于进制转换

function baseConverter(decNumber, base) {
    // 创建 Stack 类
    const remStack = new Stack();
    // 定义一个进制位数，这里设置了 36 位进制，可自定义位数
    const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    let number = decNumber;
    let rem;
    let baseString = '';

    if (!(base >= 2 && base <= 36)) {return '';}

    while (number > 0) {rem = Math.floor(number % base);
        remStack.push(rem);
        number = Math.floor(number / base);
    }

    while (!remStack.isEmpty()) {
        // 对栈中的数字做转化
        baseString += digits[remStack.pop()];
    }

    return baseString;
}

最后进行测试

console.log(baseConverter(1314, 2));    //10100100010
console.log(baseConverter(1314, 8));    //2442
console.log(baseConverter(1314, 16));    //522
console.log(baseConverter(1314, 20));    //35E
console.log(baseConverter(1314, 30));    //1DO
console.log(baseConverter(1314, 35));    //12J

2. 简述 https 原理，以及与 http 的区别

http 请求都是明文传输的，这里的明文就是指没有经过加密的信息，如果请求被黑客拦截就会非常危险。因此 Netscape 公司制定了 https 协议，https 可以将传输的数据进行加密，这样即使被黑客拦截也无法破译，保证了网络通信的安全。

https 协议 =http 协议 +SSL/TLS 协议，需要用 SSL/TLS 对数据进行加密和解密，SSL（Secure Sockets Layer）即安全套接层协议；TLS（Transport Layer Security）即安全传输层协议，它建立在 SSL 协议规范之上，是 SSL 的后续版本。TSL 和 SSL 各自所支持的加密算法不同，但在理解 https 的过程中，可以把它们看作是同一种协议。

HTTPS 开发的主要目的，是提供对网站服务器的身份认证，保护交换数据的隐私与完整性。它其实就是 HTTP+ 加密 + 身份认证 + 完整性保护。

为了兼顾安全与效率，https 同时使用了对称加密和非对称加密。要传输的数据使用了对称加密，对称加密的过程需要客户端一个秘钥，为了确保能把该秘钥安全地传输到服务器端，将该秘钥进行了非对称加密传输。总结就是：数据进行了对称加密，对称加密使用的秘钥进行了非对称加密。

客户端与服务器建立连接后，各自生成私钥和公钥。服务器返给客户端一个公钥，客户端拿着公钥把要传输的内容进行加密，连同自己的公钥一起返给服务器，服务器用自己的私钥解密密文，然后把响应的数据用客户端公钥加密，再返给客户端，客户端用自己的私钥解密密文，完成数据的展现。

3. 操作系统中进程和线程怎么通信

进程和线程的区别

进程和线程通信

4.node 中 cluster 是怎样开启多进程的，并且一个端口可以被多个进程监听吗？

nodejs是单线程的模式，不能充分利用服务器的多核资源。使用 node 的 cluster 模块可以监控应用进程，退出后重新启动 node 应用进程，并可以启动多个 node 应用进程，做到负载均衡，充分利用资源。

const cluster = require('cluster');
const cpus = require('os').cpus();

const accessLogger = require("../logger").accessLogger();

accessLogger.info('master' + process.pid + 'is starting.');

cluster.setupMaster({
    /* 应用进程启动文件 */
    exec: 'bin/www'
});

/* 启动应用进程个数和服务器 CPU 核数一样 */
for (let i = 0; i < cpus.length; i++) {cluster.fork();
}

cluster.on('online', function (worker) {
    /* 进程启动成功 */
    accessLogger.info('worker' + worker.process.pid + 'is online.');
});
cluster.on('exit', function (worker, code, signal) {
    /* 应用进程退出时，记录日志并重启 */
    accessLogger.info('worker' + worker.process.pid + 'died.');
    cluster.fork();});

5. 实现原生 ajax

通过 XmlHttpRequest 对象向服务器发异步请求，从服务器获得数据，然后用 javascript 来操作 DOM 更新页面的技术

var xhr = new XMLHttpRequest();
xhr.open("post","http:www.domain.com");
xhr.setRequestHeader('content-type','application/x-www-form-urlencoded');
xhr.send();
xhr.onreadystatechange = function(){if(xhr.readyState == 4 && xhr.status == 200){return xhr.responseText;}
}

主要考察的是服务器响应的 5 个状态

• 0: 请求未初始化（代理被创建，但尚未调用 open() 方法）
• 1: 服务器连接已建立（open 方法已经被调用）
• 2: 请求已接收（send 方法已经被调用，并且头部和状态已经可获得）
• 3: 请求处理中（下载中，responseText 属性已经包含部分数据）
• 4: 请求已完成，且响应已就绪（下载操作已完成）

6.vue-router 源码

这里仅展示关键方法，细节处不讨论。

先看目录结构

├─vue-router
│  ├─components # 存放 vue-router 的两个核心组件
│  │  ├─link.js
│  │  └─view.js
│  ├─history    # 存放浏览器跳转相关逻辑
│  │  ├─base.js
│  │  └─hash.js
│  ├─create-matcher.js # 创建匹配器
│  ├─create-route-map.js # 创建路由映射表
│  ├─index.js # 引用时的入口文件
│  ├─install.js # install 方法

编写 install 方法

export let _Vue;
export default function install(Vue) {
    _Vue = Vue;
    Vue.mixin({ // 给所有组件的生命周期都增加 beforeCreate 方法
        beforeCreate() {if (this.$options.router) { // 如果有 router 属性说明是根实例
                this._routerRoot = this; // 将根实例挂载在_routerRoot 属性上
                this._router = this.$options.router; // 将当前 router 实例挂载在_router 上

                this._router.init(this); // 初始化路由, 这里的 this 指向的是根实例
            } else { // 父组件渲染后会渲染子组件
                this._routerRoot = this.$parent && this.$parent._routerRoot;
                // 保证所有子组件都拥有_routerRoot 属性，指向根实例
                // 保证所有组件都可以通过 this._routerRoot._router 拿到用户传递进来的路由实例对象
            }
        }
    })
}

编写 createMatcher 方法

import createRouteMap from './create-route-map'
export default function createMatcher(routes) {
    // 收集所有的路由路径, 收集路径的对应渲染关系
    // pathList = ['/','/about','/about/a','/about/b']
    // pathMap = {'/':'/ 的记录','/about':'/about 记录'...}
    let {pathList,pathMap} = createRouteMap(routes);
    
    // 这个方法就是动态加载路由的方法
    function addRoutes(routes){
        // 将新增的路由追加到 pathList 和 pathMap 中
        createRouteMap(routes,pathList,pathMap);
    }   
    function match(){} // 稍后根据路径找到对应的记录
    return {
        addRoutes,
        match
    }
}

创建映射关系，还需要 createRouteMap 方法

export default function createRouteMap(routes,oldPathList,oldPathMap){
    // 当第一次加载的时候没有 pathList 和 pathMap
    let pathList = oldPathList || []; 
    let pathMap = oldPathMap || Object.create(null);
    routes.forEach(route=>{
        // 添加到路由记录，用户配置可能是无限层级，稍后要递归调用此方法
        addRouteRecord(route,pathList,pathMap);
    });
    return { // 导出映射关系
        pathList,
        pathMap
    }
}   
// 将当前路由存储到 pathList 和 pathMap 中
function addRouteRecord(route,pathList,pathMap,parent){
    // 如果是子路由记录 需要增加前缀 
    let path = parent?`${parent.path}/${route.path}`:route.path;
    let record = { // 提取需要的信息
        path,
        component:route.component,
        parent
    }
    if(!pathMap[path]){pathList.push(path);
        pathMap[path] = record;
    }
    if(route.children){ // 递归添加子路由
        route.children.forEach(r=>{ 
            // 这里需要标记父亲是谁
            addRouteRecord(r,pathList,pathMap,route);
        })
    }
}

vue路由有三种模式：hash / h5api /abstract，这里以 hash 为例

以 hash 路由为主, 创建 hash 路由实例

import History from './base'
// hash 路由
export default class HashHistory extends History{constructor(router){super(router);
    }
}
// 路由的基类
export default class History {constructor(router){this.router = router;}
}

如果是 hash 路由, 打开网站如果没有 hash 默认应该添加#/

import History from './base';
function ensureSlash(){if(window.location.hash){return}
    window.location.hash = '/'
}
export default class HashHistory extends History{constructor(router){super(router);
        ensureSlash(); // 确保有 hash}
}

再把焦点转向初始化逻辑

init(app){
        const history = this.history;
        // 初始化时，应该先拿到当前路径，进行匹配逻辑

        // 让路由系统过度到某个路径
        const setupHashListener = ()=> {history.setupListener(); // 监听路径变化
        }
        history.transitionTo( // 父类提供方法负责跳转
            history.getCurrentLocation(), // 子类获取对应的路径
            // 跳转成功后注册路径监听，为视图更新做准备
            setupHashListener
        )
}

这里我们要分别实现 transitionTo(基类方法)、getCurrentLocation、setupListener

//getCurrentLocation
function getHash(){return window.location.hash.slice(1);
}
export default class HashHistory extends History{
    // ...
    getCurrentLocation(){return getHash();
    }
}

//setupListener
export default class HashHistory extends History{
    // ...
    setupListener(){window.addEventListener('hashchange', ()=> {
            // 根据当前 hash 值 过度到对应路径
            this.transitionTo(getHash());
        })
    }
}

// 核心方法 TransitionTo
export function createRoute(record, location) {// {path:'/',matched:[record,record]}
    let res = [];
    if (record) { // 如果有记录 
        while(record){res.unshift(record); // 就将当前记录的父亲放到前面
            record = record.parent
        }
    }
    return {
        ...location,
        matched: res
    }
}
export default class History {constructor(router) {
        this.router = router;
        // 根据记录和路径返回对象, 稍后会用于 router-view 的匹配
        this.current = createRoute(null, {path: '/'})
    }
    // 核心逻辑
    transitionTo(location, onComplete) {
        // 去匹配路径
        let route = this.router.match(location);
        // 相同路径不必过渡
        if(
            location === route.path && 
            route.matched.length === this.current.matched.length){return}
        this.updateRoute(route); // 更新路由即可
        onComplete && onComplete();}
    updateRoute(route){ // 跟新 current 属性
        this.current =route;
    }
}

不难发现路径变化时都会更改 current 属性，我们可以把 current 属性变成响应式的，每次 current 变化刷新视图即可

export let _Vue;
export default function install(Vue) {
    _Vue = Vue;
    Vue.mixin({ // 给所有组件的生命周期都增加 beforeCreate 方法
        beforeCreate() {if (this.$options.router) { // 如果有 router 属性说明是根实例
                // ...
                Vue.util.defineReactive(this,'_route',this._router.history.current);
            } 
            // ...
        }
    });
    // 仅仅是为了更加方便
    Object.defineProperty(Vue.prototype,'$route',{ // 每个实例都可以获取到 $route 属性
        get(){return this._routerRoot._route;}
    });
    Object.defineProperty(Vue.prototype,'$router',{ // 每个实例都可以获取 router 实例
        get(){return this._routerRoot._router;}
    })
}

其中不难看出 Vue.util.defineReactive 这个方法是vue 中响应式数据变化的核心。

export default class History {constructor(router) {
        // ...
        this.cb = null;
    }
    listen(cb){this.cb = cb; // 注册函数}
    updateRoute(route){
        this.current =route;
        this.cb && this.cb(route); // 更新 current 后 更新_route 属性
    }
}

实现router-view

export default {
    functional:true,
    render(h,{parent,data}){
        let route = parent.$route;
        let depth = 0;
        data.routerView = true;
        while(parent){ // 根据 matched 渲染对应的 router-view
            if (parent.$vnode && parent.$vnode.data.routerView){depth++;}
            parent = parent.$parent;
        }
        let record = route.matched[depth];
        if(!record){return h();
        }
        return h(record.component, data);
    }
}

实现router-link

export default {
    props:{
        to:{
            type:String,
            required:true
        },
        tag:{type:String}
    },
    render(h){
        let tag = this.tag || 'a';
        let handler = ()=>{this.$router.push(this.to);
        }
        return <tag onClick={handler}>{this.$slots.default}</tag>
    }
}

实现beforeEach

this.beforeHooks = [];
beforeEach(fn){ // 将 fn 注册到队列中
    this.beforeHooks.push(fn);
}
function runQueue(queue, iterator,cb) { // 迭代 queue
    function step(index){if(index >= queue.length){cb();
        }else{let hook = queue[index];
            iterator(hook,()=>{ // 将本次迭代到的 hook 传递给 iterator 函数中, 将下次的权限也一并传入
                step(index+1)
            })
        }
    }
    step(0)
}
export default class History {transitionTo(location, onComplete) {
        // 跳转到这个路径
        let route = this.router.match(location);
        if (location === this.current.path && route.matched.length === this.current.matched.length) {return}
        let queue = [].concat(this.router.beforeHooks);
        const iterator = (hook, next) => {hook(route,this.current,()=>{ // 分别对应用户 from，to，next 参数
                next();});
        }
        runQueue(queue, iterator, () => { // 依次执行队列 , 执行完毕后更新路由
            this.updateRoute(route);
            onComplete && onComplete();});
    }
    updateRoute(route) {
        this.current = route;
        this.cb && this.cb(route);
    }
    listen(cb) {this.cb = cb;}
}

7.vue 原理（手写代码，实现数据劫持）

• 1. 核心点:Object.defineProperty
• 2. 默认 Vue 在初始化数据时，会给 data 中的属性使用 Object.defineProperty 重新定义所有属性, 当页面取到对应属性时。会进行依赖收集（收集当前组件的 watcher）如果属性发生变化会通知相关依赖进行更新操作
• 3. 本文主要描述的是 vue2.0 版本的实现

Object.defineProperty(obj, key, {
    enumerable: true,
    configurable: true,
    get: function reactiveGetter () {const value = getter ? getter.call(obj) : val
      if (Dep.target) {dep.depend() // ** 收集依赖 ** /
        if (childOb) {childOb.dep.depend()
          if (Array.isArray(value)) {dependArray(value)
          }
        }
      }
      return value
    },
    set: function reactiveSetter (newVal) {const value = getter ? getter.call(obj) : val
      if (newVal === value || (newVal !== newVal && value !== value)) {return}
      if (process.env.NODE_ENV !== 'production' && customSetter) {customSetter()
      }
      val = newVal
      childOb = !shallow && observe(newVal)
      dep.notify() /** 通知相关依赖进行更新 **/}
})

数组方法的劫持涉及到原型相关的知识，首先数组实例大部分方法都是来源于 Array.prototype对象。

但是这里不能直接篡改 Array.prototype 对象，这样会影响所有的数组实例，为了避免这种情况，需要采用原型继承得到一个新的原型对象：

const methods = [
  'push',
  'pop',
  'shift',
  'unshift',
  'sort',
  'reverse',
  'splice'
]
const arrayProto = Array.prototype
const injackingPrototype = Object.create(arrayProto);
methods.forEach(method => {const originArrayMethod = arrayProto[method]
  injackingPrototype[method] = function (...args) {const result = originArrayMethod.apply(this, args)
    let inserted
    switch (method) {
      case 'push':
      case 'unshift':
        inserted = args
        break
      case 'splice':
        inserted = args.slice(2)
        break
    }
    if (inserted) {
      // 对于新增的元素，继续劫持
      // ob.observeArray(inserted)
    }
    // 通知变化
    return result
  }
})

通过对能改变原数组的方法进行拦截，达到对数组对象的劫持，遍历直到普通值。

8. 算法：树的遍历有几种方式，实现下层次遍历

• 前序遍历

// 根节点、左子树、右子树
function DLR(tree){console.log(tree.value);
    if(tree.left){DLR(tree.left);
    }
    if(tree.right){DLR(tree.right);
    }
}

• 中序遍历

// 左子树、根节点、右子树
function LDR(tree){if(tree.left){LDR(tree.left);
    }
    console.log(tree.value);
    if(tree.right){LDR(tree.right);
    }
}

• 后序遍历

// 左子树、右子树、根节点
function LRD(tree){if(tree.left){LRD(tree.left);
    }
    if(tree.right){LRD(tree.right);
    }
    console.log(tree.value);
}

三种遍历操作大致相同，而差异就在于执行额外操作的时机，例如 console.log

9. 算法：判断对称二叉树

• 首先判断根节点是否相同
• 左子树的右节点和右子树的左节点是否相同
• 右子树的左节点和左子树的右节点是否相同

// 一个对称二叉树
const symmetricalBinaryTree = {
  val: 8,
  left: {
    val: 6,
    left: {val: 2, left: null, right: null},
    right: {val: 4, left: null, right: null}
  },
  right: {
    val: 6,
    left: {val: 4, left: null, right: null},
    right: {val: 2, left: null, right: null}
  }
}

// 一个非对称二叉树
const AsymmetricBinaryTree = {
  val: 8,
  left: {
    val: 6,
    left: {val: 2, left: null, right: null},
    right: {val: 4, left: null, right: null}
  },
  right: {
    val: 9,
    left: {val: 4, left: null, right: null},
    right: {val: 2, left: null, right: null}
  }
}

利用递归实现对称二叉树判断

function isSymmetrical(root) {return isSymmetricalTree(root, root);
}

function isSymmetricalTree(node1, node2) {
  // 判断两个节点都是否为空
  if (!node1 && !node2) {return true;}
  // 判断两个节点是否存在一个为空
  if (!node1 || !node2) {return false;}
  // 判断两个节点是否相同
  if (node1.val != node2.val) {return false;}
  return isSymmetricalTree(node1.left, node2.right) && isSymmetricalTree(node1.right, node2.left);
}

console.log(isSymmetrical(symmetricalBinaryTree));        //true
console.log(isSymmetrical(AsymmetricBinaryTree));        //false

主要是利用递归来判断同一层级的节点左右是否同时相等，达到对称判断的目的。