2026年携程技术部面试题及答案速查手册

2026年携程技术部面试题及答案速查手册一、编程基础（3题，每题10分）1.题目：请用Python实现一个函数，输入一个整数列表，返回其中所有奇数的平方和。要求时间复杂度为O(n)。2.题目：请用Java实现一个方法，输入一个字符串，返回该字符串中所有字符的唯一排列组合。例如，输入"abc"，返回["abc","acb","bac","bca","cab","cba"]。3.题目：请用C++实现一个算法，输入一个无序数组，原地排序并返回排序后的数组。要求使用快速排序算法，并说明其时间复杂度和空间复杂度。答案与解析1.Python实现奇数平方和pythondefsum_of_odd_squares(nums):returnsum(xxforxinnumsifx%2!=0)解析：-使用生成器表达式遍历列表，过滤奇数并计算平方，最后求和。-时间复杂度：O(n)，只需遍历一次列表。-空间复杂度：O(1)，额外空间不随输入规模变化。2.Java实现字符串排列组合javaimportjava.util.ArrayList;importjava.util.List;publicclassPermutations{publicstaticList<String>permute(Strings){List<String>res=newArrayList<>();if(s==null)returnres;char[]chars=s.toCharArray();backtrack(chars,0,res);returnres;}privatestaticvoidbacktrack(char[]chars,intindex,List<String>res){if(index==chars.length){res.add(newString(chars));return;}for(inti=index;i<chars.length;i++){swap(chars,i,index);backtrack(chars,index+1,res);swap(chars,i,index);}}privatestaticvoidswap(char[]chars,inti,intj){chartemp=chars[i];chars[i]=chars[j];chars[j]=temp;}}解析：-使用回溯算法生成所有排列，通过交换字符位置实现。-时间复杂度：O(n!)，n为字符串长度。-空间复杂度：O(n!+n)，存储所有排列和递归栈。3.C++实现快速排序cppinclude<vector>include<algorithm>voidquickSort(std::vector<int>&arr,intleft,intright){if(left>=right)return;intpivot=arr[left+(right-left)/2];inti=left,j=right;while(i<=j){while(arr[i]<pivot)i++;while(arr[j]>pivot)j--;if(i<=j){std::swap(arr[i],arr[j]);i++,j--;}}quickSort(arr,left,j);quickSort(arr,i,right);}解析：-快速排序采用分治策略，选择pivot（中间值）分割数组。-时间复杂度：平均O(nlogn)，最坏O(n^2)。-空间复杂度：O(logn)，递归栈深度。二、数据结构与算法（5题，每题10分）1.题目：请解释什么是二叉搜索树（BST），并给出一个递归方法判断一棵二叉树是否为BST。2.题目：请实现一个LRU（最近最少使用）缓存，要求支持get和put操作，时间复杂度为O(1)。3.题目：请用动态规划算法计算斐波那契数列的第n项，要求时间复杂度为O(n)。4.题目：请解释什么是图的拓扑排序，并给出一个基于DFS的实现方法。5.题目：请用贪心算法解决“活动选择问题”，输入活动列表（按结束时间排序），返回最优活动集合。答案与解析1.二叉搜索树与判断pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_bst(root):defhelper(node,lower,upper):ifnotnode:returnTrueifnot(lower<node.val<upper):returnFalsereturnhelper(node.left,lower,node.val)andhelper(node.right,node.val,upper)returnhelper(root,float('-inf'),float('inf'))解析：-BST性质：左子树所有值<根<右子树所有值。-递归验证每个节点是否在合法范围内。2.LRU缓存实现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:self.cache.pop(self.order.pop(0))self.cache[key]=valueself.order.append(key)解析：-使用哈希表记录缓存，链表维护使用顺序。-get时移动到链表末尾，put时淘汰最久未使用项。3.动态规划斐波那契数列pythondeffib(n):ifn<=1:returnndp=[0](n+1)dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]解析：-状态转移：f(n)=f(n-1)+f(n-2)。-时间复杂度：O(n)，空间复杂度：O(n)。4.图的拓扑排序pythondeftopological_sort(num_nodes,edges):in_degree=[0]num_nodesgraph=[[]for_inrange(num_nodes)]foru,vinedges:graph[u].append(v)in_degree[v]+=1queue=[iforiinrange(num_nodes)ifin_degree[i]==0]res=[]whilequeue:node=queue.pop(0)res.append(node)forneighboringraph[node]:in_degree[neighbor]-=1ifin_degree[neighbor]==0:queue.append(neighbor)returnresiflen(res)==num_nodeselse[]解析：-拓扑排序用于有向无环图（DAG），按依赖顺序排列。-使用Kahn算法，优先处理入度为0的节点。5.活动选择问题pythondefactivity_selection(start,finish):n=len(start)activities=sorted(zip(start,finish),key=lambdax:x[1])res=[]last_end=0fors,finactivities:ifs>=last_end:res.append((s,f))last_end=freturnres解析：-贪心策略：按结束时间排序，选择不冲突的活动。-时间复杂度：O(nlogn)，排序占主导。三、系统设计（2题，每题20分）1.题目：设计一个高并发的短链接生成系统，要求支持实时生成和解析短链接，并保证唯一性。2.题目：设计一个分布式限流系统，要求支持全局限流，并兼容本地缓存优化。答案与解析1.短链接生成系统text方案：1.使用哈希函数（如CRC32）将长链接映射为固定长度的短ID（如6位数字）。2.使用Redis或ZooKeeper保证ID全局唯一。3.链接存储：短ID+长链接（数据库或缓存）。4.解析时，短ID查缓存，缓存未命中则查数据库。解析：-哈希冲突概率低，Redis可保证ID唯一。-缓存分层