2026年软件工程师面试编程题集

2026年软件工程师面试编程题集1.数值计算（3题，每题10分）地域/行业针对性：金融科技、大数据处理题目1（数组求和）给定一个整数数组`nums`，返回数组中所有奇数元素的平方和。例如，输入`[1,2,3,4,5]`，输出`1²+3²+5²=35`。要求：时间复杂度O(n)，不使用内置函数。题目2（滑动窗口最大值）给定一个整数数组`nums`和整数`k`，返回一个长度为`nums.length-k+1`的数组，其中每个元素是窗口`[i,i+k-1]`的最大值。例如，输入`[1,3,-1,-3,5,3,6,7]`，`k=3`，输出`[3,3,5,5,6,7]`。要求：时间复杂度O(n)，不使用排序。题目3（斐波那契数列优化）实现一个函数`fib(n)`，返回第`n`个斐波那契数（0-indexed）。要求：-`n`为0或1时，返回`n`；-时间复杂度O(logn)，空间复杂度O(1)。提示：可使用矩阵快速幂方法。2.字符串处理（4题，每题10分）地域/行业针对性：中文自然语言处理、网络安全题目4（最长回文子串）给定一个字符串`s`，返回其最长回文子串的长度。例如，输入`"babad"`，输出`3`（"bab"或"aba"）。要求：时间复杂度O(n²)，不使用动态规划。题目5（字符串异位词判断）给定两个字符串`s`和`t`，判断`t`是否是`s`的异位词（字母顺序不同但字符相同）。例如，输入`s="anagram"`,`t="nagaram"`，输出`true`。要求：不使用额外空间。题目6（敏感词过滤）实现一个函数`filterSensitiveWords(text,bannedWords)`，将`text`中的所有`bannedWords`替换为``。例如，输入`text="helloworld"`,`bannedWords=["hello"]`，输出`"world"`。要求：支持中文和英文混合输入。题目7（正则表达式匹配）实现一个函数`isMatch(s,p)`，判断`s`是否匹配正则表达式`p`，其中`p`只包含字母和``（``表示任意字符序列）。例如，输入`s="aab"`,`p="cab"`，输出`true`。要求：递归解法，不使用现成库。3.数据结构（5题，每题12分）地域/行业针对性：云计算、电商后端题目8（二叉树遍历）给定一个二叉树，返回其前序遍历（根-左-右）的列表。例如，输入`[3,9,20,null,null,15,7]`（用层序表示），输出`[3,9,20,15,7]`。要求：迭代解法，不使用递归。题目9（链表反转）给定一个单链表`head`，返回其反转后的链表。例如，输入`1->2->3->4->5`，输出`5->4->3->2->1`。要求：原地修改，不使用额外链表。题目10（LRU缓存）实现一个LRU（最近最少使用）缓存，支持`get(key)`和`put(key,value)`操作。例如，容量为2：-`put(1,1)`-`put(2,2)`-`get(1)`→返回`1`-`put(3,3)`→哈希表为`{2:2,3:3}`，`1`被移除-`get(4)`→返回`-1`要求：使用哈希表+双向链表实现。题目11（并查集应用）给定`n`个节点和`m`个边，用并查集判断是否形成环。例如，输入`n=5`,`edges=[[0,1],[1,2],[2,3],[3,4],[4,0]]`，输出`true`。要求：路径压缩优化。题目12（树的最大深度）给定一个二叉树，返回其最大深度（根到最远叶节点的路径长度）。例如，输入`[3,9,20,null,null,15,7]`，输出`3`。要求：递归解法。4.算法设计（4题，每题15分）地域/行业针对性：自动驾驶、推荐系统题目13（K个最近邻）给定一个数组`nums`和整数`k`，返回所有元素中第`k`个最接近`target`的元素。例如，输入`nums=[1,2,3,4,5]`,`k=4`,`target=3`，输出`2`或`4`（取决于定义）。要求：时间复杂度O(nlogn)。题目14（贪心算法：活动选择）给定`n`个活动`[start_i,end_i]`，选择尽可能多的不冲突活动。例如，输入`[[1,4],[2,3],[3,5],[6,7]]`，输出`[1,4],[3,5],[6,7]`。要求：按结束时间排序。题目15（二分查找变种）给定一个旋转排序数组`nums`（如`[4,5,6,7,0,1,2]`），返回`target`的索引，若不存在返回`-1`。例如，输入`nums=[4,5,6,7,0,1,2]`,`target=0`，输出`4`。要求：时间复杂度O(logn)。题目16（动态规划：最长递增子序列）给定一个数组`nums`，返回其最长递增子序列的长度。例如，输入`[10,9,2,5,3,7,101,18]`，输出`4`（[2,3,7,101]或[2,5,7,101]）。要求：时间复杂度O(n²)。5.系统设计（2题，每题20分）地域/行业针对性：高并发、分布式系统题目17（设计LRU缓存）详细设计一个支持高并发的分布式LRUCache系统，要求：-支持多线程访问；-节点失效时自动重平衡；-时间和空间效率高。要求：说明数据结构、锁机制、分布式策略。题目18（设计短链接系统）设计一个短链接系统（如`tinyurl`），要求：-输入长链接，返回短链接；-支持反向解析；-高可用、高并发。要求：说明哈希算法、数据库设计、缓存策略。答案与解析1.数值计算题目1pythondefsum_of_odds(nums):returnsum(xxforxinnumsifx%2!=0)解析：列表推导式遍历奇数，计算平方和，时间O(n)题目2pythondefmax_sliding_window(nums,k):fromcollectionsimportdequedq=deque()res=[]foriinrange(len(nums)):whiledqandnums[i]>nums[dq[-1]]:dq.pop()dq.append(i)ifi>=k-1:ifdq[0]==i-k:dq.popleft()res.append(nums[dq[0]])returnres解析：双端队列维护最大值窗口，时间O(n)题目3pythondeffib(n):F=[[1,1],[1,0]]defmultiply(F,M):return[[F[0][0]M[0][0]+F[0][1]M[1][0],F[0][0]M[0][1]+F[0][1]M[1][1]],[F[1][0]M[0][0]+F[1][1]M[1][0],F[1][0]M[0][1]+F[1][1]M[1][1]]]defpower(F,n):ifn==0orn==1:returnFM=[[1,1],[1,0]]power(F,n//2)F=multiply(F,F)ifn%2!=0:F=multiply(F,M)returnFifn==0:return0returnpower(F,n-1)[0][0]解析：矩阵快速幂，时间O(logn)2.字符串处理题目4pythondeflongest_palindrome(s):n=len(s)max_len=1foriinrange(n):l,r=i,iwhilel>=0andr<nands[l]==s[r]:ifr-l+1>max_len:max_len=r-l+1l-=1r+=1returnmax_len解析：中心扩展法，时间O(n²)题目5pythondefis_anagram(s,t):iflen(s)!=len(t):returnFalsecount=[0]128fora,binzip(s,t):count[ord(a)]+=1count[ord(b)]-=1returnall(x==0forxincount)解析：ASCII字符统计，空间O(1)题目6pythondeffilter_sensitive_words(text,bannedWords):banned=set(bannedWords)words=text.split()filtered=[''ifwordinbannedelsewordforwordinwords]return''.join(filtered)解析：分词替换，支持中文题目7pythondefisMatch(s,p):ifnotp:returnnotsfirst_match=bool(s)andp[0]in{s[0],'.'}iflen(p)>=2andp[1]=='':returnisMatch(s,p[2:])or(first_matchandisMatch(s[1:],p))else:returnfirst_matchandisMatch(s[1:],p[1:])解析：递归处理''，时间O(nm)3.数据结构题目8pythondefpreorder_iterative(root):ifnotroot:return[]stack,res=[root],[]whilestack:node=stack.pop()res.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnres解析：栈模拟递归，时间O(n)题目9pythondefreverse_list(head):prev,curr=None,headwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodereturnprev解析：三指针法，时间O(n)题目10pythonclassLRUCache:classNode:def__init__(self,key,val):self.key=keyself.val=valself.prev,self.next=None,Nonedef__init__(self,capacity):self.capacity=capacityself.cache={}self.head,self.tail=self.Node(0,0),self.Node(0,0)self.head.next,self.tail.prev=self.tail,self.headdef_add_node(self,node):node.prev,node.next=self.head,self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):node.prev.next=node.nextnode.next.prev=node.prevdef_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):node=self.cache.get(key,None)ifnotnode:return-1self._move_to_head(node)returnnode.valdefput(self,key,value):node=self.cache.get(key)ifnode:node.val=valueself._move_to_head(node)else:newNode=self.Node(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]解析：双向链表+哈希表，时间O(1)题目11pythonclassUnionFind:def__init__(self,n):self.parent=list(range(n))deffind(self,x):ifself.parent[x]!=x:self.parent[x]=self.find(self.parent[x])returnself.parent[x]defunion(self,x,y):fx,fy=self.find(x),self.find(y)iffx==fy:returnTrueself.parent[fy]=fxreturnFalsedefhas_cycle(n,edges):uf=UnionFind(n)fora,binedges:ifuf.union(a,b):returnTruereturnFalse解析：并查集，时间O(nα(n))题目12pythondefmax_depth(root):ifnotroot:return0return1+max(max_depth(root.left),max_depth(root.right))解析：递归遍历，时间O(n)4.算法设计题目13pythondefkth_closest(nums,k,target):nums.sort(key=lambdax:abs(x-target))returnnums[k-1]解析：排序法，时间O(nlogn)题目14pythondefactivity_selection(start,end):events=sorted(zip(end,start))res,last_end=[],events[0][0]fore,sinevents[1:]:ifs>last_end:res.append((last_end,e))last_end=ereturnres解析：按结束时间排序，时间O(nlogn)题目15pythondefsearch_rotated(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidifnums[mid]>=nums[left]:ifnums[left]<=target<nums[mid]:right=mid-1else:left=mid+1else:ifnums[mid]<target<=nums[right]:left=mid+1else:righ