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

1.数据结构和算法

1.1 反转单向链表

代码语言：javascript复制

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 如何以递归和非递归方式实现二分查找

非递归：

代码语言：javascript复制

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;
}

递归：

代码语言：javascript复制

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 求二叉树的深度

代码语言：javascript复制

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).

代码语言：javascript复制

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;
    }
}

代码语言：javascript复制

    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 如何把字符串中的指定字符移动到字符串的前面

代码语言：javascript复制

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 排序算法总结

冒泡排序

代码语言：javascript复制

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 区别

代码语言：javascript复制

interface User {
  name: string,
  age: number
}

insterface SetUser {
  (name: string, age: number) : void;
}


type SetUser = (name: string, age: number) => void;

// 都允许扩展


// interface extends type

type Name = {
  name: string;
}

instance

• 不同点

代码语言：javascript复制

// 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 捕获异常 （推荐）

代码语言：javascript复制

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 里面

代码语言：javascript复制

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('异常了)
  }
}

代码语言：javascript复制

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

     }
  }
}

注意

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

代码语言：javascript复制

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('失败了')
}

// 没有错误

缓存 typescript javascript node.js 编程算法

0 人点赞