10月8号 虾皮、喜马拉雅秋招笔试记录
虾皮
有单选，多选，3道编程。只有最后一题编程偏难
相关知识点记录：
- cat grep chmod的区别
- 下列哪个属于对称加密：AES,DES,RSA,MD5
- 选择排序和堆排序是否是稳定的
- 二者都不稳定。在选择排序过程中，最小（或最大）元素会被选出并与当前排序部分的最后一个元素交换。堆排序通过构建堆来实现排序，而在堆的操作过程中，元素的位置可能会发生变化，特别是当有相同值的元素在堆中时，它们的相对顺序可能会被打乱。因此，堆排序也是不稳定的。
- 分布式系统的CAP理论
AES 和 DES 都属于对称加密。
而 RSA DSA是一种非对称加密算法，MD5 是一种哈希算法
第三题的编程题目：
给你一个整数数组nums,找出并返回所有该数组中不同的递增子序列个数，递增子序列中至少有两个元素
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
例如，若数组为{4,6,7,7}，则答案应为8
喜马拉雅
有单选，多选，2道编程。共一小时。
相关知识点记录：
- 广度优先除了队列还可以用什么数据结构=》链表，数组
- 归并排序是否会退化，最坏情况是什么=》无论输入数据的排列方式如何，归并排序的时间复杂度始终是 O(n log n)。并且它是稳定的
- 迪杰斯特拉是深度优先吗=》不是。是贪心算法
- 什么情况会发生page fault=》1.缺页，当进程试图访问某个页面时，该页面并不在物理内存中，而是在硬盘。这可能是由于：a.当一个程序第一次被加载到内存时，其所有的页面并不一定会被立即加载 b.页面被换出 2.访问被保护的页面
此时会发生什么：1.触发中断，进入内核态，由操作系统接管控制权 2.确定缺失的页面的物理地址，将页面从硬盘加载到内存，如果内存已满则会有换页 3.更新页表以反映新加载的页面 4.恢复之前被暂停的进程，重新执行导致页面错误的指令
- nginx支持反向代理 负载均衡 虚拟主机吗
反向代理 是指客户端的请求先到达代理服务器（Nginx），然后由代理服务器将请求转发到后端的实际服务器上。Nginx 作为反向代理具有以下优点：
- 隐藏真实服务器：客户端只与 Nginx 交互，后端服务器的 IP 地址被隐藏，增强了安全性。
- SSL 终止：可以在 Nginx 中处理 SSL 加密，从而减轻后端服务器的负担。
- 请求分发：Nginx 可以根据自定义规则将请求分发到不同的后端服务器。
主要的负载均衡方法包括：
- 轮询（Round Robin）：默认方法，按顺序将请求分发到后端服务器。
- 最少连接（Least Connections）：将请求发送到当前连接数最少的服务器。
- IP 哈希（IP Hash）：根据客户端 IP 地址进行哈希，将请求路由到特定的服务器，适合需要会话保持的场景。
虚拟主机 是指在同一台服务器上配置多个网站或应用。Nginx 支持基于主机名和 IP 地址的虚拟主机配置。
意义：资源共享。多个域名可以共享同一个 IP 地址，但每个域名都可以配置不同的 SSL 证书。这样就不需要为每个网站购买独立的 IP 地址。
具体功能如下：
- 基于主机名的虚拟主机：根据请求的
Host头部信息，将请求转发到不同的后端服务。例如，你可以为example.com和example.org配置不同的后端。- 基于 IP 地址的虚拟主机：可以根据请求的 IP 地址来处理不同的请求。
- SSL协议握手的时候要交换哪些信息
握手的目的是为了建立一个安全的连接，并在客户端和服务器之间协商加密参数。
客户端 Hello 消息
客户端向服务器发送一条
ClientHello消息，内容包括：
- 协议版本：支持的 SSL/TLS 版本（如 TLS 1.2, TLS 1.3 等）。
- 随机数：一个随机生成的数值，用于生成会话密钥。
- 加密套件列表：客户端支持的加密算法组合，包括对称加密、非对称加密和散列函数的列表。
- 压缩方法：支持的压缩算法（如果使用）。
- 扩展信息：如支持的 Server Name Indication (SNI)，用于指示服务器名等。
2. 服务器 Hello 消息
服务器回应一个
ServerHello消息，内容包括：
- 协议版本：选择的 SSL/TLS 版本（通常是客户端支持的最高版本）。
- 随机数：服务器生成的随机数，用于密钥生成。
- 加密套件：服务器选择的加密算法组合。
- 压缩方法：服务器选择的压缩算法。
- 扩展信息：可能包含关于会话恢复或其他参数的信息。
3. 服务器证书
- 服务器发送其数字证书，包含服务器的公钥以及由证书颁发机构 (CA) 签名的信息。客户端使用此证书验证服务器的身份。
4. 证书链
- 服务器可能还会发送一系列中间证书，以便客户端可以验证服务器证书的有效性。整个证书链必须由客户端信任的根证书颁发。
5. 服务器密钥交换（可选）
- 如果使用的加密算法（如 Diffie-Hellman）需要服务器提供额外的参数，服务器会在此阶段发送这些参数。
6. 服务器 Hello Done
- 服务器发送
ServerHelloDone消息，表示其所有的 Hello 消息已发送完毕，并准备接收客户端的响应。7. 客户端密钥交换
- 客户端生成一个预主密钥（Pre-Master Secret），并用服务器的公钥加密后发送给服务器。只有服务器可以使用私钥解密此信息。
8. 改变密码规范（Change Cipher Spec）
- 客户端发送
ChangeCipherSpec消息，通知服务器后续消息将使用协商的加密算法和密钥。9. 握手完成（Finished）
- 客户端发送一个
Finished消息，表示客户端的握手消息已结束。此消息经过加密，确认所有的握手信息没有被篡改。10. 服务器也进行 Change Cipher Spec 和 Finished
- 服务器收到客户端的
Finished消息后，也发送自己的ChangeCipherSpec消息，随后发送Finished消息，确认握手完成。
编程
第一题90%通过 字符串s里面，找最多出现k种字母的子串，满足条件的最长子串有多长
public static int longestSubstring (String s, int k) {
//贪心算法，随时记录start和end，用哈希表存每个字母上次出现的位置
if(k==0)
return 0;
Map<Character,Integer> map=new HashMap();
int ans=0;
int len=s.length();
int start=0,count=0;
int i=0;
while(i<len){
char c=s.charAt(i);
if(map.getOrDefault(c,-1)<start){
//说明前面没出现过
count++;
if(count>k){
//说明这个地方不能留
ans=Math.max(ans,i-start);
char first=s.charAt(start);
start=map.get(first)+1;//找到这个字母最后出现的位置
if(start==len)break;
count=1;i=start;c=s.charAt(i);map.clear();
}
}
map.put(c,i);
i++;
}
//最后再判断一遍
if(count<=k&&count>0)
ans=Math.max(ans,len-start);
return ans;
}
上述代码存在的问题：窗口每次收缩太多了
GPT提供的答案：
public static int longestSubstring2(String s, int k) {
if (k == 0) return 0;
Map<Character, Integer> map = new HashMap<>();
int ans = 0;
int start = 0;
for (int end = 0; end < s.length(); end++) {
char endChar = s.charAt(end);
map.put(endChar, map.getOrDefault(endChar, 0) + 1);//用map来计数
// 当窗口中的不同字符超过k时，通过while循环收缩窗口，步长为1 确保不会把start移到太后面
while (map.size() > k) {
char startChar = s.charAt(start);
map.put(startChar, map.get(startChar) - 1);
if (map.get(startChar) == 0) {
map.remove(startChar);
}
start++;
}
// 更新最大长度
ans = Math.max(ans, end - start + 1);
}
return ans;
}
第二题AC 是找数组中单个出现的元素
public static int singleElement (ArrayList<Integer> v) {
// write code here
int ans=0;
for(int i:v)
ans=ans^i;
return ans;
}
如果用二分查找：
public static int findSingleNumber(int[] nums) {
// 首先，确保数组是有序的。如果输入数组已经有序，则这步可以忽略
// Arrays.sort(nums); // 如果数组不保证有序，则需要先排序
int left = 0;
int right = nums.length - 1;
while (left < right) {
// 找到中间位置
int mid = left + (right - left) / 2;
// 确保 mid 是偶数，方便判断成对的数字
if (mid % 2 == 1) {
mid--; // 如果 mid 是奇数，则向下调整到前一个
}
// 判断 mid 和 mid + 1 的值是否相同
if (nums[mid] == nums[mid + 1]) {
// 如果相同，说明只出现一次的数字在右侧
left = mid + 2;
} else {
// 如果不同，说明只出现一次的数字在左侧（可能是 mid，或者在 mid 之前）
right = mid;
}
}
// left 应该是只出现一次的数字的位置
return nums[left];
}
进一步地，如果有两个数字只出现一次：
- 通过异或所有数字，得到这两个只出现一次的数字的异或结果。
- 找到这个结果的某一位为 1 的位（即这两个数字的某些位不同），利用这个位将数组分为两部分，以此可以分开这两个只出现一次的数字。
- 分别对这两部分进行异或运算，最终得到这两个数字。
public static int[] findSingleNumbers(int[] nums) {
int xor = 0;
// 首先，对所有数字进行异或，得到两个只出现一次的数字的异或值
for (int num : nums) {
xor ^= num;
}
// 找到异或结果中一个为 1 的位
int diffBit = xor & (-xor); // 取得最低位的 1
int[] result = new int[2];
// 根据 diffBit 将数字分成两个组
for (int num : nums) {
// 根据 diffBit 进行分组
if ((num & diffBit) == 0) {
result[0] ^= num; // 第一个组
} else {
result[1] ^= num; // 第二个组
}
}
return result;
}
查看22道真题和解析