无人车公司C++面试题（求讨论）

foreverzad

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

挂在这轮C++面试上了，求elegant的solution。我后来调出了用inheritance和vector<std::function>的方法，但都感觉不够好。大家讨论讨论。。。
/*
We are working on a batch image processing pipeline. We want to be able to list
the operations to be applied on all the images (and their parameters) in a
config file. For example:

ConvertToGrayScale
Blur 3.
Resize 256 256
BlendWith

The idea is to load the config file, create the pipeline, and process all the
images through the pipeline. We have access to a library for image manipulation
that has all the functions that we need for those operations.

How would you design such a pipeline?
This is intentionally vague, so part of the exercise is to define the scope.
Keep in mind that you have 30 minutes, so you are encouraged to first go for
a decently simple solution, and then discuss extensions.

In this case we will mock the behavior because we don't have IO, so basically
it should print:

one: Converting to gray scale
one: Blurring with factor 3
one: Resizing img with x = 256 and y = 256
one: Blending with

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限或查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

main() {
// Read the config file
vector<string> cmds = { "ConvertToGrayScale",
"Blur 3.",
"Resize 256 256",
"BlendWith " };

vector<Image> imgs = { Image("one"),
Image("two"),
Image("three") };

// Your work goes here

return 0;
}

magicsets

我觉得这个题目主要有两个注意点：
(1) 效率
(2) 可扩展性 (extensibility)

效率就是在创建pipeline时把能做的预处理都做了（主要是parse那些参数），这样你使用同一个pipeline处理不同的image的时候就不用做重复工作。

可扩展性就是说如果我们想要添加一个新的operation，只需要修改代码中很少的地方，而不是要东改一点西改一点。也就是说，代码要有低耦合度(low coupling)。

下面是一份参考代码——在这一实现中，如果要添加一个新的operation，那么不用修改已有代码，只要
(1) 继承并实现ImageTransformationHandle / ImageTransformationFunction规定的接口
(2) 用一行代码注册该operation：ImageTransformationPipeline::RegisterFunction<...>()

#include <algorithm>
#include <iostream>
#include <memory>
#include <sstream>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>
// Mock image class
class Image {
public:
Image(const std::string &name) : name_(name) {}
const std::string& name() const { return name_; }
private:
const std::string name_;
};
// Sample image manipulation library.
namespace ImgLib {
void convertToGrayScale(Image & img) {
std::cout << img.name() << ": Converting to gray scale" << std::endl;
}
void blur(Image & img, float factor) {
std::cout << img.name() << ": Blurring with factor " << factor << std::endl;
}
void resize(Image & img, int x, int y) {
std::cout << img.name() << ": Resizing img with x = " << x << " and y = " << y << std::endl;
}
void blend(Image & img, const Image& other) {
std::cout << img.name() << ": Blending with " << other.name() << std::endl;
}
/* Potentially many more! */
} // namespace ImgLib
////////////////////////////////////////////////////////////////////////////////
/////////////////////////////// Pipeline 组件抽象 ///////////////////////////////
////////////////////////////////////////////////////////////////////////////////
class ImageTransformationHandle {
public:
virtual void transform(Image &image) const = 0;
};
class ImageTransformationFunction {
public:
virtual std::string getName() const = 0;
virtual ImageTransformationHandle* generateHandle(std::istringstream &params) const = 0;
};
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////// Pipeline ////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
class ImageTransformationPipeline {
public:
ImageTransformationPipeline(const std::vector<std::string> &cmds) {
for (const std::string &cmd : cmds) {
std::istringstream iss(cmd);
std::string fname;
iss >> fname;
ImageTransformationFunction *func = FindFunction(fname);
if (func == nullptr) {
throw std::runtime_error("Invalid image transformation");
}
pipeline_.emplace_back(func->generateHandle(iss));
}
}
void transform(Image &image) {
for (const auto &handle : pipeline_) {
handle->transform(image);
}
}
void transform(std::vector<Image> &images) {
for (Image &image : images) {
transform(image);
}
}
private:
std::vector<std::unique_ptr<ImageTransformationHandle>> pipeline_;
// 为了简便把function resolving写在这里，其实最好再写一个class ImageTransformationFactory
static std::unordered_map<
std::string, std::unique_ptr<ImageTransformationFunction>> functions_;
static ImageTransformationFunction* FindFunction(const std::string &name) {
auto it = functions_.find(ToLowerCase(name));
if (it == functions_.end()) {
return nullptr;
} else {
return it->second.get();
}
}
static std::string ToLowerCase(const std::string &str) {
std::string ret(str.size(), ' ');
std::transform(str.begin(), str.end(), ret.begin(), tolower);
return ret;
}
public:
template <typename Function>
static void RegisterFunction() {
Function *function = new Function();
functions_.emplace(ToLowerCase(function->getName()), function);
}
};
std::unordered_map<std::string, std::unique_ptr<ImageTransformationFunction>>
ImageTransformationPipeline::functions_;
////////////////////////////////////////////////////////////////////////////////
/////////////////////////// Pipeline 各个组件的实现 //////////////////////////////
////////////////////////////////////////////////////////////////////////////////
// Convert to gray scale.
class ConvertToGrayScaleHandle : public ImageTransformationHandle {
public:
void transform(Image &image) const override {
ImgLib::convertToGrayScale(image);
}
};
class ConvertToGrayScaleFunction : public ImageTransformationFunction {
public:
std::string getName() const override {
return "ConvertToGrayScale";
}
ImageTransformationHandle* generateHandle(std::istringstream &params) const override {
return new ConvertToGrayScaleHandle();
}
};
// Blur.
class BlurHandle : public ImageTransformationHandle {
public:
BlurHandle(const float factor) : factor_(factor) {}
void transform(Image &image) const override {
ImgLib::blur(image, factor_);
}
private:
const float factor_;
};
class BlurFunction : public ImageTransformationFunction {
public:
std::string getName() const override {
return "Blur";
}
ImageTransformationHandle* generateHandle(std::istringstream &params) const override {
float factor;
params >> factor;
return new BlurHandle(factor);
}
};
// Resize.
class ResizeHandle : public ImageTransformationHandle {
public:
ResizeHandle(const int x, const int y) : x_(x), y_(y) {}
void transform(Image &image) const override {
ImgLib::resize(image, x_, y_);
}
private:
const int x_;
const int y_;
};
class ResizeFunction : public ImageTransformationFunction {
public:
std::string getName() const override {
return "Resize";
}
ImageTransformationHandle* generateHandle(std::istringstream &params) const override {
int x, y;
params >> x >> y;
return new ResizeHandle(x, y);
}
};
// Blend.
class BlendWithHandle : public ImageTransformationHandle {
public:
BlendWithHandle(const std::string &url) : other_(url) {}
void transform(Image &image) const override {
ImgLib::blend(image, other_);
}
private:
const Image other_;
};
class BlendWithFunction : public ImageTransformationFunction {
public:
std::string getName() const override {
return "BlendWith";
}
ImageTransformationHandle* generateHandle(std::istringstream &params) const override {
std::string url;
params >> url;
return new BlendWithHandle(url);
}
};
int main() {
// Read the config file
std::vector<std::string> cmds = {
"ConvertToGrayScale",
"Blur 3.",
"Resize 256 256",
"BlendWith http://www.solstation.com/stars/earth3au.jpg"
};
std::vector<Image> imgs = {
Image("one"), Image("two"), Image("three")
};
// Your work goes here.
// Register transformations.
ImageTransformationPipeline::RegisterFunction<ConvertToGrayScaleFunction>();
ImageTransformationPipeline::RegisterFunction<BlurFunction>();
ImageTransformationPipeline::RegisterFunction<ResizeFunction>();
ImageTransformationPipeline::RegisterFunction<BlendWithFunction>();
// Construct a pipeline instance from the commands.
ImageTransformationPipeline pipeline(cmds);
// Apply the transformations to imgs.
pipeline.transform(imgs);
return 0;
}

