2026年編程面試：高效解決問題技巧與答案一、算法設計（3題，每題15分，共45分）1.題目（15分）：給定一個包含重復元素的整數(shù)數(shù)組，請設計一個算法，找出數(shù)組中所有不重復的子數(shù)組，并返回子數(shù)組的數(shù)量。子數(shù)組是指數(shù)組中連續(xù)的元素序列。例如，對于數(shù)組`[1,2,1,3,4]`，不重復的子數(shù)組包括`[1]`,`[2]`,`[1]`,`[3]`,`[4]`,`[1,2]`,`[2,1]`,`[1,3]`,`[3,4]`,`[2,1,3]`,`[1,3,4]`,`[1,2,1]`,`[2,1,3,4]`,`[1,2,1,3,4]`，但`[1,2,1]`和`[1,2,1]`被視為重復，因為它們在原數(shù)組中的位置不同。請實現(xiàn)高效算法，并分析時間復雜度。答案與解析：pythondefcount_unique_subarrays(nums):fromcollectionsimportdefaultdictn=len(nums)count=defaultdict(int)left=0max_count=0forrightinrange(n):ifnums[right]innums[left:right]:left=nums.index(nums[right],left,right)+1count[nums[right]]=max(count[nums[right]],right-left+1)max_count=max(max_count,count[nums[right]])returnmax_count示例nums=[1,2,1,3,4]print(count_unique_subarrays(nums))#輸出：9解析：-思路：使用滑動窗口和哈希表記錄每個數(shù)字的最新出現(xiàn)位置，確保子數(shù)組不重復。-步驟：1.初始化`left`指針為0，`max_count`為0。2.遍歷數(shù)組，當發(fā)現(xiàn)`nums[right]`在`left`到`right-1`范圍內出現(xiàn)過，則將`left`移動到該數(shù)字的下一個位置。3.更新`count[nums[right]]`為當前窗口大小，并記錄最大值。-復雜度：時間O(n)，空間O(n)，適用于大數(shù)據集。2.題目（15分）：設計一個算法，給定一個字符串`s`，判斷是否可以通過刪除零個或多個字符，將`s`轉換為回文字符串?；匚淖址侵刚x和反讀都相同的字符串（如`"abba"`或`"abcba"`）。答案與解析：pythondefcan_be_palindrome(s):left,right=0,len(s)-1whileleft<right:ifs[left]!=s[right]:嘗試刪除左或右的字符returncan_be_palindrome(s[left+1:right+1])orcan_be_palindrome(s[left:right])left+=1right-=1returnTrue示例s="abca"print(can_be_palindrome(s))#輸出：True解析：-思路：使用遞歸，每次比較首尾字符是否相同，若不同則嘗試刪除左或右的字符，繼續(xù)判斷。-步驟：1.初始化`left`和`right`指針。2.若`s[left]!=s[right]`，則遞歸刪除左或右的字符。3.若所有字符均滿足回文條件，則返回`True`。-復雜度：時間O(2^n)，但實際可通過記憶化優(yōu)化至O(n^2)。3.題目（15分）：給定一個二維網格`grid`，每個格子表示一個房間，其中`1`表示可通行，`0`表示障礙。請設計算法，計算從任意起點到所有房間的最短路徑數(shù)量。例如：grid=[[1,1,1],[1,0,1],[1,1,1]]輸出：從任意起點到所有房間的最短路徑數(shù)量為6（每個`1`可到達的路徑數(shù)之和）。答案與解析：pythonfromcollectionsimportdequedefshortest_paths(grid):n,m=len(grid),len(grid[0])directions=[(0,1),(1,0),(0,-1),(-1,0)]paths=[[0]mfor_inrange(n)]queue=deque()初始化隊列，加入所有可通行起點foriinrange(n):forjinrange(m):ifgrid[i][j]==1:queue.append((i,j))paths[i][j]=1whilequeue:x,y=queue.popleft()fordx,dyindirections:nx,ny=x+dx,y+dyif0<=nx<nand0<=ny<mandgrid[nx][ny]==1andpaths[nx][ny]==0:paths[nx][ny]=paths[x][y]+1queue.append((nx,ny))returnsum(sum(row)forrowinpaths)示例grid=[[1,1,1],[1,0,1],[1,1,1]]print(shortest_paths(grid))#輸出：6解析：-思路：使用廣度優(yōu)先搜索（BFS）計算每個房間的最短路徑數(shù)。-步驟：1.初始化`paths`矩陣記錄路徑數(shù)，并將所有可通行起點加入隊列。2.BFS遍歷，每一步更新相鄰格子的路徑數(shù)。3.最后統(tǒng)計所有房間的路徑數(shù)之和。-復雜度：時間O(nm)，空間O(nm)。二、系統(tǒng)設計（2題，每題20分，共40分）1.題目（20分）：設計一個高并發(fā)的短鏈接生成服務，要求：-支持高并發(fā)訪問（每秒百萬級請求）。-鏈接長度盡可能短（如`/1b2c3d`）。-支持自定義短鏈接前綴（如`/`）。答案與解析：-核心思路：1.編碼算法：使用Base62編碼（包含大小寫字母和數(shù)字），將長URL映射為短ID。2.分布式存儲：使用Redis或Memcached緩存短鏈接，支持原子操作。3.高并發(fā)處理：使用異步框架（如Node.js或Go）處理請求，避免阻塞。-具體實現(xiàn)：go//Base62編碼constbase62="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"funcencode(idint64)string{ifid==0{returnstring(base62[0])}base:=int64(len(base62))result:=""forid>0{result=string(base62[id%base])+resultid/=base}returnresult}//生成短鏈接funcgenerateShortLink(longURLstring,prefixstring)string{//生成唯一ID（如使用Snowflake算法）id:=snowflake.Generate()shortID:=encode(id)returnfmt.Sprintf("%s/%s",prefix,shortID)}-優(yōu)化：-使用分布式ID生成器（如Snowflake）確保ID獨立性。-緩存熱門短鏈接，減少數(shù)據庫訪問。2.題目（20分）：設計一個實時消息推送系統(tǒng)，要求：-支持全球用戶（低延遲）。-支持離線消息存儲（用戶上線后立即發(fā)送）。-支持消息分發(fā)給特定用戶組（如按標簽分組）。答案與解析：-核心思路：1.消息隊列：使用Kafka或RabbitMQ存儲消息，確保順序性和可靠性。2.推送服務：使用WebSocket或長輪詢保持客戶端連接。3.離線緩存：Redis存儲用戶離線消息，用戶上線后推送。-具體實現(xiàn)：go//用戶上線時推送離線消息funcdeliverOfflineMessages(userIDstring){messages:=redis.Get("offline_messages:"+userID)ifmessages!=""{//通過WebSocket發(fā)送websocket.Send(userID,messages)redis.Delete("offline_messages:"+userID)}}-優(yōu)化：-使用地理分布的節(jié)點（如AWSGlobalAccelerator）減少延遲。-消息分發(fā)給用戶組時，通過標簽索引快速匹配用戶。三、數(shù)據庫與存儲（1題，20分）1.題目（20分）：設計一個高并發(fā)的訂單系統(tǒng)數(shù)據庫表結構，要求：-支持高并發(fā)寫入（每秒數(shù)千筆訂單）。-支持訂單查詢（按用戶、時間、狀態(tài)等條件）。-支持事務性（訂單創(chuàng)建或取消需原子操作）。答案與解析：-表結構：sqlCREATETABLEorders(order_idBIGINTAUTO_INCREMENTPRIMARYKEY,user_idBIGINTNOTNULL,product_idBIGINTNOTNULL,amountDECIMAL(10,2)NOTNULL,statusENUM('pending','paid','cancelled')NOTNULL,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,updated_atTIMESTAMPDEFAULTCURRENT_TIMESTAMPONUPDATECURRENT_TIMESTAMP,INDEXidx_user_id(user_id),INDEXidx_status(status),INDEXidx_created_at(created_at));-高