京东商城算法工程师面试题集

2026年京东商城算法工程师面试题集一、编程能力测试（共5题，每题10分）1.（10分）题目：实现一个函数，输入一个非空字符串，统计并返回字符串中所有字符的出现频率，并以字典形式返回。例如，输入`"hello"`，返回`{'h':1,'e':1,'l':2,'o':1}`。要求：-时间复杂度O(n)，空间复杂度O(1)（假设字符集固定）。-不使用内置的`collections.Counter`等工具。答案：pythondefcount_frequency(s:str)->dict:ifnots:return{}假设字符集为ASCII，初始化计数器counter=[0]128forcharins:counter[ord(char)]+=1转换为字典result={}foriinrange(128):ifcounter[i]>0:result[chr(i)]=counter[i]returnresult解析：-使用固定长度的数组（128个ASCII字符）存储每个字符的出现次数，避免哈希表的额外开销。-时间复杂度O(n)，空间复杂度O(1)（固定字符集）。2.（10分）题目：给定一个包含`n`个正整数的数组，设计算法找到数组中和最大的子数组（至少包含一个元素），并返回该子数组的和。例如，输入`[-2,1,-3,4,-1,2,1,-5,4]`，返回`6`（子数组`[4,-1,2,1]`）。要求：-时间复杂度O(n)，空间复杂度O(1)。答案：pythondefmax_subarray_sum(nums:list)->int:ifnotnums:return0max_sum=current_sum=nums[0]fornuminnums[1:]:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)returnmax_sum解析：-动态规划思想，维护两个变量：`current_sum`（当前子数组的最大和）和`max_sum`（全局最大和）。-每次遍历时，选择`num`或`current_sum+num`作为新的子数组起点。3.（10分）题目：实现一个函数，将一个二叉树的所有左子树替换为右子树，右子树替换为左子树。例如，输入二叉树`[3,9,20,null,null,15,7]`，输出`[3,20,9,null,null,7,15]`（二叉树的中序遍历）。要求：-不使用额外的数据结构，原地修改。答案：pythonDefinitionforabinarytreenode.classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefswap_tree(root:TreeNode)->TreeNode:ifnotroot:returnNone交换左右子树root.left,root.right=root.right,root.left递归交换左右子树swap_tree(root.left)swap_tree(root.right)returnroot解析：-递归遍历二叉树，交换每个节点的左右子树。-原地修改，不使用额外空间。4.（10分）题目：实现一个函数，判断一个字符串是否是有效的括号组合。例如，输入`"()[]{}"`，返回`True`；输入`"(]"`，返回`False`。要求：-使用栈结构，时间复杂度O(n)。答案：pythondefis_valid_parentheses(s:str)->bool:stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack解析：-使用栈存储左括号，遇到右括号时弹出栈顶并判断是否匹配。-如果栈为空或所有括号匹配，返回`True`。5.（10分）题目：实现一个函数，将一个字符串中的所有空格替换为`%20`。例如，输入`"Wearehappy."`，返回`"We%20are%20happy."`。要求：-时间复杂度O(n)，空间复杂度O(1)。答案：pythondefreplace_spaces(s:str)->str:双指针法：一个从后往前，一个记录替换后的位置s=list(s)#字符串不可变，转为列表write=len(s)-1read=len(s)-1whileread>=0:ifs[read]=='':s[write-2:write+1]='%20'write-=3else:s[write]=s[read]write-=1read-=1return''.join(s)解析：-双指针法：一个从后往前遍历，一个记录替换后的位置。-遇到空格时替换为`%20`，其他字符直接移动。二、算法设计题（共5题，每题10分）1.（10分）题目：京东商城的商品评论中包含大量文本，需要实现一个函数，输入一个评论列表，返回出现频率最高的`k`个关键词。例如，输入`["好评","性价比高","好评","物流快","好评"]`，`k=2`，返回`["好评","物流快"]`。要求：-时间复杂度O(nlogk)，空间复杂度O(n)。答案：pythonfromcollectionsimportdefaultdictimportheapqdeftop_k_keywords(comments:list,k:int)->list:frequency=defaultdict(int)forcommentincomments:words=comment.split()forwordinwords:frequency[word]+=1使用小顶堆维护前k个高频词heap=[]forword,freqinfrequency.items():iflen(heap)<k:heapq.heappush(heap,(freq,word))else:iffreq>heap[0][0]:heapq.heapreplace(heap,(freq,word))提取结果return[wordfor_,wordinsorted(heap,reverse=True)]解析：-使用哈希表统计词频，然后使用小顶堆维护前`k`个高频词。-时间复杂度O(nlogk)，空间复杂度O(n)。2.（10分）题目：京东的商品推荐系统需要根据用户历史购买记录推荐商品。给定一个用户购买记录的列表（每个记录包含用户ID、商品ID和时间戳），设计算法推荐最近的`k`个商品给该用户。例如，输入`[(1,101,1627836580),(1,102,1627836600),(1,103,1627836700)]`，`k=2`，返回`[(1,103,1627836700),(1,102,1627836600)]`（按时间降序）。要求：-时间复杂度O(nlogn)，空间复杂度O(n)。答案：pythondeftop_k_recommendations(records:list,k:int)->list:按时间降序排序records.sort(key=lambdax:x[2],reverse=True)returnrecords[:k]解析：-直接排序后取前`k`条记录即可。-时间复杂度O(nlogn)，空间复杂度O(n)。3.（10分）题目：京东的物流系统需要计算最优配送路径。给定一个起点、终点和多个配送点，设计算法找到最短路径（使用Dijkstra算法）。例如，输入起点`A`，终点`D`，配送点`B`和`C`，以及边权重`[(A,B,2),(A,C,4),(B,C,1),(B,D,5),(C,D,1)]`，返回最短路径`A->B->C->D`，总权重`8`。要求：-使用邻接表实现Dijkstra算法。答案：pythonimportheapqdefdijkstra(graph:dict,start:str,end:str)->(list,int):最短路径和前驱节点distances={node:float('inf')fornodeingraph}distances[start]=0predecessors={node:Nonefornodeingraph}heap=[(0,start)]whileheap:current_distance,current_node=heapq.heappop(heap)ifcurrent_distance>distances[current_node]:continueforneighbor,weightingraph[current_node]:distance=current_distance+weightifdistance<distances[neighbor]:distances[neighbor]=distancepredecessors[neighbor]=current_nodeheapq.heappush(heap,(distance,neighbor))重建路径path=[]node=endwhilenode:path.append(node)node=predecessors[node]path.reverse()returnpath,distances[end]解析：-使用Dijkstra算法计算最短路径，通过邻接表存储图结构。-时间复杂度O((E+V)logV)，空间复杂度O(V)。4.（10分）题目：京东的商品搜索需要支持模糊匹配。给定一个字典（商品名称列表）和查询词，设计算法返回匹配的商品名称。例如，输入字典`{"京东手机","华为手机","小米手机","苹果手机"}`，查询词`"手机"`，返回`["京东手机","华为手机","小米手机","苹果手机"]`。要求：-支持前缀匹配，时间复杂度O(nm)，其中`n`是字典大小，`m`是查询词长度。答案：pythondeffuzzy_search(dictionary:list,query:str)->list:results=[]foritemindictionary:ifitem.startswith(query):results.append(item)returnresults解析：-遍历字典，检查每个商品名称是否以查询词为前缀。-时间复杂度O(nm)，适用于小规模数据。5.（10分）题目：京东的优惠券系统需要根据用户购买金额计算可用的优惠券金额。给定一个优惠券列表（每个优惠券包含金额上限和对应折扣），设计算法返回用户购买金额`x`可用的最大优惠券金额。例如，输入`[(100,0.9),(200,0.85),(300,0.8)]`，购买金额`x=150`，返回`1500.9=135`（使用金额上限为100的优惠券）。要求：-优惠券按金额上限降序排列，时间复杂度O(n)。答案：pythondefmax_coupon_value(coupons:list,x:int)->float:按金额上限降序排列coupons.sort(reverse=True,key=lambdac:c[0])forlimit,discountincoupons:ifx<=limit:returnxdiscountx=limitdiscountreturn0解析：-从金额上限最高的优惠券开始计算，直到金额`x`小于当前优惠券上限。-时间复杂度O(n)，空间复杂度O(1)。三、系统设计题（共5题，每题10分）1.（10分）题目：设计京东商城的商品推荐系统，输入用户ID和当前时间，返回推荐商品列表。要求考虑用户历史购买记录、实时行为（如点击、加购）和热门商品。要求：-说明系统架构、数据存储方案和核心算法。答案：系统架构：1.数据采集层：-用户行为日志（点击、加购、购买）实时写入Kafka，使用Flink或SparkStreaming处理。2.特征工程层：-用户画像（购买偏好、历史行为）存储在Redis，使用HBase存储商品标签和热度数据。3.推荐引擎：-使用协同过滤（基于用户的商品相似度）和实时推荐（基于用户当前行为的Lambda模型），结合热门商品（TopN商品）。4.接口层：-使用SpringCloud构建微服务，通过APIGateway返回推荐结果。核心算法：-协同过滤：-基于用户的商品相似度计算（如余弦相似度），推荐与用户历史购买相似的商品。-实时推荐：-使用Lambda模型，根据用户当前行为（如加购）进行加权推荐。-热门商品：-TopN商品根据实时点击和购买数据计算。解析：-系统分层设计，兼顾实时性和离线计算。-推荐算法结合多种模型，提高推荐准确率。2.（10分）题目：设计京东商城的实时反作弊系统，输入用户行为日志（如下单、支付、登录），检测异常行为并触发风控措施。要求：-说明系统架构、数据存储方案和核心算法。答案：系统架构：1.数据采集层：-用户行为日志实时写入Kafka，使用Flink处理。2.规则引擎层：-使用Drools或Elasticsearch实时匹配反作弊规则（如短时间内高频下单）。3.风险评分层：-使用机器学习模型（如LSTM）计算用户风险评分，存储在Redis。4.风控执行层：-根据风险评分触发措施（如限制下单、拦截支付）。核心算法：-规则引擎：-预定义规则（如连续3次下单失败）触发告警。-机器学习模型：-LSTM捕捉用户行为时序特征，预测作弊概率。解析：-结合规则引擎和机器学习，兼顾实时性和准确性。3.（10分）题目：设计京东商城的秒杀系统，支持高并发下单场景。输入用户请求，返回秒杀结果。要求：-说明系统架构、数据存储方案和核心算法。答案：系统架构：1.流量分发层：-使用Nginx进行流量分发，防止单点过载。2.秒杀服务：-使用Redis进行库存扣减（Lua脚本保证原子性），防止超卖。3.订单系统：-使用MySQL存储订单数据，使用ShardingSphere进行分库分表。4.补偿机制：-使用消息队列（RabbitMQ）记录失败请求，