2026年京东校招面试技术研发思路练习题及解析

2026年京东校招面试技术研发思路练习题及解析一、编程题（3题，每题15分，共45分）1.题1（15分）：实现LRU缓存机制背景：LRU（LeastRecentlyUsed）缓存是一种常用的数据结构，用于在内存中存储固定数量的高频访问数据。当缓存满时，需要淘汰最久未使用的数据。要求：-设计一个LRU缓存类，支持以下操作：-`LRUCache(intcapacity)`：初始化缓存容量。-`get(intkey)`：返回键对应的值，如果不存在返回-1。访问该键时，将其标记为最近使用。-`put(intkey,intvalue)`：将键值对插入缓存。如果缓存已满，先淘汰最久未使用的键。示例：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)#标记为最近使用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`方法可以快速标记最近使用的元素。-`get`操作需要将元素移动到末尾，`put`操作需要检查是否需要淘汰最久未使用的元素。-时间复杂度为O(1)，因为`OrderedDict`的`get`、`put`和`move_to_end`操作均为常数时间。2.题2（15分）：实现二叉树的最大深度背景：二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。要求：-设计一个函数`maxDepth(root)`，输入为二叉树的根节点，返回二叉树的最大深度。-可以使用递归或迭代的方式实现。示例：输入：[3,9,20,null,null,15,7]输出：3解释：3/\920/\157答案：python定义二叉树节点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解析：-递归解法通过计算左右子树的最大深度，加1得到当前节点的高度。-迭代解法使用BFS（广度优先搜索），逐层遍历二叉树，统计层数。-递归解法的时间复杂度为O(N)，空间复杂度为O(N)（递归栈）；迭代解法的时间复杂度为O(N)，空间复杂度为O(N)（队列）。3.题3（15分）：实现快速排序的随机化版本背景：快速排序是一种高效的排序算法，其核心是分治思想。随机化快速排序通过随机选择枢轴，可以避免最坏情况（如已排序数组）。要求：-设计一个函数`quickSortRandom(arr)`，输入一个数组，返回排序后的数组。-使用随机化选择枢轴的方法，提高算法的鲁棒性。示例：输入：[4,2,1,5,3]输出：[1,2,3,4,5]答案：pythonimportrandomdefquickSortRandom(arr):defpartition(left,right):pivot_index=random.randint(left,right)#随机选择枢轴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解析：-随机选择枢轴可以减少最坏情况的发生概率。-`partition`函数通过双指针法将数组划分为小于枢轴和大于枢轴的两部分。-时间复杂度平均为O(NlogN)，最坏为O(N^2)，但随机化可以降低最坏情况概率。-空间复杂度为O(logN)（递归栈）。二、系统设计题（2题，每题25分，共50分）4.题4（25分）：设计一个短链接系统背景：短链接系统可以将长URL转换为短URL，提高传播效率。例如，`/abc`可以转换为`/123`。要求：-设计一个短链接系统，支持以下功能：1.输入长URL，生成唯一的短URL。2.输入短URL，解析为原始长URL。3.系统需要具备高可用性和分布式能力。设计要点：-短URL生成算法（如Base62编码）。-分布式存储方案（如Redis+数据库）。-高可用性设计（如多机房部署）。答案：1.短URL生成算法：-使用Base62编码（字母A-Z、数字0-9、小写字母a-z），将长URL的哈希值转换为短字符串。-例如，将URL的MD5哈希值前6位转换为Base62：pythondefencode(num):chars="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"ifnum==0:returnchars[0]res=[]whilenum:res.append(chars[num%62])num//=62return''.join(res[::-1])2.分布式存储方案：-使用Redis存储短URL与长URL的映射关系，支持高并发读写。-数据库（如MySQL）存储历史访问记录，用于统计分析。3.高可用性设计：-多机房部署，使用负载均衡（如Nginx）分发请求。-Redis集群模式，保证数据冗余和故障转移。解析：-Base62编码可以生成较短的URL，提高传播效率。-Redis的高性能特性适合存储URL映射关系。-分布式部署可以避免单点故障，提升系统容错能力。5.题5（25分）：设计一个高并发计数器系统背景：在高并发场景下（如双十一），需要对特定事件进行实时计数（如页面访问量、订单量）。要求：-设计一个高并发计数器系统，支持以下功能：1.实时计数，支持高并发访问。2.分布式部署，避免数据丢失。3.支持计数回滚（如发现错误，扣减计数）。设计要点：-使用Redis的`INCR`命令实现原子计数。-分布式锁（如Redlock算法）保证数据一致性。-计数回滚方案（如事务或补偿机制）。答案：1.实时计数：-使用Redis的`INCR`命令实现原子计数，例如：redisINCRcounter_name-支持分布式部署，多个节点共享Redis集群。2.分布式锁：-使用Redlock算法，在多个Redis节点上获取锁，确保锁的可靠性。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.计数回滚：-使用Redis事务或Lua脚本保证计数的一致性。-例如，使用Lua脚本实现原子扣减：redisEVAL"ifredis.call('exists',KEYS[1])thenreturnredis.call('decr',KEYS[1])elsereturn0end"1counter_name解析：-Redis的原子操作保证了高并发下的计数一致性。-Redlock算法提高了分布式锁的可靠性。-Lua脚本确保计数操作的原子性，避免并发问题。答案解析1.题1（LRU缓存机制）-`OrderedDict`是关键，`move_to_end`方法可以高效标记最近使用元素。-时间复杂度为O(1)，空间复杂度为O(capacity)。2.题2（二叉树的最大深度）-递归解法简洁，但栈空间可能较大；迭代解法（BFS）更节省空间。-注意空节点的处理，避免无限递归。3.题3（快速排序