数据结构和算法面试常见题必考以及前端面试题

1.数据结构和算法

1.1 反转单向链表

public class Node {public int value;public Node next;
}public Node reverseList(Node head) {Node pre = null;Node next = null;while (head != null) {next = head.next;head.next = pre;pre = head;head = head.next}return pre;
}

1.2 在顺序表中插入和删除一个结点平均移动多少个结点？

在等概率的情况下，顺序表插入一个结点需要平均移动n/2个结点。删除一个结点需要平均移动(n-1)/2个结点。具体的移动次数取决于长度n和位置i，两者越近，移动的越少。

1.3 如何以递归和非递归方式实现二分查找

非递归：

private int binarySearch(int[] arr, int searchKey) {if (arr == null) {return -1;}int n = arr.length;int left = 0;int right = n - 1;while (left <= right) {int mid = left + ((right -left) >> 1);if (arr[mid] > searchKey) {right = mid - 1;} else if (arr[mid] < searchKey) {left = mid + 1;} else {return mid;}}return -1;
}

递归：

private int binarySearchRecursive(int[] arr, int left, int right) {if (arr == null) {return -1;}int n = arr.length;int left = 0;int right = n -1;while (left <= right) {int mid = left + ((right - left) >> 1);if (arr[mid] > searchKey) {binarySearchRecursive(arr, left, mid - 1);} else if (arr[mid] < searchKey) {binarySearchRecursive(arr, mid + 1, right);} else {return mid;}}return -1;
}

需要注意的是，二分查找算法的时间复杂度为O(logn)，最坏情况下的时间复杂度为O(logn)

1.4 求二叉树的深度

private int getDepth(Node node) {if (node == null) {return 0;}int left = getDepth(node.left);int right = getDepth(node.right);return left > right ? (left + 1) : (right + 1);
}

1.5 如何在排序的数组中，找出给定数字出现的次数

其实我的想法是通过hashmap来实现，其实也没必要在乎数组是否是排序的。时间复杂度方面，遍历整个数组，将数组元素添加到hash中，最后再查询，时间复杂度应该是O(n).

function getTimes(arr, key) {var n = arr.length;var hash = {};for (var i = 0; i < n; i ++) {var ele = arr[i];if (!hash[ele]) {hash[ele] = 1;} else {hash[ele] ++;}}if (hash[key]) {return hash[key];    } else {return -1;}
}

    private static void stasTimes(int[] arr, int key) {int len = arr.length;HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();for (int i =0; i < len; i++) {if (hash.containsKey(arr[i])) {Integer val = hash.get(arr[i]) + 1;hash.put(arr[i], val);} else {hash.put(arr[i], 1);}}for (Integer hashKey: hash.keySet()) {if (hashKey.intValue() == key) {System.out.println(key + " has appeared " + hash.get(hashKey) + " times");}}}

1.6 如何把字符串中的指定字符移动到字符串的前面

private char[] moveChar(String str, char a) {char[] arr = str.toCharArray();int i = arr.length - 1;while (arr[i] != a) {i --;}for (int j = i - 1; j >= 0; j --) {if (arr[j] != a) {arr[i] = arr[j];arr[j] = a;i --;}}return arr;
}

1.7 排序算法总结

冒泡排序

public static void bubbleSort(int[] arr) {if (arr == null || arr.length == 0) {return;}for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j+1]]) {swap(arr, j+1, j);}}}
}
public static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

1.8 数组和链表的区别

• 数组必须事先定义固定的长度，链表采用动态分配内存的形式实现。
• 数组从栈中分配空间，自由度小；链表从对中分配内存，自由度大，但管理麻烦。
• 数组中的数据在内存中时顺序存储的，链表是随机存储的。
• 数组便于查询；链表便于插入删除。

1.9 什么排序元素比较次数和数组初始状态无关

选择排序

