上周去美圖公司面試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匯編來提高效率

但實際上好像沒有這樣做

另外面試官還提到了用工具來分析代碼性能 我查了一下有不少開源實現

這個要關注一下。 原來的分段式分析耗時的方法還是比較落后 效率比較低一些。

總結

美圖的技術實力還是過硬的 原先參加過的面試 基本只問些項目相關的邏輯實現

這次面試問了不少基礎相關的問題 不少基礎沒打扎實 要研究清楚來。