2026年軟件工程師專業(yè)級面試問題及解答一、編程實(shí)現(xiàn)題（共3題，每題20分）1.（20分）設(shè)計(jì)一個(gè)高效的任務(wù)調(diào)度器題目描述：假設(shè)你需要設(shè)計(jì)一個(gè)任務(wù)調(diào)度器，支持動態(tài)添加任務(wù)、按優(yōu)先級執(zhí)行任務(wù)（優(yōu)先級由整數(shù)表示，數(shù)值越大優(yōu)先級越高），并確保高優(yōu)先級任務(wù)能夠及時(shí)搶占低優(yōu)先級任務(wù)的執(zhí)行。請用Python實(shí)現(xiàn)該調(diào)度器，支持以下功能：-`add_task(task_id,priority)`：添加任務(wù)，`task_id`為任務(wù)唯一標(biāo)識，`priority`為優(yōu)先級。-`execute()`：執(zhí)行當(dāng)前最高優(yōu)先級任務(wù)，并返回任務(wù)ID。如果多個(gè)任務(wù)具有相同最高優(yōu)先級，則按添加順序執(zhí)行。要求：-使用最小堆（優(yōu)先隊(duì)列）實(shí)現(xiàn)，確保`add_task`和`execute`的時(shí)間復(fù)雜度分別為O(logn)和O(1)。-提供測試代碼，驗(yàn)證功能正確性。答案與解析：pythonimportheapqclassTaskScheduler:def__init__(self):self.tasks=[]#存儲任務(wù)，格式為(-priority,task_id,index)defadd_task(self,task_id,priority):使用最小堆，優(yōu)先級高的任務(wù)存儲為較小的負(fù)數(shù)heapq.heappush(self.tasks,(-priority,task_id,len(self.tasks)))defexecute(self):ifnotself.tasks:returnNone_,task_id,_=heapq.heappop(self.tasks)returntask_id測試代碼scheduler=TaskScheduler()scheduler.add_task("task1",3)scheduler.add_task("task2",5)scheduler.add_task("task3",5)print(scheduler.execute())#輸出:task2print(scheduler.execute())#輸出:task3print(scheduler.execute())#輸出:task1解析：-使用Python的`heapq`模塊實(shí)現(xiàn)最小堆，將優(yōu)先級取負(fù)數(shù)以實(shí)現(xiàn)最大堆效果。任務(wù)存儲為三元組`(-priority,task_id,index)`，確保在優(yōu)先級相同的情況下按添加順序執(zhí)行。-`add_task`時(shí)間復(fù)雜度為O(logn)，`execute`時(shí)間復(fù)雜度為O(1)。2.（20分）實(shí)現(xiàn)LRU緩存題目描述：設(shè)計(jì)LRU（LeastRecentlyUsed）緩存，支持以下操作：-`get(key)`：返回緩存中鍵對應(yīng)的值，如果不存在返回-1。訪問鍵時(shí)將其標(biāo)記為最近使用。-`put(key,value)`：將鍵值對添加到緩存中，如果緩存已滿，則刪除最久未使用的鍵值對。緩存容量固定為`capacity`。要求：-使用哈希表+雙向鏈表實(shí)現(xiàn)，確保`get`和`put`的時(shí)間復(fù)雜度均為O(1)。-提供測試代碼。答案與解析：pythonclassDLinkedNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=DLinkedNode(),DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_pop_tail(self):res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=DLinkedNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]else:node.value=valueself._move_to_head(node)測試代碼cache=LRUCache(2)cache.put(1,1)cache.put(2,2)print(cache.get(1))#輸出:1cache.put(3,3)#去除鍵2print(cache.get(2))#輸出:-1cache.put(4,4)#去除鍵1print(cache.get(1))#輸出:-1print(cache.get(3))#輸出:3print(cache.get(4))#輸出:4解析：-使用雙向鏈表維護(hù)最近使用順序，哈希表實(shí)現(xiàn)O(1)訪問。-`get`時(shí)將節(jié)點(diǎn)移動到頭部，`put`時(shí)如果鍵已存在則更新值并移動到頭部，否則新建節(jié)點(diǎn)并添加到頭部；如果超出容量則刪除尾部節(jié)點(diǎn)。3.（20分）設(shè)計(jì)一個(gè)簡單的數(shù)據(jù)庫事務(wù)日志系統(tǒng)題目描述：設(shè)計(jì)一個(gè)數(shù)據(jù)庫事務(wù)日志系統(tǒng)，支持以下操作：-`log_action(action,timestamp)`：記錄一條事務(wù)日志，`action`為操作類型（如"INSERT"、"UPDATE"、"DELETE"），`timestamp`為時(shí)間戳。-`replay_logs()`：按時(shí)間順序重放所有日志，并返回操作序列。要求：-日志需要支持高效追加和按時(shí)間排序。-提供測試代碼。答案與解析：pythonimportbisectclassTransactionLog:def__init__(self):self.logs=[]#存儲日志，格式為(timestamp,action)deflog_action(self,action,timestamp):bisect.insort(self.logs,(timestamp,action))defreplay_logs(self):return[actionfor_,actioninself.logs]測試代碼log_system=TransactionLog()log_system.log_action("INSERT",20261001)log_system.log_action("UPDATE",20261002)log_system.log_action("DELETE",20261003)print(log_system.replay_logs())#輸出:['INSERT','UPDATE','DELETE']解析：-使用`bisect.insort`維護(hù)日志按時(shí)間戳排序，確保插入時(shí)間復(fù)雜度為O(logn)，重放時(shí)間復(fù)雜度為O(n)。-日志格式為`(timestamp,action)`，便于按時(shí)間順序重放。二、系統(tǒng)設(shè)計(jì)題（共2題，每題30分）1.（30分）設(shè)計(jì)一個(gè)高并發(fā)的短鏈接系統(tǒng)題目描述：設(shè)計(jì)一個(gè)短鏈接系統(tǒng)（如tinyURL），支持以下功能：-用戶輸入長鏈接，系統(tǒng)生成一個(gè)唯一的短鏈接。-用戶通過短鏈接訪問時(shí)，系統(tǒng)返回對應(yīng)的長鏈接。-高并發(fā)場景下保證鏈接生成和解析的效率及一致性。要求：-說明核心數(shù)據(jù)結(jié)構(gòu)和算法。-提出高并發(fā)解決方案（如分布式鎖、緩存等）。-估算系統(tǒng)容量和性能指標(biāo)。答案與解析：核心數(shù)據(jù)結(jié)構(gòu)：-使用哈希表存儲短鏈接與長鏈接的映射（`short_to_long`）。-使用自增ID或隨機(jī)算法生成短鏈接（如62位隨機(jī)字符串）。高并發(fā)解決方案：1.分布式緩存（Redis）：緩存熱點(diǎn)短鏈接，減少數(shù)據(jù)庫查詢。2.分布式鎖（RedisLock）：保證短鏈接生成唯一性。3.異步處理：使用消息隊(duì)列（如Kafka）處理高并發(fā)請求。系統(tǒng)容量和性能指標(biāo)：-每秒處理請求量：假設(shè)使用Redis+數(shù)據(jù)庫組合，可支持每秒10萬+請求。-短鏈接生成：62位隨機(jī)字符串，理論短鏈接數(shù)量超過10^18。偽代碼示例：pythonimportuuidimportredisclassShortLinkSystem:def__init__(self):self.redis=redis.Redis()self.db={}#模擬數(shù)據(jù)庫defgenerate_short_link(self,long_url):short_key=str(uuid.uuid4().int)[:6]#生成62位隨機(jī)字符串whileshort_keyinself.db:short_key=str(uuid.uuid4().int)[:6]self.db[short_key]=long_urlself.redis.set(short_key,long_url)#緩存returnshort_keydefget_long_link(self,short_key):ifshort_keyinself.redis:returnself.redis.get(short_key)returnself.db.get(short_key,"URLnotfound")解析：-使用UUID生成短鏈接，確保唯一性。-分布式緩存和鎖可顯著提升性能和一致性。2.（30分）設(shè)計(jì)一個(gè)實(shí)時(shí)數(shù)據(jù)流處理系統(tǒng)題目描述：設(shè)計(jì)一個(gè)實(shí)時(shí)數(shù)據(jù)流處理系統(tǒng)，支持以下功能：-接收來自多個(gè)源的數(shù)據(jù)流（如傳感器、日志）。-對數(shù)據(jù)流進(jìn)行實(shí)時(shí)聚合（如統(tǒng)計(jì)平均值、最大值）。-支持自定義回調(diào)函數(shù)處理數(shù)據(jù)。要求：-說明系統(tǒng)架構(gòu)（消息隊(duì)列、流處理引擎）。-提出容錯和擴(kuò)展方案。-舉例說明如何處理實(shí)時(shí)聚合。答案與解析：系統(tǒng)架構(gòu)：1.消息隊(duì)列（Kafka）：存儲原始數(shù)據(jù)流，解耦數(shù)據(jù)源和處理器。2.流處理引擎（Flink/SparkStreaming）：實(shí)時(shí)聚合和回調(diào)處理。3.狀態(tài)存儲（Redis）：存儲聚合狀態(tài)（如滑動窗口平均值）。容錯和擴(kuò)展方案：-副本機(jī)制：Kafka分區(qū)+副本保證數(shù)據(jù)不丟失。-動態(tài)擴(kuò)展：流處理引擎支持按需增加節(jié)點(diǎn)。實(shí)時(shí)聚合示例（Flink偽代碼）：javaDataStream<String>sensorData=KafkaUtils.createStream(env,"topic","group",TypeInformation.of(newTypeHint<String>(){}));DataStream<Double>avgTemp=sensorData.map(newMapFunction<String,Double>(){@OverridepublicDoublemap(Stringvalue){returnDouble.parseDouble(value.split(",")[1]);}}).keyBy(0).window(TumblingProcessingTimeWindows.of(Time.minutes(1))).aggregate(newAggregateFunction<Double,Double,Double>(){@OverridepublicDoublecreateAccumulator(){return0.0;}@OverridepublicDoubleadd(Doublevalue,Doubleaccumulator){returnaccumulator+value;}@OverridepublicDoublegetResult(Doubleaccumulator){returnaccumulator/sensorData.getParallelism();}@OverridepublicDoublemerge(Doublea,Doubleb){returna+b;}});avgTemp.addSink(newPrintSinkFunction<Double>());解析：-使用Flink的滑動窗口聚合計(jì)算平均值。-Kafka+流處理引擎架構(gòu)可支持大規(guī)模實(shí)時(shí)數(shù)據(jù)處理。三、算法與數(shù)據(jù)結(jié)構(gòu)題（共3題，每題15分）1.（15分）判斷二叉樹是否是平衡二叉樹題目描述：給定一個(gè)二叉樹，判斷其是否是平衡二叉樹。平衡二叉樹的定義是：對于任意節(jié)點(diǎn)，其左右子樹的高度差不超過1。要求：-提出時(shí)間復(fù)雜度為O(n)的解法。-提供Python代碼實(shí)現(xiàn)。答案與解析：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightclassSolution:defisBalanced(self,root:TreeNode)->bool:defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)ifnotleft_balanced:return0,Falseright_height,right_balanced=check(node.right)ifnotright_balanced:return0,Falsereturnmax(left_height,right_height)+1,abs(left_height-right_height)<=1_,balanced=check(root)returnbalanced測試代碼root=TreeNode(3)root.left=TreeNode(1)root.right=TreeNode(2)root.left.left=TreeNode(0)root.left.right=TreeNode(0)print(Solution().isBalanced(root))#輸出:False解析：-遞歸計(jì)算每個(gè)節(jié)點(diǎn)的高度，同時(shí)判斷左右子樹高度差。-時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(h)，h為樹高度。2.（15分）查找無重復(fù)元素排序數(shù)組的中位數(shù)題目描述：給定一個(gè)無重復(fù)元素的排序數(shù)組，返回中位數(shù)。如果數(shù)組長度為偶數(shù)，返回中間兩個(gè)數(shù)的平均值。要求：-提出時(shí)間復(fù)雜度為O(logn)的解法。-提供Python代碼實(shí)現(xiàn)。答案與解析：pythondeffindMedianSortedArrays(nums1,nums2):total=len(nums1)+len(nums2)iftotal%2==1:returnfindKth(nums1,nums2,total//2+1)else:left=findKth(nums1,nums2,total//2)right=findKth(nums1,nums2,total//2+1)return(left+right)/2deffindKth(nums1,nums2,k):ifnotnums1:returnnums2[k-1]ifnotnums2:returnnums1[k-1]ifk==1:returnmin(nums1[0],nums2[0])mid1=min(k//2,len(nums1))-1mid2=min(k//2,len(nums2))-1ifnums1[mid1]>nums2[mid2]:returnfindKth(nums1,nums2[mid2+1:],k-mid2-1)else:returnfindKth(nums1[mid1+1:],nums2,k-mid1-1)測試代碼nums1=[1,3,8]nums2=[7,9,10]pr