华为热设计工程师二面面经

二面

可能是我们聊的有点长了，第二个面试官进来了，第一个面试官道别后马上开始二面。当时头有点痛(就睡了 4 个小时)，自我介绍，介绍项目(拜远程面试所赐，面试官让我打开我答辩时候的 PPT 给他讲)，脑袋晕晕的思维有些混乱也算是他追问一句我就补充一些。然后问我学过的算法，我就按着算法四的目录开始说，说到树和图，就问我擅长哪一个？我说树吧，毕竟是有向无环图也算是子集了(瞎扯)，然后就手撕一道树算法题。题目是给一个遍历数组，问有可能是二叉搜索树的前序、中序、后序遍历还是不可能。写了个递归 O(N^2)O(N 2 ) 的版本(后来发现有线性时间单调栈版本的，感觉自己刷的是假题，现在还不知道线性版本的请马上去 lc 上学习相应题目，日后可以秀一下)。

写完口头检查过了之后，又打开了图那道题，说这个题你就谈谈思路。经典迷宫找具体最短路径的题，就是等权图上面有障碍物的，小图就 BFS 加 pre 数组就 okay 了，然后我最后嘴欠提了一句说这图要是大点就得用 A* 做了，面试官马上反问说你可以保障 A* 的打开节点数一定不多于 BFS 吗，当时没听懂他问的点，事后反应过来只要 h function 满足四个特性(consistent、admissible 等等，比如迷宫中的 manhattan distance)就可以保障性能是不弱于 BFS 的(我的解读见注1)。感觉面试官是有意的没有在难为我，没有往深处逼问。面完之后 12 点多，面试官客套地说你这个项目挺有意思的，我马上回复说跟您聊天也挺有意思的，他呵呵一笑说还行吧(我到现在也没想明白他是不是在敷衍我，毕竟我答的不算好)。

一个有意思的点是，面试官最后问我你有没有什么没有展示出来的特殊才能，我想了想感觉没有，自己没什么特别厉害的本事，就如实回复的没有，然后他说他以前搞了十年的无线如何如何，现在回想起来，大概是抢救性的询问一下是不是还有提高最终 offer 评级的空间？不知道，反正我感觉我没什么特殊才能，也就算了吧。

二面就这样结束了。