2026年高級軟件工程師面試題及答案參考一、編程實現(xiàn)題（共3題，每題15分，總分45分）1.題目（15分）：實現(xiàn)一個函數(shù)，輸入一個正整數(shù)`n`，返回一個列表，其中包含從`1`到`n`的所有數(shù)字，但其中所有數(shù)字包含`4`的（例如`4,14,24,34`等）用`-1`替換。示例：-輸入：`10`，輸出：`[1,2,3,-1,5,6,7,8,9,-1]`-輸入：`25`，輸出：`[1,2,3,-1,5,6,7,8,9,-1,11,12,13,14,15,16,17,18,19,-1,21,22,23,24,-1]`要求：-時間復(fù)雜度不超過`O(n)`。-可以使用Python或Java實現(xiàn)。答案與解析：Python實現(xiàn)：pythondefreplace_numbers(n):result=[]foriinrange(1,n+1):if'4'instr(i):result.append(-1)else:result.append(i)returnresult解析：-遍歷從`1`到`n`的每個數(shù)字，將其轉(zhuǎn)換為字符串檢查是否包含`'4'`。-若包含，則用`-1`替換；否則保留原數(shù)字。-時間復(fù)雜度為`O(n)`，因為每個數(shù)字只處理一次。Java實現(xiàn)：javapublicList<Integer>replaceNumbers(intn){List<Integer>result=newArrayList<>();for(inti=1;i<=n;i++){if(String.valueOf(i).contains("4")){result.add(-1);}else{result.add(i);}}returnresult;}解析：-與Python類似，使用`String.valueOf(i)`將數(shù)字轉(zhuǎn)為字符串檢查`'4'`。-時間復(fù)雜度同樣為`O(n)`。2.題目（15分）：實現(xiàn)一個LRU（LeastRecentlyUsed）緩存類的LRU淘汰策略。LRU緩存支持以下操作：-`LRUCache(intcapacity)`：初始化容量為`capacity`的緩存。-`get(intkey)`：獲取鍵`key`對應(yīng)的值，若存在則返回值并更新最近使用時間，若不存在返回`-1`。-`put(intkey,intvalue)`：插入或更新鍵值對，若緩存已滿則淘汰最久未使用的元素。示例：-初始化`LRUCache(2)`-`put(1,1)`-`put(2,2)`-`get(1)`→返回`1`（最近使用更新為`1`）-`put(3,3)`→哈希沖突，淘汰`2`（`2`最久未使用）-`get(2)`→返回`-1`（`2`被淘汰）要求：-使用哈希表+雙向鏈表實現(xiàn)，確保`get`和`put`操作的時間復(fù)雜度為`O(1)`。答案與解析：Java實現(xiàn)：javaclassLRUCache{//雙向鏈表節(jié)點privateclassNode{intkey;intvalue;Nodeprev;Nodenext;Node(intkey,intvalue){this.key=key;this.value=value;}}privateMap<Integer,Node>cache;privateintcapacity;privateNodehead,tail;publicLRUCache(intcapacity){this.capacity=capacity;cache=newHashMap<>();//初始化偽頭部和偽尾部head=newNode(0,0);tail=newNode(0,0);head.next=tail;tail.prev=head;}publicintget(intkey){Nodenode=cache.get(key);if(node==null)return-1;//更新最近使用moveToHead(node);returnnode.value;}publicvoidput(intkey,intvalue){Nodenode=cache.get(key);if(node!=null){node.value=value;moveToHead(node);}else{NodenewNode=newNode(key,value);cache.put(key,newNode);addToHead(newNode);if(cache.size()>capacity){NodetailNode=removeTail();cache.remove(tailNode.key);}}}privatevoidaddToHead(Nodenode){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}privatevoidremoveNode(Nodenode){node.prev.next=node.next;node.next.prev=node.prev;}privatevoidmoveToHead(Nodenode){removeNode(node);addToHead(node);}privateNoderemoveTail(){Noderes=tail.prev;removeNode(res);returnres;}}解析：-雙向鏈表：維護最近使用順序，頭部為最近使用，尾部為最久未使用。-哈希表：`cache`存儲鍵到節(jié)點的映射，實現(xiàn)`O(1)`的`get`和`put`。-操作流程：-`get`：查找節(jié)點，若存在則移動到頭部并返回值。-`put`：若鍵存在則更新值并移動到頭部；若不存在則新建節(jié)點并插入頭部，若超出容量則刪除尾部節(jié)點。-時間復(fù)雜度：所有操作均為`O(1)`。3.題目（15分）：給定一個字符串`s`，其中包含`'('`,`')'`,`''`和`'?'`，`''`可以代表`'('`或`')'`，`'?'`可以代表`'('`或`')'`。設(shè)計一個函數(shù)，計算字符串中有效括號組合的數(shù)量。示例：-輸入：`"()"`，輸出：`2`（`"()"`和`"()"`）-輸入：`"()?"`，輸出：`5`（`"()()"`,`"(())"`,`"(())"`,`"(())?"`,`"()?"`）要求：-可以使用動態(tài)規(guī)劃或回溯法解決，時間復(fù)雜度不超過`O(n^2)`。答案與解析：動態(tài)規(guī)劃實現(xiàn)：pythondefcount_valid_combinations(s):n=len(s)dp=[[0](n+1)for_inrange(n+1)]dp[0][0]=1#空字符串有1種有效組合foriinrange(1,n+1):forjinrange(1,i+1):ifs[i-1]=='(':dp[i][j]=dp[i-1][j-1]elifs[i-1]==')':ifj>0:dp[i][j]=dp[i-1][j-1]elifs[i-1]=='':dp[i][j]=dp[i-1][j]+dp[i-1][j-1]#代表'('或')'elifs[i-1]=='?':dp[i][j]=dp[i-1][j]+dp[i-1][j-1]#代表'('或')'returndp[n][n]解析：-狀態(tài)定義：`dp[i][j]`表示前`i`個字符中，使用`j`個`'('`能形成的有效組合數(shù)。-狀態(tài)轉(zhuǎn)移：-`'('`：只能匹配前一個`')'`，因此`dp[i][j]=dp[i-1][j-1]`。-`')'`：需要有一個未匹配的`'('`，因此`dp[i][j]=dp[i-1][j-1]`（若`j>0`）。-`''`：可以代表`'('`或`')'`，因此`dp[i][j]=dp[i-1][j]+dp[i-1][j-1]`。-`'?'`：與`''`類似，可代表`'('`或`')'`。-時間復(fù)雜度：`O(n^2)`，空間復(fù)雜度：`O(n^2)`。二、系統(tǒng)設(shè)計題（共2題，每題20分，總分40分）1.題目（20分）：設(shè)計一個高并發(fā)的短鏈接生成系統(tǒng)。要求：-用戶輸入長鏈接，系統(tǒng)返回短鏈接，并支持自動跳轉(zhuǎn)。-系統(tǒng)需支持高并發(fā)訪問（百萬級QPS），并具備分布式擴展能力。-短鏈接應(yīng)具有唯一性和可訪問性（如`http://short.ly/abcd`）。要求：-說明核心組件設(shè)計（數(shù)據(jù)庫、緩存、分布式架構(gòu)等）。-解釋如何保證唯一性和高可用性。答案與解析：核心組件設(shè)計：1.短鏈接生成模塊：-使用哈希算法（如MD5或SHA-256）對長鏈接進行加密，取前6-8位作為短碼（如`abcd`）。-為避免沖突，可添加隨機前綴或自增ID作為前綴。2.數(shù)據(jù)庫設(shè)計：-使用分片數(shù)據(jù)庫（如ShardingSphere）將鏈接存儲在多個節(jié)點，避免單點瓶頸。-表結(jié)構(gòu)：`id`（自增主鍵）、`long_url`（長鏈接）、`short_code`（短碼）、`click_count`（點擊量）、`create_time`（創(chuàng)建時間）。3.緩存層（Redis）：-緩存熱點短鏈接，減少數(shù)據(jù)庫訪問。-設(shè)置過期時間（如1小時），避免數(shù)據(jù)冗余。4.分布式架構(gòu)：-使用負載均衡（如Nginx+HAProxy）分發(fā)請求到多個服務(wù)節(jié)點。-服務(wù)節(jié)點間通過RPC（如gRPC）或RESTAPI通信。5.高可用性設(shè)計：-數(shù)據(jù)庫使用主從復(fù)制+哨兵（如RedisCluster）。-短鏈接生成時加入分布式鎖（如ZooKeeper），防止重復(fù)生成。唯一性和高可用性保障：-唯一性：通過哈希算法+隨機前綴確保短碼不沖突。-高可用性：-數(shù)據(jù)庫分片+主從復(fù)制防單點故障。-緩存層減輕數(shù)據(jù)庫壓力。-分布式鎖防止并發(fā)生成重復(fù)短碼。2.題目（20分）：設(shè)計一個實時推薦系統(tǒng)，用于新聞App的個性化內(nèi)容推薦。要求：-用戶瀏覽新聞時，系統(tǒng)需實時更新推薦內(nèi)容。-支持個性化（基于用戶歷史行為）和熱門內(nèi)容推薦。-系統(tǒng)需支持動態(tài)調(diào)整推薦權(quán)重（如突發(fā)熱點新聞優(yōu)先展示）。要求：-說明數(shù)據(jù)流處理架構(gòu)（消息隊列、實時計算等）。-解釋如何實現(xiàn)個性化推薦和熱點內(nèi)容加權(quán)。答案與解析：數(shù)據(jù)流處理架構(gòu)：1.數(shù)據(jù)采集層：-用戶行為數(shù)據(jù)（點擊、點贊、閱讀時長）通過WebSocket實時發(fā)送到消息隊列（如Kafka）。-熱點新聞數(shù)據(jù)（如百度指數(shù)、Twitter趨勢）同樣接入消息隊列。2.實時計算層（Flink/SparkStreaming）：-用戶行為數(shù)據(jù)：-用戶畫像構(gòu)建：統(tǒng)計用戶偏好（如科技類閱讀占比）。-實時推薦：根據(jù)當前閱讀內(nèi)容，通過協(xié)同過濾（如UserCF）推薦相似新聞。-熱點新聞數(shù)據(jù)：-實時計算新聞熱度（如點擊量/分鐘），高熱度新聞優(yōu)先展示。3.推薦引擎：-混合推薦：個性化推薦（70%）+熱點推薦（30%）。-使用Lambda架構(gòu)：批處理（用戶歷史行為分析）+實時流處理（當前行為）結(jié)合。4.存儲層：-用戶畫像：Redis（高頻訪問）+HBase（海量數(shù)據(jù)）。-推薦結(jié)果：Elasticsearch（支持模糊查詢）。個性化推薦和熱點加權(quán)實現(xiàn)：-個性化推薦：-用戶瀏覽某類新聞后，動態(tài)調(diào)整該類新聞的推薦權(quán)重。-使用LRU緩存最近瀏覽新聞，優(yōu)先推薦相關(guān)內(nèi)容。-熱點加權(quán)：-實時計算新聞熱度，高熱度新聞在推薦列表前30%位置展示。-熱點新聞更新權(quán)重（如熱度越高，推薦優(yōu)先級越高）。三、算法與數(shù)據(jù)結(jié)構(gòu)題（共2題，每題17.5分，總分35分）1.題目（17.5分）：給定一個無序數(shù)組`arr`，其中包含重復(fù)元素，設(shè)計一個算法，找出數(shù)組中出現(xiàn)次數(shù)最多的三個元素及其出現(xiàn)次數(shù)。示例：-輸入：`[1,1,2,2,3,3,3,4,4,4,4]`，輸出：`[(4,4),(3,3),(1,2)]`要求：-時間復(fù)雜度不超過`O(n)`，空間復(fù)雜度不超過`O(n)`。答案與解析：算法實現(xiàn)：pythondeftop_three_frequent(arr):count={}fornuminarr:count[num]=count.get(num,0)+1使用最小堆維護Top3importheapqmin_heap=[]fornum,freqincount.items():heapq.heappush(min_heap,(freq,num))iflen(min_heap)>3:heapq.heappop(min_heap)反轉(zhuǎn)結(jié)果result=[]whilemin_heap:freq,num=heapq.heappop(min_heap)result.append((num,freq))returnresult[::-1]解析：-統(tǒng)計頻率：使用哈希表`count`統(tǒng)計每個數(shù)字的出現(xiàn)次數(shù)。-最小堆維護Top3：-遍歷哈希表，將`(頻率,數(shù)字)`存入最小堆。-若堆大小超過3，彈出最小元素，確保堆中始終存儲頻率最高的三個數(shù)字。-輸出結(jié)果：將堆中元素反轉(zhuǎn)后輸出（頻率從高到低）。-時間復(fù)雜度：`O(n)`（哈希表遍歷+堆操作）。2.題目（17.5分）：給定一個二維矩陣`matrix`，其中每個元素都是非負整數(shù)。設(shè)計一個算法，從左上角（`matrix[0][0]`）出發(fā)，到達右下角（`matrix[m-1][n-1]`），每次只能向右或向下移動，且路徑上的數(shù)字之和必須最小。示例：-輸入：matrix=[[1,3,1],[1,5,1],[4,2,1]]-輸出：`7`（路徑：`1→3→1→1→1`）要求：-動態(tài)規(guī)劃實現(xiàn)，時間復(fù)雜度`O(mn)`，空間復(fù)雜度`O(mn)`。答案與解析：動態(tài)規(guī)劃實現(xiàn)：pythondefmin_path_sum(m