2026年携程软件开发工程师面试题目全解

2026年携程软件开发工程师面试题目全解一、编程基础（5题，共30分）1.题目（6分）：请实现一个函数，输入一个字符串，返回该字符串中所有唯一字符的集合。例如，输入`"leetcode"`，返回`{'l','e','t','c','d'}`。要求时间复杂度为O(n)，空间复杂度为O(1)（假设字符集为ASCII码）。答案与解析：pythondefunique_chars(s:str)->set:ifnots:returnset()char_set=set()forcins:ifcinchar_set:char_set.discard(c)else:char_set.add(c)returnchar_set示例print(unique_chars("leetcode"))#输出：{'l','e','t','c','d'}解析：-使用集合`char_set`记录遍历过程中遇到的唯一字符。-如果字符已存在于集合中，则删除（表示重复）；否则添加（表示唯一）。-最终集合中保留的即为唯一字符。-时间复杂度：O(n)，每个字符遍历一次；空间复杂度：O(1)，字符集固定为ASCII码（128个字符），集合大小上限为128。2.题目（6分）：给定一个链表，删除链表中的倒数第n个节点，并返回新的链表头。例如，输入链表`1->2->3->4->5`和`n=2`，返回`1->2->3->5`。答案与解析：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefremove_nth_from_end(head:ListNode,n:int)->ListNode:dummy=ListNode(0,head)fast=slow=dummyfor_inrange(n+1):fast=fast.nextwhilefast:slow=slow.nextfast=fast.nextslow.next=slow.next.nextreturndummy.next示例构建链表1->2->3->4->5head=ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))删除倒数第2个节点new_head=remove_nth_from_end(head,2)输出：1->2->3->5解析：-使用双指针法，`fast`先向前移动n+1步，确保与`slow`的间距为n。-然后同时移动`fast`和`slow`，当`fast`到达末尾时，`slow`指向待删除节点的前一个节点。-删除操作通过`slow.next=slow.next.next`实现。-时间复杂度：O(n)，空间复杂度：O(1)。3.题目（6分）：实现一个LRU（LeastRecentlyUsed）缓存，支持`get`和`put`操作。缓存容量为`capacity`，当访问或插入导致缓存容量超过限制时，删除最久未使用的缓存项。答案与解析：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):ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest_key=self.order.pop(0)delself.cache[oldest_key]self.cache[key]=valueself.order.append(key)示例cache=LRUCache(2)cache.put(1,1)cache.put(2,2)print(cache.get(1))#返回1cache.put(3,3)#去除键2print(cache.get(2))#返回-1解析：-使用字典`cache`存储键值对，列表`order`记录访问顺序。-`get`操作：若键存在，则将其移至`order`末尾（表示最近使用）；否则返回-1。-`put`操作：若键存在，更新值并调整顺序；若不存在且容量已满，删除最久未使用（`order`第一个元素）的键值对，然后插入新键值对。-时间复杂度：O(1)，使用列表实现顺序调整（实际可用双向链表优化）。4.题目（6分）：给定一个无重复元素的数组`nums`，返回所有可能的子集。例如，输入`[1,2,3]`，返回`[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]`。答案与解析：pythondefsubsets(nums:list)->list:result=[]nums.sort()#保证顺序一致defbacktrack(start,path):result.append(path.copy())foriinrange(start,len(nums)):path.append(nums[i])backtrack(i+1,path)path.pop()backtrack(0,[])returnresult示例print(subsets([1,2,3]))解析：-使用回溯算法，`start`表示当前可选的起始索引，`path`记录当前子集。-每次固定一个元素，递归生成所有包含该元素的子集。-时间复杂度：O(2^n)，空间复杂度：O(n)（递归栈深度）。5.题目（12分）：实现一个函数，判断一个二叉树是否为平衡二叉树（左右子树高度差不超过1，且左右子树均为平衡二叉树）。要求不使用递归，使用迭代方法。答案与解析：pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_balanced(root:TreeNode)->bool:ifnotroot:returnTruestack=deque([(root,0)])max_height=-float('inf')whilestack:node,height=stack.pop()ifabs(height)>1:returnFalseifnode.left:stack.append((node.left,height+1))ifnode.right:stack.append((node.right,height+1))max_height=max(max_height,height)returnTrue示例构建平衡树1->2->3root=TreeNode(1,TreeNode(2,TreeNode(3)),TreeNode(3))print(is_balanced(root))#输出：True解析：-使用迭代法（后序遍历变体），利用栈记录节点及其高度。-判断当前节点高度差是否超过1，若超过则返回False。-同时更新全局最大高度（用于辅助判断）。-时间复杂度：O(n)，空间复杂度：O(n)。-可优化为O(n)空间，使用双端队列实现后序遍历，避免使用递归栈。二、系统设计（3题，共30分）1.题目（10分）：设计一个短链接系统，要求：-输入长链接，输出固定长度的短链接（如6位随机字母数字组合）。-支持通过短链接查询原始长链接。-高并发场景下，查询响应时间需控制在200ms内。答案与解析：方案：1.短链接生成：-使用62进制（a-z,A-Z,0-9）将长链接ID映射为6位短码（62^6≈56亿组合）。-使用哈希算法（如SHA256）对长链接加盐后取前6位作为ID，避免冲突。pythonimporthashlibimportstringdefencode_url(long_url:str)->str:salt="cortana_"#业务盐hash_obj=hashlib.sha256((long_url+salt).encode()).hexdigest()short_id=hash_obj[:6]returnshort_id2.存储：-使用Redis（哈希表实现，支持快速查找）存储`short_id:long_url`映射。-若短链接已存在，则重新生成（概率极低）。pythonimportredisr=redis.Redis(host="localhost",port=6379)defsave_mapping(short_id:str,long_url:str):r.hset("url_map",short_id,long_url)3.高并发优化：-Redis设置高可用集群，主从复制+哨兵机制。-读取时使用本地缓存（如本地内存），减少Redis访问。解析：-哈希冲突概率极低（62^6组合），实际可用。-RedisTPS可达10万+，满足200ms内响应。-可扩展性：若短链接量超限，可增加Redis分片。2.题目（10分）：设计一个实时航班动态推送系统，要求：-支持百万级航班同时接入，推送包括延误、登机口变更等实时信息。-推送延迟需控制在100ms内，可用性≥99.9%。答案与解析：方案：1.数据采集：-航班API（如IATA）定时拉取数据，或使用消息队列（Kafka）接收机场实时推送。pythonfromkafkaimportKafkaConsumerconsumer=KafkaConsumer("flights_topic",bootstrap_servers=["localhost:9092"])formsginconsumer:flight_data=msg.valueprocess_flight_data(flight_data)2.数据处理：-使用Redis订阅模式（Pub/Sub）广播更新。pythondefprocess_flight_data(flight_data):r.publish("flight_updates",flight_data)3.客户端订阅：-客户端通过WebSocket连接Redis，实时接收更新。javascriptconstredis=require('redis');constclient=redis.createClient();client.subscribe("flight_updates",function(){client.on("message",function(channel,message){console.log("Newupdate:",message);});});4.延迟优化：-RedisCluster保证低延迟。-WebSocket协议支持全双工通信，无延迟。解析：-Kafka+Redis架构可支撑百万级并发，RedisPub/Sub延迟低。-WebSocket确保客户端实时接收。-可用性：Redis主从+异地多活部署。3.题目（10分）：设计一个高并发抢购系统，要求：-支持千万级用户同时抢购，库存秒杀场景下无超卖。-请求响应时间控制在100ms内，系统可用性≥99.9%。答案与解析：方案：1.库存预减：-用户发起请求时，先在Redis中减库存（原子操作`DECR`）。pythondeftry_purchase(user_id,item_id,stock):current_stock=r.get(f"stock:{item_id}")ifint(current_stock)>0:r.decr(f"stock:{item_id}")执行支付等后续操作returnTruereturnFalse2.分布式锁：-若`DECR`为0，则使用Redis锁（Lua脚本保证原子性）。lualocalstock_key=KEYS[1]localuser_key=KEYS[2]localstock=tonumber(redis.call("get",stock_key))ifstock>0thenredis.call("set",user_key,"locked",nx,10)--10s锁redis.call("decr",stock_key)return1endreturn03.消息队列补偿：-使用RabbitMQ记录失败请求，定时重试（避免超卖）。pythondefretry_failed_purchase(failed_queue):whileTrue:msg=failed_queue.get()ifmsg:user_id,item_id=msg重新尝试购买4.限流降级：-Nginx或APIGateway限流，超过阈值返回排队中。-熔断机制：若API延迟超200ms，降级为静态页面。解析：-Redis原子操作确保库存一致性。-Lua脚本保证锁的原子性。-消息队列处理失败请求，防止超卖。三、数据库（2题，共20分）1.题目（10分）：设计一个机票预订系统的数据库表结构，要求：-支持查询用户已预订的航班（含乘客信息）。-支持按航班日期、价格排序查询。-性能要求：查询响应时间<200ms。答案与解析：表结构：sqlCREATETABLEbookings(booking_idBIGINTAUTO_INCREMENTPRIMARYKEY,user_idBIGINT,flight_idBIGINT,passenger_nameVARCHAR(100),passenger_idVARCHAR(20),booking_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(user_id)REFERENCESusers(user_id),FOREIGNKEY(flight_id)REFERENCESflights(flight_id));CREATETABLEflights(flight_idBIGINTAUTO_INCREMENTPRIMARYKEY,airlineVARCHAR(50),departureVARCHAR(100),arrivalVARCHAR(100),departure_timeTIMESTAMP,arrival_timeTIMESTAMP,priceDECIMAL(10,2),capacityINT,INDEXidx_date_price(departure_time,price));查询优化：-使用复合索引`idx_date_price`，覆盖排序和查询场景。-分区表：按`departure_time`分区，提高范围查询效率。-缓存：将热门查询结果存入Redis，减少DB访问。解析：-索引设计满足排序需求。-分区表适用于高并发场景。-Redis缓存提升热点数据查询性能。2.题目（10分）：数据库主从复制出现延迟，如何保证数据一致性？列举至少3种方案。答案与解析：1.延迟检测：-监控工具（如Prometheus+Grafana）实时检测主从延迟（`SecondsBehindMaster`），超阈值告警。shell查看延迟mysql-uroot-p-e"SHOWSLAVESTATUS;"2.强一致性方案：-事务消息+Redis最终一致性。-将事务操作序列化到Redis，主从均消费后返回。java//SpringJMS实现@TransactionalpublicvoidhandleBooking(){redisTemplate.opsForValue().set("tx",bookingData);//确认消费}3.异步补偿：-使用消息队列（Kafka）记录失败操作，定时重试。pythondefretry_consistency(failed_topic):whileTrue:msg=kafka_consumer.get()ifmsg:retry_operation(msg)解析：-监控及时发现延迟。-事务消息保证强一致性。-消息队列处理异步场景。四、分布式与中间件（2题，共20分）1.题目（10分）：设计一个分布式计数器系统，要求：-支持高并发更新，如秒杀场景下的点击量统计。-支持分区域统计（如华东、华南）。-分布式环境下无数据丢失。答案与解析：方案：1.Redis原子操作：-使用`INCR`实现原子计数。pythondefincrement_counter(region,key):r.incr(f"counter:{region}:{key}")2.分区域存储：-键名设计为`counter:region:key`，如`counter:华东:clicks`。-范围查询：`SCAN`命令分批获取。3.持久化保障：-RedisAOF或RDB备份，防止数据丢失。confRedis配置appendonlyyesappendfsynceverysec解析：-Redis原子操作保证并发安全。-分区域设计支持横向扩展。-AOF确保数据持久化。2.题目（10分）：为什么Kafka比RabbitMQ更适合做日志收集？列举至少3点。答案与解析：1.吞吐量：-Kafka单个分区吞吐量可达百万级，RabbitMQ为万级。bashKafka压测kafka-producer-perf-test.sh--topiclogs--num-messages10000000--throughput1000002.数据持久化：-Kafka支持磁盘持久，RabbitMQ仅内存（需配置磁盘）。confRabbitMQ启用磁盘rabbitmq.confdisk_queue_limits.enabled=true3.消费者模型：-Kafka支持消费者组（多副本消费），日志聚合效率高。xml<!--Kafka消费者组配置--><propertyname="group.id"value="log_group"/>解析：-吞吐量优势明显。-Kafka更适合高吞吐日志场景。五、网络与安全（2题，共20分）1.题目（10分）：携程APP需要支持弱网环境下的数据同步，如何设计？答案与解析：方案：1.增量同步：-使用WebSocket长连接推送增量数据（如订单状态变更）。javascript//客户端WebSocketconstws=newWebSocket("wss:///sync");ws.onmessage=function(event){updateLocalData(JSON.parse(event.dat