2026年攜程軟件開(kāi)發(fā)工程師面試題集一、編程基礎(chǔ)（共5題，每題10分，總分50分）1.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，輸入一個(gè)正整數(shù)n，返回其二進(jìn)制表示中1的個(gè)數(shù)。例如，輸入5，返回2，因?yàn)?的二進(jìn)制表示為101。2.題目：給定一個(gè)鏈表，請(qǐng)實(shí)現(xiàn)反轉(zhuǎn)鏈表的功能。要求原地反轉(zhuǎn)，不使用額外空間。3.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，判斷一個(gè)字符串是否為有效的括號(hào)組合。例如，輸入"()"返回true，輸入"()[]{}"返回true，輸入"(]"返回false。4.題目：請(qǐng)實(shí)現(xiàn)快速排序算法，并對(duì)時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行分析。5.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，找出數(shù)組中重復(fù)次數(shù)超過(guò)一半的元素。例如，輸入[2,2,1,1,1,2,2]，返回2。二、數(shù)據(jù)結(jié)構(gòu)與算法（共5題，每題10分，總分50分）1.題目：請(qǐng)實(shí)現(xiàn)一個(gè)LRU（LeastRecentlyUsed）緩存機(jī)制，使用鏈表和哈希表實(shí)現(xiàn)，支持get和put操作。2.題目：給定一個(gè)無(wú)重復(fù)元素的數(shù)組，請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，返回所有可能的子集。例如，輸入[1,2,3]，返回[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]。3.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，判斷一個(gè)二叉樹(shù)是否是平衡二叉樹(shù)。平衡二叉樹(shù)是指左右子樹(shù)的高度差不超過(guò)1。4.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，找出數(shù)組中第三大的數(shù)。例如，輸入[1,2,-2147483648,2,3]，返回1。5.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，合并兩個(gè)有序鏈表，返回合并后的有序鏈表。例如，輸入鏈表1為[1,2,4]，鏈表2為[1,3,4]，返回[1,1,2,3,4,4]。三、數(shù)據(jù)庫(kù)與SQL（共3題，每題10分，總分30分）1.題目：請(qǐng)編寫(xiě)SQL查詢，找出公司中工資高于平均工資的員工姓名和工資。假設(shè)表名為employees，包含列name和salary。2.題目：請(qǐng)編寫(xiě)SQL查詢，找出每個(gè)部門的員工數(shù)量，并按員工數(shù)量降序排列。假設(shè)表名為employees，包含列department_id和name。3.題目：請(qǐng)編寫(xiě)SQL查詢，找出所有訂單的總金額，并按訂單日期升序排列。假設(shè)表名為orders，包含列order_id，order_date和amount。四、系統(tǒng)設(shè)計(jì)（共2題，每題15分，總分30分）1.題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)短URL生成系統(tǒng)，要求能夠?qū)㈤L(zhǎng)URL轉(zhuǎn)換為短URL，并支持將短URL解析回長(zhǎng)URL。請(qǐng)說(shuō)明系統(tǒng)架構(gòu)、數(shù)據(jù)結(jié)構(gòu)和主要算法。2.題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)秒殺系統(tǒng)，要求能夠支持高并發(fā)請(qǐng)求，并保證系統(tǒng)穩(wěn)定性。請(qǐng)說(shuō)明系統(tǒng)架構(gòu)、關(guān)鍵技術(shù)、數(shù)據(jù)結(jié)構(gòu)和主要算法。五、綜合應(yīng)用（共2題，每題10分，總分20分）1.題目：攜程旅游平臺(tái)需要優(yōu)化用戶搜索結(jié)果的排序算法，請(qǐng)?zhí)岢鲆环N改進(jìn)方案，并說(shuō)明其優(yōu)缺點(diǎn)。2.題目：攜程酒店預(yù)訂系統(tǒng)需要支持實(shí)時(shí)價(jià)格更新，請(qǐng)?zhí)岢鲆环N解決方案，并說(shuō)明其技術(shù)實(shí)現(xiàn)和優(yōu)缺點(diǎn)。答案與解析一、編程基礎(chǔ)1.答案：pythondefcount_bits(n):count=0whilen:count+=n&1n>>=1returncount解析：通過(guò)位運(yùn)算，每次判斷最低位是否為1，然后右移一位，直到n為0。時(shí)間復(fù)雜度為O(logn)，空間復(fù)雜度為O(1)。2.答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：通過(guò)迭代的方式，逐個(gè)反轉(zhuǎn)鏈表節(jié)點(diǎn)。時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。3.答案：pythondefisValid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack解析：使用棧結(jié)構(gòu)，遍歷字符串，遇到右括號(hào)時(shí)，檢查棧頂是否為對(duì)應(yīng)的左括號(hào)。時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。4.答案：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)解析：快速排序的時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(logn)。解析中未使用額外空間，但遞歸調(diào)用會(huì)使用?？臻g。5.答案：pythondefmajority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate解析：Boyer-Moore投票算法，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。二、數(shù)據(jù)結(jié)構(gòu)與算法1.答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=ListNode(0)self.tail=ListNode(0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valreturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=ListNode(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.next=self.head.nextnode.next.prev=nodeself.head.next=nodenode.prev=self.head解析：使用雙向鏈表和哈希表實(shí)現(xiàn)LRU緩存。時(shí)間復(fù)雜度為O(1)，空間復(fù)雜度為O(capacity)。2.答案：pythondefsubsets(nums):res=[]subset=[]defbacktrack(index):res.append(subset.copy())foriinrange(index,len(nums)):subset.append(nums[i])backtrack(i+1)subset.pop()backtrack(0)returnres解析：回溯算法，遍歷所有可能的子集。時(shí)間復(fù)雜度為O(2^n)，空間復(fù)雜度為O(n)。3.答案：pythondefisBalanced(root):defcheck(node):ifnotnode:return0left=check(node.left)ifleft==-1:return-1right=check(node.right)ifright==-1:return-1ifabs(left-right)>1:return-1returnmax(left,right)+1returncheck(root)!=-1解析：遞歸檢查每個(gè)節(jié)點(diǎn)的左右子樹(shù)高度差，如果超過(guò)1則不平衡。時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。4.答案：pythondefthirdMax(nums):first,second,third=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>first:first,second,third=num,first,secondeliffirst>num>second:second,third=num,secondelifsecond>num>third:third=numreturnthirdifthird!=float('-inf')elsefirst解析：維護(hù)三個(gè)變量，分別記錄第一大、第二大和第三大的數(shù)。時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。5.答案：pythondefmergeTwoLists(l1,l2):dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextcurrent.next=l1orl2returndummy.next解析：合并兩個(gè)有序鏈表，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。三、數(shù)據(jù)庫(kù)與SQL1.答案：sqlSELECTname,salaryFROMemployeesWHEREsalary>(SELECTAVG(salary)FROMemployees);解析：子查詢找出平均工資，然后選擇工資高于平均工資的員工。2.答案：sqlSELECTdepartment_id,COUNT(name)ASnum_employeesFROMemployeesGROUPBYdepartment_idORDERBYnum_employeesDESC;解析：按部門分組，統(tǒng)計(jì)每個(gè)部門的員工數(shù)量，并按數(shù)量降序排列。3.答案：sqlSELECTorder_date,SUM(amount)AStotal_amountFROMordersGROUPBYorder_dateORDERBYorder_dateASC;解析：按訂單日期分組，計(jì)算每個(gè)日期的總金額，并按日期升序排列。四、系統(tǒng)設(shè)計(jì)1.答案：系統(tǒng)架構(gòu)：-前端：接收用戶請(qǐng)求，展示短URL。-后端：處理URL轉(zhuǎn)換請(qǐng)求，存儲(chǔ)URL映射關(guān)系。-數(shù)據(jù)庫(kù)：存儲(chǔ)長(zhǎng)URL和短URL的映射關(guān)系。-緩存：緩存常用短URL，提高訪問(wèn)速度。數(shù)據(jù)結(jié)構(gòu)：-哈希表：存儲(chǔ)短URL和長(zhǎng)URL的映射關(guān)系。-鏈表：存儲(chǔ)短URL的順序，用于生成唯一短URL。主要算法：-生成短URL：使用Base62編碼，將長(zhǎng)URL的哈希值轉(zhuǎn)換為短字符串。-解析短URL：將短字符串解碼為哈希值，查找對(duì)應(yīng)的長(zhǎng)URL。2.答案：系統(tǒng)架構(gòu)：-前端：用戶提交秒殺請(qǐng)求。-后端：處理請(qǐng)求，驗(yàn)證庫(kù)存，扣減庫(kù)存，返回結(jié)果。-數(shù)據(jù)庫(kù)：存儲(chǔ)商品庫(kù)存信息。-緩存：緩存庫(kù)存信息，提高訪問(wèn)速度。-消息隊(duì)列：異步處理請(qǐng)求，防止超賣。關(guān)鍵技術(shù)：-分布式鎖：保證庫(kù)存扣減的原子性。-負(fù)載均衡：分散請(qǐng)求壓力。-異步處理：提高系統(tǒng)響應(yīng)速度。數(shù)據(jù)結(jié)構(gòu)：-哈希表：存儲(chǔ)商品ID和庫(kù)存數(shù)量。-隊(duì)列：存儲(chǔ)待處理的秒殺請(qǐng)求。主要算法：-驗(yàn)證庫(kù)存：檢查庫(kù)存是否足夠。-扣減庫(kù)存：使用分布式鎖扣減庫(kù)存。-返回結(jié)果：返回秒殺成功或失敗的結(jié)果。五、綜合應(yīng)用1.答案：改進(jìn)方案：-引入用戶行為數(shù)據(jù)，如搜索歷史、瀏覽記錄等，根據(jù)用戶偏好排序。-使用機(jī)器學(xué)習(xí)算法，動(dòng)態(tài)調(diào)整排序權(quán)