2025年軟件工程師面試寶典：編程技能與項目經(jīng)驗模擬題及答案代碼實現(xiàn)題(3題,每題15分)題目1(15分)問題描述：實現(xiàn)一個函數(shù)`groupAnagrams(strs)`，輸入一個字符串數(shù)組，輸出一個列表，列表中的每個元素是一個包含所有字母異位詞的子列表。字母異位詞是指由相同字母重新排列組成的單詞。示例：python輸入:strs=["eat","tea","tan","ate","nat","bat"]輸出:[["eat","tea","ate"],["tan","nat"],["bat"]]要求：1.時間復雜度優(yōu)于O(n*klogk)，其中n是字符串數(shù)組長度，k是字符串最大長度。2.不能使用內(nèi)置的排序或哈希表。題目2(15分)問題描述：實現(xiàn)一個函數(shù)`minWindow(s,t)`，輸入一個字符串`s`和一個非空字符串`t`，返回`s`中包含`t`所有字符的子串的最小長度。如果不存在這樣的子串，返回`-1`。示例：python輸入:s="aabbcc",t="abc"輸出:3解釋:最小的包含"a","b","c"的子串是"aabcc"要求：1.可以使用滑動窗口技術。2.必須處理`t`中字符重復的情況。題目3(15分)問題描述：實現(xiàn)一個函數(shù)`maxProfit(prices)`，輸入一個整數(shù)數(shù)組`prices`，其中`prices[i]`是第`i`天的股票價格。設計一個算法，找到最大的利潤，你可以選擇一天買入股票，在之后的任何一天賣出股票。如果沒有利潤，返回`0`。示例：python輸入:prices=[7,1,5,3,6,4]輸出:5解釋:在第2天買入（價格=1），在第5天賣出（價格=6），利潤為5要求：1.時間復雜度O(n)。2.不能使用額外的空間。數(shù)據(jù)結(jié)構與算法題(3題,每題20分)題目4(20分)問題描述：設計一個數(shù)據(jù)結(jié)構`LRUCache`，實現(xiàn)最近最少使用緩存。該數(shù)據(jù)結(jié)構應支持以下操作：1.`LRUCache(intcapacity)`，初始化緩存容量為`capacity`。2.`intget(intkey)`，如果鍵存在，返回鍵的值，否則返回`-1`。3.`voidput(intkey,intvalue)`，如果鍵已存在，則更新其值；如果鍵不存在，則添加鍵值對。當緩存容量已滿時，刪除最近最少使用的緩存項。示例：pythonLRUCachecache=newLRUCache(2)cache.put(1,1)cache.put(2,2)cache.get(1)//返回1cache.put(3,3)//去除鍵2cache.get(2)//返回-1(未找到)cache.put(4,4)//去除鍵1cache.get(1)//返回-1(未找到)cache.get(3)//返回3cache.get(4)//返回4要求：1.使用雙向鏈表和哈希表實現(xiàn)。2.`get`和`put`操作的時間復雜度為O(1)。題目5(20分)問題描述：給定一個整數(shù)數(shù)組`nums`，判斷是否存在一個連續(xù)的子數(shù)組，使得該子數(shù)組的和等于給定值`target`。如果存在，返回任意一個子數(shù)組的起始索引；如果不存在，返回`-1`。示例：python輸入:nums=[1,2,3],target=6輸出:1解釋:子數(shù)組[2,3]的和為6要求：1.不能使用暴力解法（O(n^2)）。2.必須使用哈希表優(yōu)化。題目6(20分)問題描述：實現(xiàn)一個函數(shù)`reverse(x)`，輸入一個32位有符號整數(shù)`x`，返回其反轉(zhuǎn)后的整數(shù)。如果反轉(zhuǎn)后的整數(shù)超出32位有符號整數(shù)的范圍（即`-2^31`到`2^31-1`），返回`0`。示例：python輸入:x=123輸出:321輸入:x=-123輸出:-321輸入:x=120輸出:21要求：1.不能使用字符串轉(zhuǎn)換。2.必須處理整數(shù)溢出問題。項目經(jīng)驗題(2題,每題25分)題目7(25分)問題描述：描述你在項目中如何實現(xiàn)一個高并發(fā)的短鏈接生成系統(tǒng)。要求說明：1.系統(tǒng)架構設計（數(shù)據(jù)庫、緩存、負載均衡等）。2.關鍵技術選型（如Redis、Snowflake算法等）。3.優(yōu)化措施（如緩存穿透、雪崩問題處理等）。4.遇到的挑戰(zhàn)及解決方案。要求：1.必須包含具體的技術細節(jié)。2.說明如何保證系統(tǒng)的高可用性和高性能。題目8(25分)問題描述：描述你在項目中如何解決一個分布式系統(tǒng)中的數(shù)據(jù)一致性問題。要求說明：1.問題背景（如CAP理論的取舍）。2.解決方案（如分布式事務、最終一致性等）。3.技術實現(xiàn)（如TCC、Saga模式等）。4.測試驗證和性能評估。要求：1.必須包含實際案例。2.說明如何權衡可用性、一致性和性能。答案代碼實現(xiàn)題答案題目1答案(15分)解法：使用固定長度的哈希函數(shù)將字符串映射為鍵。對于每個字符串，計算其字符頻率的排序版本作為鍵。代碼：pythondefgroupAnagrams(strs):anagrams={}forsinstrs:#計算字符頻率count=[0]*26forcharins:count[ord(char)-ord('a')]+=1#將頻率列表轉(zhuǎn)換為元組作為鍵key=tuple(count)ifkeynotinanagrams:anagrams[key]=[]anagrams[key].append(s)returnlist(anagrams.values())復雜度分析：-時間復雜度：O(n*k)，其中n是字符串數(shù)量，k是字符串最大長度。-空間復雜度：O(n*k)。題目2答案(15分)解法：使用滑動窗口技術，維護一個窗口包含`t`中所有字符的頻率，移動右指針擴展窗口，移動左指針收縮窗口。代碼：pythonfromcollectionsimportCounterdefminWindow(s,t):ifnottornots:return""need=Counter(t)window={}left,right=0,0valid=0start,length=0,float('inf')whileright<len(s):char=s[right]ifcharinneed:window[char]=window.get(char,0)+1ifwindow[char]==need[char]:valid+=1whilevalid==len(need):ifright-left<length:start,length=left,right-left#嘗試移動左指針left_char=s[left]ifleft_charinneed:window[left_char]-=1ifwindow[left_char]<need[left_char]:valid-=1left+=1right+=1return""iflength==float('inf')elses[start:start+length]復雜度分析：-時間復雜度：O(n)，其中n是字符串`s`的長度。-空間復雜度：O(m)，其中m是字符串`t`的長度。題目3答案(15分)解法：遍歷一次數(shù)組，記錄當前最小價格和最大利潤。代碼：pythondefmaxProfit(prices):ifnotprices:return0min_price=prices[0]max_profit=0forpriceinprices:ifprice<min_price:min_price=priceelifprice-min_price>max_profit:max_profit=price-min_pricereturnmax_profit復雜度分析：-時間復雜度：O(n)。-空間復雜度：O(1)。數(shù)據(jù)結(jié)構與算法題答案題目4答案(20分)解法：使用雙向鏈表和哈希表實現(xiàn)。哈希表存儲鍵到鏈表節(jié)點的映射，鏈表維護最近使用的順序。代碼：pythonclassNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=Node()self.tail=Node()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node):#添加節(jié)點到頭部node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):#刪除節(jié)點prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_pop_tail(self):res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=Node(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]else:node.value=valueself._move_to_head(node)復雜度分析：-時間復雜度：O(1)。-空間復雜度：O(capacity)。題目5答案(20分)解法：使用哈希表記錄前綴和，如果前綴和差值存在，則找到子數(shù)組。代碼：pythondefsubarraySum(nums,target):prefix_sum={0:-1}current_sum=0fori,numinenumerate(nums):current_sum+=numif(current_sum-target)inprefix_sum:returnprefix_sum[current_sum-target]+1,iprefix_sum[current_sum]=ireturn-1復雜度分析：-時間復雜度：O(n)。-空間復雜度：O(n)。題目6答案(20分)解法：逐位反轉(zhuǎn)數(shù)字，處理符號和溢出。代碼：pythondefreverse(x:int)->int:INT_MAX=231-1INT_MIN=-231res=0sign=-1ifx<0else1x=abs(x)whilex!=0:pop=x%10x//=10#檢查溢出ifres>INT_MAX//10or(res==INT_MAX//10andpop>7):return0ifres<INT_MIN//10or(res==INT_MIN//10andpop<-8):return0res=res*10+popreturnsign*res復雜度分析：-時間復雜度：O(logx)。-空間復雜度：O(1)。項目經(jīng)驗題答案題目7答案(25分)解法：系統(tǒng)架構：1.數(shù)據(jù)庫層：使用分片數(shù)據(jù)庫（如ShardingSphere）將短鏈接主表分散到多個數(shù)據(jù)庫節(jié)點，每個節(jié)點存儲一部分短鏈接。2.緩存層：使用RedisCluster高可用集群緩存熱點短鏈接，設置過期時間避免緩存污染。3.負載均衡：使用Nginx負載均衡，將請求分發(fā)到不同的應用服務器。4.分布式鎖：使用Redis分布式鎖處理高并發(fā)寫入問題。關鍵技術：1.Snowflake算法：生成全局唯一短ID（如1位字母+6位數(shù)字）。2.請求去重：使用布隆過濾器（BloomFilter）防止重復請求。優(yōu)化措施：1.緩存穿透：