10月8号虾皮、喜马拉雅秋招笔试记录

虾皮

有单选，多选，3道编程。只有最后一题编程偏难

喜马拉雅

有单选，多选，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;  
    }