首页 / 行业

美图面试C++工程师的经历

2019-06-26 16:55:00

上周去美图公司面试C++工程师有两位面试官

一位面试官问了一些数据结构相关的问题另一位面试官则问了一些项目相关的问题

交流比较顺畅和他们的交流也反馈给我一些信息原来工作中有些地方可以做的更好

比如代码的耗时点的评估

问到数据结构时面试官问了我这样一个问题

1. 求两个二叉树的子节点的最低公共父节点？

这个问题当时我是这样回答的：递归向上寻找父节点每一个父节点又各自向下递归寻找另一个要寻找的子节点。这个做法无疑是低效的。面试官教我这样一种方法：两个子节点都向上递归到根节点然后逐个验证两条路径中的每个节点是否是公有节点直到寻找到最低节点。

这个方法明显比我的要聪明不少，另外我查了些资料其实这个问题还有其他解法

1. 中序遍历

2. 后序遍历

为什么可以用这两种方法呢？

因为两个子节点的公共父节点必定在他们的中间！这是个容易得出的规律。

中序遍历时按顺序遍历左根右节点

后序则是左右根节点

按照这种方法可以大概圈定出公共节点的范围再采用递归寻找会快些。

2. 求最小的k个数

这个问题我是这样答的：建立小顶堆然后拿走堆顶节点后再调整堆为小顶堆

这样的话开销在于第一次小顶堆的建立

后序每次小顶堆的重调整（开销不像第一次建立那么大）

这一题面试官似乎不是很满意答案但是我回来想了下网上能查到的还有用快排实现的

实际上也是用的递归快排开销也不低这个问题可能还得再想想。

工程相关的问题：

1. 关于框架的跨平台

这个问题主要也就是回答了下怎么把C++的框架代码应用到Android和ios上

关于Android方面的我熟悉一些简单讲了下C调用Java，Java调用C的方法。

以及对应的C++接口阻塞/非阻塞 Java监听C代码的回调这些

ios就简单介绍了下自己用过的Object-C/C++混合编程

2. 关于代码的耗时点

这和我原来的想法有点不一样

原来我认为的优化是通过在代码里替换高IO代码为arm汇编来提高效率

但实际上好像没有这样做

另外面试官还提到了用工具来分析代码性能我查了一下有不少开源实现

这个要关注一下。原来的分段式分析耗时的方法还是比较落后效率比较低一些。

总结

美图的技术实力还是过硬的原先参加过的面试基本只问些项目相关的逻辑实现

这次面试问了不少基础相关的问题不少基础没打扎实要研究清楚来。