2025年华为校招留学生软件开发工程师真题机考笔试及答案

2025年华为校招留学生软件开发工程师练习题机考笔试及答案一、算法设计题题目描述：给定一个字符串`s`和一个模式串列表`patterns`（所有模式串互不相同且非空），判断是否可以通过拼接`patterns`中的若干不同模式串（每个模式串仅能使用一次）组成`s`。若可以，返回`true`；否则返回`false`。输入输出示例：-输入：`s="helloworld",patterns=["hello","world","hi"]`→输出：`true`（"hello"+"world"拼接成`s`）-输入：`s="helloworld",patterns=["hell","owo","rld"]`→输出：`false`（无法拼接）答案代码（Python）：```pythondefcan_construct(s:str,patterns:list[str])->bool:n=len(s)m=len(patterns)预处理模式串的长度和内容，按长度分组减少重复检查len_map={}foridx,pinenumerate(patterns):p_len=len(p)ifp_lennotinlen_map:len_map[p_len]=[]len_map[p_len].append((p,idx))存储（模式串，索引）回溯+记忆化：used是已使用模式串的索引集合，pos是当前s的匹配位置memo={}defbacktrack(pos:int,used:set[int])->bool:ifpos==n:returnTruekey=(pos,frozenset(used))不可变集合作为记忆化键ifkeyinmemo:returnmemo[key]遍历所有可能的模式串长度（当前剩余长度必须≥模式串长度）max_possible_len=n-posforp_leninlen_map:ifp_len>max_possible_len:continue检查所有该长度的模式串forp,idxinlen_map[p_len]:ifidxinused:continueifs[pos:pos+p_len]==p:new_used=used.copy()new_used.add(idx)ifbacktrack(pos+p_len,new_used):memo[key]=TruereturnTruememo[key]=FalsereturnFalsereturnbacktrack(0,set())```解析：本题核心是通过回溯搜索所有可能的模式串组合，同时利用记忆化优化重复子问题。关键点如下：1.预处理模式串长度：按长度分组，避免对每个位置重复遍历所有模式串，减少无效检查。2.记忆化状态设计：使用当前匹配位置`pos`和已使用模式串的索引集合`used`作为状态键，避免重复计算相同状态。3.剪枝优化：仅检查长度不超过剩余字符串长度的模式串，提前排除不可能的情况。二、编程实现题题目描述：设计一个实时统计模块，处理无限用户点击流数据（商品ID序列），支持查询最近`k`个点击中商品ID出现次数的中位数。要求：-滑动窗口大小固定为`k`，新点击加入时移除最旧的元素；-`add(intid)`方法：添加新点击的商品ID；-`getMedian()`方法：返回当前窗口内商品ID出现次数的中位数（若次数为偶数，取中间两个数的平均值）。输入输出示例：-输入：`k=3`，点击流`[1,3,2,4,5]`-首次添加后窗口`[1]`：无中位数（窗口未满）；-添加3后窗口`[1,3]`：无中位数；-添加2后窗口`[1,3,2]`：各ID次数为1（1、3、2各出现1次），中位数1；-添加4后窗口`[3,2,4]`：次数仍为1，中位数1；-添加5后窗口`[2,4,5]`：次数仍为1，中位数1。答案代码（Java）：```javaimportjava.util.;classMedianCounter{privateintk;privateDeque<Integer>window;//维护滑动窗口的顺序privateMap<Integer,Integer>freqMap;//记录ID的出现次数privateTreeMap<Integer,Integer>countMap;//次数到出现次数的映射（次数为键，出现次数的数量为值）publicMedianCounter(intk){this.k=k;this.window=newArrayDeque<>(k);this.freqMap=newHashMap<>();this.countMap=newTreeMap<>();}publicvoidadd(intid){if(window.size()==k){//移除最旧元素intoldId=window.pollFirst();intoldFreq=freqMap.get(oldId);//更新freqMap和countMapfreqMap.put(oldId,oldFreq-1);if(oldFreq-1==0){freqMap.remove(oldId);}countMap.put(oldFreq,countMap.get(oldFreq)-1);if(countMap.get(oldFreq)==0){countMap.remove(oldFreq);}if(oldFreq-1>0){countMap.put(oldFreq-1,countMap.getOrDefault(oldFreq-1,0)+1);}}//添加新元素window.addLast(id);intnewFreq=freqMap.getOrDefault(id,0)+1;freqMap.put(id,newFreq);//更新countMap：旧次数减1，新次数加1if(newFreq>1){countMap.put(newFreq-1,countMap.get(newFreq-1)-1);if(countMap.get(newFreq-1)==0){countMap.remove(newFreq-1);}}countMap.put(newFreq,countMap.getOrDefault(newFreq,0)+1);}publicdoublegetMedian(){if(window.size()<k){return-1;//窗口未满，无中位数（根据需求可调整返回值）}List<Integer>counts=newArrayList<>();for(Map.Entry<Integer,Integer>entry:countMap.entrySet()){intcnt=entry.getKey();intnum=entry.getValue();for(inti=0;i<num;i++){counts.add(cnt);}}Collections.sort(counts);//实际可优化为直接利用TreeMap的有序性intn=counts.size();if(n%2==1){returncounts.get(n/2);}else{return(counts.get(n/2-1)+counts.get(n/2))/2.0;}}}```解析：本题关键在于高效维护滑动窗口内商品ID的出现次数，并快速计算中位数。核心设计如下：1.滑动窗口管理：使用双端队列`window`记录点击顺序，确保添加新元素时能快速移除最旧元素。2.频率统计：`freqMap`记录每个商品ID的当前出现次数，`countMap`（基于TreeMap）记录“出现次数”的分布（如出现次数为2的ID有3个）。3.中位数计算：通过TreeMap的有序性，直接遍历键（出现次数）并展开为有序列表，快速定位中位数位置。三、系统设计题题目描述：设计一个分布式任务调度系统，支持百万级定时任务（如每天10点执行、延迟30分钟执行等），要求高可用、低延迟（触发误差≤100ms）、容错（节点故障时任务不丢失）。需说明核心组件、关键数据结构、任务分发策略及容错机制。设计方案：1.核心组件-任务存储层：使用分布式数据库（如TiDB）存储任务元数据（任务ID、触发时间、执行参数、状态（待执行/执行中/完成/失败）、重试次数等），按触发时间分区，支持快速范围查询。-调度控制层：主节点（Master）负责全局任务分配，从节点（Worker）负责执行任务。Master通过ZooKeeper实现主备选举，保证高可用。-时间轮组件：每个Worker节点维护分层时间轮（秒级、分钟级、小时级），用于高效触发即将执行的任务。时间轮类似钟表结构，每个槽位对应一个时间区间，任务根据触发时间放入对应槽位。2.关键数据结构-分层时间轮：-秒轮：60个槽位（0-59秒），精度1秒；-分轮：60个槽位（0-59分），每个槽位对应1分钟（含60个秒轮）；-时轮：24个槽位（0-23时），每个槽位对应1小时（含60个分轮）。任务插入时，根据触发时间计算其在时轮→分轮→秒轮的位置，逐层降级（如未来2小时15分的任务先放入时轮，时间接近时转移到分轮，最后到秒轮）。-任务队列：每个时间轮槽位关联一个阻塞队列，Worker定期扫描当前秒轮槽位的队列，取出任务执行。3.任务分发策略-负载均衡：Master统计各Worker的负载（当前执行中任务数、CPU/内存利用率），优先将任务分发给负载低的Worker。-就近执行：对有地域属性的任务（如用户所在区），分配至离用户最近的边缘节点Worker，降低执行延迟。-批量拉取：Worker主动向Master拉取任务（而非Master推送），减少Master压力，拉取量根据Worker剩余容量动态调整。4.容错机制-任务状态持久化：任务状态变更（如开始执行、失败）实时写入数据库，避免Worker故障时任务丢失。-心跳检测：Worker每30秒向Master发送心跳，超过3次未收到心跳则标