程序员中级工程师面试问题集与解析

2026年程序员中级工程师面试问题集与解析一、编程语言基础（5题，每题10分，共50分）1.Java编程题目：请用Java编写一个方法，实现将一个字符串中的所有空格替换为"%20"。要求不使用Java内置的替换方法，并考虑时间复杂度和空间复杂度。答案：javapublicstaticStringreplaceSpaces(Strings){if(s==null)returnnull;intspaceCount=0;for(charc:s.toCharArray()){if(c=='')spaceCount++;}char[]result=newchar[s.length()+spaceCount2];intj=0;for(charc:s.toCharArray()){if(c==''){result[j++]='%';result[j++]='2';result[j++]='0';}else{result[j++]=c;}}returnnewString(result,0,j);}解析：-时间复杂度：O(n)，遍历字符串一次计算空格数量，再遍历一次生成结果。-空间复杂度：O(n)，额外创建长度为`n+2m`的字符数组（n为原字符串长度，m为空格数量）。-优化：可使用StringBuilder减少数组创建开销，但题目要求明确不使用内置方法，故采用手动计算。2.Python编程题目：请用Python实现一个函数，检查一个列表是否为回文（即正序和倒序相同）。例如，`[1,2,3,2,1]`是回文，`[1,2,3]`不是。答案：pythondefis_palindrome(lst):returnlst==lst[::-1]解析：-时间复杂度：O(n)，切片操作需要遍历列表一次。-空间复杂度：O(n)，切片会复制原列表。-优化：可使用双指针从两端向中间遍历，减少空间复杂度至O(1)。3.C++编程题目：请用C++实现一个函数，找出数组中第三大的数。假设数组中没有重复元素。答案：cppintthirdMax(vector<int>&nums){longfirst=LONG_MIN,second=LONG_MIN,third=LONG_MIN;for(intnum:nums){if(num>first){third=second;second=first;first=num;}elseif(num>second&&num<first){third=second;second=num;}elseif(num>third&&num<second){third=num;}}returnthird==LONG_MIN?first:third;}解析：-时间复杂度：O(n)，遍历数组一次。-空间复杂度：O(1)，只使用三个变量记录最大值。-注意：使用`long`避免INT_MAX时的溢出问题。4.JavaScript编程题目：请用JavaScript实现一个函数，将一个数组中的所有元素平方后返回新数组，不改变原数组。答案：javascriptfunctionsquareArray(arr){returnarr.map(x=>xx);}解析：-时间复杂度：O(n)，map方法遍历数组一次。-空间复杂度：O(n)，返回新数组。-其他方法：可使用`for...of`结合`const`声明实现原地修改，但题目要求不改变原数组。5.Go编程题目：请用Go实现一个函数，统计一个字符串中每个字符的出现次数，并返回一个map。答案：gofunccountChars(sstring)map[rune]int{count:=make(map[rune]int)for_,char:=ranges{count[char]++}returncount}解析：-时间复杂度：O(n)，遍历字符串一次。-空间复杂度：O(m)，m为不同字符的数量。-注意：Go的`rune`类型表示Unicode字符，确保统计所有字符。二、数据结构与算法（6题，每题10分，共60分）1.链表题目：请用Java实现一个单链表，并实现删除链表的倒数第n个节点。答案：javaclassListNode{intval;ListNodenext;ListNode(intx){val=x;}}publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodedummy=newListNode(0);dummy.next=head;ListNodefast=dummy,slow=dummy;for(inti=0;i<n;i++)fast=fast.next;while(fast!=null){fast=fast.next;slow=slow.next;}slow.next=slow.next.next;returndummy.next;}解析：-双指针法：快指针先走n步，慢指针从dummy开始，快慢指针同步移动，最后慢指针的next即为待删除节点。-时间复杂度：O(n)，遍历链表两次。-空间复杂度：O(1)，仅使用几个指针。2.树题目：请用Python实现一个二叉树的中序遍历，并返回结果列表。答案：pythondefinorderTraversal(root):result=[]defdfs(node):ifnode:dfs(node.left)result.append(node.val)dfs(node.right)dfs(root)returnresult解析：-递归法：先左子树，再根节点，最后右子树。-时间复杂度：O(n)，遍历所有节点。-空间复杂度：O(h)，h为树的高度（递归栈深度）。3.动态规划题目：请用C++实现一个函数，计算斐波那契数列的第n项（n≥0）。答案：cppintfib(intn){if(n<=1)returnn;inta=0,b=1,c;for(inti=2;i<=n;i++){c=a+b;a=b;b=c;}returnc;}解析：-动态规划：使用两个变量记录前两项，避免重复计算。-时间复杂度：O(n)，遍历n次。-空间复杂度：O(1)，仅使用常数个变量。4.贪心算法题目：请用JavaScript实现一个函数，给定一个非负整数数组，返回一个排列，使正数和负数间隔排列（正数在前）。答案：javascriptfunctionrearrangeArray(nums){letpositive=nums.filter(x=>x>0);letnegative=nums.filter(x=>x<0);letresult=[];for(leti=0;i<positive.length;i++){result.push(positive[i],negative[i]);}returnresult;}解析：-贪心策略：先收集所有正数和负数，再交替插入。-时间复杂度：O(n)，两次filter和一次遍历。-空间复杂度：O(n)，额外创建两个数组。5.哈希表题目：请用Java实现一个函数，检查一个字符串是否包含重复字符（区分大小写）。答案：javapublicbooleancontainsDuplicate(Strings){boolean[]charSet=newboolean[128];for(charc:s.toCharArray()){if(charSet[c])returntrue;charSet[c]=true;}returnfalse;}解析：-哈希表优化：使用固定大小的布尔数组代替HashMap，时间复杂度O(n)，空间复杂度O(1)。-注意：ASCII字符集大小为128，若支持Unicode需使用HashMap。6.排序算法题目：请用Go实现快速排序算法，并返回排序后的数组。答案：gofuncquickSort(arr[]int)[]int{iflen(arr)<2{returnarr;}pivot:=arr[0];left,right:=0,len(arr)-1;fori:=1;i<=right;{ifarr[i]<pivot{arr[i],arr[left]=arr[left],arr[i];left++;i++;}elseifarr[i]>pivot{arr[i],arr[right]=arr[right],arr[i];right--;}else{i++;}}returnappend(quickSort(arr[:left]),quickSort(arr[right+1:])...)}解析：-快速排序：分治法，选择pivot将数组分为小于和大于两部分。-时间复杂度：O(nlogn)，平均情况；O(n²)，最坏情况（已排序数组）。-空间复杂度：O(logn)，递归栈深度。三、系统设计（3题，每题20分，共60分）1.短链接系统题目：请设计一个短链接系统，要求支持以下功能：-输入长链接，返回短链接；-输入短链接，返回对应长链接；-高并发场景下性能良好。答案：-核心思想：使用62进制（a-z、A-Z、0-9）对长链接ID进行编码，结合分布式缓存和数据库。-步骤：1.生成唯一ID（如数据库自增或Snowflake算法）；2.将ID转为62进制字符串；3.缓存短链接与长链接的映射关系（Redis）；4.访问短链接时，解码字符串查询长链接，若缓存未命中则查数据库。-高并发优化：Redis集群+读写分离，数据库分表（按ID前缀）。解析：-编码方式：62进制可保证短链接长度适中（如6位）；-缓存策略：热点数据（如常见短链接）优先存入Redis；-分布式ID：避免ID冲突，如使用Twitter的Snowflake算法。2.消息队列选型题目：请比较RabbitMQ和Kafka，并说明在什么场景下选择哪个。答案：-RabbitMQ：-优点：事务消息、发布/订阅、延迟队列支持；-缺点：吞吐量不如Kafka（10k-100ktps）。-Kafka：-优点：高吞吐量（1M+tps）、持久化、多副本；-缺点：功能相对简单（无事务消息）。-选型场景：-RabbitMQ：电商订单处理、秒杀（需事务保证幂等）；-Kafka：日志收集、实时大数据（如Flink/Flink）。解析：-核心差异：Kafka更适合高吞吐、持久化场景；RabbitMQ更灵活（如协议支持）。-企业实践：阿里云推荐Kafka用于核心链路，RabbitMQ用于辅助场景。3.分布式锁实现题目：请设计一个分布式锁，要求：-避免死锁；-支持高可用；-使用Redis实现。答案：redisSETkeyvalueNXPX3000EX10-步骤：1.使用Redis的`SETkeyvalueNXPXmillisecondsEXseconds`命令；2.若设置成功，返回`OK`；否则重试；3.获取锁时记录过期时间，避免无限等待。-高可用：Redis集群+哨兵（或云服务自带的集群模式）。解析：-原理：`NX`保证原子性（不存在则设置），`PX`设置过期时间，防止死锁；-优化：可结合Redlock算法（分布式锁的黄金实现）。四、数据库与缓存（2题，每题15分，共30分）1.SQL优化题目：请优化以下SQL查询，并解释原因：sqlSELECTFROMordersWHEREuser_id=?ANDorder_dateBETWEEN'2023-01-01'AND'2023-12-31'ORDERBYorder_dateDESCLIMIT10;答案：-优化建议：sqlSELECTorder_id,user_id,order_dateFROMordersWHEREuser_id=?ANDorder_dateBETWEEN'2023-01-01'AND'2023-12-31'ORDERBYorder_dateDESCLIMIT10;-解释：1.减少`SELECT`：只返回需要的列，降低网络传输；2.索引：在`user_id`和`order_date`上创建复合索引（`user_id+order_date`）；3.避免全表扫描：索引覆盖（索引包含所有查询列）可减少排序开销。解析：-SQL调优原则：索引优先、少返回列、覆盖索引。-企业实践：可使用`EXPLAIN`分析执行计划，确认索引命中。2.缓存策略题目：请设计一个电商商品详情页的缓存策略，要求：-高并发场景下缓存命中率>90%；-支持缓存穿透、击穿、雪崩解决方案。答案：-策略：1.缓