首页 > 文远知行 C++ 社招 技术二面
头像
穷人的代表
编辑于 2021-07-17 18:26
+ 关注

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

前几天刚说了简单,二面就给我整得不会了 😅😅
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   还没有被挡住的部分
这东西说实话 如果不是从事相关工作的还真不一定能在短时间内写出来 加上这个问题面试官描述的模模糊糊的 但是如果有工作经历或者论文经历肯定听到一半知道怎么做了 ,外行真的不行
很简单的问题就是 使用是什么坐标系都不清楚,二维还是三维的成像,
辅助函数可以返回线段的障碍物的交点
intersected_points



这个太实际了 需要考虑的方面太多了 给了个思路  编码层面是搞不出了
对所障碍物调用辅助函数 得到所有的交点 去重 排序 挂载是相交线的入口还是出口 然后在一系列操作的去搞


更多模拟面试

全部评论

(3) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