复制代码

foreverzad

太牛了~~这个C++功底深厚啊~~，还没看完但感觉满足了面试官所有的要求~

foreverzad

好像compile 报错了。。/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/unordered_map:546:11: error:
   no matching constructor for initialization of 'value_type' (aka 'pair<const key_type,
   mapped_type>')
      : __cc(std::forward<_Args>(__args)...) {}
      ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~

snmnmin

哇，你把这个贴出来来，我面这个题目时完全不知道怎么下手啊，顿时感觉C++学的太烂了，要仔细学习下答案。

magicsets

foreverzad 发表于 2017-12-4 13:45
好像compile 报错了。。/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain ...

编译时加上-std=c++14，然后试试第114行改成：

functions_.emplace(ToLowerCase(function->getName()),
std::unique_ptr<Function>(function));

复制代码

(从报错信息上来看似乎是这行代码问题，你可以把整个stack贴出来)

我也是用的xcode，可以编译通过的...

foreverzad

snmnmin 发表于 2017-12-4 14:19
哇，你把这个贴出来来，我面这个题目时完全不知道怎么下手啊，顿时感觉C++学的太烂了，要仔细学习下答案。

momo,我也挂了～～你最后去做无人车了吗？

foreverzad

magicsets 发表于 2017-12-4 14:28
编译时加上-std=c++14，然后试试第114行改成：(从报错信息上来看似乎是这行代码问题，你可以把整个stack ...

ok,谢谢啊，我回头再试试～～xcode我用得不多。。。所以不熟～～

bearjoe

aimotive, yaml file

bearjoe

or autosar manifest load

无人车公司C++面试题（求讨论）

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

本帖被以下淘专辑推荐:

评分

浏览过的版块

无人车公司C++面试题 （求讨论）

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

本帖被以下淘专辑推荐:

评分

浏览过的版块

无人车公司C++面试题（求讨论）