软件工程师技术岗位面试题解

2026年软件工程师技术岗位面试题解一、编程实现题（共3题，每题20分）1.（20分）题目：编写一个函数`merge_sorted_lists`，实现将两个已排序的链表合并为一个新链表，且新链表依然保持排序。链表节点定义如下：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next要求：-输入：两个头节点`l1`和`l2`，分别指向两个排序链表。-输出：合并后的新链表头节点。-示例：输入：l1=[1,2,4],l2=[1,3,4]输出：[1,1,2,3,4,4]答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmerge_sorted_lists(l1:ListNode,l2:ListNode)->ListNode:dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<=l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextifl1:current.next=l1ifl2:current.next=l2returndummy.next解析：-使用虚拟头节点`dummy`简化边界处理。-双指针遍历两个链表，每次选择较小的节点接入新链表。-时间复杂度：O(m+n)，m和n分别为两个链表的长度。-空间复杂度：O(1)，仅使用常数额外空间。2.（20分）题目：实现一个函数`topKFrequent`，统计数组中频率最高的`k`个元素。要求：-输入：数组`nums`和整数`k`。-输出：一个包含频率最高的`k`个元素的数组。-示例：输入：nums=[1,1,1,2,2,3],k=2输出：[1,2]答案：pythonfromcollectionsimportCounterdeftopKFrequent(nums,k):count=Counter(nums)按频率降序排序，取前k个return[numfornum,freqincount.most_common(k)]解析：-使用`Counter`统计频率。-`most_common(k)`返回频率最高的`k`个元素。-时间复杂度：O(nlogn)，排序消耗主导。-空间复杂度：O(n)，存储频率计数。3.（20分）题目：实现一个函数`isValid`，判断一个字符串是否为有效的括号组合。要求：-输入：字符串`s`，包含`'('`,`')'`,`{'}`,`'}'`,`'['`,`']'`。-输出：布尔值，表示是否有效。-示例：输入：s="{[]}"输出：True输入：s="(]"输出：False答案：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack解析：-使用栈匹配括号。-遇到右括号时，检查栈顶是否为对应左括号。-时间复杂度：O(n)，遍历一次字符串。-空间复杂度：O(n)，栈最大深度为字符串长度。二、系统设计题（共2题，每题30分）1.（30分）题目：设计一个高并发的短链接系统（如tinyURL）。要求：-用户输入长链接，系统返回短链接。-短链接应具备唯一性和可访问性。-支持高并发访问。答案：核心方案：1.短链接生成：-使用自增ID或UUID生成唯一标识，如`62`进制编码（a-z,A-Z,0-9）。-示例：`1`转为`zY`。2.存储映射：-使用Redis或内存缓存存储`短链接<->长链接`映射，支持高并发读写。-若ID自增，可使用Redis的`INCR`命令原子操作。3.分布式部署：-通过负载均衡（如Nginx）分发请求。-使用分布式ID生成器（如Snowflake）避免冲突。4.访问穿透：-短链接访问时，先查缓存，若未命中则查数据库。-数据库使用分片或索引优化查询。伪代码示例：pythondefshorten(url):id=generate_unique_id()#如UUID或自增IDshort_code=encode62(id)store.set(short_code,url)return"/"+short_codedefredirect(short_code):url=cache.get(short_code)ifnoturl:url=db.query(short_code)cache.set(short_code,url)returnurl解析：-关键点：唯一性、高并发、可扩展性。-缓存可显著提升访问速度。-分区或分布式存储解决大数据量问题。2.（30分）题目：设计一个实时消息推送系统（如微信消息）。要求：-支持多客户端实时接收消息。-保证消息不丢失。-支持离线推送。答案：核心方案：1.消息队列：-使用Kafka或RabbitMQ存储待推送消息，保证顺序性和可靠性。2.客户端管理：-客户端登录时，服务器记录其WebSocket连接或长连接ID。-维护`用户ID<->连接ID`映射。3.实时推送：-推送时直接通过WebSocket或WebSocket协议发送。-若客户端离线，消息存入Redis或数据库，待客户端上线时补发。4.离线处理：-客户端定期心跳，服务器检测超时则标记为离线。-使用定时任务（如Cron）清理过期离线消息。伪代码示例：pythondefsend_message(user_id,message):conn_id=user_to_conn.get(user_id)ifconn_id:websocket.send(conn_id,message)else:queue.push((user_id,message))#存入消息队列defoffline_push():messages=db.query_expired_messages()foruser_id,msginmessages:send_message(user_id,msg)解析：-关键点：消息可靠性、低延迟、离线支持。-WebSocket保证实时性，队列防消息丢失。三、数据库与SQL题（共2题，每题25分）1.（25分）题目：假设有一个订单表`orders`：sqlCREATETABLEorders(idINTPRIMARYKEY,user_idINT,product_idINT,amountDECIMAL,order_timeTIMESTAMP);要求：-查询每个用户的订单总金额，按金额降序排列。答案：sqlSELECTuser_id,SUM(amount)AStotal_amountFROMordersGROUPBYuser_idORDERBYtotal_amountDESC;解析：-`SUM`计算总金额，`GROUPBY`按用户分组。-`ORDERBY`实现降序。2.（25分）题目：假设有一个用户表`users`：sqlCREATETABLEusers(idINTPRIMARYKEY,usernameVARCHAR(50),reg_timeTIMESTAMP);要求：-查询注册时间在2023年的用户数量，按月份降序排列。答案：sqlSELECTEXTRACT(MONTHFROMreg_time)ASmonth,COUNT()ASuser_countFROMusersWHEREEXTRACT(YEARFROMreg_time)=2023GROUPBYmonthORDERBYmonthDESC;解析：-`EXTRACT`提取年月，`WHERE`筛选2023年。-`GROUPBY`按月份分组统计。四、算法与数据结构题（共2题，每题25分）1.（25分）题目：给定一个整数数组，返回其中和为特定值`target`的“连续子数组”的个数。要求：-输入：数组`nums`和`target`。-输出：满足条件的子数组数量。-示例：输入：nums=[1,2,3],target=3输出：2（[1,2]和[3]）答案：pythondefsubarraySum(nums,target):count=0current_sum=0prefix_sums={0:1}#初始化fornuminnums:current_sum+=numifcurrent_sum-targetinprefix_sums:count+=prefix_sums[current_sum-target]prefix_sums[current_sum]=prefix_sums.get(current_sum,0)+1returncount解析：-前缀和+哈希表优化。-时间复杂度：O(n)，只需遍历一次数组。2.（25分）题目：实现一个函数`maxProfit`，计算买卖股票的最佳时机。要求：-输入：价格数组`prices`（第i个元素代表第i天的价格）。-输出：最大利润。-示例：输入：prices=[7,1,5,3,6,4]输出：5（买入1，卖出6）答案：pythondefmaxProfit(prices):min_price=float('inf')max_profit