京东技术部面试指南及答案详解

2026年京东技术部面试指南及答案详解一、编程能力测试（5题，每题10分，共50分）1.题目：编写一个函数，实现快速排序算法，并分析其时间复杂度和空间复杂度。假设输入为一个整数数组，函数需要返回排序后的数组。答案与解析：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)时间复杂度：平均O(nlogn)，最坏O(n^2)；空间复杂度：O(logn)解析：快速排序通过分治法实现，核心是选择一个基准值（pivot），将数组分为三部分：小于基准值的、等于基准值的、大于基准值的。递归对左右两部分继续排序。平均时间复杂度为O(nlogn)，但最坏情况下（如已排序数组选择最左或最右为基准）会退化到O(n^2)。空间复杂度为O(logn)，主要由递归栈决定。2.题目：实现一个LRU（最近最少使用）缓存，支持get和put操作。缓存容量为固定值，超出时需要淘汰最久未使用的元素。答案与解析：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：LRU缓存的核心是维护一个有序列表记录访问顺序。get操作时，若key存在则将其移到末尾（表示最近使用）；put操作时，若已满则删除最久未使用的元素（即列表第一个元素），然后插入新元素。时间复杂度为O(1)。3.题目：给定一个二叉树，编写代码判断其是否为平衡二叉树（左右子树高度差不超过1）。答案与解析：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_balanced(root:TreeNode)->bool:defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)returnmax(left_height,right_height)+1,left_balancedandright_balancedandabs(left_height-right_height)<=1returncheck(root)[1]解析：通过递归计算每个节点的左右子树高度，若所有子树都平衡且高度差不超过1，则整个树平衡。时间复杂度为O(n)，空间复杂度为O(h)（递归栈深度）。4.题目：实现一个无锁（lock-free）队列，支持push和pop操作。假设使用Python，可借助原子操作库（如`queue.Queue`的部分特性模拟）。答案与解析：pythonfromcollectionsimportdequeclassLockFreeQueue:def__init__(self):self.in_queue=deque()self.out_queue=deque()defpush(self,item):self.in_queue.append(item)defpop(self):ifnotself.out_queue:whileself.in_queue:self.out_queue.append(self.in_queue.popleft())ifnotself.out_queue:returnNonereturnself.out_queue.popleft()解析：无锁队列通过双缓冲机制实现，一个入队队列（in_queue）和一个出队队列（out_queue）。pop时先尝试从out_queue获取，若为空则将in_queue元素转移至out_queue再出队。Python标准库无原子操作，此代码为简化模拟。实际工业级实现需依赖C++或Java的CAS操作。5.题目：编写一个函数，统计一个字符串中所有子串的出现次数。例如，输入"abcabc"，子串"abc"出现2次。答案与解析：pythondefcount_substrings(s:str,sub:str)->int:ifnotsub:return0count=0sub_len=len(sub)foriinrange(len(s)-sub_len+1):ifs[i:i+sub_len]==sub:count+=1returncount解析：暴力解法通过遍历所有可能的子串，与目标子串比较。时间复杂度为O(nm)，其中n是字符串长度，m是子串长度。实际面试可能要求优化（如KMP算法），但此题考察基础字符串操作能力。二、系统设计测试（3题，每题15分，共45分）1.题目：设计一个高并发的短链接系统（如tinyURL），要求支持高并发访问、快速生成与解析，并考虑分布式部署。答案与解析：核心组件：-短链接生成服务：采用哈希算法（如Base62编码）将长URL映射为短链接。-分布式缓存：使用Redis集群存储短链接与长URL的映射，支持快速读写。-负载均衡：通过Nginx或HAProxy分发请求到多个生成服务实例。-数据库：关系型数据库（如PostgreSQL）存储持久化数据，配合触发器或消息队列确保一致性。实现步骤：1.短链接生成：将长URL通过MD5+Base62编码生成6位短码（如"abcde"）。2.缓存查找：先查询Redis，命中则直接返回；未命中则查询数据库。3.分布式锁：使用RedisLua脚本确保短码唯一性。4.解析服务：反向映射短码到长URL，缓存结果以加速后续请求。优化点：-雪崩防护：对高频短链接使用本地缓存（如本地内存或Memcached）。-监控告警：集成Prometheus+Grafana，监控QPS、错误率等指标。2.题题：设计一个实时物流轨迹追踪系统，支持百万级车辆并发上传数据，并对外提供查询服务。答案与解析：架构设计：-数据采集层：车辆端通过MQ（如Kafka）上报轨迹数据（GPS、时间戳）。-处理层：-实时计算：Flink或SparkStreaming计算速度、停留点等衍生指标。-消息队列：分批发送数据至存储层，防数据丢失。-存储层：-时序数据库：InfluxDB存储原始轨迹数据（支持毫秒级查询）。-关系型数据库：存储车辆静态信息（车型、区域等）。-查询服务：-API网关：Nginx+JWT认证，限流防刷。-缓存层：Redis存储热门查询结果。-SQL引擎：ClickHouse聚合分析（如路段拥堵统计）。关键点：-容错性：Kafka多副本+ZooKeeper保证数据不丢失。-冷热数据分离：将高频查询数据预热到内存。-地理空间索引：使用R-Tree优化区域范围查询。3.题目：设计一个支持秒杀活动的商品库存系统，要求处理百万级并发下单请求，并保证库存准确。答案与解析：核心机制：-分布式锁：使用RedisCluster的SETNX命令，确保每件商品只有一个锁。-库存预减：通过消息队列（如RocketMQ）异步扣减库存，防超卖。-状态机：订单状态（待支付→已支付→已发货）通过数据库事务保证一致性。架构设计：1.请求入口：-流量削峰：Nginx配合Lua脚本验证验证码、验证IP冷热。-熔断限流：Hystrix或Sentinel防雪崩。2.库存服务：-Redis集群存储库存（每个商品1个key）。-Lua脚本实现原子性检查与扣减（如`IFEXISTSTHENDELkeyELSEreturn-1END`）。3.订单服务：-事务表：PostgreSQL的MVCC机制防脏读。-补偿机制：若扣减失败则重试或发送短信通知买家。优化点：-预热库存：活动开始前将库存数据加载到内存。-预付款校验：支付宝/Tenpay返回时立即锁定库存1分钟。三、系统运维与架构（2题，每题20分，共40分）1.题目：京东某核心业务系统突发流量导致CPU飙高，请分析可能原因并提出优化方案。答案与解析：常见原因：1.热点代码：某函数被频繁调用（如Redis缓存穿透）。2.长任务堆积：Celery队列任务执行缓慢。3.内存泄漏：未释放的连接或对象导致JVM/GC压力。排查步骤：1.监控定位：-Prometheus+Grafana查看CPU、内存、线程数。-JProfiler分析Java线程堆栈。2.优化方案：-代码层面：-缓存优化：对热点数据加互斥锁（如RedisPipeline）。-异步处理：将耗时任务转为消息队列（如RabbitMQ）。-架构层面：-弹性伸缩：K8s自动扩容Pod。-限流降级：熔断器隔离慢模块。2.题目：设计一个分布式ID生成方案，要求全局唯一、高可用、低延迟。答案与解析：方案对比：1.数据库自增ID：简单但单机瓶颈（如MySQL分表）。2.UUID：无中心节点但随机性高，存储开销大。3.Snowflake算法（Twitter开源）：分布式ID生成器。Snowflake实现：pythonclassSnowflakeID:def__init__(self,worker_id,datacenter_id,sequence=0):self.worker_id=worker_id&0xFFFF#5位self.datacenter_id=datacenter_id&0xFFFF#5位self.sequence=sequence&0x31#5位self.twepoch=1288834974657#时间戳起始点self.worker_datacenter_id_bits=10self.sequence_bits=5self.max_sequence=-1^(-1<<self.sequence_bits)self.worker_id_shift=self.sequence_bitsself.datacenter_id_shift=self.sequence_bits+self.worker_datacenter_id_bitsself.timestamp_left_shift=self.sequence_bits+self.worker_datacenter_id_bits+self.datacenter_id_shiftself.sequence_mask=1<<self.sequence_bitsdefnext_id(self):timestamp=self.time_millis()iftimestamp<self.last_timestamp:raiseException("Clockmovedbackwards.Refusingtogenerateid.")ifself.sequence==self.max_sequence:wait_millis=selftil_next_millis(self.last_timestamp)timestamp=self.time_millis()self.sequence=(self.sequence+1)&self.sequence_masks