一面--2.6
1.介绍你所知道的常用的时间复杂度
2.解释每一个数据结构的意义，在什么场景中使用？
3.每个数据结构查找与插入的时间复杂度
4.讲一个你所熟知的技术？
5.kv存储项目中初始化的耗时？
6.怎么确定每一个桶的最后一个数据？
7.编程题：
//5 个 1 - 100 的整数
// 输出前面 4 个数通过加法的 1 个或者多个等于第 5 个数的组合
// 例如 1，1，1，1，3 ===> 1，1，1
// 1，2，3，4，10 ====> 1，2，3，4
// 如果没有，输出空。
提问：时间复杂度能优化到2^n-1以下吗
思路：深度优先搜索遍历每一种情况，可以通过剪枝进行优化
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class test02_2 {
public static List<List<Integer>> res;
public static int currretnSum;
public static Deque<Integer> path;
public static int cnt;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] nums = new int[5];
for(int i = 0;i<5;i++){
nums[i] = in.nextInt();
}
List<List<Integer>> res = targetSum(nums);
for(List<Integer> temp : res){
for(int t : temp){
System.out.print(t + " ");
}
System.out.println();
}
System.out.println("时间复杂度为："+cnt);
}
public static List<List<Integer>> targetSum(int[] nums){
res = new LinkedList<>();
currretnSum = 0;
path = new LinkedList<>();
cnt = 0;
int target = nums[4];
dfs(0,target,nums);
return res;
}
public static void dfs(int k, int target,int[] nums){
for(int i = k;i<4;i++){
cnt++;
currretnSum += nums[i];
path.addLast(nums[i]);
if(currretnSum == target){
res.add(new LinkedList<>(path));
}
//剪枝优化
if(currretnSum>target){
currretnSum -= nums[i];
path.removeLast();
return;
}
dfs(i+1,target,nums);
currretnSum -= nums[i];
path.removeLast();
}
}
}
二面--2.8
1.聊一下研究生的研究方向？
2.讲一下秒杀项目
3.redis如何mysql保证一致
注：这里应该指的是缓存的读写策略
- 读策略：在读取是先读取缓存，如果命中则直接返回，如果未命中，则访问数据库然后回填到数据库中
- 写策略：先更新数据库，然后输出缓存中的数据。
4.如何压测，压测的结果，了解Jmter的原理吗？
5.如何体现该系统的高并发？
6.限流适用什么做的？
7.手写令牌桶算法的介绍？
8.滑动时间窗口算法如何设计，谈下你的实现思路？
9.数据库：id，age，性别三个字短，查出age>20性别是男的记录，sql是应该怎么写？
10.数据表的索引应该怎么设计？
11.联合索引中age与性别的先后顺序？
这个应该回答有误，正确答案应该是联合索引讲性别字段放前面，因为联合索引要符合最左匹配原则，最左匹配原则遇到范围查找会失效，原因是接下来的第二个字段不是局部有序的，无法利用二分查找继续优化，所以会将满足第一个条件的所有情况进行回表（但有索引下伸优化，会以o（n）的时间复杂度比较第二个字段），如果将性别放在前面，则查到性别为男的所有索引，第二个字段age是有序排列的。
重点：联合索引遇到范围查找失效，范围查找后的字段无法继续匹配。
12.你最近看的书？
13.一门新语言比如rust应该怎么学？
14.未来的规划？
最近面试遇到的算法题；
1.设计一个运算器
力扣227--基本计算器2
2.
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
堆排序，大顶堆和小顶堆才是最优算法
（堆排序）
让数组的前半部分为大顶堆，需要最大值。后半部分为小顶堆，需要最小值
偶数是两边数目一样，取大顶堆的最大值和小顶堆的最小值的平均
奇数时，使右边边数目多一个，直接取小顶堆的最小值即可
由于左边的所有值都小于右边的。所以想往左边插入，则需先插入到右边的小顶堆，之后再弹出个最小的加到左边。反之亦然
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
PriorityQueue<Integer> min_heap=new PriorityQueue<>();
PriorityQueue<Integer> max_heap=new PriorityQueue<>(new Comparator<Integer>(){
@Override
public int compare(Integer o1,Integer o2){
return o2-o1;//默认是小顶堆，o1-o2
}
});
int count=0;//记录已获取数字的个数
public void Insert(Integer num) {
if(count%2==0){
max_heap.offer(num);
int tmp=max_heap.poll();
min_heap.offer(tmp);
}
else{
min_heap.offer(num);
int tmp=min_heap.poll();
max_heap.offer(tmp);
}
count++;
}
public Double GetMedian() {
if(count%2==0){
return new Double(min_heap.peek()+max_heap.peek())/2;
}
else{
return new Double(min_heap.peek());
}
}
}