2026年軟件工程師技術(shù)面試題集及答案解析一、編程語言基礎(chǔ)（5題，每題10分，共50分）題目1（10分）請用Java實現(xiàn)一個方法，判斷一個字符串是否為有效的括號組合，例如"()[]{}"是有效的，而"(]"無效。要求時間復(fù)雜度為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實現(xiàn)快速排序算法，并分析其時間復(fù)雜度。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)時間復(fù)雜度：平均O(nlogn)，最壞O(n^2)，空間復(fù)雜度O(logn)。題目3（10分）用C++實現(xiàn)一個單鏈表節(jié)點結(jié)構(gòu)，并實現(xiàn)反轉(zhuǎn)該鏈表的功能。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中的垃圾回收機(jī)制，并說明常見的垃圾回收算法。Java使用標(biāo)記-清除、復(fù)制、標(biāo)記-整理等算法。標(biāo)記-清除：標(biāo)記所有可達(dá)對象，然后回收不可達(dá)對象。復(fù)制：將內(nèi)存分為兩半，每次只使用一半，用完就回收另一半。標(biāo)記-整理：先標(biāo)記，然后整理所有存活對象到內(nèi)存的一端，回收邊界之外的內(nèi)存。題目5（10分）用JavaScript實現(xiàn)一個函數(shù)，找出數(shù)組中所有唯一的數(shù)字，要求時間復(fù)雜度為O(n)。javascriptfunctionfindUniques(arr){constcount={};for(constnumofarr){count[num]=(count[num]||0)+1;}returnObject.keys(count).filter(key=>count[key]===1).map(Number);}二、數(shù)據(jù)結(jié)構(gòu)與算法（8題，每題12分，共96分）題目6（12分）設(shè)計一個LRU（最近最少使用）緩存系統(tǒng)，使用雙向鏈表和哈希表實現(xiàn)，要求實現(xiàn)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個整數(shù)的數(shù)組，找到其中三個數(shù)，使得它們的乘積最大。假設(shè)數(shù)組長度至少為3。pythondefmaximumProduct(nums):nums.sort()n=len(nums)returnmax(nums[0]nums[1]nums[-1],nums[-1]nums[-2]nums[-3])題目8（12分）實現(xiàn)一個函數(shù)，檢查一個二叉樹是否是平衡的（左右子樹高度差不超過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分）用動態(tài)規(guī)劃解決背包問題：給定一個容量為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分）實現(xiàn)二分查找算法，并處理數(shù)組中存在多個重復(fù)元素的情況。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分）設(shè)計一個算法，找出二叉搜索樹中的第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分）實現(xiàn)一個函數(shù)，判斷一個字符串是否是有效的羅馬數(shù)字。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三、系統(tǒng)設(shè)計（3題，每題20分，共60分）題目13（20分）設(shè)計一個簡單的消息隊列系統(tǒng)，包括生產(chǎn)者和消費者模型，需要考慮如何保證消息的可靠傳遞。核心組件：1.消息存儲：使用持久化隊列（如RabbitMQ或Kafka）2.消息確認(rèn)：消費者確認(rèn)機(jī)制3.重試機(jī)制：失敗消息重新入隊4.死信隊列：無法處理的消息進(jìn)入死信隊列5.負(fù)載均衡：多消費者共享任務(wù)偽代碼：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分）設(shè)計一個短URL生成系統(tǒng)，要求每個URL都是唯一的，且盡可能短。方案：1.使用哈希算法（如SHA-256）將原始URL轉(zhuǎn)換為固定長度的哈希值2.使用Base62編碼（A-Z,a-z,0-9）將哈希值轉(zhuǎn)換為短鏈接3.數(shù)據(jù)庫存儲映射關(guān)系，防止沖突pythonimporthashlibimportbase64defencode_url(url):hash_object=hashlib.sha256(url.encode())hash_digest=hash_object.digest()取前6個字節(jié)short_code=base64.urlsafe_b64encode(hash_digest[:6