2026年京東校招面試技術(shù)研發(fā)思路練習(xí)題及解析一、編程題（3題，每題15分，共45分）1.題1（15分）：實(shí)現(xiàn)LRU緩存機(jī)制背景：LRU（LeastRecentlyUsed）緩存是一種常用的數(shù)據(jù)結(jié)構(gòu)，用于在內(nèi)存中存儲(chǔ)固定數(shù)量的高頻訪問數(shù)據(jù)。當(dāng)緩存滿時(shí)，需要淘汰最久未使用的數(shù)據(jù)。要求：-設(shè)計(jì)一個(gè)LRU緩存類，支持以下操作：-`LRUCache(intcapacity)`：初始化緩存容量。-`get(intkey)`：返回鍵對(duì)應(yīng)的值，如果不存在返回-1。訪問該鍵時(shí)，將其標(biāo)記為最近使用。-`put(intkey,intvalue)`：將鍵值對(duì)插入緩存。如果緩存已滿，先淘汰最久未使用的鍵。示例：LRUCachecache=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答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache=OrderedDict()#使用OrderedDict記錄順序defget(self,key:int)->int:ifkeynotinself.cache:return-1self.cache.move_to_end(key)#標(biāo)記為最近使用returnself.cache[key]defput(self,key:int,value:int)->None:ifkeyinself.cache:self.cache.move_to_end(key)self.cache[key]=valueiflen(self.cache)>self.capacity:self.cache.popitem(last=False)#淘汰最久未使用的解析：-使用`OrderedDict`可以高效地記錄元素的使用順序，`move_to_end`方法可以快速標(biāo)記最近使用的元素。-`get`操作需要將元素移動(dòng)到末尾，`put`操作需要檢查是否需要淘汰最久未使用的元素。-時(shí)間復(fù)雜度為O(1)，因?yàn)閌OrderedDict`的`get`、`put`和`move_to_end`操作均為常數(shù)時(shí)間。2.題2（15分）：實(shí)現(xiàn)二叉樹的最大深度背景：二叉樹的最大深度是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。要求：-設(shè)計(jì)一個(gè)函數(shù)`maxDepth(root)`，輸入為二叉樹的根節(jié)點(diǎn)，返回二叉樹的最大深度。-可以使用遞歸或迭代的方式實(shí)現(xiàn)。示例：輸入：[3,9,20,null,null,15,7]輸出：3解釋：3/\920/\157答案：python定義二叉樹節(jié)點(diǎn)classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right遞歸解法defmaxDepth(root:TreeNode)->int:ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))迭代解法（BFS）defmaxDepthIterative(root:TreeNode)->int:ifnotroot:return0depth=0queue=deque([root])whilequeue:depth+=1level_size=len(queue)for_inrange(level_size):node=queue.popleft()ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)returndepth解析：-遞歸解法通過計(jì)算左右子樹的最大深度，加1得到當(dāng)前節(jié)點(diǎn)的高度。-迭代解法使用BFS（廣度優(yōu)先搜索），逐層遍歷二叉樹，統(tǒng)計(jì)層數(shù)。-遞歸解法的時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(N)（遞歸棧）；迭代解法的時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(N)（隊(duì)列）。3.題3（15分）：實(shí)現(xiàn)快速排序的隨機(jī)化版本背景：快速排序是一種高效的排序算法，其核心是分治思想。隨機(jī)化快速排序通過隨機(jī)選擇樞軸，可以避免最壞情況（如已排序數(shù)組）。要求：-設(shè)計(jì)一個(gè)函數(shù)`quickSortRandom(arr)`，輸入一個(gè)數(shù)組，返回排序后的數(shù)組。-使用隨機(jī)化選擇樞軸的方法，提高算法的魯棒性。示例：輸入：[4,2,1,5,3]輸出：[1,2,3,4,5]答案：pythonimportrandomdefquickSortRandom(arr):defpartition(left,right):pivot_index=random.randint(left,right)#隨機(jī)選擇樞軸arr[pivot_index],arr[right]=arr[right],arr[pivot_index]#交換樞軸到末尾pivot=arr[right]i=left-1forjinrange(left,right):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[right]=arr[right],arr[i+1]returni+1defquickSort(left,right):ifleft<right:pivot=partition(left,right)quickSort(left,pivot-1)quickSort(pivot+1,right)quickSort(0,len(arr)-1)returnarr解析：-隨機(jī)選擇樞軸可以減少最壞情況的發(fā)生概率。-`partition`函數(shù)通過雙指針法將數(shù)組劃分為小于樞軸和大于樞軸的兩部分。-時(shí)間復(fù)雜度平均為O(NlogN)，最壞為O(N^2)，但隨機(jī)化可以降低最壞情況概率。-空間復(fù)雜度為O(logN)（遞歸棧）。二、系統(tǒng)設(shè)計(jì)題（2題，每題25分，共50分）4.題4（25分）：設(shè)計(jì)一個(gè)短鏈接系統(tǒng)背景：短鏈接系統(tǒng)可以將長(zhǎng)URL轉(zhuǎn)換為短URL，提高傳播效率。例如，`/abc`可以轉(zhuǎn)換為`/123`。要求：-設(shè)計(jì)一個(gè)短鏈接系統(tǒng)，支持以下功能：1.輸入長(zhǎng)URL，生成唯一的短URL。2.輸入短URL，解析為原始長(zhǎng)URL。3.系統(tǒng)需要具備高可用性和分布式能力。設(shè)計(jì)要點(diǎn)：-短URL生成算法（如Base62編碼）。-分布式存儲(chǔ)方案（如Redis+數(shù)據(jù)庫）。-高可用性設(shè)計(jì)（如多機(jī)房部署）。答案：1.短URL生成算法：-使用Base62編碼（字母A-Z、數(shù)字0-9、小寫字母a-z），將長(zhǎng)URL的哈希值轉(zhuǎn)換為短字符串。-例如，將URL的MD5哈希值前6位轉(zhuǎn)換為Base62：pythondefencode(num):chars="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"ifnum==0:returnchars[0]res=[]whilenum:res.append(chars[num%62])num//=62return''.join(res[::-1])2.分布式存儲(chǔ)方案：-使用Redis存儲(chǔ)短URL與長(zhǎng)URL的映射關(guān)系，支持高并發(fā)讀寫。-數(shù)據(jù)庫（如MySQL）存儲(chǔ)歷史訪問記錄，用于統(tǒng)計(jì)分析。3.高可用性設(shè)計(jì)：-多機(jī)房部署，使用負(fù)載均衡（如Nginx）分發(fā)請(qǐng)求。-Redis集群模式，保證數(shù)據(jù)冗余和故障轉(zhuǎn)移。解析：-Base62編碼可以生成較短的URL，提高傳播效率。-Redis的高性能特性適合存儲(chǔ)URL映射關(guān)系。-分布式部署可以避免單點(diǎn)故障，提升系統(tǒng)容錯(cuò)能力。5.題5（25分）：設(shè)計(jì)一個(gè)高并發(fā)計(jì)數(shù)器系統(tǒng)背景：在高并發(fā)場(chǎng)景下（如雙十一），需要對(duì)特定事件進(jìn)行實(shí)時(shí)計(jì)數(shù)（如頁面訪問量、訂單量）。要求：-設(shè)計(jì)一個(gè)高并發(fā)計(jì)數(shù)器系統(tǒng)，支持以下功能：1.實(shí)時(shí)計(jì)數(shù)，支持高并發(fā)訪問。2.分布式部署，避免數(shù)據(jù)丟失。3.支持計(jì)數(shù)回滾（如發(fā)現(xiàn)錯(cuò)誤，扣減計(jì)數(shù)）。設(shè)計(jì)要點(diǎn)：-使用Redis的`INCR`命令實(shí)現(xiàn)原子計(jì)數(shù)。-分布式鎖（如Redlock算法）保證數(shù)據(jù)一致性。-計(jì)數(shù)回滾方案（如事務(wù)或補(bǔ)償機(jī)制）。答案：1.實(shí)時(shí)計(jì)數(shù)：-使用Redis的`INCR`命令實(shí)現(xiàn)原子計(jì)數(shù)，例如：redisINCRcounter_name-支持分布式部署，多個(gè)節(jié)點(diǎn)共享Redis集群。2.分布式鎖：-使用Redlock算法，在多個(gè)Redis節(jié)點(diǎn)上獲取鎖，確保鎖的可靠性。pythondefacquire_lock(lock_id,timeout):whileTrue:forredis_nodeinredis_nodes:ifredis_node.set(lock_id,'locked',nx=True,ex=timeout):returnTruetime.sleep(0.1)defrelease_lock(lock_id,redis_node):redis_node.delete(lock_id)3.計(jì)數(shù)回滾：-使用Redis事務(wù)或Lua腳本保證計(jì)數(shù)的一致性。-例如，使用Lua腳本實(shí)現(xiàn)原子扣減：redisEVAL"ifredis.call('exists',KEYS[1])thenreturnredis.call('decr',KEYS[1])elsereturn0end"1counter_name解析：-Redis的原子操作保證了高并發(fā)下的計(jì)數(shù)一致性。-Redlock算法提高了分布式鎖的可靠性。-Lua腳本確保計(jì)數(shù)操作的原子性，避免并發(fā)問題。答案解析1.題1（LRU緩存機(jī)制）-`OrderedDict`是關(guān)鍵，`move_to_end`方法可以高效標(biāo)記最近使用元素。-時(shí)間復(fù)雜度為O(1)，空間復(fù)雜度為O(capacity)。2.題2（二叉樹的最大深度）-遞歸解法簡(jiǎn)潔，但?？臻g可能較大；迭代解法（BFS）更節(jié)省空間。-注意空節(jié)點(diǎn)的處理，避免無限遞歸。3.題3（快速排序