文远知行 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
这个太实际了 需要考虑的方面太多了 给了个思路 编码层面是搞不出了
对所障碍物调用辅助函数 得到所有的交点 去重 排序 挂载是相交线的入口还是出口 然后在一系列操作的去搞
投递美的集团等公司10个岗位