共计 11932 个字符,预计需要花费 30 分钟才能阅读完成。
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. 操作系统中进程和线程怎么通信
进程和线程的区别
进程 | 线程 |
---|---|
进程是资源分配的最小单位 | 线程是程序执行的最小单位,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
//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
主要是利用递归来判断同一层级的节点左右是否同时相等,达到对称判断的目的。