软件工程师面试技巧编程能力考察与答案解析

2026年软件工程师面试技巧：编程能力考察与答案解析一、编程基础与数据结构（共5题，总分20分）1.数组轮转（4分）题目：给定一个数组`arr`和一个正整数`k`，将数组中的元素向右轮转`k`次。请编写代码实现该功能，并说明时间复杂度。示例：输入：`arr=[1,2,3,4,5]`,`k=2`输出：`[4,5,1,2,3]`答案解析：pythondefrotate(arr,k):n=len(arr)k=k%n#防止k大于数组长度returnarr[-k:]+arr[:-k]示例print(rotate([1,2,3,4,5],2))#输出:[4,5,1,2,3]解析：-将数组分为两部分：`arr[-k:]`（后`k`个元素）和`arr[:-k]`（前`n-k`个元素），然后拼接即可。-时间复杂度：O(n)，空间复杂度：O(n)（可以使用原地操作优化空间复杂度）。2.快速排序实现（4分）题目：请实现快速排序算法，并解释其核心思想。答案解析：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)示例print(quick_sort([3,6,8,10,1,2,1]))#输出:[1,1,2,3,6,8,10]解析：-核心思想：选择一个基准值（pivot），将数组分为小于、等于、大于三部分，然后递归排序左右两部分。-时间复杂度：平均O(nlogn)，最坏O(n²)（当基准值选择不均时）。3.环形链表判断（4分）题目：设计一个算法，判断一个链表是否存在环。如果存在，返回环的入口节点；否则返回`None`。答案解析：pythonclassListNode:def__init__(self,x):self.val=xself.next=Nonedefdetect_cycle(head):slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:找到环，计算入口slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone示例创建链表1->2->3->4->2(环)node1=ListNode(1)node2=ListNode(2)node3=ListNode(3)node4=ListNode(4)node1.next=node2node2.next=node3node3.next=node4node4.next=node2#创建环print(detect_cycle(node1).val)#输出:2解析：-使用快慢指针：快指针每次走两步，慢指针每次走一步，相遇则存在环。-相遇后，慢指针回到头节点，再次与快指针同步移动，相遇点即为环入口。-时间复杂度：O(n)，空间复杂度：O(1)。4.树的最大深度（4分）题目：给定一个二叉树，请编写代码计算其最大深度（即从根节点到最远叶节点的最长路径）。答案解析：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmax_depth(root):ifnotroot:return0return1+max(max_depth(root.left),max_depth(root.right))示例创建二叉树:1/\23/\45root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)print(max_depth(root))#输出:3解析：-递归计算左子树和右子树的最大深度，取较大值加1。-时间复杂度：O(n)，空间复杂度：O(h)（h为树的高度）。5.字符串最长不重复子串（4分）题目：给定一个字符串`s`，请找到其中最长的无重复字符的子串，并返回其长度。答案解析：pythondeflength_of_longest_substring(s):char_map={}left=0max_len=0forrightinrange(len(s)):ifs[right]inchar_map:left=max(left,char_map[s[right]]+1)char_map[s[right]]=rightmax_len=max(max_len,right-left+1)returnmax_len示例print(length_of_longest_substring("abcabcbb"))#输出:3("abc")解析：-使用滑动窗口：左指针移动时跳过重复字符，右指针遍历字符串。-使用哈希表记录字符上一次出现的位置，更新窗口左边界。-时间复杂度：O(n)，空间复杂度：O(min(m,n))（m为字符集大小）。二、算法设计与问题解决（共5题，总分25分）1.排列组合问题（5分）题目：给定两个数组`nums1`和`nums2`，请编写代码合并它们的所有排列，并去除重复的排列。示例：输入：`nums1=[1,2]`,`nums2=[1,2,3]`输出：`[[1,1,2],[1,2,1],[1,2,3],[2,1,1],[2,1,2],[2,1,3]]`答案解析：pythonfromitertoolsimportpermutationsdefunique_permutations(nums1,nums2):returnlist(set(permutations(nums1+nums2)))示例nums1=[1,2]nums2=[1,2,3]print(unique_permutations(nums1,nums2))解析：-使用`itertools.permutations`生成所有排列，然后转换为集合去重。-注意：集合是无序的，如果需要有序输出，可先排序再去重。2.最小路径和（5分）题目：给定一个二维网格`grid`，每个格子中的值代表该位置的代价，请找到从左上角到右下角的最低总代价路径。示例：输入：`grid=[[1,3,1],[1,5,1],[4,2,1]]`输出：7（路径：1→3→1→1→1）答案解析：pythondefmin_path_sum(grid):ifnotgridornotgrid[0]:return0m,n=len(grid),len(grid[0])dp=[[0]nfor_inrange(m)]dp[0][0]=grid[0][0]foriinrange(1,m):dp[i][0]=dp[i-1][0]+grid[i][0]forjinrange(1,n):dp[0][j]=dp[0][j-1]+grid[0][j]foriinrange(1,m):forjinrange(1,n):dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]returndp[-1][-1]示例print(min_path_sum([[1,3,1],[1,5,1],[4,2,1]]))#输出:7解析：-动态规划：dp[i][j]表示到达`(i,j)`的最小代价。-状态转移：dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]。-时间复杂度：O(mn)，空间复杂度：O(mn)。3.爬楼梯问题（5分）题目：假设你正在爬楼梯，每次可以爬1或2级台阶。给定总台阶数`n`，请计算共有多少种不同的爬法。示例：输入：`n=3`输出：3（爬法：1+1+1，1+2，2+1）答案解析：pythondefclimb_stairs(n):ifn==1:return1dp=[0](n+1)dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]示例print(climb_stairs(3))#输出:3解析：-动态规划：dp[i]表示到达第`i`级台阶的爬法数量。-状态转移：dp[i]=dp[i-1]+dp[i-2]。-时间复杂度：O(n)，空间复杂度：O(n)（可优化为O(1)）。4.括号匹配问题（5分）题目：给定一个字符串`s`，请判断其中的括号（`()`、`[]`、`{}`）是否匹配。示例：输入：`s="{[()]}"`输出：`True`输入：`s="{[(])}"`输出：`False`答案解析：pythondefis_valid(s):stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack示例print(is_valid("{[()]}"))#输出:Trueprint(is_valid("{[(])}"))#输出:False解析：-使用栈：遇到左括号入栈，右括号时与栈顶比较。-如果匹配则出栈，否则返回`False`。-时间复杂度：O(n)，空间复杂度：O(n)。5.翻转二叉树（5分）题目：给定一个二叉树，请编写代码将其左右子树互换。答案解析：pythondefinvert_tree(root):ifnotroot:returnNoneleft,right=root.left,root.rightroot.left=invert_tree(right)root.right=invert_tree(left)returnroot示例创建二叉树:1/\23/\45root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)invert_tree(root)翻转后:1->3->2,2->5->4解析：-递归交换左右子树。-时间复杂度：O(n)，空间复杂度：O(h)（h为树的高度）。三、系统设计（共5题，总分25分）1.设计LRU缓存（8分）题目：请设计一个LRU（LeastRecentlyUsed）缓存系统，支持容量限制和最近最少使用淘汰策略。答案解析：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)==self.capacity:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)示例lru=LRUCache(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))#返回1lru.put(3,3)#去除键2print(lru.get(2))#返回-1(未找到)解析：-使用哈希表记录键值，双端队列记录访问顺序。-`get`操作将键移到队尾，`put`操作先判断容量，淘汰最久未使用的键。-时间复杂度：O(1)。2.设计短URL服务（7分）题目：请设计一个短URL服务，将长URL转换为短URL，并支持反向解析。答案解析：pythonimporthashlibimportrandomclassShortURL:def__init__(self):self.url_map={}self.base_url="http://short.url/"defencode(self,long_url:str)->str:hash_code=hashlib.md5(long_url.encode()).hexdigest()[:8]short_id=''.join(random.choices('0123456789abcdef',k=6))self.url_map[self.base_url+short_id]=long_urlreturnself.base_url+short_iddefdecode(self,short_url:str)->str:returnself.url_map.get(short_url,"InvalidURL")示例shortener=ShortURL()long_url="/article"short_url=shortener.encode(long_url)print(short_url)#输出:http://short.url/xyz123print(shortener.decode(short_url))#输出:/article解析：-使用MD5哈希长URL生成短ID，结合随机码避免冲突。-哈希后截取前8位，随机生成6位字母组合。-时间复杂度：O(1)。3.设计分布式计数器（6分）题目：请设计一个分布式计数器，支持高并发下的原子性计数。答案解析：pythonfromthreadingimportLockclassDistributedCounter:def__init__(self):self.count=0self.lock=Lock()defincrement(self):withself.lock:self.count+=1returnself.count示例counter=DistributedCounter()for_inrange(10):print(counter.increment())#输出:1到10解析：-使用锁保证线程安全。-若需分布式支持，可结合Redis的`INCR`命令。-时间复杂度：O(1)。4.设计微博关注系统（5分）题目：请设计一个微博关注系统，支持用户关注/取消关注、获取关注者列表等功能。答案解析：pythonclassWeiboFollowSystem:def__init__(self):self.followees={}deffollow(self,follower:str,followee:str)->None:iffollowernotinself.followees:self.followees[follower]=set()self.followees[follower].add(followee)defunfollow(self,follower:str,followee:str)->None:iffollowerinself.followeesandfolloweeinself.followees[follower]:self.followees[follower].remove(followee)defget_followees(self,user:str)->list:returnlist(self.followees.get(user,[]))示例system=WeiboFollowSystem()system.follow("Alice","Bob")system.follow("Alice","Charlie")print(system.get_followees("Alice"))#输出:["Bob","Charlie"]system.unfollow("Alice","Bob")print(system.get_followees("Alice"))#输出:["C