2025年計算機專業(yè)面試預測題一、編程實現(xiàn)題（3題，每題20分）題目1：實現(xiàn)LRU緩存機制問題描述：設(shè)計一個LRU（最近最少使用）緩存機制。它應(yīng)該支持以下操作：-`LRUCache(intcapacity)`，用容量`capacity`初始化緩存-`get(intkey)`-如果鍵存在，返回鍵的值，否則返回-1-`put(intkey,intvalue)`-如果鍵已經(jīng)存在，則更新其值并移動到緩存的前端；如果鍵不存在，則添加鍵值對到緩存的前端。如果緩存已滿，則刪除最久未使用（LRU）的緩存項。示例：plaintextLRUCachelru=newLRUCache(2);lru.put(1,1);//緩存是{1=1}lru.put(2,2);//緩存是{1=1,2=2}lru.get(1);//返回1lru.put(3,3);//去除鍵2，緩存是{1=1,3=3}lru.get(2);//返回-1(未找到)lru.put(4,4);//去除鍵1，緩存是{4=4,3=3}lru.get(1);//返回-1(未找到)lru.get(3);//返回3lru.get(4);//返回4要求：-使用雙向鏈表和哈希表實現(xiàn)。-`get`和`put`操作的時間復雜度為O(1)。題目2：合并K個排序鏈表問題描述：合并k個排序鏈表，返回合并后的排序鏈表。你需要設(shè)計一個合并函數(shù)，該函數(shù)可以合并兩個排序鏈表，然后使用遞歸或迭代的方式合并所有鏈表。示例：plaintext輸入:[1->4->5,1->3->4,2->6]輸出:1->1->2->3->4->4->5->6要求：-鏈表節(jié)點定義如下：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next題目3：實現(xiàn)二叉樹的深度優(yōu)先遍歷問題描述：實現(xiàn)二叉樹的深度優(yōu)先遍歷（前序、中序、后序），使用遞歸或迭代的方式。示例：給定二叉樹：1/\23/\45-前序遍歷:`[1,2,4,5,3]`-中序遍歷:`[4,2,5,1,3]`-后序遍歷:`[4,5,2,3,1]`要求：-可以選擇其中一種或全部實現(xiàn)。-迭代方式需要使用棧。二、算法設(shè)計題（4題，每題15分）題目4：最長上升子序列問題描述：給定一個無序的整數(shù)數(shù)組，找到其中最長的上升子序列的長度。子序列是指數(shù)組中元素保持原始順序，但不需要連續(xù)。示例：plaintext輸入:[10,9,2,5,3,7,101,18]輸出:4解釋:最長的上升子序列是[2,3,7,101]，長度為4。要求：-時間復雜度O(nlogn)。題目5：N皇后問題問題描述：給定一個整數(shù)`n`，返回所有不同的`n`皇后問題的解決方案。每個解決方案包含一個明確的`n`皇后放置方式，其中`'Q'`和`'.'`分別代表一個皇后和一個空位。示例：plaintext輸入:4輸出:[[".Q..",//解法1"...Q","Q...","..Q."],["..Q.",//解法2"Q...","...Q",".Q.."]]解釋:如上圖所示，兩種不同的解決方案。要求：-只需要返回解的數(shù)量和一種解即可。題目6：背包問題問題描述：給定一個非空的整數(shù)數(shù)組，表示不同面額的硬幣，以及一個總金額`amount`，計算可以組成總金額的硬幣組合數(shù)。假設(shè)每一種面額的硬幣數(shù)量是無限的。示例：plaintext輸入:coins=[1,2,5],amount=5輸出:4解釋:有四種方式：52+2+12+1+21+2+21+1+1+2要求：-動態(tài)規(guī)劃解決。題目7：滑動窗口最大值問題描述：給定一個整數(shù)數(shù)組和一個整數(shù)`k`，找到滑動窗口的最大值?；瑒哟翱跁跀?shù)組中不斷向右滑動。示例：plaintext輸入:nums=[1,3,-1,-3,5,3,6,7],k=3輸出:[3,3,5,5,6,7]解釋:窗口位置最大值--[13-1]3[3-1-3]3[-1-35]5[-353]5[536]6[367]7要求：-使用單調(diào)隊列實現(xiàn)，時間復雜度O(n)。三、系統(tǒng)設(shè)計題（2題，每題25分）題目8：設(shè)計一個簡單的URL短鏈接系統(tǒng)問題描述：設(shè)計一個URL短鏈接系統(tǒng)。用戶可以輸入一個長URL，系統(tǒng)返回一個短URL；通過短URL可以跳轉(zhuǎn)到對應(yīng)的長URL。系統(tǒng)需要支持高并發(fā)訪問，并保證短URL的唯一性和可訪問性。要求：-系統(tǒng)需要支持：-生成短URL-跳轉(zhuǎn)到長URL-高并發(fā)處理-簡要說明系統(tǒng)架構(gòu)和關(guān)鍵技術(shù)選型。題目9：設(shè)計一個簡單的消息隊列系統(tǒng)問題描述：設(shè)計一個簡單的消息隊列系統(tǒng)（如Kafka或RabbitMQ的簡化版）。系統(tǒng)需要支持：-生產(chǎn)者（Producer）發(fā)送消息-消費者（Consumer）接收消息-消息的持久化（防止數(shù)據(jù)丟失）-消息的確認機制（確保消息被正確處理）要求：-系統(tǒng)需要支持至少一個生產(chǎn)者和多個消費者。-簡要說明系統(tǒng)架構(gòu)、關(guān)鍵技術(shù)選型以及消息的可靠性保證機制。四、數(shù)據(jù)庫設(shè)計題（1題，20分）題目10：設(shè)計一個簡單的社交系統(tǒng)數(shù)據(jù)庫問題描述：設(shè)計一個簡單的社交系統(tǒng)數(shù)據(jù)庫，支持以下功能：-用戶注冊和登錄-用戶發(fā)布動態(tài)（文本、圖片、視頻）-用戶關(guān)注其他用戶-用戶點贊動態(tài)要求：-設(shè)計主要的數(shù)據(jù)庫表及其字段。-說明表之間的關(guān)系（主外鍵等）。-簡要說明如何支持用戶點贊功能。答案答案1：實現(xiàn)LRU緩存機制實現(xiàn)思路：使用雙向鏈表和哈希表實現(xiàn)。哈希表存儲鍵和鏈表節(jié)點的映射，鏈表維護最近使用的順序。代碼示例（Python）：pythonclassListNode:def__init__(self,key=None,value=None):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=ListNode()self.tail=ListNode()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node:ListNode):#Alwaysaddthenewnoderightafterhead.node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node:ListNode):#Removeanexistingnodefromthelinkedlist.prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node:ListNode):#Movecertainnodeinbetweentothehead.self._remove_node(node)self._add_node(node)def_pop_tail(self)->ListNode:#Popthecurrenttail.res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1#Movetheaccessednodetothehead;self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=ListNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:#Popthetailtail=self._pop_tail()delself.cache[tail.key]else:#Updatethevalue.node.value=valueself._move_to_head(node)答案2：合并K個排序鏈表實現(xiàn)思路：使用最小堆（優(yōu)先隊列）維護當前最小的節(jié)點，每次彈出最小節(jié)點并添加其下一個節(jié)點。代碼示例（Python）：pythonimportheapqclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextclassSolution:defmergeKLists(self,lists:List[ListNode])->ListNode:heap=[]foridx,nodeinenumerate(lists):ifnode:heapq.heappush(heap,(node.val,idx,node))dummy=ListNode()current=dummywhileheap:val,idx,node=heapq.heappop(heap)current.next=nodecurrent=current.nextifnode.next:heapq.heappush(heap,(node.next.val,idx,node.next))returndummy.next答案3：實現(xiàn)二叉樹的深度優(yōu)先遍歷前序遍歷（遞歸）：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpreorderTraversal(root:TreeNode)->List[int]:res=[]defdfs(node):ifnotnode:returnres.append(node.val)dfs(node.left)dfs(node.right)dfs(root)returnres中序遍歷（迭代）：pythondefinorderTraversal(root:TreeNode)->List[int]:res=[]stack=[]cur=rootwhilestackorcur:whilecur:stack.append(cur)cur=cur.leftcur=stack.pop()res.append(cur.val)cur=cur.rightreturnres后序遍歷（迭代）：pythondefpostorderTraversal(root:TreeNode)->List[int]:res=[]stack=[root]whilestack:node=stack.pop()res.append(node.val)ifnode.left:stack.append(node.left)ifnode.right:stack.append(node.right)returnres[::-1]答案4：最長上升子序列實現(xiàn)思路：使用動態(tài)規(guī)劃和二分查找優(yōu)化，時間復雜度O(nlogn)。代碼示例（Python）：pythondeflengthOfLIS(nums:List[int])->int:frombisectimportbisect_leftifnotnums:return0tails=[]fornuminnums:idx=bisect_left(tails,num)ifidx==len(tails):tails.append(num)else:tails[idx]=numreturnlen(tails)答案5：N皇后問題實現(xiàn)思路：使用回溯法，記錄每一行的皇后位置以及列和對角線的占用情況。代碼示例（Python）：pythondefsolveNQueens(n:int)->List[List[str]]:defdfs(row,diagonals,anti_diagonals,cols,state):ifrow==n:board=[]fornuminstate:board.append(''.join(['Q'ifc==numelse'.'forcinrange(n)]))res.append(board)returnforcolinrange(n):diag=row-colanti_diag=row+colifcolincolsordiagindiagonalsoranti_diaginanti_diagonals:continuecols.add(col)diagonals.add(diag)anti_diagonals.add(anti_diag)state.append(col)dfs(row+1,diagonals,anti_diagonals,cols,state)state.pop()cols.remove(col)diagonals.remove(diag)anti_diagonals.remove(anti_diag)res=[]dfs(0,set(),set(),set(),[])returnres答案6：背包問題實現(xiàn)思路：使用動態(tài)規(guī)劃，dp[i][j]表示前i個硬幣組成金額j的組合數(shù)。代碼示例（Python）：pythondefcoinChange(coins:List[int],amount:int)->int:dp=[amount+1]*(amount+1)dp[0]=0forcoinincoins:forxinrange(coin,amount+1):dp[x]=min(dp[x],dp[x-coin]+1)returndp[amount]ifdp[amount]!=amount+1else-1答案7：滑動窗口最大值實現(xiàn)思路：使用單調(diào)遞減隊列，每次滑動時維護隊列頭部為最大值。代碼示例（Python）：pythonfromcollectionsimportdequedefmaxSlidingWindow(nums:List[int],k:int)->List[int]:ifnotnums:return[]q=deque()res=[]foriinrange(len(nums)):whileqandnums[i]>=nums[q[-1]]:q.pop()q.append(i)ifq[0]<=i-k:q.popleft()ifi>=k-1:res.append(nums[q[0]])returnres答案8：設(shè)計一個簡單的URL短鏈接系統(tǒng)系統(tǒng)架構(gòu)：1.前端服務(wù)：接收用戶請求，返回短URL或跳轉(zhuǎn)到長URL。2.后端服務(wù)：生成短URL，存儲長URL和短URL映射關(guān)系。3.數(shù)據(jù)庫：存儲URL映射關(guān)系，支持高并發(fā)讀寫。4.分布式緩存：緩存熱點短URL，提高訪問速度。關(guān)鍵技術(shù)選型：-前端服務(wù)：Nginx或HAProxy-后端服務(wù)：使用Go或Python實現(xiàn)，采用異步處理-數(shù)據(jù)庫：Redis（緩存）+PostgreSQL（持久化）-短URL生成：使用Base62編碼（a-z,A-Z,0-9）實現(xiàn)細節(jié)：-生成短URL：使用隨機數(shù)或hash算法生成唯一標識，然后進行Base62編碼。-存儲映射關(guān)系：將短URL和長URL的映射關(guān)系存儲在Redis和PostgreSQL中。-高并發(fā)處理：使用異步IO和分布式架構(gòu)，數(shù)據(jù)庫讀寫分離。答案9：設(shè)計一個簡單的消息隊列系統(tǒng)系統(tǒng)架構(gòu)：1.生產(chǎn)者（Producer）：發(fā)送消息到消息隊列。2.