华OD-c++面经

22届非科班，自学c++，应聘的华为OD岗位，机考分数350分

笔试

【中】根据子数组和等分一维整数数组的最大组数

【易】二维矩阵的遍历

【难】字符串的数组的调整与下标修改，边界处理

技术一面

自我介绍

单片机项目

linux如何查看上一条命令？

Linux查询进程的命令？

介绍一下map？

红黑树的底层原理知道吗？
增加，删除，查询的时间复杂度？
红黑树有什么特殊的要求吗？

介绍下vector和list的区别和适用场景？

线程安全的实现？标准容器库的线程安全性？

C++ sort 的算法是怎么实现的？为什么要设置这几种排序？

除了上述的排序你还了解什么排序算法？基数排序的稳定性怎么实现的？

C++多态了解吗？简单介绍下它的实现原理和应用场景？

C++重载和重写了解吗？介绍下。

中等难度（面试官给出的难度定级）算法题，20分钟，涉及租金的最大利润，减除租金（索引）的一次遍历，算法不难，主要是想到减除租金的影响

还能优化吗？不可以，二分法的时间复杂度更低，但是数据没有二段性，最低需要将数据遍历一遍。

//终端某合作经销商遇到一个烦恼，由于下半年各平台的打折活动频繁，其终端商品价格具有一定波动性。经销商为了保证获取最大利益，将该商品在连续的K天内的价格记录在了数组prices中。经销商在某天（设为i）决定购入某商品，将它们存入仓库。并在另外一天（设为j），经销商将商品卖出（i<=j），同时他还需要付给该仓库j-i元的租金（每天租金为1）。此经销商请你帮忙判断一下基无现在的规则，最多可以赚多少利润，并输出。注：为了简化实现，整个过程只买卖一次。。
//示例1：输入：prices=[2，1，5]输出：3解释：最优策略是第二天买入，第三天卖出，租金为1，利润为5-1-1=3.
//示例2：输入：prices=[7，6，5]输出：0解释：最优策略是任意一天买入，当天卖出，利润为0.

int profit(vector<int>& price) {
    if (price.size() == 0) return 0;
	int ret = 0;
	int minval = price[0];
	for (int i = 0; i < price.size(); ++i) {
		if (price[i] - i <= minval) {
			minval = price[i] - i;
		}
		else {
			ret = max(ret, price[i] - minval - i);
		}
	}
	return ret;
}

技术二面

自我介绍
介绍下IO多路复用？
介绍下TCP/IP协议中的三次握手和四次挥手？
算法有练习吗？
中等难度算法题，时间15~20分钟，括号生成，递归实现的回溯法

//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//示例 1：
//输入：n = 3
//输出：["((()))", "(()())", "(())()", "()(())", "()()()"]
//示例 2：
//输入：n = 1
//输出：["()"]

vector<string> ret;
string rec;
void create(int n, int l, int r) {
	if (rec.size() == n * 2) {
		ret.push_back(rec);
		return;
	}
	if (l < n) {
		rec.push_back('(');
		++l;
		create(n, l, r);
		rec.pop_back();
		--l;
	}
	if (r < l) {
		rec.push_back(')');
		++r;
		create(n, l, r);
		rec.pop_back();
		--r;
	}
}
int main() {
	create(3, 0, 0);
	for (auto& str : ret) {
		cout << str << endl;
	}
}