一、引言
算法在目前的大厂面试当中属于必须做的一个环节，作者根据面试过的大厂聊聊算法这块各个大厂的难度和常考题型。
二、难度
最难：某猪
这就很神奇，阿里的其他部门都不像他这么难，手写lru之类的给你上强度，但是他还不是为难你，因为笔试是他的第一轮，这时候什么都还没问你
次难：鹅厂、字节
正常：豚厂、B站、快手、得物、pdd
简单：蚂蚁
这个也很神奇，作者参加过蚂蚁两个部门的面试，都冲到了人事面，但是算法题非常简单，属于走走过场
三、题型
字节都喜欢做动态规划相关的，每一轮都要做题。其他家基本都是有一轮做题
比如买卖股票的最佳时机，第二档的难度。但是聊起来很靠运气，聊的开心没做出来也无所谓，只要你是有出彩点的，有的纯粹是为难你。
给你一个整数数组 prices ，
其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。
你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if(n < 2){
return 0;
}
int[][] dp = new int[n][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1; i < n;i++){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
}
return dp[n-1][0];
}
某猪喜欢数据结构相关的，比如lru、树之类的，还会给表让你写sql，考察挺全面的。一面一次性做完四道题
public class LruCache {
class Node {
String key;
Object value;
Node prev;
Node next;
public Node(String key, Object value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<String, Node> cache;
private Node head;
private Node tail;
public LruCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.head = new Node("head", 0);
this.tail = new Node("tail", 0);
head.next = tail;
tail.prev = head;
}
public Object get(String key) {
Node node = cache.get(key);
if (node != null) {
moveToHead(node);
return node.value;
}
return null;
}
public void put(String key, Object value) {
Node node = cache.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
} else {
node = new Node(key, value);
cache.put(key, node);
addToHead(node);
if (cache.size() > capacity) {
Node removedNode = removeTail();
cache.remove(removedNode.key);
}
}
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private Node removeTail() {
Node removedNode = tail.prev;
removeNode(removedNode);
return removedNode;
}
}
豚厂不是非常在乎这个，把解题思路说清楚也行，会结合业务做一些字符串的题目。
B站喜欢dfs和回溯，字节有时候也会dfs，要把全排列的几个拓展题都会
给定一个不含重复数字的数组 nums，返回其 所有可能的全排列。
你可以 按任意顺序 返回答案。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/**
* @author LiFang
* @version 1.0
* @since 2022/2/17 12:01
*/
public class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
// 使用一个动态数组保存所有可能的全排列
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
boolean[] used = new boolean[len];
ArrayList<Integer> path = new ArrayList<>(len);
dfs(nums, len, 0, path, used, res);
return res;
}
private void dfs(int[] nums, int len, int depth,
ArrayList<Integer> path, boolean[] used,
List<List<Integer>> res) {
if (depth == len) {
// java中参数传递是址传递，需要进行深拷贝（重新开辟一个内 ）来记录某一时刻path的状态（相当于快照）
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < len; i++) {
if (!used[i]) {
path.add(nums[i]);
used[i] = true; // 如果used[i]已经添加进path了，就记录used[i]的状态为true
System.out.println(" 递归之前 => " + path);
dfs(nums, len, depth + 1, path, used, res); //递归把nums[i]之后的数排列完
used[i] = false; // 以used[i]开头的数列已经排列完了，就将used[i]状态置为false
path.remove(path.get(path.size()-1)); // 在path的末尾移除掉nums[i]（回溯）
System.out.println("递归之后 => " + path);
}
}
}
}
鹅厂和pdd喜欢字符串
给定两个字符串形式的非负整数 num1 和num2
计算它们的和并同样以字符串形式返回。
public String addStrings(String num1, String num2) {
StringBuilder res = new StringBuilder("");
int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
while(i >= 0 || j >= 0){
int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
int tmp = n1 + n2 + carry;
carry = tmp / 10;
res.append(tmp % 10);
i--;
j--;
}
// 最后的进位不为零，单独处理
if(carry == 1) res.append(1);
// 逆输出正确的和
return res.reverse().toString();
}
蚂蚁简单的一些算法估计中等难度都够不上
还有一些做过的题都不记得了，大致也就是动态规划、字符串、dfs、回溯这几类频率最高
还有一些面试题也贴在这儿吧，都是八股文
http1.0与2.0的区别
为什么不重新封装通信协议，而使用http
物联网协议的区别
redis为什么快
分布式事务目前的缺点
aof写满会怎么样
宕机怎么保证redis与mysql一致性
线程池空闲之后线程什么状态，枚举值多少
threadlocal对象是在堆还是虚拟机栈
4c8g的服务，服务处理简单，spring线程池应该设置多少线程
虚拟机栈深度为什么设置2048，不设置不就不会溢出了嘛
tomcat线程数
es分词器设置
四、总结
以作者的经验来说，刷题是必须的，hot100都掌握就行，出的再难再偏就是纯粹不想要你了。毕竟这种算法主要还是看你的准备和意志力，刷题真的挺烦人的，但是这些大厂都要你坚持，那你行不行。