2026年系统架构师面试复杂算法题的解决思路

2026年系统架构师面试：复杂算法题的解决思路题型一：动态规划（3题，每题10分）题目1（10分）：背景：某电商平台需要对用户购买的商品进行推荐，推荐策略基于用户的历史购买记录。假设用户的历史购买行为可以用一个序列表示，例如`[A,B,C,A,B]`。系统需要推荐一个用户尚未购买的商品，且推荐的商品与用户最近购买的商品相关性最高。相关性定义为两个商品在序列中相距最近的出现位置。问题：给定用户的历史购买序列`purchase`和一个未购买的商品`unpurchased`，请设计一个算法，找出`unpurchased`在`purchase`中相距最近的出现位置，并返回该位置（从0开始计数）。如果`unpurchased`不在`purchase`中，返回`-1`。示例：-输入：`purchase=[A,B,C,A,B]`,`unpurchased=C`-输出：`2`（C在序列中的第二个位置）要求：-时间复杂度O(n)，空间复杂度O(1)。题目2（10分）：背景：在分布式系统中，节点之间需要通过多跳路由传输数据包。每条边的传输时间不同，系统需要找到一条从源节点到目标节点的最短路径。问题：给定一个无向图`graph`（用邻接矩阵表示），其中`graph[i][j]`表示节点`i`到节点`j`的传输时间（若无法直接传输，则为无穷大）。请设计一个算法，计算从源节点`src`到目标节点`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，总时间2+1+5+2=10）要求：-使用Dijkstra算法或Bellman-Ford算法，时间复杂度O(V^2)或O(VE)。题目3（10分）：背景：某物流公司在配送货物时，需要规划最优的配送路线。每条路线的收益不同，但需要满足一定的配送顺序（例如，必须按城市编号顺序配送）。问题：给定一个任务序列`tasks`（每个任务包含起点和终点），以及每个任务的收益`profits`。系统需要选择一个子序列，使得起点和终点满足递增顺序，且总收益最大。示例：-输入：tasks=[(1,3),(2,5),(3,6),(4,7)]profits=[10,20,30,40]-输出：`100`（选择(2,5)和(4,7)，总收益20+40=60）要求：-使用动态规划或贪心算法，时间复杂度O(n^2)或O(nlogn)。题型二：图算法（3题，每题10分）题目4（10分）：背景：在金融系统中，需要对交易网络进行风险监控。交易网络可以用有向图表示，每个节点代表一个用户，每条边代表一笔交易。系统需要检测是否存在一个环，且环中所有节点的交易金额总和超过阈值`threshold`。问题：给定一个有向图`edges`（用邻接表表示）和一个阈值`threshold`，请设计一个算法，判断是否存在满足条件的环。示例：-输入：edges=[[1,2],//用户0交易给用户1，金额1[2,3],//用户1交易给用户2，金额2[3,0],//用户2交易给用户0，金额3[0,1]//用户0交易给用户1，金额1]threshold=5-输出：`True`（环0->1->2->0，总金额1+2+3=6>5）要求：-使用DFS或BFS，时间复杂度O(V+E)。题目5（10分）：背景：在社交网络中，用户之间的关注关系可以用有向图表示。系统需要计算每个用户的“影响力”，定义为与其直接或间接相关的用户数量。问题：给定一个有向图`graph`（用邻接表表示），请设计一个算法，计算每个用户的“影响力”，并返回一个字典或数组。示例：-输入：graph={0:[1,2],1:[3],2:[3],3:[]}-输出：`{0:4,1:3,2:3,3:2}`（用户0可达4个用户，用户1可达3个，以此类推）要求：-使用BFS或DFS，时间复杂度O(V+E)。题目6（10分）：背景：在供应链管理中，多个工厂需要向多个仓库供货。每条供应路径的运输成本不同，系统需要计算从每个工厂到每个仓库的最小运输成本。问题：给定一个有向图`graph`（用邻接矩阵表示），其中`graph[i][j]`表示工厂`i`到仓库`j`的运输成本（若无法运输，则为无穷大）。请设计一个算法，计算从每个工厂到每个仓库的最小运输成本。示例：-输入：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算法，时间复杂度O(V^3)。题型三：贪心算法（3题，每题10分）题目7（10分）：背景：在云计算资源调度中，多个任务需要分配到多个服务器上。每个任务有资源需求（CPU、内存），每个服务器的资源容量有限。系统需要最大化可分配的任务数量。问题：给定一个任务列表`tasks`（每个任务包含CPU和内存需求）和一个服务器列表`servers`（每个服务器包含CPU和内存容量），请设计一个贪心算法，计算最多可以分配多少个任务。示例：-输入：tasks=[(1,2),(2,1),(3,3),(2,2)]servers=[(4,4),(3,3),(2,2)]-输出：`3`（可分配(1,2),(2,1),(2,2)）要求：-使用贪心策略（如优先分配资源需求小的任务），时间复杂度O(nlogn)。题目8（10分）：背景：在网络路由中，多个数据包需要通过不同链路传输。每条链路有带宽限制，系统需要最小化数据包的传输时间。问题：给定一个链路列表`links`（每个链路包含起点、终点和带宽），以及一个数据包列表`packets`（每个数据包包含大小和优先级）。请设计一个贪心算法，计算所有数据包传输的总时间（按优先级从小到大传输）。示例：-输入：links=[(A,B,10),(B,C,5),(A,C,15)]packets=[(3,1),(4,2),(2,1)]//优先级1更高-输出：`5`（传输顺序：3(A->B),2(A->C),4(B->C)）要求：-使用贪心策略（优先处理高优先级数据包），时间复杂度O(nlogn)。题目9（10分）：背景：在任务调度中，多个任务需要按特定顺序执行。每个任务有执行时间和依赖关系。系统需要最小化总完成时间。问题：给定一个任务列表`tasks`（每个任务包含执行时间和依赖任务列表），请设计一个贪心算法，计算所有任务完成的总时间。示例：-输入：tasks={1:(3,[]),//执行时间3，无依赖2:(2,[1]),//执行时间2，依赖任务13:(4,[1]),//执行时间4，依赖任务14:(1,[2,3])//执行时间1，依赖任务2和3}-输出：`8`（执行顺序：1->2->3->4，总时间3+2+4+1=10）要求：-使用贪心策略（优先执行无依赖任务），时间复杂度O(nlogn)。答案与解析动态规划题目1：思路：遍历`purchase`，记录`unpurchased`最近出现的位置。代码：pythondeffind_nearest_position(purchase,unpurchased):last_pos=-1fori,iteminenumerate(purchase):ifitem==unpurchased:last_pos=ireturnlast_pos解析：-时间复杂度O(n)，空间复杂度O(1)。-遍历一次序列，记录最近出现位置。题目2：思路：使用Dijkstra算法，维护最短路径距离。代码：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解析：-时间复杂度O(V^2)或O(VE)，取决于实现方式。-Dijkstra算法适用于带权图的最短路径问题。题目3：思路：使用动态规划，记录最大收益的子序列。代码：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]解析：-时间复杂度O(n^2)，空间复杂度O(n)。-动态规划通过记录子问题的最大收益来求解。图算法题目4：思路：使用DFS检测环，并计算环内交易金额。代码：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解析：-时间复杂度O(V+E)，空间复杂度O(V)。-通过DFS检测环，并累加环内交易金额。题目5：思路：使用BFS计算每个节点的可达节点数量。代码：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解析：-时间复杂度O(V+E)，空间复杂度O(V)。-BFS遍历每个节点的邻接节点，统计可达数量。题目6：思路：使用Floyd-Warshall算法计算所有对最短路径。代码：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解析：-时间复杂度O(V^3)，空间复杂度O(V^2)。-Floyd-Warshall适用于计算所有对最短路径。贪心算法题目7：思路：优先分配资源需求小的任务。代码：pythondefmax_task_allocation(tasks,servers):tasks.sort(key=lambdax:x[0]+x[1])#按CPU+内存排序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解析：-时间复杂度O(nlogn)，空间复杂度O(n)。-贪心策略优先分配资源需求小的服务器和任务。题目8：思路：优先处理高优先级数据包。代码：pythondefmin_transmission_time(links,packets):packets.sort(key=lambdax:x[1])#按优先级排序total_time=0forsize,_inpacke