2026年攜程軟件開發(fā)工程師面試題目全解一、編程基礎(chǔ)（5題，共30分）1.題目（6分）：請實(shí)現(xiàn)一個(gè)函數(shù)，輸入一個(gè)字符串，返回該字符串中所有唯一字符的集合。例如，輸入`"leetcode"`，返回`{'l','e','t','c','d'}`。要求時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)（假設(shè)字符集為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`記錄遍歷過程中遇到的唯一字符。-如果字符已存在于集合中，則刪除（表示重復(fù)）；否則添加（表示唯一）。-最終集合中保留的即為唯一字符。-時(shí)間復(fù)雜度：O(n)，每個(gè)字符遍歷一次；空間復(fù)雜度：O(1)，字符集固定為ASCII碼（128個(gè)字符），集合大小上限為128。2.題目（6分）：給定一個(gè)鏈表，刪除鏈表中的倒數(shù)第n個(gè)節(jié)點(diǎ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示例構(gòu)建鏈表1->2->3->4->5head=ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))刪除倒數(shù)第2個(gè)節(jié)點(diǎn)new_head=remove_nth_from_end(head,2)輸出：1->2->3->5解析：-使用雙指針法，`fast`先向前移動(dòng)n+1步，確保與`slow`的間距為n。-然后同時(shí)移動(dòng)`fast`和`slow`，當(dāng)`fast`到達(dá)末尾時(shí)，`slow`指向待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。-刪除操作通過`slow.next=slow.next.next`實(shí)現(xiàn)。-時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(1)。3.題目（6分）：實(shí)現(xiàn)一個(gè)LRU（LeastRecentlyUsed）緩存，支持`get`和`put`操作。緩存容量為`capacity`，當(dāng)訪問或插入導(dǎo)致緩存容量超過限制時(shí)，刪除最久未使用的緩存項(xiàng)。答案與解析：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`操作：若鍵存在，更新值并調(diào)整順序；若不存在且容量已滿，刪除最久未使用（`order`第一個(gè)元素）的鍵值對，然后插入新鍵值對。-時(shí)間復(fù)雜度：O(1)，使用列表實(shí)現(xiàn)順序調(diào)整（實(shí)際可用雙向鏈表優(yōu)化）。4.題目（6分）：給定一個(gè)無重復(fù)元素的數(shù)組`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`表示當(dāng)前可選的起始索引，`path`記錄當(dāng)前子集。-每次固定一個(gè)元素，遞歸生成所有包含該元素的子集。-時(shí)間復(fù)雜度：O(2^n)，空間復(fù)雜度：O(n)（遞歸棧深度）。5.題目（12分）：實(shí)現(xiàn)一個(gè)函數(shù)，判斷一個(gè)二叉樹是否為平衡二叉樹（左右子樹高度差不超過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示例構(gòu)建平衡樹1->2->3root=TreeNode(1,TreeNode(2,TreeNode(3)),TreeNode(3))print(is_balanced(root))#輸出：True解析：-使用迭代法（后序遍歷變體），利用棧記錄節(jié)點(diǎn)及其高度。-判斷當(dāng)前節(jié)點(diǎn)高度差是否超過1，若超過則返回False。-同時(shí)更新全局最大高度（用于輔助判斷）。-時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(n)。-可優(yōu)化為O(n)空間，使用雙端隊(duì)列實(shí)現(xiàn)后序遍歷，避免使用遞歸棧。二、系統(tǒng)設(shè)計(jì)（3題，共30分）1.題目（10分）：設(shè)計(jì)一個(gè)短鏈接系統(tǒng)，要求：-輸入長鏈接，輸出固定長度的短鏈接（如6位隨機(jī)字母數(shù)字組合）。-支持通過短鏈接查詢原始長鏈接。-高并發(fā)場景下，查詢響應(yīng)時(shí)間需控制在200ms內(nèi)。答案與解析：方案：1.短鏈接生成：-使用62進(jìn)制（a-z,A-Z,0-9）將長鏈接ID映射為6位短碼（62^6≈56億組合）。-使用哈希算法（如SHA256）對長鏈接加鹽后取前6位作為ID，避免沖突。pythonimporthashlibimportstringdefencode_url(long_url:str)->str:salt="cortana_"#業(yè)務(wù)鹽hash_obj=hashlib.sha256((long_url+salt).encode()).hexdigest()short_id=hash_obj[:6]returnshort_id2.存儲：-使用Redis（哈希表實(shí)現(xiàn)，支持快速查找）存儲`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.高并發(fā)優(yōu)化：-Redis設(shè)置高可用集群，主從復(fù)制+哨兵機(jī)制。-讀取時(shí)使用本地緩存（如本地內(nèi)存），減少Redis訪問。解析：-哈希沖突概率極低（62^6組合），實(shí)際可用。-RedisTPS可達(dá)10萬+，滿足200ms內(nèi)響應(yīng)。-可擴(kuò)展性：若短鏈接量超限，可增加Redis分片。2.題目（10分）：設(shè)計(jì)一個(gè)實(shí)時(shí)航班動(dòng)態(tài)推送系統(tǒng)，要求：-支持百萬級航班同時(shí)接入，推送包括延誤、登機(jī)口變更等實(shí)時(shí)信息。-推送延遲需控制在100ms內(nèi)，可用性≥99.9%。答案與解析：方案：1.數(shù)據(jù)采集：-航班API（如IATA）定時(shí)拉取數(shù)據(jù)，或使用消息隊(duì)列（Kafka）接收機(jī)場實(shí)時(shí)推送。pythonfromkafkaimportKafkaConsumerconsumer=KafkaConsumer("flights_topic",bootstrap_servers=["localhost:9092"])formsginconsumer:flight_data=msg.valueprocess_flight_data(flight_data)2.數(shù)據(jù)處理：-使用Redis訂閱模式（Pub/Sub）廣播更新。pythondefprocess_flight_data(flight_data):r.publish("flight_updates",flight_data)3.客戶端訂閱：-客戶端通過WebSocket連接Redis，實(shí)時(shí)接收更新。javascriptconstredis=require('redis');constclient=redis.createClient();client.subscribe("flight_updates",function(){client.on("message",function(channel,message){console.log("Newupdate:",message);});});4.延遲優(yōu)化：-RedisCluster保證低延遲。-WebSocket協(xié)議支持全雙工通信，無延遲。解析：-Kafka+Redis架構(gòu)可支撐百萬級并發(fā)，RedisPub/Sub延遲低。-WebSocket確保客戶端實(shí)時(shí)接收。-可用性：Redis主從+異地多活部署。3.題目（10分）：設(shè)計(jì)一個(gè)高并發(fā)搶購系統(tǒng)，要求：-支持千萬級用戶同時(shí)搶購，庫存秒殺場景下無超賣。-請求響應(yīng)時(shí)間控制在100ms內(nèi)，系統(tǒng)可用性≥99.9%。答案與解析：方案：1.庫存預(yù)減：-用戶發(fā)起請求時(shí)，先在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}")執(zhí)行支付等后續(xù)操作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.消息隊(duì)列補(bǔ)償：-使用RabbitMQ記錄失敗請求，定時(shí)重試（避免超賣）。pythondefretry_failed_purchase(failed_queue):whileTrue:msg=failed_queue.get()ifmsg:user_id,item_id=msg重新嘗試購買4.限流降級：-Nginx或APIGateway限流，超過閾值返回排隊(duì)中。-熔斷機(jī)制：若API延遲超200ms，降級為靜態(tài)頁面。解析：-Redis原子操作確保庫存一致性。-Lua腳本保證鎖的原子性。-消息隊(duì)列處理失敗請求，防止超賣。三、數(shù)據(jù)庫（2題，共20分）1.題目（10分）：設(shè)計(jì)一個(gè)機(jī)票預(yù)訂系統(tǒng)的數(shù)據(jù)庫表結(jié)構(gòu)，要求：-支持查詢用戶已預(yù)訂的航班（含乘客信息）。-支持按航班日期、價(jià)格排序查詢。-性能要求：查詢響應(yīng)時(shí)間<200ms。答案與解析：表結(jié)構(gòu)：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));查詢優(yōu)化：-使用復(fù)合索引`idx_date_price`，覆蓋排序和查詢場景。-分區(qū)表：按`departure_time`分區(qū)，提高范圍查詢效率。-緩存：將熱門查詢結(jié)果存入Redis，減少DB訪問。解析：-索引設(shè)計(jì)滿足排序需求。-分區(qū)表適用于高并發(fā)場景。-Redis緩存提升熱點(diǎn)數(shù)據(jù)查詢性能。2.題目（10分）：數(shù)據(jù)庫主從復(fù)制出現(xiàn)延遲，如何保證數(shù)據(jù)一致性？列舉至少3種方案。答案與解析：1.延遲檢測：-監(jiān)控工具（如Prometheus+Grafana）實(shí)時(shí)檢測主從延遲（`SecondsBehindMaster`），超閾值告警。shell查看延遲mysql-uroot-p-e"SHOWSLAVESTATUS;"2.強(qiáng)一致性方案：-事務(wù)消息+Redis最終一致性。-將事務(wù)操作序列化到Redis，主從均消費(fèi)后返回。java//SpringJMS實(shí)現(xiàn)@TransactionalpublicvoidhandleBooking(){redisTemplate.opsForValue().set("tx",bookingData);//確認(rèn)消費(fèi)}3.異步補(bǔ)償：-使用消息隊(duì)列（Kafka）記錄失敗操作，定時(shí)重試。pythondefretry_consistency(failed_topic):whileTrue:msg=kafka_consumer.get()ifmsg:retry_operation(msg)解析：-監(jiān)控及時(shí)發(fā)現(xiàn)延遲。-事務(wù)消息保證強(qiáng)一致性。-消息隊(duì)列處理異步場景。四、分布式與中間件（2題，共20分）1.題目（10分）：設(shè)計(jì)一個(gè)分布式計(jì)數(shù)器系統(tǒng)，要求：-支持高并發(fā)更新，如秒殺場景下的點(diǎn)擊量統(tǒng)計(jì)。-支持分區(qū)域統(tǒng)計(jì)（如華東、華南）。-分布式環(huán)境下無數(shù)據(jù)丟失。答案與解析：方案：1.Redis原子操作：-使用`INCR`實(shí)現(xiàn)原子計(jì)數(shù)。pythondefincrement_counter(region,key):r.incr(f"counter:{region}:{key}")2.分區(qū)域存儲：-鍵名設(shè)計(jì)為`counter:region:key`，如`counter:華東:clicks`。-范圍查詢：`SCAN`命令分批獲取。3.持久化保障：-RedisAOF或RDB備份，防止數(shù)據(jù)丟失。confRedis配置appendonlyyesappendfsynceverysec解析：-Redis原子操作保證并發(fā)安全。-分區(qū)域設(shè)計(jì)支持橫向擴(kuò)展。-AOF確保數(shù)據(jù)持久化。2.題目（10分）：為什么Kafka比RabbitMQ更適合做日志收集？列舉至少3點(diǎn)。答案與解析：1.吞吐量：-Kafka單個(gè)分區(qū)吞吐量可達(dá)百萬級，RabbitMQ為萬級。bashKafka壓測kafka-producer-perf-test.sh--topiclogs--num-messages10000000--throughput1000002.數(shù)據(jù)持久化：-Kafka支持磁盤持久，RabbitMQ僅內(nèi)存（需配置磁盤）。confRabbitMQ啟用磁盤rabbitmq.confdisk_queue_limits.enabled=true3.消費(fèi)者模型：-Kafka支持消費(fèi)者組（多副本消費(fèi)），日志聚合效率高。xml<!--Kafka消費(fèi)者組配置--><propertyname="group.id"value="log_group"/>解析：-吞吐量優(yōu)勢明顯。-Kafka更適合高吞吐日志場景。五、網(wǎng)絡(luò)與安全（2題，共20分）1.題目（10分）：攜程APP需要支持弱網(wǎng)環(huán)境下的數(shù)據(jù)同步，如何設(shè)計(jì)？答案與解析：方案：1.增量同步：-使用WebSocket長連接推送增量數(shù)據(jù)（如訂單狀態(tài)變更）。javascript//客戶端WebSocketconstws=newWebSocket("wss:///sync");ws.onmessage=function(event){updateLocalData(JSON.parse(event.dat