文远知行 C++ 社招技术二面

技术一面：https://www.nowcoder.com/discuss/682724?source_id=profile_create_nctrack&channel=-1

前几天刚说了简单，二面就给我整得不会了 😅😅

1 面试官自我介绍

2 候选人自我介绍

我听起前面的面试官说你很能写啊 🤔 那这次加大难度吧结合实际工程应用开发代码哭了这哪会啊隔行如隔山啊....

再说了会武功也不是错啊ORZ

两个工程实际问题：

1 给你一段路线图，上面每隔一段有一个road_point，每个road_point挂载一个kappa值，求路线中的一段固定长度的区间中的road_point的最大kappa

我给了个滑动窗口的解法复杂度 mO(n) 面试官说不行还有没更快的我说优先队列logmO(n) ，还是不行最后探讨下来还有个什么最大队列可以做到O(n) 盲区了....

最大队列是剑指offer 59题看来多刷题还是有好处的

最大队列的所有操作都可以做到O(1) 的复杂度后来查了查原来当时自己没做出来就放弃了哈哈哈哈

#include <queue>
#include <vector>

//自定义数据结构
struct road_point {
	road_point(double kap) :kappa(kap) {}
	double kappa;


	//else 
};
//input
std::vector<road_point> road_path;


class MaxQueue {
public:
	MaxQueue() {}

	double max_value() {
		if (deque.size() == 0)
			return -1;
		return deque.front();
	}

	void push_back(double value) {
		queue.push(value);

		if (deque.size() == 0)
		{
			deque.push_back(value);
		}
		else if (value > deque.front())
		{
			deque.clear();
			deque.push_back(value);
		}
		else
		{
			while (deque.back() < value)
			{
				deque.pop_back();
			}
			deque.push_back(value);
		}
	}

	int pop_front() {
		if (queue.size() == 0)
			return -1;
		int res = queue.front();
		queue.pop();
		if (res == deque.front())
			deque.pop_front();
		return res;
	}

	std::queue<double> queue;
	std::deque<double> deque;
};

std::vector<double> func(std::vector<road_point>& road_path) {
	auto cmp = [](const road_point& a, const road_point& b) {
		return a.kappa > b.kappa;
	};

	if (road_path.size() < 10) {
		return { (double)(max_element(road_path.begin(), road_path.end(),cmp)->kappa) };
	}
	//使用最大队列
	MaxQueue max_queue;

	std::deque<double> dq;
	for (int i = 0; i < 10; i++) {
		max_queue.push_back(road_path[i].kappa);
	}
	std::vector<double> res;
	int size = road_path.size();

	int j = 9;
	while (j < size) {
		double max_ = max_queue.max_value();
		res.push_back(max_);
		max_queue.pop_front();
		max_queue.push_back(road_path[j].kappa);
		j++;
	}
	return res;
}

2 找出图中红色的线段也就是道路中的free_segment 还没有被挡住的部分

这东西说实话如果不是从事相关工作的还真不一定能在短时间内写出来加上这个问题面试官描述的模模糊糊的但是如果有工作经历或者论文经历肯定听到一半知道怎么做了，外行真的不行

文远知行 C++ 社招 技术二面

全站热榜

文远知行 C++ 社招技术二面