国内编程面试题库及答案

国内编程面试题库及答案一、算法与数据结构类1.快速排序实现问题：实现快速排序算法，要求时间复杂度为O(nlogn)（平均情况），并说明其空间复杂度。解答：快速排序采用分治思想，核心是选择基准值（pivot），将数组分为小于基准和大于基准的两部分，递归处理子数组。步骤：选择基准（通常选首元素、尾元素或随机元素）。分区（partition）：将小于基准的元素移到左边，大于的移到右边，返回基准最终位置。递归对左右子数组排序。示例代码（Java）：```javapublicstaticvoidquickSort(int[]arr,intleft,intright){if(left<right){intpivotIndex=partition(arr,left,right);quickSort(arr,left,pivotIndex1);quickSort(arr,pivotIndex+1,right);}}privatestaticintpartition(int[]arr,intleft,intright){intpivot=arr[right];//选末尾为基准inti=left1;//小于基准的右边界for(intj=left;j<right;j++){if(arr[j]<=pivot){i++;swap(arr,i,j);}}swap(arr,i+1,right);//将基准放到正确位置returni+1;}privatestaticvoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}```时间复杂度：平均O(nlogn)，最坏（已排序数组且选固定基准）O(n²)；空间复杂度：递归栈深度，平均O(logn)，最坏O(n)。2.最长递增子序列（LIS）问题：给定整数数组nums，求最长递增子序列（子序列元素顺序不变且严格递增）的长度。解答：动态规划法（O(n²)）：定义dp[i]为以nums[i]结尾的LIS长度。初始dp[i]=1（每个元素自身为长度1的序列）。对每个i，遍历j=0到i-1，若nums[j]<nums[i]，则dp[i]=max(dp[i],dp[j]+1)。最终结果为dp数组最大值。贪心+二分法（O(nlogn)）：维护数组tail，其中tail[k]表示长度为k+1的递增子序列的最小末尾元素。遍历nums，对每个元素x，用二分查找找到tail中第一个≥x的位置，替换为x；若x大于所有元素，则添加到tail末尾。最终tail长度即为LIS长度。示例（贪心+二分）：输入nums=[10,9,2,5,3,7,101,18]，tail变化：10→[10]9→[9]（替换10）2→[2]（替换9）5→[2,5]（添加）3→[2,3]（替换5）7→[2,3,7]（添加）101→[2,3,7,101]（添加）18→[2,3,7,18]（替换101）最终长度4。3.反转单链表问题：反转一个单链表（如1→2→3→4→5反转为5→4→3→2→1）。解答：迭代法：用三个指针prev（前一个节点）、curr（当前节点）、next（下一个节点）。遍历链表，每次将curr.next指向prev，然后prev、curr后移。递归法：递归反转curr.next，然后调整curr.next.next=curr，curr.next=null。迭代法代码（Java）：```javapublicListNodereverseList(ListNodehead){ListNodeprev=null;ListNodecurr=head;while(curr!=null){ListNodenext=curr.next;curr.next=prev;prev=curr;curr=next;}returnprev;}```二、操作系统类1.进程与线程的区别解答：资源分配：进程是资源分配的基本单位（内存、文件句柄等），线程是CPU调度的基本单位，共享进程资源（如堆、方法区），但有独立的栈和程序计数器。并发性：进程间并发需切换上下文（消耗大），同一进程的线程间并发切换仅需切换线程上下文（消耗小）。通信方式：进程间通信（IPC）需通过管道、消息队列、共享内存等；线程间通信可直接访问共享变量（需注意线程安全）。健壮性：一个进程崩溃不影响其他进程；一个线程崩溃可能导致整个进程崩溃。2.死锁的条件与解决方法解答：死锁的四个必要条件：互斥：资源同一时间只能被一个进程占用。占有并等待：进程已占有至少一个资源，又请求其他被占用的资源，且不释放已占资源。不可抢占：资源只能被进程主动释放，不能被强制抢占。循环等待：多个进程形成环形等待链，每个进程等待下一个进程占有的资源。解决方法：预防死锁：打破任一必要条件（如资源一次性分配打破“占有并等待”；资源有序分配打破“循环等待”）。避免死锁：银行家算法（检查资源请求是否会导致系统进入不安全状态）。检测与解除：通过资源分配图检测死锁，终止部分进程或抢占资源。三、计算机网络类1.TCP三次握手与四次挥手解答：三次握手（建立连接）：客户端发送SYN=1，seq=x（初始序号），进入SYN_SENT状态。服务器收到后发送SYN=1，ACK=1，ack=x+1，seq=y，进入SYN_RCVD状态。客户端发送ACK=1，ack=y+1，seq=x+1，进入ESTABLISHED；服务器收到后也进入ESTABLISHED。目的：同步双方初始序号，防止旧连接的重复请求被接收。四次挥手（关闭连接）：客户端发送FIN=1，seq=u，进入FIN_WAIT_1状态。服务器收到后发送ACK=1，ack=u+1，seq=v，进入CLOSE_WAIT状态；客户端收到后进入FIN_WAIT_2。服务器处理完数据后发送FIN=1，ACK=1，ack=u+1，seq=w，进入LAST_ACK状态。客户端发送ACK=1，ack=w+1，seq=u+1，进入TIME_WAIT（等待2MSL后关闭）；服务器收到后关闭。TIME_WAIT的作用：确保最后一个ACK到达服务器，避免旧连接的报文影响新连接。2.HTTP状态码分类解答：1xx（信息性状态码）：请求已接收，继续处理（如100Continue）。2xx（成功）：请求成功（200OK、201Created）。3xx（重定向）：需要进一步操作完成请求（301永久重定向、302临时重定向、304未修改）。4xx（客户端错误）：请求包含错误（400BadRequest、404NotFound、403Forbidden）。5xx（服务器错误）：服务器处理请求失败（500InternalServerError、503ServiceUnavailable）。四、数据库类1.索引的类型与优化解答：索引类型：按数据结构：B+树索引（最常用，支持范围查询）、哈希索引（等值查询快，不支持范围）、全文索引（用于文本搜索）。按约束：主键索引（唯一且非空）、唯一索引（值唯一）、普通索引（无约束）。按存储方式：聚集索引（数据行按索引顺序存储，一个表只有一个，通常是主键）、非聚集索引（索引与数据分开存储，通过键值关联）。优化策略：选择高区分度的列（如用户ID）作为索引，避免对低区分度列（如性别）建索引。避免索引列使用函数（如WHEREYEAR(create_time)=2023会导致索引失效）。复合索引遵循“最左前缀法则”（如索引(a,b,c)支持a、a+b、a+b+c的查询）。定期重建或分析索引，避免碎片影响性能。2.事务的ACID特性解答：原子性（Atomicity）：事务中的操作要么全部完成，要么全部回滚，不可部分执行。一致性（Consistency）：事务执行前后数据库状态保持一致（如转账后双方余额总和不变）。隔离性（Isolation）：多个事务并发执行时，彼此互不干扰，避免脏读、不可重复读、幻读。持久性（Durability）：事务提交后，修改永久保存，即使系统崩溃也可通过日志恢复。隔离级别（从低到高）：读未提交（ReadUncommitted）：允许脏读（读取未提交的修改）。读已提交（ReadCommitted）：禁止脏读（默认级别，如MySQL的InnoDB）。可重复读（RepeatableRead）：禁止不可重复读（MySQL默认，通过MVCC实现）。串行化（Serializable）：最高隔离级别，事务串行执行，避免幻读。五、编程语言特性（Java）1.HashMap底层实现（JDK8）解答：JDK8中HashMap由“数组+链表+红黑树”组成：数组（哈希桶）：初始大小16，负载因子0.75（当元素数>容量×负载因子时扩容，容量翻倍）。链表：当哈希冲突时，冲突元素以链表形式挂在数组节点下（JDK7为头插法，JDK8为尾插法，避免扩容时死循环）。红黑树：当链表长度≥8且数组长度≥64时，链表转换为红黑树（查询时间从O(n)降至O(logn)）；当红黑树节点数≤6时，退化为链表。关键方法：put(Kkey,Vvalue)：计算key的hash值（(h=key.hashCode())^(h>>>16)），找到数组索引，若冲突则遍历链表/红黑树，存在则覆盖，否则添加。若链表过长则转红黑树。get(Objectkey)：计算hash值找到数组索引，遍历链表/红黑树查找对应节点。线程不安全场景：多线程put时可能导致数据覆盖（JDK7扩容时还可能导致链表成环，JDK8修复但仍不安全），需用ConcurrentHashMap或Hashtable（效率低）。2.线程池核心参数与工作流程解答：ThreadPoolExecutor构造参数：corePoolSize：核心线程数（即使空闲也保留）。maximumPoolSize：最大线程数（核心+非核心）。keepAliveTime：非核心线程空闲超时时间（超时则销毁）。unit：时间单位。workQueue：任务队列（如ArrayBlockingQueue、LinkedBlockingQueue）。threadFactory：线程工厂（创建工作线程）。handler：拒绝策略（任务队列满且线程数达最大值时的处理方式）。工作流程：1.提交任务，若当前线程数<corePoolSize，创建新线程执行任务。2.若线程数≥corePoolSi