上周去美圖公司面試C++工程師 有兩位面試官

一位面試官問了一些數(shù)據(jù)結(jié)構(gòu)相關(guān)的問題 另一位面試官則問了一些項(xiàng)目相關(guān)的問題

交流比較順暢 和他們的交流也反饋給我一些信息 原來工作中有些地方可以做的更好

比如代碼的耗時(shí)點(diǎn)的評(píng)估

問到數(shù)據(jù)結(jié)構(gòu)時(shí) 面試官問了我這樣一個(gè)問題

1. 求兩個(gè)二叉樹的子節(jié)點(diǎn)的最低公共父節(jié)點(diǎn)？

這個(gè)問題當(dāng)時(shí)我是這樣回答的：遞歸向上尋找父節(jié)點(diǎn) 每一個(gè)父節(jié)點(diǎn)又各自向下遞歸尋找另一個(gè)要尋找的子節(jié)點(diǎn)。 這個(gè)做法無疑是低效的。面試官教我這樣一種方法：兩個(gè)子節(jié)點(diǎn)都向上遞歸到根節(jié)點(diǎn) 然后逐個(gè)驗(yàn)證兩條路徑中的每個(gè)節(jié)點(diǎn)是否是公有節(jié)點(diǎn) 直到尋找到最低節(jié)點(diǎn)。

這個(gè)方法明顯比我的要聰明不少，另外我查了些資料 其實(shí)這個(gè)問題還有其他解法

1. 中序遍歷

2. 后序遍歷

為什么可以用這兩種方法呢？

因?yàn)閮蓚€(gè)子節(jié)點(diǎn)的公共父節(jié)點(diǎn)必定在他們的中間！這是個(gè)容易得出的規(guī)律。

中序遍歷時(shí) 按順序遍歷 左 根 右節(jié)點(diǎn)

后序則是 左 右 根節(jié)點(diǎn)

按照這種方法可以大概圈定出公共節(jié)點(diǎn)的范圍 再采用遞歸尋找會(huì)快些。

2. 求最小的k個(gè)數(shù)

這個(gè)問題我是這樣答的：建立小頂堆 然后拿走堆頂節(jié)點(diǎn)后再調(diào)整堆為小頂堆

這樣的話開銷在于 第一次小頂堆的建立

后序每次小頂堆的重調(diào)整（開銷不像第一次建立那么大）

這一題面試官似乎不是很滿意答案 但是我回來想了下 網(wǎng)上能查到的還有用快排實(shí)現(xiàn)的

實(shí)際上也是用的遞歸快排 開銷也不低 這個(gè)問題可能還得再想想。

工程相關(guān)的問題：

1. 關(guān)于框架的跨平臺(tái)

這個(gè)問題主要也就是回答了下怎么把C++的框架代碼應(yīng)用到Android和ios上

關(guān)于Android方面的我熟悉一些 簡單講了下C調(diào)用Java，Java調(diào)用C的方法。

以及對(duì)應(yīng)的C++接口阻塞/非阻塞 Java監(jiān)聽C代碼的回調(diào)這些

ios就簡單介紹了下自己用過的Object-C/C++混合編程

2. 關(guān)于代碼的耗時(shí)點(diǎn)

這和我原來的想法有點(diǎn)不一樣

原來我認(rèn)為的優(yōu)化是通過在代碼里替換高IO代碼為arm匯編來提高效率

但實(shí)際上好像沒有這樣做

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

這個(gè)要關(guān)注一下。 原來的分段式分析耗時(shí)的方法還是比較落后 效率比較低一些。

總結(jié)

美圖的技術(shù)實(shí)力還是過硬的 原先參加過的面試 基本只問些項(xiàng)目相關(guān)的邏輯實(shí)現(xiàn)

這次面試問了不少基礎(chǔ)相關(guān)的問題 不少基礎(chǔ)沒打扎實(shí) 要研究清楚來。