2026年系統(tǒng)架構(gòu)師面試：復(fù)雜算法題的解決思路題型一：動(dòng)態(tài)規(guī)劃（3題，每題10分）題目1（10分）：背景：某電商平臺(tái)需要對(duì)用戶購買的商品進(jìn)行推薦，推薦策略基于用戶的歷史購買記錄。假設(shè)用戶的歷史購買行為可以用一個(gè)序列表示，例如`[A,B,C,A,B]`。系統(tǒng)需要推薦一個(gè)用戶尚未購買的商品，且推薦的商品與用戶最近購買的商品相關(guān)性最高。相關(guān)性定義為兩個(gè)商品在序列中相距最近的出現(xiàn)位置。問題：給定用戶的歷史購買序列`purchase`和一個(gè)未購買的商品`unpurchased`，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，找出`unpurchased`在`purchase`中相距最近的出現(xiàn)位置，并返回該位置（從0開始計(jì)數(shù)）。如果`unpurchased`不在`purchase`中，返回`-1`。示例：-輸入：`purchase=[A,B,C,A,B]`,`unpurchased=C`-輸出：`2`（C在序列中的第二個(gè)位置）要求：-時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。題目2（10分）：背景：在分布式系統(tǒng)中，節(jié)點(diǎn)之間需要通過多跳路由傳輸數(shù)據(jù)包。每條邊的傳輸時(shí)間不同，系統(tǒng)需要找到一條從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑。問題：給定一個(gè)無向圖`graph`（用鄰接矩陣表示），其中`graph[i][j]`表示節(jié)點(diǎn)`i`到節(jié)點(diǎn)`j`的傳輸時(shí)間（若無法直接傳輸，則為無窮大）。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，計(jì)算從源節(jié)點(diǎn)`src`到目標(biāo)節(jié)點(diǎn)`dst`的最短路徑長度。示例：-輸入：graph=[[0,2,3,0,0],[2,0,1,4,0],[3,1,0,5,0],[0,4,5,0,2],[0,0,0,2,0]]src=0,dst=4-輸出：`6`（路徑：0->1->2->3->4，總時(shí)間2+1+5+2=10）要求：-使用Dijkstra算法或Bellman-Ford算法，時(shí)間復(fù)雜度O(V^2)或O(VE)。題目3（10分）：背景：某物流公司在配送貨物時(shí)，需要規(guī)劃最優(yōu)的配送路線。每條路線的收益不同，但需要滿足一定的配送順序（例如，必須按城市編號(hào)順序配送）。問題：給定一個(gè)任務(wù)序列`tasks`（每個(gè)任務(wù)包含起點(diǎn)和終點(diǎn)），以及每個(gè)任務(wù)的收益`profits`。系統(tǒng)需要選擇一個(gè)子序列，使得起點(diǎn)和終點(diǎn)滿足遞增順序，且總收益最大。示例：-輸入：tasks=[(1,3),(2,5),(3,6),(4,7)]profits=[10,20,30,40]-輸出：`100`（選擇(2,5)和(4,7)，總收益20+40=60）要求：-使用動(dòng)態(tài)規(guī)劃或貪心算法，時(shí)間復(fù)雜度O(n^2)或O(nlogn)。題型二：圖算法（3題，每題10分）題目4（10分）：背景：在金融系統(tǒng)中，需要對(duì)交易網(wǎng)絡(luò)進(jìn)行風(fēng)險(xiǎn)監(jiān)控。交易網(wǎng)絡(luò)可以用有向圖表示，每個(gè)節(jié)點(diǎn)代表一個(gè)用戶，每條邊代表一筆交易。系統(tǒng)需要檢測是否存在一個(gè)環(huán)，且環(huán)中所有節(jié)點(diǎn)的交易金額總和超過閾值`threshold`。問題：給定一個(gè)有向圖`edges`（用鄰接表表示）和一個(gè)閾值`threshold`，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，判斷是否存在滿足條件的環(huán)。示例：-輸入：edges=[[1,2],//用戶0交易給用戶1，金額1[2,3],//用戶1交易給用戶2，金額2[3,0],//用戶2交易給用戶0，金額3[0,1]//用戶0交易給用戶1，金額1]threshold=5-輸出：`True`（環(huán)0->1->2->0，總金額1+2+3=6>5）要求：-使用DFS或BFS，時(shí)間復(fù)雜度O(V+E)。題目5（10分）：背景：在社交網(wǎng)絡(luò)中，用戶之間的關(guān)注關(guān)系可以用有向圖表示。系統(tǒng)需要計(jì)算每個(gè)用戶的“影響力”，定義為與其直接或間接相關(guān)的用戶數(shù)量。問題：給定一個(gè)有向圖`graph`（用鄰接表表示），請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，計(jì)算每個(gè)用戶的“影響力”，并返回一個(gè)字典或數(shù)組。示例：-輸入：graph={0:[1,2],1:[3],2:[3],3:[]}-輸出：`{0:4,1:3,2:3,3:2}`（用戶0可達(dá)4個(gè)用戶，用戶1可達(dá)3個(gè)，以此類推）要求：-使用BFS或DFS，時(shí)間復(fù)雜度O(V+E)。題目6（10分）：背景：在供應(yīng)鏈管理中，多個(gè)工廠需要向多個(gè)倉庫供貨。每條供應(yīng)路徑的運(yùn)輸成本不同，系統(tǒng)需要計(jì)算從每個(gè)工廠到每個(gè)倉庫的最小運(yùn)輸成本。問題：給定一個(gè)有向圖`graph`（用鄰接矩陣表示），其中`graph[i][j]`表示工廠`i`到倉庫`j`的運(yùn)輸成本（若無法運(yùn)輸，則為無窮大）。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，計(jì)算從每個(gè)工廠到每個(gè)倉庫的最小運(yùn)輸成本。示例：-輸入：graph=[[0,5,Inf,10],[Inf,0,3,Inf],[Inf,Inf,0,1],[Inf,Inf,Inf,0]]-輸出：[[0,5,Inf,10],[Inf,0,3,Inf],[Inf,Inf,0,1],[Inf,Inf,Inf,0]]要求：-使用Floyd-Warshall算法，時(shí)間復(fù)雜度O(V^3)。題型三：貪心算法（3題，每題10分）題目7（10分）：背景：在云計(jì)算資源調(diào)度中，多個(gè)任務(wù)需要分配到多個(gè)服務(wù)器上。每個(gè)任務(wù)有資源需求（CPU、內(nèi)存），每個(gè)服務(wù)器的資源容量有限。系統(tǒng)需要最大化可分配的任務(wù)數(shù)量。問題：給定一個(gè)任務(wù)列表`tasks`（每個(gè)任務(wù)包含CPU和內(nèi)存需求）和一個(gè)服務(wù)器列表`servers`（每個(gè)服務(wù)器包含CPU和內(nèi)存容量），請(qǐng)?jiān)O(shè)計(jì)一個(gè)貪心算法，計(jì)算最多可以分配多少個(gè)任務(wù)。示例：-輸入：tasks=[(1,2),(2,1),(3,3),(2,2)]servers=[(4,4),(3,3),(2,2)]-輸出：`3`（可分配(1,2),(2,1),(2,2)）要求：-使用貪心策略（如優(yōu)先分配資源需求小的任務(wù)），時(shí)間復(fù)雜度O(nlogn)。題目8（10分）：背景：在網(wǎng)絡(luò)路由中，多個(gè)數(shù)據(jù)包需要通過不同鏈路傳輸。每條鏈路有帶寬限制，系統(tǒng)需要最小化數(shù)據(jù)包的傳輸時(shí)間。問題：給定一個(gè)鏈路列表`links`（每個(gè)鏈路包含起點(diǎn)、終點(diǎn)和帶寬），以及一個(gè)數(shù)據(jù)包列表`packets`（每個(gè)數(shù)據(jù)包包含大小和優(yōu)先級(jí)）。請(qǐng)?jiān)O(shè)計(jì)一個(gè)貪心算法，計(jì)算所有數(shù)據(jù)包傳輸?shù)目倳r(shí)間（按優(yōu)先級(jí)從小到大傳輸）。示例：-輸入：links=[(A,B,10),(B,C,5),(A,C,15)]packets=[(3,1),(4,2),(2,1)]//優(yōu)先級(jí)1更高-輸出：`5`（傳輸順序：3(A->B),2(A->C),4(B->C)）要求：-使用貪心策略（優(yōu)先處理高優(yōu)先級(jí)數(shù)據(jù)包），時(shí)間復(fù)雜度O(nlogn)。題目9（10分）：背景：在任務(wù)調(diào)度中，多個(gè)任務(wù)需要按特定順序執(zhí)行。每個(gè)任務(wù)有執(zhí)行時(shí)間和依賴關(guān)系。系統(tǒng)需要最小化總完成時(shí)間。問題：給定一個(gè)任務(wù)列表`tasks`（每個(gè)任務(wù)包含執(zhí)行時(shí)間和依賴任務(wù)列表），請(qǐng)?jiān)O(shè)計(jì)一個(gè)貪心算法，計(jì)算所有任務(wù)完成的總時(shí)間。示例：-輸入：tasks={1:(3,[]),//執(zhí)行時(shí)間3，無依賴2:(2,[1]),//執(zhí)行時(shí)間2，依賴任務(wù)13:(4,[1]),//執(zhí)行時(shí)間4，依賴任務(wù)14:(1,[2,3])//執(zhí)行時(shí)間1，依賴任務(wù)2和3}-輸出：`8`（執(zhí)行順序：1->2->3->4，總時(shí)間3+2+4+1=10）要求：-使用貪心策略（優(yōu)先執(zhí)行無依賴任務(wù)），時(shí)間復(fù)雜度O(nlogn)。答案與解析動(dòng)態(tài)規(guī)劃題目1：思路：遍歷`purchase`，記錄`unpurchased`最近出現(xiàn)的位置。代碼：pythondeffind_nearest_position(purchase,unpurchased):last_pos=-1fori,iteminenumerate(purchase):ifitem==unpurchased:last_pos=ireturnlast_pos解析：-時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。-遍歷一次序列，記錄最近出現(xiàn)位置。題目2：思路：使用Dijkstra算法，維護(hù)最短路徑距離。代碼：pythonimportheapqdefdijkstra(graph,src,dst):n=len(graph)dist=[float('inf')]ndist[src]=0heap=[(0,src)]whileheap:d,u=heapq.heappop(heap)ifu==dst:returndifd>dist[u]:continueforv,winenumerate(graph[u]):ifw!=float('inf'):new_dist=d+wifnew_dist<dist[v]:dist[v]=new_distheapq.heappush(heap,(new_dist,v))return-1解析：-時(shí)間復(fù)雜度O(V^2)或O(VE)，取決于實(shí)現(xiàn)方式。-Dijkstra算法適用于帶權(quán)圖的最短路徑問題。題目3：思路：使用動(dòng)態(tài)規(guī)劃，記錄最大收益的子序列。代碼：pythondefmax_profit(tasks,profits):n=len(tasks)dp=[0](n+1)foriinrange(n):start,end=tasks[i]forjinrange(i-1,-1,-1):iftasks[j][1]<start:dp[i+1]=max(dp[i+1],dp[j+1]+profits[i])returndp[n]解析：-時(shí)間復(fù)雜度O(n^2)，空間復(fù)雜度O(n)。-動(dòng)態(tài)規(guī)劃通過記錄子問題的最大收益來求解。圖算法題目4：思路：使用DFS檢測環(huán)，并計(jì)算環(huán)內(nèi)交易金額。代碼：pythondefhas_cycle(graph,threshold):n=len(graph)visited=[False]nrec_stack=[False]ndefdfs(node,total):ifnotvisited[node]:visited[node]=Truerec_stack[node]=Truetotal+=graph[node]forneighboringraph[node]:ifnotvisited[neighbor]:ifdfs(neighbor,total):returnTrueelifrec_stack[neighbor]:returnTruerec_stack[node]=Falsereturntotal>thresholdreturnFalseforiinrange(n):ifnotvisited[i]:ifdfs(i,0):returnTruereturnFalse解析：-時(shí)間復(fù)雜度O(V+E)，空間復(fù)雜度O(V)。-通過DFS檢測環(huán)，并累加環(huán)內(nèi)交易金額。題目5：思路：使用BFS計(jì)算每個(gè)節(jié)點(diǎn)的可達(dá)節(jié)點(diǎn)數(shù)量。代碼：pythondefcalculate_influence(graph):n=len(graph)influence=[0]nvisited=[False]nforiinrange(n):ifnotvisited[i]:queue=[i]visited[i]=Truewhilequeue:u=queue.pop(0)influence[i]+=1forvingraph[u]:ifnotvisited[v]:visited[v]=Truequeue.append(v)returninfluence解析：-時(shí)間復(fù)雜度O(V+E)，空間復(fù)雜度O(V)。-BFS遍歷每個(gè)節(jié)點(diǎn)的鄰接節(jié)點(diǎn)，統(tǒng)計(jì)可達(dá)數(shù)量。題目6：思路：使用Floyd-Warshall算法計(jì)算所有對(duì)最短路徑。代碼：pythondefall_pairs_shortest_path(graph):n=len(graph)dist=[row[:]forrowingraph]forkinrange(n):foriinrange(n):forjinrange(n):ifdist[i][k]+dist[k][j]<dist[i][j]:dist[i][j]=dist[i][k]+dist[k][j]returndist解析：-時(shí)間復(fù)雜度O(V^3)，空間復(fù)雜度O(V^2)。-Floyd-Warshall適用于計(jì)算所有對(duì)最短路徑。貪心算法題目7：思路：優(yōu)先分配資源需求小的任務(wù)。代碼：pythondefmax_task_allocation(tasks,servers):tasks.sort(key=lambdax:x[0]+x[1])#按CPU+內(nèi)存排序servers.sort(key=lambdax:x[0]+x[1])allocated=0forcpu,meminservers:fortaskintasks:iftask[0]<=cpuandtask[1]<=mem:allocated+=1servers.remove((cpu,mem))tasks.remove(task)breakreturnallocated解析：-時(shí)間復(fù)雜度O(nlogn)，空間復(fù)雜度O(n)。-貪心策略優(yōu)先分配資源需求小的服務(wù)器和任務(wù)。題目8：思路：優(yōu)先處理高優(yōu)先級(jí)數(shù)據(jù)包。代碼：pythondefmin_transmission_time(links,packets):packets.sort(key=lambdax:x[1])#按優(yōu)先級(jí)排序total_time=0forsize,_inpacke