2026年程序员技术面试手册编程与算法考题集

2026年程序员技术面试手册：编程与算法考题集一、编程基础（5题，每题10分）1.数组操作（10分）题目：给定一个无序数组`arr`，不使用额外的存储空间，原地调整数组使所有偶数位于数组前半部分，所有奇数位于数组后半部分。例如，输入`[1,2,3,4,5]`，输出`[2,4,1,3,5]`。2.字符串处理（10分）题目：实现一个函数`reverseWords(s)`，将输入字符串`s`中的单词顺序反转，但每个单词内部的字母顺序保持不变。例如，输入`"helloworld"`，输出`"worldhello"`。3.基础数据结构（10分）题目：用代码实现一个栈（Stack）数据结构，支持`push`、`pop`和`peek`操作。要求不使用任何现成的库（如`collections.deque`）。4.算法复杂度分析（10分）题目：给定以下代码片段，分析其时间复杂度：pythondeffun(n):foriinrange(n):forjinrange(n):print(i,j)5.递归与迭代（10分）题目：用递归和迭代两种方式实现斐波那契数列的第`n`项计算（`n>=0`）。二、算法设计（5题，每题15分）1.排序算法（15分）题目：实现快速排序（QuickSort）算法，要求在平均时间复杂度为`O(nlogn)`的情况下对数组进行排序。2.搜索算法（15分）题目：给定一个二维矩阵`matrix`，其中每行每列都按升序排列。实现一个函数`searchMatrix(matrix,target)`，判断`target`是否存在于矩阵中。3.图算法（15分）题目：给定一个无向图，用邻接矩阵表示。实现深度优先搜索（DFS）算法，输出从指定起点出发的遍历顺序。4.动态规划（15分）题目：给定一个字符串`s`，计算其最长回文子串的长度。例如，输入`"babad"`，输出`3`（"bab"或"aba"）。5.堆与优先队列（15分）题目：用最小堆实现一个优先队列，支持`push`和`pop`操作，要求时间复杂度分别为`O(logn)`和`O(1)`。三、编程进阶（5题，每题20分）1.高频面试题：链表操作（20分）题目：给定一个单链表`head`，判断链表中是否存在环。如果存在，返回环的入口节点；否则返回`None`。2.系统设计：缓存算法（20分）题目：设计一个LRU（LeastRecentlyUsed）缓存系统，支持`get`和`put`操作。要求`get`操作的时间复杂度为`O(1)`，`put`操作的时间复杂度为`O(1)`。3.并发编程：线程安全（20分）题目：用Python实现一个线程安全的计数器，要求多个线程可以同时调用`increment`方法。4.数据结构：二叉树（20分）题目：给定一个二叉树，实现它的中序遍历（InorderTraversal），要求使用迭代方式而非递归。5.算法应用：字符串匹配（20分）题目：实现KMP（Knuth-Morris-Pratt）字符串匹配算法，要求预处理模式串并计算部分匹配表。答案与解析一、编程基础1.数组操作（10分）答案：pythondefrearrange(arr):left,right=0,len(arr)-1whileleft<right:whileleft<rightandarr[left]%2==0:left+=1whileleft<rightandarr[right]%2!=0:right-=1arr[left],arr[right]=arr[right],arr[left]returnarr解析：双指针法，`left`从左向右移动，`right`从右向左移动，交换不满足条件的元素，直到`left>=right`。2.字符串处理（10分）答案：pythondefreverseWords(s):words=s.split()return''.join(words[::-1])解析：先按空格分割字符串，反转单词顺序，再拼接为结果。3.基础数据结构（10分）答案：pythonclassStack:def__init__(self):self.items=[]defpush(self,item):self.items.append(item)defpop(self):returnself.items.pop()ifself.itemselseNonedefpeek(self):returnself.items[-1]ifself.itemselseNone解析：使用列表实现栈，`push`添加元素，`pop`删除最后一个元素，`peek`查看最后一个元素。4.算法复杂度分析（10分）答案：时间复杂度为`O(n^2)`，因为有两层嵌套循环，每次循环执行`n`次。5.递归与迭代（10分）答案：-递归：pythondeffib_recursive(n):ifn<=1:returnnreturnfib_recursive(n-1)+fib_recursive(n-2)-迭代：pythondeffib_iterative(n):a,b=0,1for_inrange(n):a,b=b,a+breturna解析：递归方式效率低（时间复杂度`O(2^n)`），迭代方式效率高（时间复杂度`O(n)`）。二、算法设计1.排序算法（15分）答案：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)解析：快速排序核心是分治思想，选择枢轴（pivot）并分区，递归排序左右子数组。2.搜索算法（15分）答案：pythondefsearchMatrix(matrix,target):ifnotmatrixornotmatrix[0]:returnFalserows,cols=len(matrix),len(matrix[0])row,col=0,cols-1whilerow<rowsandcol>=0:ifmatrix[row][col]==target:returnTrueelifmatrix[row][col]>target:col-=1else:row+=1returnFalse解析：从右上角开始搜索，向左或向下移动，时间复杂度`O(m+n)`。3.图算法（15分）答案：pythondefdfs(matrix,start,visited):stack=[start]result=[]whilestack:node=stack.pop()ifnotvisited[node]:visited[node]=Trueresult.append(node)forneighborinreversed(matrix[node]):ifnotvisited[neighbor]:stack.append(neighbor)returnresult解析：使用栈实现DFS，记录已访问节点避免重复。4.动态规划（15分）答案：pythondeflongestPalindrome(s):n=len(s)dp=[[False]nfor_inrange(n)]max_len=1start=0foriinrange(n):dp[i][i]=Trueforiinrange(n-1):ifs[i]==s[i+1]:dp[i][i+1]=Truemax_len=2start=iforlengthinrange(3,n+1):foriinrange(n-length+1):j=i+length-1ifs[i]==s[j]anddp[i+1][j-1]:dp[i][j]=Truemax_len=lengthstart=ireturnmax_len解析：动态规划枚举所有子串，`dp[i][j]`表示`s[i:j+1]`是否为回文。5.堆与优先队列（15分）答案：pythonimportheapqclassPriorityQueue:def__init__(self):self.heap=[]defpush(self,item):heapq.heappush(self.heap,item)defpop(self):returnheapq.heappop(self.heap)解析：使用`heapq`实现最小堆，`push`和`pop`操作均满足时间复杂度要求。三、编程进阶1.高频面试题：链表操作（20分）答案：pythondefdetectCycle(head):ifnothead:returnNoneslow,fast=head,headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone解析：快慢指针检测环，相遇后重新移动直到再次相遇，相遇点为环入口。2.系统设计：缓存算法（20分）答案：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.order=[]defget(self,key):ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key,value):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)解析：使用哈希表记录缓存，双向链表维护访问顺序。3.并发编程：线程安全（20分）答案：pythonimportthreadingclassThreadSafeCounter:def__init__(self):self.value=0self.lock=threading.Lock()defincrement(self):withself.lock:self.value+=1解析：使用`threading.Lock`保证`increment`操作的原子性。4.数据结构：二叉树（20分）答案：pythondefinorderTraversal(root):stack,result=[],[]current=rootwhilestackorcurrent:whilecurrent:stack.append(current)current=current.leftcurrent=stack.pop()result.append(current.val)current=current.rightreturnresult解析：迭代中序遍历使用栈，模拟递归过程。5.算法应用：字符串匹配（20分）答案：pythondefkmp_search(text,pattern):defcomputeLPS(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=