华为OD 技术综合面，手撕代码真题整理（75）：集合覆盖问题 | 最长递增子序列问题

ゝ一纸荒年。 2023-10-16 16:08 14阅读 0赞

### 华为 OD 面试环节：机考-综测-专业面-hr 面-主管面 ###

> 华为 od 手撕代码真题，每篇博客含 2 道真题，来源华为候选人反馈~

![华为OD 技术综合面，手撕代码真题整理（二八）：网络包调度 | 最小费用最大流问题][OD _ _]

### 什么是华为 OD，华为 OD 怎么样？ ###

OD，全名 Outsourcing Dispacth，中文 **外包派遣**。  
华为 19 年开始探索并实行新的研发“人力外包”模式，按正式员工标准进行招聘（话虽如此，实际要求没那么高），由业务部门负责培养和管理，解决更为核心的业务问题，对于绩效优秀且能力突出的人才提供转正式员工通道。

### OD 趋势 ###

由于传统的“项目外包”人员无法完成华为的可信认证代码提交，他们大量被释放出华为项目。此外，华为对招聘质量的要求也在提高。  
同时，由于外部经济环境持续不乐观和社招及校招 HC 紧缩等因素的影响，未来“招聘高质量的 OD 转华为”将成为一种确定性的常态。

### 华为 OD 基本介绍 ###

1.  人力外包签约方为德科/科锐国际，劳动合同期为 4 年，试用期 6 个月。
2.  员工关系、五险一金、考勤发薪由德科/科锐国际负责；定级定薪、员工培训、工作安排、绩效评比和晋升等由华为负责。
3.  工作关系与华为正式员工一起在华为研究所办公，工作内容基本没有差异。某些人可能因项目定位差异导致工作性质、学习资源和发展空间不同，但不存在核心非核心区别对待，主管和导师都是华为正式员工。
4.  薪酬福利薪资结构：
    
     *  基本工资+绩效工资+年终奖（2-4 个月，一般绩效 A-4 个月，B-2 个月）；
     *  D1-D5 分别对应华为 13-17 级，参考范围 10-40K；
     *  试用期内（6 个月）工资不打折，按 B 绩效发绩效工资，转正时重新评绩效，一般分 A、B、C 三档（主要 A 或 B，C 概率较小），和正式员工分开评，半年评一次；
     *  五险一金基数按基本工资，公积金比例 5%-12%，具体看 base 地。
     *  福利补贴：带薪年假、入职&年度免费体检、免费夜宵、班车/加班打车免费、下午茶、节假日礼品等。
5.  工作时间：
    
     *  上班时间为 8:0-9:00（弹性制），午休时间为 12:00-14:00，下班时间为 17:30-18:30（上下班时间一般跟所在项目组走）；
     *  一般一周中第一天需要补工时到晚上 20:30 左右，剩余四天正常时间下班（确保工时平均每天够 8 小时即可下班，工时不需补且无加班需要，自己灵活安排下班时间，重点看产出）；
     *  周末双休，月末周六固定加班双倍工资，其他因业务需求指令性加班情况，可申请加班费，按国家规定支付加班费。

> 华为云现在规定一个月周末加班不能 36 个小时，公司不让员工周末加班太多，很多同事基本周六都会选择加班，一个月加班工资就是大几千到一万多不等，这个还是想当可观的。

#### 两专业面试流程 ####

华为的 OD 面试通常包括两轮专业面试，如下所述：

**第一轮专业面试：八股+场景面试**

*  这一轮面试包括了两个主要环节：八股知识和实际场景问题。
 *  面试官会提问涵盖广泛知识领域的问题，要求你展示八股知识。
 *  你需要准备充分，以便在这一环节中表现出自己的专业知识。

**第二轮专业面试：编程实践**

*  在第二轮专业面试中，你需要进行编程任务。
 *  这个环节非常重要，要求你展示编程技能和优秀的编码习惯。
 *  请注意命名规范、良好的注释和清晰的思维过程，以帮助面试官理解你的代码。

整个专业面试通常需要约 1 小时，具体时长可能会根据面试官的要求有所不同。在准备期间，建议参考其他面试者的经验分享，以更好地了解面试的内容和期望。

### 华为 OD 手撕代码 ###

> 注意手撕代码题目，不提供题解，仅供大家学习使用~

### **题目 1：集合覆盖问题** ###

**场景描述：**  
假设你有一个需要覆盖的一维空间，以及一组开放区间。你需要选择最少数量的开放区间，以确保整个一维空间都被覆盖。请设计一个算法来解决这个问题。

**输入：**

*  一维空间的长度。
 *  一组开放区间，每个区间由其起始点和结束点表示。

**输出：**

*  选择的开放区间的最小数量。

**示例：**

输入：
    一维空间长度： 20
    开放区间： [(1, 5), (3, 8), (7, 12), (10, 15)]
    
    输出：
    最小数量的开放区间： 2

### **题目 2：最长递增子序列问题** ###

**场景描述：**  
给定一个整数数组，找到其中的一个最长递增子序列（不一定连续），并计算其长度。例如，对于数组 `[10, 22, 9, 33, 21, 50, 41, 60, 80]`，最长递增子序列是 `[10, 22, 33, 50, 60, 80]`，其长度为 6。

**输入：**

*  一个整数数组。

**输出：**

*  最长递增子序列的长度。

**示例：**

输入：
    整数数组： [10, 22, 9, 33, 21, 50, 41, 60, 80]
    
    输出：
    最长递增子序列的长度： 6

### 华为 OD 机试真题专栏订阅地址 ###

特别提醒，订阅专栏前一定要看好题解语言哦~

*  华为 OD 机考 **Python** [https://blog.csdn.net/hihell/category\_12199275.html][https_blog.csdn.net_hihell_category_12199275.html]
 *  华为 OD 机考 **C++** [https://blog.csdn.net/hihell/category\_12199283.html][https_blog.csdn.net_hihell_category_12199283.html]
 *  华为 OD 机考真 **C 语言** [https://blog.csdn.net/hihell/category\_12225286.html][https_blog.csdn.net_hihell_category_12225286.html]
 *  华为 OD 机考 **JAVA** [https://blog.csdn.net/hihell/category\_12201821.html][https_blog.csdn.net_hihell_category_12201821.html]
 *  华为 OD 机考 **JS** [https://blog.csdn.net/hihell/category\_12201825.html][https_blog.csdn.net_hihell_category_12201825.html]
 *  华为 OD 机考 **Golang** [https://blog.csdn.net/hihell/category\_12231589.html][https_blog.csdn.net_hihell_category_12231589.html]

[OD _ _]: https://img-blog.csdnimg.cn/341c40a7d75543db9b3e9d810e4bdab6.png
[https_blog.csdn.net_hihell_category_12199275.html]: https://blog.csdn.net/hihell/category_12199275.html
[https_blog.csdn.net_hihell_category_12199283.html]: https://blog.csdn.net/hihell/category_12199283.html
[https_blog.csdn.net_hihell_category_12225286.html]: https://blog.csdn.net/hihell/category_12225286.html
[https_blog.csdn.net_hihell_category_12201821.html]: https://blog.csdn.net/hihell/category_12201821.html
[https_blog.csdn.net_hihell_category_12201825.html]: https://blog.csdn.net/hihell/category_12201825.html
[https_blog.csdn.net_hihell_category_12231589.html]: https://blog.csdn.net/hihell/category_12231589.html