2018 G氏實習電面經驗

標題裡面這麼多關鍵詞，應該很容易被搜到了吧。。。

前面都是廢話，想看乾貨，直接goto 乾貨；

之所以想寫這篇，也是因為之前在網上各種搜面經，結果就是九九八十一難之後還是不給你看，相對有用的就是一畝三分地，但它主要針對海外場，看了之後還是心慌慌。。。

先說一下我的結果－掛了掛了 掛了。。。下面直接上乾貨＋總結

乾貨：

直接上題吧～

我的兩道題：

1， 給定一個linked list, 如果有任何元素連續重複出現，則將該元素全部刪 除，舉栗：2->2->2->3->3->4->5 變成 4->5，因為2、3連續重複出現了，類似leetcode 82

2，給一個無序的int數組，找出所有逆序對，效率要求為O(n*lgn)，逆序對定義為pos i < pos j，數組中i位置的值卻大於位置j的值，舉栗：1, 4, 5, 9, 8, 1, 2 逆序對為{(4, 1), (4, 2), (5, 1), (5, 2), (9, 8), (9, 1), (9, 2), (8, 1), (8, 2)} 結果為9，據同學說也是leetcode原題，大家可以找一找

同學A的題：

1， 背包問題－一共有n個物品，每件物品價值為1或2，但重量可能不同，每件物品只能拿一次，給定總重量限制為W的前提下，求能取得的最大收益，題目很直觀，就不舉栗了，可以想下線性做法

2， 兩個字元串string str1, str2，均由字母和backspace構成，backspace即代表刪除前一個字元，求連個字元是否相等，舉栗 (假設代表backspace): "aacg" and "aa\adcg" 都是 "acg" 所以結果相等，想下線性方法（從後往前scan）

總結：

1，除博士生之外，想進G氏可能只有刷題了，據說是"最不care簡歷"的神奇存在（當然是指面試），直接寫代碼，因為是google doc，也很速食麵試官複製粘貼編譯嘍～（同學A說面完之後，看到自己的代碼被選中，估計下一步就是run了），所以一定不要存在僥倖心理，踏實刷題吧

2，先想出naive的方法說出來（這個時候就不要處女症啦），面試官會一步步引導你，注意和他們交流，不要只悶頭想

3，看官方面經說要把面試官當成幫助你的人，雖然有點雞湯，但能一定程度緩解緊張，聽聽也無妨

雖然電面掛了，但賊心不死的我還會參加校招，胖仙女去睡覺了，祝大家好夢～

未完待續。。。（後續也會把其他同學的面試題放上來）

———————— 分割線 —————————

被同學吐槽說標題太明顯。。。翻看HR郵件里確實是說不要泄露，所以低調一點吧。補充兩道題，前兩刀是同學B和C的一面（題目比較開放），後兩刀是同學A的二面（相對難一點）

同學B的題：

Given String mainText and an array of texts test[1], …, test[m] which have same length (<=6). Please check if texts are subsequence of mainText or not.

e.g. mainText="ababc", test=["aac", "acb"], return [true, false].

有熱心網友說是leetcode 792

同學C的題：

一個掃地機器人，如何探測房間里的所有room。。。（上這道題只是為了說明題目有可能很開放）

同學A的二面題（並不是onsite，是難度稍高的又一次電面）：

1，Given a dot separated string list. Each string has a label, good or bad. These strings forms a tree. Internal nodes has no label. Output the root node of the subtrees whose leaf nodes are all good, but not contained in a larger good subtree.

e.g. a.b.c good a.b.d good a.e bad a.f good

return {b, f}

我感覺就是遞歸，注意黑色加粗的條件，肯定得回到caller才能確定它的child是否滿足要求（例如a->b，得回到a的函數里才能確定b是否最大）

2， Given a set of banknote values (e.g. {「1」, 「5」, 「10」, 「20」}) and a target value V. You are asked to choose some backnotes (values can duplicate), such that all values from 1 to V can be made out of these banknotes. What is the minimum number of chosen backnotes.

e.g. {「1」, 「5」, 「10」, 「20」}，V = 47

「1」 x 4, 「5」 x 1, 「10」 x 1, 「20」 x 2 ->

answer is 8（貪心法）

現在終於知道每天我的時間都去哪兒了。。。

———————— 分割線 —————————

回答一下背包問題：

貪心法：把v=1和v=2的分成兩堆，分別按照weight從小到大排序，假設最後拿了X個v=1的物體和Y個v=2的物體，那麼這X個物體肯定是{v=1}中weight最小的，同理這Y個物體是{v=2}中weight最小的。整個問題可以抽象為線性規劃：

1，優先拿{v=2}的，最多拿到第j個（如圖）

2，從{v=1}中拿，如果放得下第i個，就直接放進去，否則，剔除{v=2}中的最後一個j(也就是weight最大的，貪心策略)，每次都計算一下當前的收益，並更新到目前為止的最大收益

推薦閱讀：