##1.10 排序算法比较

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
插入排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
希尔排序	O(nlogn)	O(nlog^2n)	O(nlog^2n)	O(1)	不稳定
归并排序	O(nlog(n))	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(logn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定
桶排序	O(n+k)	O(n+k)	O(n^2)	O(n+k)	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	稳定
.

2.面试题

2.1 百度一面

1. 如何实现水平垂直居中
2. Position 属性的几种区别
3. 讲一下盒子模型
4. BFC 怎么实现
5. 如何实现左右固定，中间自适应的布局
6. 用 JS 实现一个柯里化函数
7. 用 JS 实现一个栈
8. 实现一个 TS 类，如 Partial 、Tick
9. JS 任务执行机制
10. 给出一段 Promise+setTimeout 的代码，写出输出顺序
11. Promise 有哪些方法
12. 对 async/await 的理解
13. HTTP 请求响应头有哪些
14. HTTPS 的是如何进行数据加密的

2.2 字节

1. redux 中间件有了解吗
2. Hooks 有了解吗
3. Canvas 了解吗
4. 开发过程中图表组件用的是是什么，看过 Echarts 的源码吗
5. 在开发过程中遇到了哪些难点

2.3 小米

一面（技术面）

基本围绕简历聊，印象比较深的有几个问题

• 1.vue 的源码是否看过，说一下比较有收获的几个点
• 2.说一下 css 的三大特性并展开说一下应用场景
• 3.说一下 CSS 七层层叠顺序
• 4.说一下从浏览器输入网址到页面渲染中间发生了什么
• 5.说下你知道的 HTTP 状态码并说出它们的出现场景

二面（技术面）

主要聊项目，技术聊的比较少，说一下印象深的问题

• 1.如何实现一个简单的单点登录
• 2.说一下关系数据库和非关系数据库的区别，并说下使用场景
• 3.说一下关系数据库外键的使用

三面（技术面）

有印象的问题

• 1.手写翻转二叉树
• 2.说下归并排序的思路和应用场景
• 3.说下你知道的设计模式及应用场景
• 4.说一下从浏览器输入网址到页面渲染中间发生了什么
• 5.如何用缓存进行前端优化；说下浏览器缓存、DNS 缓存、nginx 缓存、服务端缓存的区别；强缓存和协商缓存的应用

四面（技术面）

项目经历为主，以及管理方面的问题，技术方面没聊，有印象的问题

• 1.如何确保项目按时交付
• 2.如何安排开发和管理的时间分配
• 3.如何体现项目价值

五面（技术加面）

感觉是专门准备了一些有深度的问题来问，有印象的有

• 1.如何进行前端性能优化
• 2.说说重绘、重排、回流
• 3.如何开启 GPU 加速，GPU 加速的作用是什么
• 4.是否了解浏览器内核相关技术
• 5.说一下 jsbridge 是如何实现的
• 6.说一下 V8 的垃圾回收机制
• 7.说一下 VUE3.0 比 VUE2.0 做了哪些改动

1、关于ES6 Proxy (2019 今日头条)

2、你觉得TypeScript 和 JavaScript有什么区别

• 语言层面
• Javascript 和 TypeScript 都是ECMAScript 的具体实现
• TypeScript 是静态类型，而JavaScript 是动态类型
• TypeScript 扩展了JavaScript 并且完全包容javascript
  执行方面
• TS 需要编译
• JS 不需要编译
  厂商层面
• Javascript 由Netscape 率先

TypeScript中的 type 和 instance 区别

interface User {name: string,age: number
}insterface SetUser {(name: string, age: number) : void;
}type SetUser = (name: string, age: number) => void;// 都允许扩展// interface extends typetype Name = {name: string;
}instance

• 不同点

// type 不是一个类型，它是类型别名// type 可以声明基本类型别名，联合类型，元祖等类型// 基本类型别名type Name = string// interface 可以 而type不行// interface 能够声明合并
interface User {name: string,age: number
}
interface User {sex: string
}new Error 不会终止成员运行

async / await 如果右边的方法执行出错了该怎么办 （百度一面2020)

• 方式一 使用Promise 的catch 方法捕获异常 不完善
• 方式二 在async 函数中使用try -catch 捕获异常 （推荐）

async function f() {console.log(1)await new Promise((resolve, reject) => {console.log(2)throw new Error('出错了')}).catch(err => {console.log(3)console.log('执行失败了')})console.log(4)
}
// 1234

使用 try-catch 的时候，会把容易引发异常的代码写到try 里面

async function f() {try {// await new Promise((resolve, reject) => {//   // throw new Error('出错了')//   resolve()// })await new Promise((resolve, reject) => {throw new Error('出错了')})console.log('正常输出')} catch (err) {// 这里用来捕获异常console.log('异常了)}
}

async function Login () {// 接口请求异常， // 用户名错误、密码错误、用户不存在、500// 前提条件： 接口把所有的异常都通过HTTp状态吗来返回// 尤其是在使用axios 请求库的时候， 它会把所有超出200- 300范围的状态码捕获try {catch (err) {}}
}

注意

• try-catch 只能捕获同步异常
• 还有async 中的await Promise异常
• try-catch 不能直接捕获Promise 调用异常

try {const p = new Promise((resolve, reject) => {throw new Error('error')fs.readFile('./login.js', (err, data) => {if (err) {reject(err)} else {resolve(data)}})})// 这样可以捕获到// p.then(data => {//   console.log(data)// }).catch (err => {//   console.log('手动 调用catch 捕获异常')// })
} catch (err) {console.log('失败了')
}// 没有错误