2026年软件工程师技术面试题集及答案解析

2026年软件工程师技术面试题集及答案解析一、编程语言基础（5题，每题10分，共50分）题目1（10分）请用Java实现一个方法，判断一个字符串是否为有效的括号组合，例如"()[]{}"是有效的，而"(]"无效。要求时间复杂度为O(n)。javapublicbooleanisValid(Strings){if(s==null||s.length()%2!=0)returnfalse;Map<Character,Character>map=newHashMap<>();map.put(')','(');map.put('}','{');map.put(']','[');Stack<Character>stack=newStack<>();for(charc:s.toCharArray()){if(map.containsKey(c)){if(stack.isEmpty()||stack.pop()!=map.get(c))returnfalse;}else{stack.push(c);}}returnstack.isEmpty();}题目2（10分）用Python实现快速排序算法，并分析其时间复杂度。pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)时间复杂度：平均O(nlogn)，最坏O(n^2)，空间复杂度O(logn)。题目3（10分）用C++实现一个单链表节点结构，并实现反转该链表的功能。cppstructListNode{intval;ListNodenext;ListNode(intx):val(x),next(nullptr){}};ListNodereverseList(ListNodehead){ListNodeprev=nullptr;ListNodecurr=head;while(curr){ListNodenext=curr->next;curr->next=prev;prev=curr;curr=next;}returnprev;}题目4（10分）请解释Java中的垃圾回收机制，并说明常见的垃圾回收算法。Java使用标记-清除、复制、标记-整理等算法。标记-清除：标记所有可达对象，然后回收不可达对象。复制：将内存分为两半，每次只使用一半，用完就回收另一半。标记-整理：先标记，然后整理所有存活对象到内存的一端，回收边界之外的内存。题目5（10分）用JavaScript实现一个函数，找出数组中所有唯一的数字，要求时间复杂度为O(n)。javascriptfunctionfindUniques(arr){constcount={};for(constnumofarr){count[num]=(count[num]||0)+1;}returnObject.keys(count).filter(key=>count[key]===1).map(Number);}二、数据结构与算法（8题，每题12分，共96分）题目6（12分）设计一个LRU（最近最少使用）缓存系统，使用双向链表和哈希表实现，要求实现get和put操作。javaclassLRUCache{staticclassNode{intkey;intvalue;Nodeprev;Nodenext;Node(intkey,intvalue){this.key=key;this.value=value;}}Map<Integer,Node>cache=newHashMap<>();Nodehead=newNode(0,0),tail=newNode(0,0);intcapacity;publicLRUCache(intcapacity){this.capacity=capacity;head.next=tail;tail.prev=head;}publicintget(intkey){Nodenode=cache.get(key);if(node==null)return-1;moveToHead(node);returnnode.value;}publicvoidput(intkey,intvalue){Nodenode=cache.get(key);if(node!=null){node.value=value;moveToHead(node);}else{NodenewNode=newNode(key,value);cache.put(key,newNode);addToHead(newNode);if(cache.size()>capacity){NodetoDel=tail.prev;removeNode(toDel);cache.remove(toDel.key);}}}privatevoidmoveToHead(Nodenode){removeNode(node);addToHead(node);}privatevoidaddToHead(Nodenode){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}privatevoidremoveNode(Nodenode){node.prev.next=node.next;node.next.prev=node.prev;}}题目7（12分）给定一个包含n个整数的数组，找到其中三个数，使得它们的乘积最大。假设数组长度至少为3。pythondefmaximumProduct(nums):nums.sort()n=len(nums)returnmax(nums[0]nums[1]nums[-1],nums[-1]nums[-2]nums[-3])题目8（12分）实现一个函数，检查一个二叉树是否是平衡的（左右子树高度差不超过1）。javaclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}publicclassSolution{publicbooleanisBalanced(TreeNoderoot){returnheight(root)!=-1;}privateintheight(TreeNodenode){if(node==null)return0;intleft=height(node.left);if(left==-1)return-1;intright=height(node.right);if(right==-1||Math.abs(left-right)>1)return-1;returnMath.max(left,right)+1;}}题目9（12分）用动态规划解决背包问题：给定一个容量为W的背包和n个物品，每个物品有重量和价值，求背包能装入的最大价值。pythondefknapsack(weights,values,W):n=len(weights)dp=[[0](W+1)for_inrange(n+1)]foriinrange(1,n+1):forwinrange(1,W+1):ifweights[i-1]<=w:dp[i][w]=max(dp[i-1][w],dp[i-1][w-weights[i-1]]+values[i-1])else:dp[i][w]=dp[i-1][w]returndp[n][W]题目10（12分）实现二分查找算法，并处理数组中存在多个重复元素的情况。pythondefbinary_search(arr,target):left,right=0,len(arr)-1whileleft<=right:mid=left+(right-left)//2ifarr[mid]==target:找到第一个等于target的元素whilemid>0andarr[mid-1]==target:mid-=1returnmidelifarr[mid]<target:left=mid+1else:right=mid-1return-1题目11（12分）设计一个算法，找出二叉搜索树中的第k小元素。javaclassSolution{intcount=0;intresult=0;publicintkthSmallest(TreeNoderoot,intk){inorder(root,k);returnresult;}privatevoidinorder(TreeNodenode,intk){if(node==null||count>=k)return;inorder(node.left,k);count++;if(count==k){result=node.val;return;}inorder(node.right,k);}}题目12（12分）实现一个函数，判断一个字符串是否是有效的罗马数字。pythondefromanToInt(s):roman={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}total=0prev=0forcharins[::-1]:value=roman[char]ifvalue<prev:total-=valueelse:total+=valueprev=valuereturntotal三、系统设计（3题，每题20分，共60分）题目13（20分）设计一个简单的消息队列系统，包括生产者和消费者模型，需要考虑如何保证消息的可靠传递。核心组件：1.消息存储：使用持久化队列（如RabbitMQ或Kafka）2.消息确认：消费者确认机制3.重试机制：失败消息重新入队4.死信队列：无法处理的消息进入死信队列5.负载均衡：多消费者共享任务伪代码：javapublicclassMessageQueue{privateQueue<String>queue=newLinkedList<>();privateSet<String>processing=newHashSet<>();publicsynchronizedvoidproduce(Stringmessage){queue.offer(message);notifyAll();}publicsynchronizedStringconsume()throwsInterruptedException{while(queue.isEmpty()){wait();}Stringmessage=queue.poll();processing.add(message);returnmessage;}publicsynchronizedvoidacknowledge(Stringmessage){processing.remove(message);}}题目14（20分）设计一个短URL生成系统，要求每个URL都是唯一的，且尽可能短。方案：1.使用哈希算法（如SHA-256）将原始URL转换为固定长度的哈希值2.使用Base62编码（A-Z,a-z,0-9）将哈希值转换为短链接3.数据库存储映射关系，防止冲突pythonimporthashlibimportbase64defencode_url(url):hash_object=hashlib.sha256(url.encode())hash_digest=hash_object.digest()取前6个字节short_code=base64.urlsafe_b64encode(hash_digest[:6