2026年软件工程师面试常见算法题解含答案

2026年软件工程师面试常见算法题解含答案一、排序算法（3题，每题10分）1.题目：实现快速排序（QuickSort）算法，并说明其平均时间复杂度和最坏情况时间复杂度。答案：快速排序是一种分治算法，核心思想是选择一个基准值（pivot），将数组分为两部分，使得左边的元素都小于基准值，右边的元素都大于基准值，然后递归地对左右两部分进行排序。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)解析：-平均时间复杂度：O(nlogn)，因为每次分区操作的时间复杂度为O(n)，分区次数为logn。-最坏情况时间复杂度：O(n²)，当基准值选择不均匀时（如已排序数组选择最左或最右为基准），会导致不平衡分区。2.题目：实现归并排序（MergeSort）算法，并解释其稳定性。答案：归并排序也是一种分治算法，将数组递归地分成两半，分别排序后再合并。pythondefmerge_sort(arr):iflen(arr)<=1:returnarrmid=len(arr)//2left=merge_sort(arr[:mid])right=merge_sort(arr[mid:])returnmerge(left,right)defmerge(left,right):result=[]i=j=0whilei<len(left)andj<len(right):ifleft[i]<=right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1result.extend(left[i:])result.extend(right[j:])returnresult解析：归并排序是稳定的排序算法，因为合并时相同元素的相对顺序不会改变。时间复杂度始终为O(nlogn)，适用于链表和外部排序场景。3.题目：给定一个数组，实现堆排序（HeapSort），并说明其时间复杂度。答案：堆排序利用堆（通常是最大堆）的性质进行排序，步骤包括构建最大堆、交换堆顶与末尾元素、调整堆。pythondefheap_sort(arr):defheapify(arr,n,i):largest=ileft=2i+1right=2i+2ifleft<nandarr[left]>arr[largest]:largest=leftifright<nandarr[right]>arr[largest]:largest=rightiflargest!=i:arr[i],arr[largest]=arr[largest],arr[i]heapify(arr,n,largest)n=len(arr)foriinrange(n//2-1,-1,-1):heapify(arr,n,i)foriinrange(n-1,0,-1):arr[i],arr[0]=arr[0],arr[i]heapify(arr,i,0)returnarr解析：堆排序的时间复杂度为O(nlogn)，因为构建堆的时间复杂度为O(n)，每次调整堆的时间复杂度为O(logn)，共n次。适用于内存受限场景。二、链表问题（3题，每题10分）1.题目：实现反转链表（ReverseLinkedList）函数。答案：使用迭代法或递归法反转链表。python迭代法defreverse_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：通过逐个节点反转next指针，最终prev成为新的头节点。时间复杂度O(n)，空间复杂度O(1)。2.题目：判断链表是否存在环（CycleDetection），并实现检测算法。答案：使用快慢指针（Floyd'sTortoiseandHare）算法。pythondefhas_cycle(head):slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:returnTruereturnFalse解析：快指针每次移动两步，慢指针每次移动一步，若存在环，快慢指针会相遇。时间复杂度O(n)，空间复杂度O(1)。3.题目：合并两个有序链表，返回合并后的头节点。答案：使用递归或迭代法合并。pythondefmerge_sorted_lists(l1,l2):ifnotl1:returnl2ifnotl2:returnl1ifl1.val<l2.val:l1.next=merge_sorted_lists(l1.next,l2)returnl1else:l2.next=merge_sorted_lists(l1,l2.next)returnl2解析：递归地比较两个链表头节点的值，选择较小的节点作为新链表的头，并递归处理剩余部分。时间复杂度O(n)，空间复杂度O(n)（递归栈）。三、栈与队列（2题，每题10分）1.题目：实现一个栈，支持在顶部插入和删除元素，并支持返回栈中最小元素的时间复杂度为O(1)。答案：使用辅助栈记录当前最小值。pythonclassMinStack:def__init__(self):self.stack=[]self.min_stack=[]defpush(self,x):self.stack.append(x)ifnotself.min_stackorx<=self.min_stack[-1]:self.min_stack.append(x)defpop(self):ifnotself.stack:returnNonetop=self.stack.pop()iftop==self.min_stack[-1]:self.min_stack.pop()returntopdefmin(self):ifnotself.min_stack:returnNonereturnself.min_stack[-1]解析：每次push时，若新元素小于等于当前最小值，则将其也push到min_stack；pop时若弹出元素等于当前最小值，则min_stack也pop。时间复杂度O(1)。2.题目：实现一个队列，支持在队首插入元素和在队尾删除元素。答案：使用两个栈实现队列。pythonclassQueueUsingStacks:def__init__(self):self.in_stack=[]self.out_stack=[]defenqueue(self,x):self.in_stack.append(x)defdequeue(self):ifnotself.out_stack:whileself.in_stack:self.out_stack.append(self.in_stack.pop())ifnotself.out_stack:returnNonereturnself.out_stack.pop()解析：enqueue时直接push到in_stack；dequeue时若out_stack为空，则将in_stack中的元素全部pop到out_stack，再从out_stackpop。时间复杂度O(1)（摊销）。四、树与二叉搜索树（2题，每题10分）1.题目：给定一个二叉树，实现中序遍历（In-orderTraversal）算法。答案：使用递归或迭代法。python递归法definorder_traversal(root):ifnotroot:return[]returninorder_traversal(root.left)+[root.val]+inorder_traversal(root.right)解析：中序遍历的顺序是左子树、根节点、右子树。递归法简单直观，时间复杂度O(n)，空间复杂度O(h)（h为树的高度）。2.题目：实现二叉搜索树（BST）的插入操作。答案：从根节点开始，递归地比较值，选择左子树或右子树插入。pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinsert_into_bst(root,val):ifnotroot:returnTreeNode(val)ifval<root.val:root.left=insert_into_bst(root.left,val)else:root.right=insert_into_bst(root.right,val)returnroot解析：BST的性质是左子树所有值小于根节点，右子树所有值大于根节点。插入时根据此性质递归查找位置。时间复杂度O(h)，最坏为O(n)。五、动态规划（2题，每题10分）1.题目：给定一个字符串，计算最长的回文子串（LongestPalindromicSubstring）的长度。答案：使用中心扩展法。pythondeflongest_palindrome(s):ifnots:return0start,end=0,0foriinrange(len(s)):len1=expand_from_center(s,i,i)len2=expand_from_center(s,i,i+1)max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returnend-start+1defexpand_from_center(s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1解析：遍历每个字符，分别以单个字符和两个字符为中心扩展，记录最大长度。时间复杂度O(n²)，空间复杂度O(1)。2.题目：给定一个数组，计算最长递增子序列（LongestIncreasingSubsequence,LIS）的长度。答案：使用动态规划+二分查找优化。pythondeflength_of_lis(nums):tails=[]fornuminnums:left,right=0,len(tails)whileleft<right:mid=(left+right)//2iftails[mid]<num:left=mid+1else:right=midifleft==len(tails):tails.append(num)else:tails[left]=numreturnlen(tails)解析：tails数组存储当前最长递增子序列的末尾元素。遍历时用二分查找tails中的位置，更新或替换元素。时间复杂度O(nlogn)，空间复杂度O(n)。六、贪心算法（2题，每题10分）1.题目：给定一个非负整数数组，每次可以选择一个元素减半（只能减偶数），求使数组元素之和最小的操作次数。答案：每次选择最大的偶数元素减半。pythondefhalve_array(nums):importheapqnums=[-xforxinnums]#最小堆heapq.heapify(nums)sum_before=sum(nums)count=0whilesum(nums)>sum_before/2:max_num=-heapq.heappop(nums)halved=max_num/2heapq.heappush(nums,-halved)sum_before-=halvedcount+=1returncount解析：贪心策略是每次减少最大的偶数元素，可以更快地减少总和。时间复杂度O(nlogn)，空间复杂度O(n)。2.题目：给定一个字符串，找到最长的无重复字符的子串（LongestSubstringWithoutRepeatingCharacters）的长度。答案：使用滑动窗口法。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解析：维护一个左指针和字符映射表，当遇到重复字符时，将左指针移动到重复字符的下一个位置。时间复杂度O(n)，空间复杂度O(1)。七、哈希表（2题，每题10分）1.题目：给定一个数组，找出其中和为特定值的三元组（ThreeSum）的数量。答案：排序后使用双指针法。pythondefthree_sum(nums,target):nums.sort()count=0n=len(nums)foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:current_sum=nums[i]+nums[left]+nums[right]ifcurrent_sum==target:count+=1whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1elifcurrent_sum<target:left+=1else:right-=1returncount解析：排序后，固定一个数，使用双指针在剩余部分查找和为target的另外两个数。时间复杂度O(n²)，空间复杂度O(1)。2.题目：判断一个字符串是否是另一个字符串的子串（不区分大小写，且允许字符重叠）。答案：使用哈希表记录字符频率，滑动窗口匹配。pythondefis_substring(s1,s2):s1,s2=s1.lower(),s2.lower()count_s2={}forcharins2