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)); //10100100010console.log(baseConverter(1314, 8)); //2442console.log(baseConverter(1314, 16)); //522console.log(baseConverter(1314, 20)); //35Econsole.log(baseConverter(1314, 30)); //1DOconsole.log(baseConverter(1314, 35)); //12J2.简述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.操作系统中进程和线程怎么通信
进程和线程的区别
| 进程 | 线程 |
|---|---|
| 进程是资源分配的最小单位 | 线程是程序执行的最小单位，CPU调度的最小单位 |
| 进程有自己独立的地址空间 | 线程共享进程的地址空间 |
| 进程之间的资源是独立的 | 线程共享本进程的资源 |
进程和线程通信
| 进程通信 | 线程通信 |
|---|---|
| 管道(包括管道和命名管道) 内存中类似于文件的模型，多进程可读写 | 共享内存 |
| 消息队列 内核中的队列 | 管道 |
| 共享内存 | |
| 信号量 | |
| 套接字 不同主机上的进程通信方式 |
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
//getCurrentLocationfunction getHash(){ return window.location.hash.slice(1);}export default class HashHistory extends History{ // ... getCurrentLocation(){ return getHash(); }}//setupListenerexport default class HashHistory extends History{ // ... setupListener(){ window.addEventListener('hashchange', ()=> { // 根据当前hash值 过度到对应路径 this.transitionTo(getHash()); }) }}//核心方法TransitionToexport 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.prototypeconst 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)); //trueconsole.log(isSymmetrical(AsymmetricBinaryTree)); //false主要是利用递归来判断同一层级的节点左右是否同时相等，达到对称判断的目的。