软件工程师的求职攻略与面试题目

2026年软件工程师的求职攻略与面试题目一、编程语言与数据结构（15题，共60分）1.题目（10分）：编写一个函数，实现快速排序算法，并对以下数组进行排序：`[8,3,1,7,0,10,2,5]`。请展示排序过程中的关键步骤，并说明时间复杂度。2.题目（10分）：给定一个链表，设计一个算法删除链表中的所有重复元素，使得每个元素只出现一次。例如，输入`[1,2,2,3,3,4]`，输出`[1,2,3,4]`。请说明算法的时空复杂度。3.题目（15分）：实现一个LRU（最近最少使用）缓存，容量为3。支持`get`和`put`操作，并展示以下操作后的缓存状态：-`put(1,10)`-`put(2,20)`-`get(1)`-`put(3,30)`（驱逐最久未使用的元素）-`get(2)`4.题目（10分）：编写一个函数，判断一个二叉树是否是平衡二叉树（左右子树高度差不超过1）。例如：3/\920/\157输出：`true`。5.题目（10分）：实现一个字符串的子串搜索算法（如KMP算法），并分析其效率。6.题目（10分）：给定一个数组，找出其中不重复的三元组，使得三元组的和为0。例如：`[-1,0,1,2,-1,-4]`，输出：`[[-1,0,1],[-1,-1,2]]`。7.题目（10分）：编写一个函数，实现二叉树的层序遍历（广度优先搜索）。8.题目（10分）：实现一个LRU缓存，使用双向链表和哈希表实现，并说明原理。9.题目（10分）：给定一个数组，找出其中重复次数超过一半的元素。例如：`[2,2,1,1,1,2,2]`，输出：`2`。10.题目（10分）：编写一个函数，实现整数反转，例如：`-123`输出`-321`，注意边界条件。11.题目（10分）：实现一个二叉搜索树，支持插入和查找操作。12.题目（10分）：编写一个函数，检查一个字符串是否是回文串，例如：`"racecar"`输出`true`。13.题目（10分）：实现一个最小堆，支持插入和弹出操作。14.题目（10分）：给定一个数组，找出其中所有唯一的双峰元素（即存在一个峰值，左边严格递增，右边严格递减）。例如：`[1,2,3,5,4,3,2,1]`，输出：`[3,5]`。15.题目（10分）：编写一个函数，合并两个排序链表，并返回合并后的链表。二、系统设计（5题，共50分）1.题目（10分）：设计一个短链接服务（如tinyURL），支持将长链接转换为短链接，并能通过短链接快速访问原链接。2.题目（10分）：设计一个高并发的计数器服务，支持高并发访问和更新。3.题目（10分）：设计一个消息队列系统（如Kafka），支持消息的持久化、解耦和异步处理。4.题目（10分）：设计一个高可用、可扩展的在线音乐播放系统，支持millionsofusers。5.题目（10分）：设计一个微博系统的数据存储方案，支持高并发读写和实时推荐。三、数据库与分布式系统（5题，共40分）1.题目（8分）：解释MySQL中的事务隔离级别（读未提交、读已提交、可重复读、串行化），并说明脏读、不可重复读和幻读的区别。2.题目（8分）：设计一个分布式缓存系统（如Redis集群），并说明如何解决缓存一致性问题。3.题目（8分）：解释CAP理论，并说明在分布式系统中如何选择一致性、可用性和分区容错性。4.题目（8分）：设计一个分布式数据库的读写分离方案，并说明其优缺点。5.题目（8分）：解释分布式事务的解决方案（如2PC、TCC），并说明其适用场景。四、算法与编程（5题，共30分）1.题目（6分）：给定一个字符串，统计其中最长回文子串的长度。例如：`"babad"`，输出：`3`（"bab"或"aba"）。2.题目（6分）：设计一个算法，找出无序数组中的第K大元素。例如：`[3,2,1,5,6,4]`，K=2，输出：`5`。3.题目（6分）：编写一个函数，实现二进制字符串的翻转，例如：`"101001"`输出`"100110"`。4.题目（6分）：给定一个数组，找出其中所有和为特定值的三元组。例如：`[2,7,4,11,15]`，目标和为`18`，输出：`[2,4,12]`。5.题目（6分）：编写一个函数，判断一个数是否是素数。答案与解析一、编程语言与数据结构1.快速排序pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)arr=[8,3,1,7,0,10,2,5]print(quick_sort(arr))#[0,1,2,3,5,7,8,10]时间复杂度：平均O(nlogn)，最坏O(n^2)。2.删除重复元素pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefdelete_duplicates(head):dummy=ListNode(0)dummy.next=headprev,curr=dummy,headwhilecurr:ifcurr.nextandcurr.val==curr.next.val:whilecurr.nextandcurr.val==curr.next.val:curr=curr.nextprev.next=curr.nextelse:prev=currcurr=curr.nextreturndummy.next时空复杂度：O(n)，O(1)。3.LRU缓存pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=Node(0,0),Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.next=self.head.nextnode.next.prev=nodeself.head.next=nodenode.prev=self.head4.平衡二叉树pythondefis_balanced(root):defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)returnmax(left_height,right_height)+1,left_balancedandright_balancedandabs(left_height-right_height)<=1returncheck(root)[1]5.KMP算法pythondefkmp_search(text,pattern):defcompute_lps(pattern):lps=[0]len(pattern)length=0i=1whilei<len(pattern):ifpattern[i]==pattern[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:length=lps[length-1]else:lps[i]=0i+=1returnlpslps=compute_lps(pattern)i=j=0whilei<len(text):ifpattern[j]==text[i]:i+=1j+=1ifj==len(pattern):returni-jj=lps[j-1]elifi<len(text)andpattern[j]!=text[i]:ifj!=0:j=lps[j-1]else:i+=1return-16.三数之和pythondefthree_sum(nums):nums.sort()result=[]foriinrange(len(nums)-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,len(nums)-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==0:result.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<0:left+=1else:right-=1returnresult7.层序遍历pythondeflevel_order(root):ifnotroot:return[]result,queue=[],[root]whilequeue:level=[]for_inrange(len(queue)):node=queue.pop(0)level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(level)returnresult8.LRU缓存（双向链表+哈希表）pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=Node(0,0),Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.next=self.head.nextnode.next.prev=nodeself.head.next=nodenode.prev=self.head9.多数元素pythondefmajority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate10.整数反转pythondefreverse_integer(x):INT_MAX,INT_MIN=231-1,-231result=0whilex:pop=x%10x//=10ifresult>INT_MAX//10or(result==INT_MAX//10andpop>7):return0ifresult<INT_MIN//10or(result==INT_MIN//10andpop<-8):return0result=result10+popreturnresult11.二叉搜索树pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinsert(root,val):ifnotroot:returnTreeNode(val)ifval<root.val:root.left=insert(root.left,val)else:root.right=insert(root.right,val)returnrootdefsearch(root,val):ifnotrootorroot.val==val:returnrootifval<root.val:returnsearch(root.left,val)returnsearch(root.right,val)12.回文串pythondefis_palindrome(s):s=''.join(filter(str.isalnum,s)).lower()returns==s[::-1]13.最小堆pythonimportheapqheap=[]heapq.heappush(heap,3)heapq.heappush(heap,1)heapq.heappush(heap,2)heapq.heappop(heap)#114.双峰元素pythondeffind_peaks(nums):peaks=[]n=len(nums)i=1whilei<n-1:ifnums[i]>nums[i-1]andnums[i]>nums[i+1]:peaks.append(nums[i])whilei<n-1andnums[i]==nums[i+1]:i+=1i+=1returnpeaks15.合并排序链表pythondefmerge_two_lists(l1,l2):dummy=ListNode(0)tail=dummywhilel1andl2:ifl1.val<l2.val:tail.next=l1l1=l1.nextelse:tail.next=l2l2=l2.nexttail=tail.nexttail.next=l1orl2returndummy.next二、系统设计1.短链接服务-使用哈希函数（如MD5）将长链接映射为短链接。-存储短链接与长链接的映射关系（数据库或缓存）。-重定向HTTP请求到原链接。2.高并发计数器-使用Redis的`INCR`命令。-分布式环境下，使用`Redlock`算法解决并发问题。3.消息队列-使用Kafka或RabbitMQ。-持久化消息到磁盘，支持重试和补偿。4.在线音乐播放系统-使用CDN加速静态资源（音乐文件）。-使用消息队列处理播放请求，支持异步处理。-数据库分片存储用户数据和播放记录。5.微博系统-使用MySQL+Redis存储用户数据和实时推荐。-使用Elasticsearch进行全文搜索。-使用消息队列处理动态消息推送。三、数据库与分布式系统1.事务隔离级别-读未提交：可能脏读。-读已提交：解决脏读，但不可重复读。-可重复读：解决不可重复读，但可能出现幻读。-串行化：完全隔离，但性能最低。2.分布式缓存-使用Redis集群，分片存储数据。-使用发布订阅机制解决缓存一致性问题。3.CAP理论-分布式系统只能同时满足一致性、可用性和分区容错性中的两项。-例如，Twitter优先可用性，牺牲部分一致性。4.读写分离-主库处理写操作，从库处理读操作。-使用Redis缓存热点数据。5.分布式事务-2PC：强一致性，但性能低。-TCC：柔性一致性，适用于电商场景。四、算法与编程1.最长回文子串pythondeflongest_palindrome(s):ifnots:return""start,end=0,0foriinrange(len(s)):len1=expand_from_center(s,i,i)len2=expand_from_center(s,i,i+