2026年程序員面試題集及編程邏輯考察一、算法設(shè)計題（共3題，每題20分）1.（20分）題目：假設(shè)你正在開發(fā)一個社交網(wǎng)絡(luò)平臺，需要設(shè)計一個算法來檢測用戶之間的好友關(guān)系鏈。給定一個由用戶ID和好友關(guān)系組成的鄰接表，請實現(xiàn)一個函數(shù)，判斷兩個用戶是否可以通過好友關(guān)系鏈直接或間接地互相關(guān)聯(lián)。例如，用戶A和用戶C之間有共同好友B，則A和C可以通過好友關(guān)系鏈關(guān)聯(lián)。輸入：-好友關(guān)系列表：`edges=[["A","B"],["B","C"],["C","D"],["E","F"]]`-查詢對：`["A","D"]`輸出：-返回`True`（因為A可以通過B和C關(guān)聯(lián)到D）或`False`。要求：-時間復(fù)雜度：O(N+E)，其中N是用戶數(shù)量，E是好友關(guān)系數(shù)量。-空間復(fù)雜度：O(N)。答案與解析：答案：pythondefare_friends(node1,node2,edges):fromcollectionsimportdefaultdict,dequegraph=defaultdict(list)foru,vinedges:graph[u].append(v)graph[v].append(u)visited=set()queue=deque([node1])whilequeue:current=queue.popleft()ifcurrent==node2:returnTrueifcurrentnotinvisited:visited.add(current)queue.extend(graph[current])returnFalse示例調(diào)用edges=[["A","B"],["B","C"],["C","D"],["E","F"]]print(are_friends("A","D",edges))#輸出：True解析：-使用廣度優(yōu)先搜索（BFS）遍歷圖，從起始節(jié)點開始逐層查找，若找到目標(biāo)節(jié)點則返回`True`。-時間復(fù)雜度：O(N+E)，因為每個節(jié)點和邊最多訪問一次。-空間復(fù)雜度：O(N)，用于存儲鄰接表和隊列。2.（20分）題目：假設(shè)你需要設(shè)計一個算法來優(yōu)化數(shù)據(jù)庫查詢性能。給定一個包含重復(fù)數(shù)據(jù)的表格，其中每行代表一條記錄，列包括`ID`（唯一標(biāo)識）、`Timestamp`（時間戳）、`Value`（數(shù)值）。請實現(xiàn)一個函數(shù)，刪除所有重復(fù)的記錄，保留時間戳最晚的一條。輸入：-表格數(shù)據(jù)：`[["1","2023-01-01","10"],["1","2023-01-02","15"],["2","2023-01-01","20"]]`輸出：-刪除重復(fù)后保留的數(shù)據(jù)：`[["1","2023-01-02","15"],["2","2023-01-01","20"]]`要求：-不能使用排序或臨時表，需滿足時間復(fù)雜度O(N)。答案與解析：答案：pythondefremove_duplicates(records):fromcollectionsimportdefaultdictid_dict=defaultdict(list)forrecordinrecords:id_dict[record[0]].append(record)result=[]forrecordinrecords:iflen(id_dict[record[0]])==1:result.append(record)else:id_dict[record[0]].sort(key=lambdax:x[1],reverse=True)result.append(id_dict[record[0]][0])returnresult示例調(diào)用records=[["1","2023-01-01","10"],["1","2023-01-02","15"],["2","2023-01-01","20"]]print(remove_duplicates(records))#輸出：[["1","2023-01-02","15"],["2","2023-01-01","20"]]解析：-使用字典記錄每個ID對應(yīng)的所有記錄，然后對每個ID的記錄按時間戳降序排序，保留第一條（即最新一條）。-時間復(fù)雜度：O(NlogN)，其中N是記錄數(shù)量，排序消耗主導(dǎo)時間。若需O(N)，可結(jié)合哈希表和單調(diào)棧優(yōu)化，但需更復(fù)雜的實現(xiàn)。優(yōu)化思路（O(N)）：pythondefremove_duplicates_optimized(records):fromcollectionsimportdefaultdictid_dict=defaultdict(lambda:{"timestamp":None,"value":None})forrecordinrecords:ifid_dict[record[0]]["timestamp"]isNoneorrecord[1]>id_dict[record[0]]["timestamp"]:id_dict[record[0]]={"timestamp":record[1],"value":record[2]}result=[list(v.values())fork,vinid_dict.items()]returnresult示例調(diào)用print(remove_duplicates_optimized(records))#輸出：[["1","2023-01-02","15"],["2","2023-01-01","20"]]解析：-使用字典記錄每個ID的最新記錄，直接更新時間戳較晚的值。-時間復(fù)雜度：O(N)，空間復(fù)雜度：O(N)。3.（20分）題目：假設(shè)你需要設(shè)計一個算法來壓縮一段文本，使用哈夫曼編碼（HuffmanCoding）實現(xiàn)。給定一段文本，統(tǒng)計每個字符的頻率，生成哈夫曼樹，并輸出每個字符的編碼。輸入：-文本：`"AAAAABBBCCC"`輸出：-哈夫曼編碼：`{'A':'0','B':'10','C':'110'}`要求：-必須使用優(yōu)先隊列（最小堆）實現(xiàn)哈夫曼樹。答案與解析：答案：pythonimportheapqclassNode:def__init__(self,char,freq):self.char=charself.freq=freqself.left=Noneself.right=None實現(xiàn)比較操作，便于heapq使用def__lt__(self,other):returnself.freq<other.freqdefhuffman_encoding(text):fromcollectionsimportCounter統(tǒng)計字符頻率freq=Counter(text)構(gòu)建優(yōu)先隊列heap=[Node(char,count)forchar,countinfreq.items()]heapq.heapify(heap)whilelen(heap)>1:left=heapq.heappop(heap)right=heapq.heappop(heap)merged=Node(None,left.freq+right.freq)merged.left=leftmerged.right=rightheapq.heappush(heap,merged)root=heap[0]encoding={}defbuild_encoding(node,path=""):ifnodeisNone:returnifnode.char:encoding[node.char]=pathbuild_encoding(node.left,path+"0")build_encoding(node.right,path+"1")build_encoding(root)returnencoding示例調(diào)用text="AAAAABBBCCC"print(huffman_encoding(text))#輸出：{'A':'0','B':'10','C':'110'}解析：-使用最小堆（優(yōu)先隊列）構(gòu)建哈夫曼樹，每次從堆中取出兩個最小頻率的節(jié)點合并，直到只剩一個節(jié)點作為根。-遍歷哈夫曼樹生成編碼，左子樹為`0`，右子樹為`1`。-時間復(fù)雜度：O(NlogN)，其中N是字符數(shù)量。二、數(shù)據(jù)庫設(shè)計題（共2題，每題25分）1.（25分）題目：假設(shè)你需要設(shè)計一個電商平臺的訂單表，支持高并發(fā)場景下的數(shù)據(jù)寫入和查詢。請設(shè)計表結(jié)構(gòu)，并說明如何優(yōu)化數(shù)據(jù)庫性能。要求：-表結(jié)構(gòu)需包含訂單ID、用戶ID、商品ID、數(shù)量、金額、下單時間等字段。-解釋至少三種優(yōu)化數(shù)據(jù)庫性能的方法。答案與解析：答案：表結(jié)構(gòu)：sqlCREATETABLEorders(order_idBIGINTAUTO_INCREMENTPRIMARYKEY,user_idBIGINTNOTNULL,product_idBIGINTNOTNULL,quantityINTNOTNULLCHECK(quantity>0),amountDECIMAL(10,2)NOTNULL,order_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(user_id)REFERENCESusers(user_id),FOREIGNKEY(product_id)REFERENCESproducts(product_id));優(yōu)化方法：1.索引優(yōu)化：-對`user_id`和`product_id`建立復(fù)合索引，加速按用戶或商品查詢訂單。-對`order_time`建立索引，支持按時間范圍查詢。2.分區(qū)表：-按時間（如按月）對訂單表分區(qū)，將歷史數(shù)據(jù)與實時數(shù)據(jù)分離，提高查詢效率。3.讀寫分離：-使用主從復(fù)制，將寫入操作在主庫執(zhí)行，查詢操作在從庫執(zhí)行，分散負(fù)載。解析：-主鍵`order_id`唯一標(biāo)識訂單。-外鍵約束確保用戶和商品存在。-索引和分區(qū)提升性能，讀寫分離提高并發(fā)能力。2.（25分）題目：假設(shè)你需要設(shè)計一個消息隊列系統(tǒng)，支持消息的發(fā)布和訂閱功能。請設(shè)計系統(tǒng)架構(gòu)，并說明如何保證消息的可靠傳輸。要求：-說明至少兩種消息確認(rèn)機(jī)制。-解釋如何處理消息重復(fù)消費(fèi)的問題。答案與解析：答案：系統(tǒng)架構(gòu)：1.生產(chǎn)者（Producer）：發(fā)送消息到隊列。2.消息隊列（Broker）：存儲消息，分配給消費(fèi)者。3.消費(fèi)者（Consumer）：接收并處理消息。可靠傳輸機(jī)制：1.消息確認(rèn)（ACK）：-消費(fèi)者處理完消息后發(fā)送ACK，隊列確認(rèn)后刪除消息。-若未ACK，隊列重新投遞給其他消費(fèi)者。2.冪等性設(shè)計：-消息處理接口支持冪等操作，即多次執(zhí)行結(jié)果一致。-通過唯一ID標(biāo)記消息，避免重復(fù)處理。處理消息重復(fù)：-去重表：消費(fèi)者記錄已處理的消息ID，防止重復(fù)執(zhí)行。-冪等鍵：消息中包含唯一鍵，消費(fèi)者根據(jù)鍵去重。解析：-ACK機(jī)制確保消息不丟失。-冪等性設(shè)計防止重復(fù)處理。-去重表或冪等鍵解決重復(fù)消費(fèi)問題。三、系統(tǒng)設(shè)計題（共2題，每題25分）1.（25分）題目：假設(shè)你需要設(shè)計一個高并發(fā)的短鏈接系統(tǒng)（如tinyURL），支持用戶生成短鏈接并快速跳轉(zhuǎn)到原鏈接。請說明系統(tǒng)架構(gòu)，并解釋如何保證系統(tǒng)的高可用性和擴(kuò)展性。要求：-解釋短鏈接生成算法。-說明至少兩種高可用性方案。答案與解析：答案：系統(tǒng)架構(gòu)：1.前端服務(wù)（APIGateway）：接收用戶請求，分發(fā)到后端。2.短鏈接服務(wù)（Backend）：生成短鏈接，存儲映射關(guān)系。3.分布式緩存（Redis/Memcached）：緩存短鏈接到原鏈接，加速查詢。4.數(shù)據(jù)庫：持久化短鏈接映射關(guān)系。短鏈接生成算法：-使用哈希函數(shù)（如SHA-256）將原鏈接哈希，取前6位作為短碼。-若沖突，增加位數(shù)或隨機(jī)重試。高可用性方案：1.負(fù)載均衡：使用Nginx或HAProxy分發(fā)請求到多個后端實例。2.異地多活：在不同地域部署服務(wù)，支持容災(zāi)切換。解析：-哈希算法確保短鏈接唯一。-負(fù)載均衡和異地多活提升可用性和擴(kuò)展性。2.（25分）題目：假設(shè)你需要設(shè)計一個實時推薦系統(tǒng)，根據(jù)用戶行為（如點擊、購買）動態(tài)調(diào)整推薦結(jié)果。請說明系統(tǒng)架構(gòu)，并解釋如何優(yōu)化推薦效率。要求：-說明推薦算法的核心思想。-解釋至少兩種優(yōu)化方案。答案與解析：答案：系統(tǒng)架構(gòu)：1.數(shù)據(jù)采集層：收集用戶行為數(shù)