0425 问了些八股（10min），没问项目，做了三题手撕（50min）
在pdd的面试平台，需要共享屏幕。面试官很和蔼，比约的时间早进面试间。
不会的也说没事，手撕也提示
0429更新，已经挂了QAQ
自我介绍（1min）
- 常见的集合有哪些
- 哈希表有哪些实现方式
- 除了哈希表，还有什么数据结构能实现输入key，找到他的value
位图、布隆过滤器能查key是否存在
前缀树找字符串是否存在
跳表、平衡树找有序数据
- 哈希表怎么实现的
- 为什么链表长度大于8，要用红黑树
在链表中查找元素需要逐个遍历，时间复杂度为 _O(n)_。如果哈希冲突严重（例如大量元素映射到同一个桶），链表会变得很长，导致查询性能急剧下降。
在正常情况下，链表长度很少会达到8。根据泊松分布统计，长度达到8的概率约为 0.00000006（即千万分之一）。因此，这种转换是针对极端情况的优化。
- 为什么红黑树是log(n)的时间复杂度
红黑树是自平衡的二叉搜索树，红黑树通过颜色规则和旋转操作保持近似平衡
- 优先队列怎么实现的
用堆实现的，大根堆：父节点的值大于两个子节点
- 说一下堆怎么实现的，pop之后堆怎么调整
小根堆的建立：堆一般用数组实现，父节点下标为i，子节点的下标为2i + 1, 2i + 2。从最后一个非叶子节点开始调整，从父节点的子节点中选择一个小于父节点的节点，交换位置，递归再往下调整。
小根堆的插入：将新元素插入在数组末尾，将新节点和它的父节点开始比较，如果新节点比父节点小，就交换两者；继续这个过程，知道满足堆的要求
小根堆的删除：将堆顶元素和末尾元素进行交换，移除末尾元素（也就是前堆顶），将新堆顶比较、下沉，直到满足堆的要求。
- 说一下TCP协议
- 说一下IP协议
- 说一下HTTP协议和TCP/IP整体关系
HTTP是TCP/IP协议栈的上层协议，专注于Web应用逻辑，而TCP/IP负责底层数据传输和网络互联。
HTTP将请求/响应消息封装成TCP报文段
IP协议将TCP报文分段为数据包，通过路由选择送达目标服务器
- 说一下HTTPS
- 说一下HTTPS的原理
- 说一下公钥、私钥和数字证书
- 为什么一开始要用非对称加密，后来用对称加密
- HTTPS 如何防范中间人攻击
手撕
- 给了两个有序的数组（数组中有重复元素），把a中存在，但b中不存在的数据加入新数组，利用a和b有序的性质。
双指针，一个指针指向a，一个指针指向b
- 一个有序序列构造成二叉搜索树有很多种结构，如何判断两个二叉搜索树是一样的。
先说了中序遍历获得序列判断，但面试官提示说能不能一边遍历一边判断，比如最小的数不相等就不往下遍历了
- 给一个字符数组，写一个排序函数，数字排在字母前面，但数字之间相对顺序不变，字母之间相对顺序不变。（原地排序，不能用新数组）
一些问题的代码
构建小根堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void heapify(int arr[], int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest])
smallest = left;
if (right < n && arr[right] < arr[smallest])
smallest = right;
if (smallest != i) {
swap(arr[i], arr[smallest]);
heapify(arr, n, smallest);
}
}
void buildMinHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
}
|
小根堆插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| ```java
public int insert(int[] heap, int size, int val) {
if (size >= heap.length) {
throw new RuntimeException("Heap is full");
}
heap[size] = val;
int child = size;
int parent = (child - 1) / 2;
while (child > 0 && heap[child] < heap[parent]) {
swap(heap, child, parent);
child = parent;
parent = (child - 1) / 2;
}
return size + 1;
}
|
小根堆删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public int deleteMin(int[] heap, int size) {
if (size <= 0) {
throw new RuntimeException("Heap is empty");
}
heap[0] = heap[size - 1];
size--;
int parent = 0;
while (true) {
int left = 2 * parent + 1;
int right = 2 * parent + 2;
int min = parent;
if (left < size && heap[left] < heap[min]) {
min = left;
}
if (right < size && heap[right] < heap[min]) {
min = right;
}
if (min == parent) break;
swap(heap, parent, min);
parent = min;
}
return size;
}
|
手撕1
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public static List<Integer> findDifference(int[] A, int[] B) {
List<Integer> C = new ArrayList<>();
int i = 0, j = 0;
while (i < A.length && j < B.length) {
if (A[i] < B[j]) {
if(i > 0 && A[i] == A[i - 1]) {
i++;
continue;
}
C.add(A[i]);
i++;
} else if (A[i] == B[j]) {
i++;
j++;
} else {
j++;
}
}
while (i < A.length) {
C.add(A[i]);
i++;
}
return C;
}
|
手撕2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public boolean isSameTree(TreeNode p, TreeNode q) {
TreeNode cur1 = p, cur2 = q;
Stack<TreeNode> st1 = new Stack<>();
Stack<TreeNode> st2 = new Stack<>();
while((cur1 != null || !st1.isEmpty()) && (cur2 != null || st2.isEmpty())) {
while(cur1 != null) {
st1.add(cur1);
cur1 = cur1.left;
}
while(cur2 != null) {
st2.add(cur2);
cur2 = cur2.left;
}
cur1 = st1.pop();
cur2 = st2.pop();
if(cur1.val != cur2.val) {
return false;
}
cur1 = cur1.right;
cur2 = cur2.right;
}
return cur1 == null && cur2 == null;
}
|
手撕3
每当遇到一个数字字符，并且它前面是一个字母字符时，就把它向前交换。
这样保证数字和字符的相对顺序不变
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public static void sortDigitsBeforeLetters(char[] arr) {
int n = arr.length;
for(int i = 1; i < n; i ++ ) {
if(arr[i] >= '0' && arr[i] <= '9') {
char temp = arr[i];
int j = i - 1;
while(j >= 0 && arr[j] >= 'a' && arr[j] <= 'z') {
arr[j + 1] = arr[j];
j -- ;
}
arr[j + 1] = temp;
}
}
}
|