共计 16327 个字符，预计需要花费 41 分钟才能阅读完成。
本文由 杨珏成 原创发布于 SegmentFault，未经许可请勿转载
原文链接：https://segmentfault.com/a/11…
0x00 作者是谁
我就读于北京理工大学软件工程专业，从大一开始投入以前端为主的全栈开发，独立开发过多个中型和小型项目，是 佬铁 | 宿舍市集 小程序的社区创始人及独立项目负责人。
我在学校里读书的时候就是一个闲不住的人。最近因为一个偶然的契机接触到了校招季，最后促成我定下了本科毕业就工作的规划目标。在一个月的时间里，我总共参与了 9 家国内大厂校招，结果如下（截至 2019 年 9 月 3 日，持续更新）：
- 腾讯（WXG）：等待二面
- 阿里巴巴（淘宝 FED）：三面等结果
- 字节跳动：收到 offer
- 美团点评（LBS）：收到 offer
- B 站（电商平台）：等待 offer 结果
- 小米：等待 offer 结果
- 网易（严选）：放弃 offer
- 携程：放弃笔试
- 滴滴：放弃笔试
0x01 为什么要写这篇文章
从一开始手指冒汗被怼的说不出话，到最后和面试官侃侃而谈游刃有余，我发现一个现象：同样的能力水平，在不同的面试表现下，反馈到面试官眼中的结果可以有着天壤之别。如果你希望把自己的真实水平展示给面试官，那么掌握一些合适的方法是非常有必要的。
本文的内容聚焦于应聘大厂校招所需具备的能力，以及分析各个大厂具体的校招策略。全文分为两个部分：1. 如何进入面试，2. 如何通过面试。希望能为第一次走上职场的同学们提供参考，也是对自己过去数周奔波忙碌的一个总结。
0x02 大厂前端校招：如何进入面试？
想要拿到大厂 offer，第一步自然是通过大厂的校招初筛，很多人觉得初筛很容易，其实不然。在初筛，尤其是大厂的初筛环节中，面试官面对的将是成千上万份看起来没什么区别的简历文件，都是白纸黑字，。
仔细打磨的简历
完备的逻辑思维
扎实的技术基础（系统知识）
工程实践
职业规划
每次结束后一定要复盘总结
克服紧张
0x03 大厂前端校招：如何通过面试？
我所遇到的所有技术面试题
一般来说，大厂的前端校招会比其他中小企业更看重对面试者的全方位考核，如果你是科班出身，校招的技术考核会包括且不限于：
- 计算机专业基础（数据结构，算法，计算机网络，操作系统，数据库）
- 职位相关基础（JS/ES 知识体系，浏览器渲染与缓存，前后端通信，Web 安全）
- 工程实践经验（性能优化，依赖管理，依赖打包，模块化，组件化，用户鉴权，版本管理，包管理，服务器基础）
- 主流框架理解（Vue，React 二选一）
- 部分要求极高的大厂还会考核你的理科基础（线性代数，高等数学）
另外，不同的大厂也有不同的侧重点。
技术实力最顶尖的阿里淘系 FED 会对你的基础知识体系以及你简历上写到的技能 展开一场惨绝人寰的全方位考核，而字节跳动则更看重你的实际工程经验以及对于软件系统架构的理解。
通过每家大厂的面试策略，你也可以侧面观察出这家企业的团队技术实力和业务发展前景。
为了更清晰的描述大厂校招知识体系，我将考核中涉及到的所有面试题整理成了一张思维导图。建议一条一条仔细查阅，对于任何没有百分百把握的知识点，我都建议你把它整理到一个列表里，逐条梳理。
PS. 标星的是非必须知识，可以略过：
职业规划
每次结束后一定要复盘总结
0x04 各家大厂的面试体验
0x05 写在最后：一个优秀的前端工程师应具备哪些素养
探索最佳实践
附录 1：大厂面试题整理
符号约定
| 符号 | 含义 |
|---|---|
| √ | 现场回答正确 |
| × | 现场回答错误 |
| ? | 现场无法判断是否答对 |
| 追问 | 对于父问题的追问 |
| () | 我在面试现场的回答思路 |
| ()右边 | 最合适的回答（或对现场回答的补充） |
| 补充 | 面试官亲自对现场回答的补充 |
| 问 | 我向面试官提出的问题 |
阿里实习一面
- 用 js 描述一棵树 √
- 非递归遍历树 ×
- 详述 js new 操作 √
-
方法调用模式 this 指向 ×
- 追问：函数调用模式 this 指向 √
- 什么是 js 闭包 √
- 如何跨域访问 √
- vue 的父子组件之间如何通信 ×
- 用 css 写无限循环动画 ×
- 如何响应式布局 √
- 如何清除 float √
- 手写 jsonp √
- 为什么禁止跨域 ×
- osi 七层 × 漏说了
- tcp 三次握手 √ 四次挥手 ×
- setTimeout 为何能在单线程的 js 里异步执行 ×
- 进程和线程的区别？
- 写一个数字转中文的程序 √
- js 函数中如何绑定 this 到新对象上 √
- bind 和 call 有什么区别 ×
- 手写快排 ×
- 讲一下 http 状态码 √，其中 303 304 代表什么 ×
- 死锁的原理和四要素 √
- cookie 和 session 的区别 √
- 同源的定义 √
Bilibili 校招一面
- 详述 es5 es6 中的作用域和闭包 √（es5 全局 + 函数级，函数化闭包，es6 块级）
- 详述输入 url 到页面渲染完成 √（域名解析 -TCP 分包 -IP 寻路 - 握手 - 滑动窗口传输 - 持久化连接 - 挥手 - 解析 - 构建 dom 树与 cssom- 构建渲染树 - 回流 - 重绘 - 渲染）
- 详述 js 异步机制 Event Loop，MacroTask 和 MicroTask √（1 个主线程 + n 个任务队列，浏览器异步处理后推入队列，循环处理，一个 macroTask 后跟全部 microtask）
- Promise.all 的用法 √（在所有 all 中的 promise 结束后再执行）
- 如何让 Promise.all 在抛出异常后依然有效 ×（正确答案：主动 reject）
-
什么是 VueX √（状态量跨组件管理）
- VueX 中 action 和 mutation 的区别 ×（正确答案：同步和异步）
- 详述 Vue 的双向数据绑定原理 √（语法糖，dom 监听 + 模型监听）
- Vue 的优势 √（virtual dom，数据绑定，视图与模型分离，隐去冗杂的 dom 操作）
- 如何实现 SEO 优化？（只答了服务器端伪静态）
- 详述回流和重绘优化 √（回流是对物理尺寸的变更，回流一定会重绘，重绘不一定回流，因此尽量减少回流次数，将元素移出 dom 树再变更）
- 详述防抖和节流优化 √（状态锁 / 同步锁）
- 简述 ES6 新特性 √（块级作用域, 变量不提升,let, const, 箭头函数, 模板字符串,promise,async）
- 简述箭头函数特性 ×
- webpack 打包如何优化 ×
阿里校招一面
- 列举几个 css 中可继承和不可继承的元素 √
- 用 css 选中列表第二项 √
- 伪类和伪元素的区别 √
- h5 字体如何自适应屏幕 √
-
rpx 是什么 √
- 追问：rem 是什么？
- 追问：vw 是什么 √
- 追问：vw 和 rem 区别 ×（vw 根据屏幕宽度，rem 根据根元素确定 font-size 换算比例）
- 什么情况下 css 会使用 gpu 加速 √
- css filter 是什么 ×（元素的可视效果例如：模糊与饱和度）
- 网页如何去适配不同宽度 √
- 详述 meta 标签的作用 √
- position 默认值和所有可能值 √
- 什么是 sass 和 less √
- css 动画最小间隔 √
- shadow dom 是什么 ×
- svg 和 canvas 的概念和区别 √
- canvas 图层怎么用 ×
- dom 渲染的性能损耗在哪里 √
- 如何高效地从 1000 个 div 中删除 10 个 div √
- 如何监听 img 加载完成 √
- 浏览器里除了 js 还能运行什么 × (webAssembly 和 actionscript)
- promise 有几种状态 × (fufilled, rejected, pending)
- 如何捕获 promise 错误 √
- promise 可以串联吗？答的不清晰
- 详述 vue 都能解决什么问题 √
- virtual dom 如何进行 diff 操作 ×
- vue 中 data 为什么是函数不是对象 √
- 为什么需要深拷贝 √
- 简述指针是什么 √
- node.js 了解吗 × 不了解
- 进程和线程的区别 √
- 你自己开发的平台有多少用户和访问量 √
- 如何监控未处理的异常 ?（只说了监听 console error）
- 5G 是什么，为什么要用 5G（开放题目）
- 想象一下 5G 的应用场景（开放题目）
- http 和 https 的区别 √
- 为什么 https 不会被截获 √
- 量子计算机能否破解非对称加密 √（附加）
- 量子计算机的原理 √（附加）
- 浏览器如何缓存？(答的不好，设置 http 头部）
- 详述 http 1.0, 1.1, 2.0 的区别 √
- 详述 TCP 如何保证传输完整性 √
- UDP 和 TCP 有什么区别 √
- 为什么使用 UDP × 答的不好
- WebSocket 是基于什么协议连接 √
- 冒泡算法和快排时间复杂度 √
- 分布式系统用什么算法排序？半对
- 广搜和深搜的应用 √
- 广搜的数据结构 √
- 链式求导是什么 ×
- 矩阵的秩是什么？半对
- 梯度和导数，偏导 √
- 信息熵 √
- 编译原理？半对
- sql 如何获取当前时间 √
- char 和 varchar 区别 √
- drop, delete, truncate？（半对，truncate 可以持久化）
- python 用过吗？做过爬虫
小米实习电话面试
- 作为全栈为什么报前端 √
- js 用的哪个版本 √
- es6 新特性 √
- promise 有几种状态 √
- promise 如何满足多个异步进程的同步顺序 √
- promise.race 和 promise.all 的区别 ×
- 怎么设计页面布局（开放题目）
- 如何用 flex 让 8 个图标排成两行 ×（flex-wrap）
- 垂直居中和水平居中 ×（说反了）
- 你的页面是用一套界面响应不同宽度吗 √
- 自己如何调前后端 api √
- vue 中的 fetch 和 axios 是什么×
- 跨域问题怎么解决 √
- 跨域怎么做 post ×（用 iframe）
- 详述 git 操作 √
- vue.js 加载完成前隐藏花括号 ×（v-clock）
- 开发主要用 react，有兴趣转技术栈吗（有）
- 可以实习多久
Bilibili 校招二面
- 纯 js 如何获取 scrolltop 值 √
- 详述 js 闭包原理和意义 √
- 深拷贝 浅拷贝是什么 √
- arguments 如何转数组 √
- 移动端和 pc 端 click 事件为什么差了 300 毫秒 ×（因为 iphone 可以双击缩放）
- flex 布局用法 √
- 如何实现移动端响应式布局 √
- ES6 的作用域 √
- async await 是什么 √
- 块级作用域有哪些 √
- 详述 promise 异步机制 √
- 如何实现跨域访问 √
- http 通信如何设置缓存 √
- 详述 http 状态码 √
- 如何实现 vue 组件通信 √
- 简述 VueX 的作用 √
- 如何实现一个 swiper √
- hybrid 是什么 √
- hybrid js 如何调用 native 接口 ×
- 为什么要做前端
- 对于自己的发展规划
- 上海怎么样
网易校招一面
- 块状元素 行内元素 √
- 标签语义化是什么 √
- css 清除浮动 √
- 什么是盒模型 √
- css 优先级 √
- position 属性 √
- 移动端适配？（媒体查询，flex，rem）还有 viewport
- px em rem √
- == 和 === 的区别 √
- 原型和原型链是什么 √
- 什么是深拷贝 √
- 什么是同步 什么是异步 √
- 如何顺序执行 10 个异步任务？（答的不全）
- es6 proxy 是什么？（不了解，说了下代理模式的概念）
- 题目：遍历一个任意长度的 list 中的元素并依次创建异步任务，如何获取所有任务的执行结果？（用 promise.all，感觉面试官不是很满意，应该是用 proxy 代理）
- 对一个对象数组排序？（增加原型方法）
- 乱序一维数组排序
- 数组去重？（map.set，键值对象）
- 如何进行 git 的分支管理？（答的不全）
- 浏览器有哪些缓存 √
- 什么是跨域 √
- 如何解决跨域 √（jsonp，代理，白名单）
-
不考虑还有别的办法 √
- 补充 本地存储，window.name，form.message
- 页面性能的优化 √（重绘，回流，防抖，节流
- 还有吗 √（懒加载，预加载）还有 base64，压缩，骨架屏
- 浏览器安全处理 √（xss，数据库注入）还有 csrf，文件上传漏洞
- 有没有真机浏览器 debug 经验（开放题）
阿里校招二面
- 一分钟介绍一下你的项目经历 √
- 是否了解淘系 FED 这个部门 √
一. 基础部分
-
html
-
如何在移动端处理兼容性？（css 前缀）
- 追问 工程中遇到过类似的问题（svg）
- 追问 还有补充吗（没了…）还有 meta viewport http-equiv
- vw em rem 的区别和使用场景 √
- 不同定位模式之间的区别 √
- fix 的显示问题？（宽度塌陷）没答全，还有 z -index 覆盖
-
canvas 如何使用图层 √
- 追问 如何避免图层覆盖？（答的封装）
-
-
css
- 所有绝对居中的实现？(flex, text, padding: auto）没答全，还有 translate
- sass 和 less 有什么区别 √
-
实现响应式布局的方法 √ (flex 媒体查询 rem)
- 追问 还有吗 √ (grid)
- 了解过 BFC 吗 ×（不了解）
-
js
- 用三句话概括所有值传递类型，所有引用传递类型，以及如何用引用的方式传递值类型？
-
js 所有基础类型？（布尔值，数字，字符串）还有 null 和 undefined，symbol
- 追问 null 和 undefined 的区别 √（未定义和赋空值）
- 追问 怎么比较 ×
- 指针和引用的区别 √（地址和别名）
-
js 当中对于不同环境的变量什么时候释放 √（标记清除和引用计数）
- 追问 在非闭包的情况下变量什么时候会被回收？（不确定）
- js 的作用域你怎么理解 √
-
js 里的多重继承怎么实现 √（call，es6 extend)
- 追问 还有吗？（不知道）
二、工程部分
- React 和 Vue 生命周期有什么区别？（答了 vue，react 不了解）
- Vue 如何监听数据的变化 √ (defineProperty，订阅者模式)
- Vue 里如何实现父子组件之间的通信 √
- 了解过高阶组件吗（不了解）
- 看过 Vue 的源码吗（目前主要在理解原理阶段）
- 有没有使用工具构建过工程项目（vue cli+webpack）
- webpack 编译和构建原理（分析依赖，chunk）没有说 loader
- 平时使用什么工具转换 es6（babel）
- babel 转码流程（配置.babelrc，解析语法数，改变块级变量名等等）
三、算法部分
- js 哈希存储结构的构成方式 √（哈希值，哈希表，哈希冲突）
- js 当中如何实现某一个数的阶乘？（只答了 for 循环）
- 设计一个算法找到乱序数组中相加等于指定值的所有数对 √（快排 + 两端查询 / 两层 for）
阿里校招三面
- 介绍一下你的项目（中大型小程序系统，企业控制台，Vue CLI 单页面 web 应用等）
-
你的小程序是怎样一个软件（校内交易社区）
- 追问 为什么不通过闲鱼去卖呢（解决楼内交易）
-
你的小程序用 openid 去登陆，可以讲一下 OAuth 流程吗（可信平台对前端发放 token，后端处理敏感信息）
- 追问 OAuth 有什么优势（避免前端直接接触敏感信息）
-
你的小程序 Websocket 通信系统是做什么的（各种类型消息的实时通信）
- 追问 你的实时语音通信是怎么做的（接口鉴权 -> 手势状态机 -> 本地持久化 -> 上传服务器 -> 缓存管理）
- 追问 微信的录音返回数据是传回 base64 吗（不是 是返回 tmp 协议路径）
- 追问 你的录音本地持久化的目的是什么（减轻服务器负载，减少冗余的资源重传）
- 追问 你的本地持久化是怎么做的（用 local storage）
- 追问 你的一条语音大概有多大（几十 k 到几百 k）
- 追问 小程序的 localstorage 有多大（10-20M）
- 追问 你的 websocket 为什么要做心跳（避免网络环境变化带来的通信中断）
- 追问 你的心跳机制是怎么做的（计时器控制 超时重连 网络状态监听）
- 你是自己买的服务器吗（阿里云）
- 你的 CDN 服务是怎么做的（阿里云）
- 你的 SSL 是怎么做的（配置 ssl 证书链，非对称加密）
-
你的搜索为什么用 Elastic Search（中文分词，倒排索引，高效）
- 追问 你的中文分词搜索是怎么做的（IK 分词器）
-
你的数据库用的是什么引擎（INNODB）
- 追问 为什么用 INNODB 引擎（外键，索引类型，utf8mb4）
- 追问 INNODB 的锁是什么粒度级别（答的表级，不太确定）
- 追问 对于事务的原子性有了解吗（不了解）
- 你的单页面 web 应用是怎么做的（Vue CLI+Webpack 自动构建，Vue Router 路由）
-
你的用户密码是怎么存在数据库里的（PASSWORD 函数）
- 追问 用户密码在前端传输的时候有做加密吗（有了 ssl 不需要）
-
你有没有做登陆态持久化，怎么做的（设置 cookie 过期时间）
- 追问 你的服务器端怎么管理 session 登陆态（php 自动分发）
- 追问 怎么在多台服务器同步 session 数据（数据库或者分布式系统）
- 追问 分布式怎么做（hbase 或者 es）
- 追问 存储完以后怎么用 php 获取呢（不知道）
-
在中航通用实习的主要成果（独立开发 web 系统，数据控制台，后端服务器）
- 追问 你的控制台管理什么数据（产品，新闻，职位，简历）
- 追问 你的 WYSIWYG 编辑器是自己做的吗（基于 summernote 二次开发）
- 追问 你的异步交互和事物存储是什么（AJAX+PDO）
- 你对于自己未来发展的规划是什么样（读框架源码 - 写自己的框架 - 掌握前后端深层知识 - 掌握整个软件架构）
- XSS，CSRF，数据库注入怎么防范（控制前端渲染，控制后端处理，预编译）
- 解释一下深拷贝和浅拷贝（引用传递和值传递 blablabla）
- 平时自己是怎么关注前端领域的知识的（工具书，技术博客，官方文档，交流群）
美团校招一面
- 介绍一下你的项目经历
- 影响页面加载性能的主要因素√
-
你是怎么统计页面数据的√
- 补充 其实这些数据可以用小程序控制台查看
- 你的微信 OAuth 登陆怎么做的√
- 你的微信模板消息怎么做的√
- 小程序的分包原理是什么×（用户点击时加载对应包）
- 如何自动构建前端项目并自动部署？（webpack+ 第三方插件自动化）
-
视差屏原理√
- 追问 用 absolute 和 translate 做视差哪个好√
- 追问 你的 vue 项目里为什么用了 jquery，用在哪√
- 数组有哪些方法√
- 函数 bind 方法会接收什么，返回什么√
- 哪些静态资源会阻塞页面渲染，怎么解决，有什区别√
- 如何跨域访问√
- JSONP 原理√
- 事件代理原理√
- 你现在的实习主要做什么
- 能接受加班吗 以及能接受的加班时间
- 为什么选择美团
字节跳动校招一面
- 你的项目经历
- js 有哪些基础类型√
- 闭包是什么√
- 如何循环间隔 1 秒输出数组元素√
-
如何实现事件监听√ (callback，addEventListener)
- 追问 两者有什么区别√ (后者会被覆盖)
- Vue 生命周期√
- BFC 了解吗× 块级格式化上下文
-
画一个盒模型√
- 追问 box-sizing√
- 实现一个三栏布局√
- websocket 原理√
- 登陆的 cookie 怎么存的√
- 把
www.toutiao.com转为com.toutiao.www√
字节跳动校招二面
- 介绍一下你的项目经历
- 你的 php 包管理用什么√ composer
- composer 的 autoloader 怎么实现的？
- php fast-cgi 是什么？并发管理
- php set_cookie 是否会改变 $_COOKIE 数组√不会
- 你的 MYSQL Procedure 是干什么的√函数交互
- 跨域请求怎么设置 header 字段√
- Vue Router 原理√
- VueX 具体应用在哪些场景内√
- 用过哪些 Ajax 组件√ Axios
- Axios 怎么实现拦截√
- js 二维数组反向合并√
输入：[1, 2, [3, 4], 5, 6, [7, 8], 9]
输出: [[3, 4, 1, 2, 5, 6][7, 8 ,9]]- js 驼峰转换√
输入：contentType
输出：content_type字节跳动校招三面
- 介绍一下你的项目经历
-
给我看看你上线的小程序√
- 追问 这里瀑布流不平衡怎么回事√（用 10px 显示误差换取预加载带来的性能提升）
- 追问 服务器用的什么√（阿里云腾讯云都用）
- 追问 服务器运维了解吗√
- 追问 服务器宕机以后怎么解锁 mysql×（工程中没有遇到，不确定）
- 追问 cpu 使用率异常升高怎么解决√
- 描述一下你的小程序开发流程√
-
你的 websocket 是干什么的√
- 追问 你的 websocket 是怎么通信的√
- 离线怎么获取消息√
- Vue Router 原理√
- 你的发展规划（前端工程 - 前端架构 - 系统架构）
- 你的意向部门（C 端）
- 问 有可能去哪个部门（不确定，双向选择）
网易校招二面
坑点：没有准备耳机，视频面试官声音比较小，一开场乱了节奏
-
性能上面做过优化效果最好的×××（懒加载，预加载）
- 追问 在什么情况下判断预加载（点击时利用 150ms 延迟进行预加载）
- 追问 还有其他情况会用预加载吗（没有用过）
这两个是你认为最明显的吗×××（严重失误，忘记说重绘和回流以及防抖和节流，浏览器缓存，代码压缩，异步加载等等）
- 其他方面比如构建 组件化的拆分做过吗（）
Bilibili 校招三面
腾讯校招一面
附录 2：大厂笔试题整理
腾讯校招笔试
1. 字符串解码
小明和小红用字符串压缩通信。
字符串压缩规则是：如果有连续重复的字符串比如 ABCABCABC 就缩写成 [3|ABC]。
现有压缩后的字符串，设计一个解压程序还原字符串。
样例：
输入：HG[3|B[2|CA]]F
输出：HGBCACABCACABCACAF坑点：
需要优化内存，我之所以 87.5 就是因为内存溢出 MLE 了，正在考虑用栈结构重写一次。
思路（87.5/100 分）：
string decode(string s) {
string res = "", ans ="";
int len, start , end;
int time, counting;
time = 0, counting = 1;
len = s.size();
for (int i = 0; i < len; i++)
{if (s[i] == '[')
{
start = i;
for (i = len; s[i] != ']'; i--);
end = i;
res += decode(s.substr(start + 1, end - start - 1));
i++;
}
if (counting && s[i] >= '0' && s[i] <= '9')
{time = time * 10 + (s[i] - '0');
}
else if (s[i] == '|')
{counting = 0;}
else
{res += s[i];
}
}
char tmp = res[res.size() - 1];
if (tmp == '\0')
{res = res.substr(0, res.size() - 1);
}
if (time > 0)
{for (int i = 0; i < time; i++)
{ans.append(res);
}
}
else
{ans = res;}
return ans;
}
int main()
{
string s;
cin >> s;
cout << decode(s) << endl;
return 0;
} 2. 识别 IP
判断一个 ip 地址是不是私有的
已知私有 IP 范围是：
10.0.0.0 - 10.255.255.255
172.16.0.0-172.16.255.255
192.168.0.0-192.168.255.255
127.0.0.0/8 # 注意！这里是一个巨坑，0/ 8 的意思代表子网掩码 255.255.255.0，也就是最后 8 位可以有动态范围，这是一种简写方法，但是腾讯并没有说明其含义，可能也是一处考察。样例：
输入：0.0.0.0
输出：false思路（100/100 分）：
function isPrivate(ip){
// TODO
let ipVal = ip.split('.');
ipVal[0] = Number(ipVal[0]);
ipVal[1] = Number(ipVal[1]);
ipVal[2] = Number(ipVal[2]);
ipVal[3] = Number(ipVal[3]);
if (ipVal[0] == 10) {if (ipVal[1] >= 0 && ipVal[1] <= 255) {if (ipVal[2] >= 0 && ipVal[2] <= 255) {if (ipVal[3] >= 0 && ipVal[3] <= 255) {return true;}
}
}
}
if (ipVal[0] == 172) {if (ipVal[1] >= 16 && ipVal[1] <= 31) {if (ipVal[2] >= 0 && ipVal[2] <= 255) {if (ipVal[3] >= 0 && ipVal[3] <= 255) {return true;}
}
}
}
if (ipVal[0] == 192) {if (ipVal[1] == 168) {if (ipVal[2] >= 0 && ipVal[2] <= 255) {if (ipVal[3] >= 0 && ipVal[3] <= 255) {return true;}
}
}
}
if (ipVal[0] == 127) {if (ipVal[1] == 0) {if (ipVal[2] == 0) {if (ipVal[3] >= 0 && ipVal[3] <= 8) {return true;}
}
}
}
return false;
}3. 驼峰转换
把一个由 – 或 _ 或 @ 连接的变量词组转换成驼峰写法
样例：
输入：content-type
输出：contentType思路（100/100 分）：
function camel(str) {
// TODO
let ans = "";
let upper = false;
for (let index = 0; index < str.length; index++) {const element = str[index];
if (element == '_' || element == '-' || element == '@') {upper = true;} else {if (upper) {ans += element.toUpperCase();
} else {ans += element;}
upper = false;
}
}
return ans;
};4. 星球开会
企鹅星球上一天有 N(<200000)个小时（时间不包含 0 点），对应 N 个时区，当第 1 时区一点的时候第 2 时区已经两点了，以此类推
每个时区有 Ai 个人，每个时区上的人只有在 [u,v) 时间内有空，现在想要让尽可能多的人开会，给出开会时第一时区的时刻
样例：
输入：3
2 5 6
1 3
输出：3坑点：
时区的对应有一点绕，我一开始理解成后一个时区比前一个时区落后，实际上是超前的，每后一个时区比前一个时区快 1 个小时，解决掉这个问题就没有大问题了。
另外要考虑一下时间复杂度的问题，我的优化比较差，最坏复杂度是 O(n2/2)
思路（80/100 分）：
int main() {
int n, u, v, len, pos;
long long ans, tmp;
cin >> n;
vector<int> a(n, 0);
for (int i = 0; i < n; i++)
{cin >> a[i];
}
cin >> u >> v;
u--;
v--;
len = v - u;
pos = 0;
if (len < n / 2)
{
ans = 0;
for (int i = 0; i < n; i++)
{
tmp = 0;
for (int j = 0; j < len; j++)
{tmp += a[(i + j) % n];
}
if (tmp > ans || (tmp == ans && ((n + u - pos) % n < (n + u - pos) % n)))
{
ans = tmp;
pos = i;
}
}
}
else
{
ans = INF;
for (int i = 0; i < n; i++)
{
tmp = 0;
for (int j = 0; j < n - len; j++)
{tmp += a[(i + j) % n];
}
if (tmp < ans || (tmp == ans && ((n + u - pos) % n < (n + u - pos) % n)))
{
ans = tmp;
pos = i;
}
}
}
cout << (n + u - pos) % n + 1 << endl;
return 0;
}网易校招笔试
1. 超大数和一个长整型的最大公约数。
第一题的思路比较简单，就是辗转相除法，用字符串存储大数，然后分段辗转相除
辗转相除法：
假如有两个正整数 p1,p2，其中 p1>p2，那么必然存在两个自然数 k，b，使得 p1=k*p2。
如果 p1,p2 的最大公约数是 p3，那么 p2,b 的最大公约数也是 p3。
例如 gcb(55,30)=gcb(25,30)=gcb(25,5)
2. 一个数组中长度从 1 到 n 的子序列中最大值的最小值。
题目：在一个最大长度 200000 的数组中，分别求出长度从 1 到 n 的子序列中最大值的最小值
样例：
输入：6
1 8 7 5 4 2
输出：1 4 5 7 8 8简单来说，就是把一个数组进行连续子序列的划分，从长度为 1 的子序列开始划分，每次划分子序列后，求出每个子序列的最大值，再求出所有这些最大值中最小的那个，一直到长度为 n 的子序列（序列本身）。
这题一开始把我看绕了，其实就是一道标准的 DP 题，然而我最后做的这题，考完才写出来。。。这次笔试基本是按照最差的答题顺序来的，估计跪了。
状态转移方程可以这样想出来：
设 dp[j][i] 是从数组第 j 个数字开始的长度为 i 的子序列的最大值，当长度 i =0（实际长度应该为 1，从 0 开始方便些）时，dp[j][0]等于数字本身 num[j]，从 i = 1 开始，dpj 的长度等于MAX(dp[j][i-1], dp[j+1][i-1]) 也就是前后相邻的两个长度为 i - 1 的子序列最大值中的最大值。
这题要求的是同一划分长度下所有最大值的最小值，所以在计算 dp 数组的同时还要计算这个值是否为当前划分长度的最小值，于是定义一个 min 数组，长度 100000，先初始化成最大数值, 每次计算 dp[j][i] 的时候与 min[i] 比较哪个值更小，一趟下来就能得到最小值了。
思路：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define INF 0x7FFFFFFF
using namespace std;
int num[100000] = {0};
int (*dp)[100000];
int main()
{
int n;
int min[100000] = {0};
scanf("%d", &n);
dp = (int (*)[100000])malloc(n * 100000 * sizeof(int));
for (int i = 0; i < n; i++)
{scanf("%d", &num[i]);
min[i] = INF;
}
for (int i = 0; i < n; i++) {for (int j = 0; j < n - i; j++)
{if (i == 0)
{dp[j][0] = num[j];
}
else
{dp[j][i] = MAX(dp[j][i - 1], dp[j + 1][i - 1]);
}
if (dp[j][i] < min[i])
{min[i] = dp[j][i];
}
i = i;
}
}
for (int i = 0; i < n; i++)
{if (i>0)
{printf(" ");
}
printf("%d", min[i]);
}
printf("\n");
return 0;
}3. 奇偶互换
一个数组中，奇偶数可互换，求任意次互换后字典序最小的数组序列。
个人思路：没有特别好的想法
4. 数组减一
给定一个长度 M（<=100000）的数组，然后输入 N(<=100000)个整数，每次将数组中所有大于等于该整数的元素减一，并输出改变了多少个元素，要求时间性能小于 1s。
个人思路：
用二分查找结果 70% 结果都 TLE 了，经过分析认为主要是遍历数组进行减一的操作太费时间（O(n^2)的复杂度)后来考虑用一个数组储存更新过的下标分界位置来绕过遍历减一的环节，然而没写完。
大疆校招笔试
1. 玩游戏
给定暑假时间 X 天(<=1000)，游戏数量 N 个(<=11)，接下来 N 行给定每种游戏需要花费的天数（Ai），以及通关该游戏带来的成就点数（Bi），求：在暑假 X 天里能够达成的最高成就点数。
个人思路：
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
// 需要填充一个容量为 X 的背包，使得成就点数最大
class Knapsack01 {
private:
vector<vector<int>> memo;
// 用 [0...index]的物品, 填充容积为 c 的背包的最大价值
int bestValue(const vector<int> &w, const vector<int> &v, int index, int c) {if (c <= 0 || index < 0)
return 0;
if (memo[index] != -1)
return memo[index];
int res = bestValue(w, v, index - 1, c);
if (c >= w[index])
res = max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));
memo[index] = res;
return res;
}
public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C) {assert(w.size() == v.size() && C >= 0);
int n = w.size();
if (n == 0 || C == 0)
return 0;
memo.clear();
for (int i = 0; i < n; i++)
memo.push_back(vector<int>(C + 1, -1));
return bestValue(w, v, n - 1, C);
}
};
int main() {
// X 为暑假天数，N 为游戏数量
int X, N;
cin >> X >> N;
int w, v;
// vs 存的是价值(成就点数)
// ws 存的是每一件物品的重量(天数)
vector<int> vs, ws;
for (int i = 0; i < N; i++) {
cin >> w >> v;
vs.push_back(v);
ws.push_back(w);
}
cout << Knapsack01().knapsack01(ws, vs, X) << endl;
return 0;
}PS. 这题我特么写成完全背包了，其实是 01 背包，结果只对 50%。
2. 输入指令：
输入指令集长度 M 和指令操作长度 N 接下来输入 M 个指令 (字符串)=》指令值(字符串) 的映射关系 然后随机输入 N 个指令，要求输出对应指令值。
个人思路：
最简单的用 c ++ map 容器，然而忘记 map 写法，耽误大量时间，超级遗憾。
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
map<string, string> ops;
int x, y;
cin >> x >> y;
for (int i = 0; i < x; i++)
{
string a, b;
cin >> a >> b;
ops[a] = b;
}
for (int i = 0; i < y; i++)
{
string op;
cin >> op;
cout << ops[op] << endl;
}
}3. 买水果
给定 N 块钱，M 种水果，每种水果价格 Pi，其中有 X 种特别喜欢的水果，给定不同水果喜欢程度的排序，并要求排序靠前的水果购买量不得小于靠后的，求所有把钱花光的可能性，结果对 10000007 取模。
个人思路：
跪了 …
字节跳动校招笔试
1. 上学闹钟 O(nlogn)
小明定了 n 个闹钟，他只能在闹钟响起时出发去学校，每个闹钟时间分别为 hi 点 mi 分，小明家到学校要 x 分钟，学校上课时间 a 点 b 分（0-24 小时，0-59 分钟），求他最晚几点起
输入：3 // 定了几个闹钟
5 0 // 第 1 个闹钟的小时数和分钟数
6 0 // 第 2 个闹钟的小时数和分钟数
7 0 // 第 3 个闹钟的小时数和分钟数
59 // 到学校要多少分钟
6 59 // 上课的小时数和分钟数
输出：6 0 // 最晚的起床时间思路（80/100 分）：
纯智障思路，自定义结构体存储闹钟时间，全部输入后对闹钟时间从晚到早排序，接下来从前往后遍历闹钟时间，计算从当前时刻出发到学校的时间，输出第一个能够到达学校的，由于算法很粗劣，很明显被卡边界了，没时间管了直接看下一题。
代码：
struct Time
{
int h;
int m;
friend bool operator < (Time a, TIme b){if(a.h == b.h){return a.m > b.m;}
return a.h > b.h;
}
}
int main()
{
int n, x, a, b, rest;
cin >> n;
Time* time = (Time*)malloc(n * sizeof(Time));
for (int i = 0; i < n; i++)
{cin >> time[i].h >> time[i].m;
}
sort(time, time + n);
cin >> x;
cin >> a >> b;
for (int i = 0; i < n; i++)
{
rest = 0;
if (time[i].h < a || time[i].h == a && time[i].m < b)
{rest = (a - time[i].h) * 60 + b - time[i].m;
if (rest >= x)
{cout << time[i].h << ' ' << time[i].m << endl;
break;
}
}
}
return 0;
}2. 加密通信 O(n)
小明和小红采用密码加密通信，每次通信有固定的明文长度 n 和加密次数 k。
比如：密码二进制明文是 1001010，加密次数是 4，则每次将密文右移 1 位与明文做异或操作，总共位移 3 次（k=4, 所以 k – 1 = 3）
输入：7 4 // n k
1110100110 // 密文
输出：1001010 // 明文
解释：1001010---
-1001010--
--1001010-
---1001010加密次数为 4，故对于明文右移 4 -1= 3 轮，每轮与当前密文进行一次异或，故 1001010 对应密文为 1110100110
思路（100/100 分）：
一道标准的异或数学题，不知道该怎么归类，有一点考数学的感觉，看几眼就能看出规律了直接上代码
简单讲一下思路：
首先密文和明文第 1 位是一样的，看一下上方样例里的解释就懂了。
然后考虑第 2 到 k - 1 位，可以发现这一段的每一位都是由前一位密文的异或结果再与当前位明文异或得到的。
接下来考虑第 k 到 n - 1 位，观察规律可以发现这一段的每一位都是由前一位密文与第 i - k 位明文异或得到的结果再与当前位明文异或得到的。
如何消除异或影响大家应该都能理解，因此只要把参与异或的部分再与密文异或一下即可得到明文。
int main() {
int n, k, tmp;
string s,ans="";
cin >> n >> k;
cin >> s;
ans += s[0];
for (int i = 1; i < k; i++)
{tmp = (int)(s[i] - '0') ^ (int)(s[i - 1] - '0');
ans += tmp + '0';
}
for (int i = k; i < n; i++)
{ans += (int)(s[i] - '0') ^ (int)(s[i - 1] - '0') ^ (int)(ans[i - k] - '0') + '0';
}
cout << ans;
return 0;
}3. 发工资 O(n)
王大锤要给员工发工资，员工从左到右坐成一排，每个员工知道彼此的资历，每个员工只知道自己左右员工的工资，如果某员工比左边或右边的人资历老，那他一定比这个人工资高 100 元，每个人最低工资 100 元，求王大锤最低给多少工资。
样例
输入：4 // 几个员工
3 9 2 7 // 员工顺序以及对应的资历
输出：600 //100 元，200 元，100 元，200 元
6
1 2 3 4 5 6
2100 //100，200，300，400，500，600
5
1 1 1 1 1
500 //100，100，100，100，100
8
1 2 3 4 3 2 3 4
1800 //100 200 300 400 200 100 200 300
8
3 4 3 4 3 4 3 4
1200 //100 200 100 200 100 200 100 200
5
1 2 3 4 1
1100 //100 200 300 400 500思路（100/100 分）：
广度优先搜索，可以把员工序列看作一棵多根树，每个工资最低的员工就是根节点，一个员工的工资其实就是他在多根树里的深度，
首先在输入的时候找到比左右资历都年轻的员工入队，每次从队列 pop 一个员工，然后判断该员工的最小工资，然后判断左右员工是否可以入队，直到所有员工出队
int main() {
int n, now;
long long ans = 0;
cin >> n;
if (n == 0)
{
cout << 0 << endl;
return 0;
}
vector<int> epy(n, 0), depth(n, 0);
queue<int> sal;
for (int i = 0; i < n; i++)
{cin >> epy[i];
if (i > 1 && epy[i - 1] <= epy[i - 2] && epy[i - 1] <= epy[i])
{depth[i - 1] = 1;
sal.push(i - 1);
}
}
if (epy[0] <= epy[1])
{depth[0] = 1;
sal.push(0);
}
if (epy[n - 1] <= epy[n - 2])
{depth[n - 1] = 1;
sal.push(n - 1);
}
while (!sal.empty())
{now = sal.front();
int left = (now > 0 && epy[now-1] < epy[now]) ? depth[now - 1] : 0;
int right = (now < n - 1 && epy[now + 1] < epy[now]) ? depth[now + 1] : 0;
sal.pop();
if (depth[now] == 0)
{depth[now] = max(left, right) + 1;
}
//left
if (now > 0 && depth[now - 1] == 0 && (now == 1 || epy[now - 2] > epy[now - 1] || depth[now - 2] > 0))
{sal.push(now - 1);
}
//right
if (now < n - 1 && (depth[now + 1] == 0) && (now == n - 2 || epy[now + 2] > epy[now + 1] || depth[now + 2] > 0))
{sal.push(now + 1);
}
}
for (auto salary : depth) {ans += salary;}
cout << ans * 100 << endl;
}
