Seeker的奇妙求職曆險（位元組跳動三面）

位元組跳動三面

• 前言
• 面試開始
• • 代碼混淆的原理
  • Binding的原理
  • DLL的原理
  • JVM類加載
  • 雙親委派機制
  • 兩個Java程序運作在同一個JVM上嗎？
  • 共享記憶體的原理
• 算法題
• • 數組的最大子數組和
  • 數組的K個元素最大子數組和
  • 要求保持相對順序
• 閑聊
• 後記

前言

7月22日晚上8點鐘，我進行了位元組跳動用戶端的第三次面試。說實話，在面試開始之前我還是有點忐忑不安的，走到最後一面了就感覺格外緊張，根據隔壁同學面試的經曆反複刷了二叉樹的疊代周遊和各種排序的遞歸和疊代方法（隔壁是實驗室的同學三面問了二叉樹的疊代中序周遊），不過最後并沒有用上。

面試開始

面試官稍微遲到了一小會，簡單寒暄過後，就開始了正式的面試。

他首先問我，你C#和Java哪個更加擅長一些？

我回答說Java。

然後他就開始問我關于C#桌面開發相關的内容。

代碼混淆的原理

因為之前開發過桌面端的項目，在代碼被人反編譯之後，我就給桌面端的釋出版本進行了代碼的混淆，當時用的是一個VS下的免費的代碼混淆，是以最後隻是對變量名、方法名進行了一個替換，使得代碼的可閱讀性變得很差，對于原理其實我并不清楚。

是以，當我回答到這裡的時候，面試官其實不太滿意。

後來我查閱了一下資料，發現常用的代碼混淆技術有如下幾種：

• 混淆方法名和變量名：最簡單的，隻是降低了代碼的可讀性，還會造成DLL連接配接的錯誤。
• 常量展開：把一些指令的立即數對其進行展開，說白了就是常量折疊的反面。
• 恒等運算：把

  nor reg32

  之類的指令轉化為

  xor reg32,-1

• 模式替換：用執行結果相同的指令進行替換，可以多次重複。
• 插入死代碼：僞造出一些不會執行的死分支，比如在執行的時候進行條件判斷柯西不等式，如果為真則執行真代碼。這樣的代碼也可以讓人摸不到頭腦。
• 虛拟機技術：把一部分代碼重新編譯，并且打包解釋器程序式，運作的時候動态解釋執行。
• 打亂代碼順序局部性：改變部分代碼塊之前的排序。
• 特殊的控制流模糊化：強行觸發異常，然後在異常處理的handle中将程式設定為正常的狀态。

參考文章：https://zhuanlan.zhihu.com/p/46247049

Binding的原理

既然做過WPF項目，那麼肯定用到了Binding技術（聽說這還是一個WPF首創的技術），那麼你了解Binding的原理嗎？

我說，我們項目是這麼用的，巴拉巴拉，但是原理我不太清楚，我猜測他是一個監聽者模式，當資料發生變化的時候會發送消息給前端頁面，這樣就達到了一個實時更新的功能。

原理：

　一個最簡單的Binding就是把A的屬性綁定到B的屬性上，當B的屬性變化時，A的屬性可以自動更新。這個Binding分兩層含義：

A需要監視B屬性的變化，當B屬性變化時A得到通知。

當收到變化通知時，A要根據B的屬性新值來設定自己的屬性值。

關于監視B屬性變化，這是一個經典的Observer模式，在.net中用event 來表示，如：

b.PropertyChanged += a.HandlePropertyChanged;
void HandlePropertyChanged()
 {
    a.Prop = b.Prop;
 }
           

關于PropertyChange事件，.net在System.ComponentModel裡提供INotifyPropertyChanged接口，裡面定義了event PropertyChangedEventHandlerPropertyChanged。通常可被用于資料綁定Model類都要實作INotifyPropertyChanged接口，在屬性變化時raise這PropertyChanged事件。

參考文章：https://www.cnblogs.com/umlchina/articles/2067723.html

DLL的原理

你用過DLL嗎？知道原理嗎？

答：不太清楚。

原理：

靜态連接配接庫就是把(lib)檔案中用到的函數代碼直接連結進目标程式，程式運作的時候不再需要其它的庫檔案；動态連結就是把調用的函數所在檔案子產品（DLL）和調用函數在檔案中的位置等資訊連結進目标程式，程式運作的時候再從DLL中尋找相應函數代碼，是以需要相應DLL檔案的支援。

靜态連結庫與動态連結庫都是共享代碼的方式，如果采用靜态連結庫，則無論你願不願意，lib 中的指令都全部被直接包含在最終生成的 EXE 檔案中了。但是若使用 DLL，該 DLL 不必被包含在最終 EXE 檔案中，EXE 檔案執行時可以“動态”地引用和解除安裝這個與 EXE 獨立的 DLL 檔案。靜态連結庫和動态連結庫的另外一個差別在于靜态連結庫中不能再包含其他的動态連結庫或者靜态庫，而在動态連結庫中還可以再包含其他的動态或靜态連結庫。

參考文章：https://www.cnblogs.com/AI-Algorithms/p/3725696.html

JVM類加載

可能他看我C#掌握的不太好，于是就開始問Java相關的内容。

首先問了我你知道類是怎麼加載的嗎？

答：五個階段，每個階段幹了什麼大緻說了一下。

雙親委派機制

雙親委派機制了解嗎？有哪些類加載器？為什麼要這麼做？

答：原理，責任鍊模式、4種加載器，保證加載出來類的唯一性，然後詳細說了說。

兩個Java程序運作在同一個JVM上嗎？

其實這個問題我确實不知道，但是我回答說我覺得應該不是，從作業系統層面來說兩個使用者級程序應該是互相不可見的，而且JVM書上的記憶體分布中隻有一個堆，而不是若幹個不同程序的堆，是以我覺得應該是一個Java程序一個JVM。

然後查了一下也确實如此。

共享記憶體的原理

剛才你說到記憶體分布對吧，那共享記憶體你用過嗎？

我說我沒有用過，但是原理我還是知道的，就是兩個程序各自拿出一部分虛拟記憶體映射到同一塊實體記憶體，這樣兩個程序就可以對同一塊實體記憶體進行操作。

算法題

到這裡大概問了二十多分鐘，他說我們來做一道簡單點的算法題吧。

數組的最大子數組和

給出一個數組，求這個數組中元素的最大和的子數組。

輸入：

[1,2,-3,4,5,-6]

輸出：

[1,2,4,5]

我心想：這好像有點簡單，不是把所有的正數加起來嗎？

數組的K個元素最大子數組和

當我說了我的想法之後，他說很好，那我再加一個限制條件，要求是K個元素的最大和。

輸入：

[1,2,-3,4,5,-6]

和

k=2

輸出：

[4,5]

我說我想把數組進行排序，然後取前K個不為0的正數，這樣的時間複雜度是o(nlogn)。

要求保持相對順序

他說，好的，那我再加一個限制條件，要求子數組的元素相對順序不變。

輸入：

[1,2,-3,4,5,-6]

和

k=2

輸出：

[4,5]

而不能是

[5,4]

到這裡感覺這道題目就有一些難度了，我思考了一會之後，說了我的想法：

保持一個滑動視窗，當一個新的正數進來之後，移除最小的一個正數，然後把這個元素後面的元素都向前移動一格，然後把新的元素放在最後一格上。

這樣的話時間複雜度比較高，最壞的情況是每次都要移動，是以是一個o(nk)的時間複雜度。

他說那你還能進行優化嗎？然後提示我用o(2k)的額外空間可以降低複雜度。

最後他看我實在想不到，說你實在不行就用hashmap儲存一下數組下标。

那我說：首先儲存數組中所有正數的下标，然後排序，取前k個數，然後再對結果數組按照下标排序，這樣的話，時間複雜度是(nlogn+klogk)。

面試官覺得我可能實在是想不到了，就說，那你能用代碼把你剛才說的任意一種方式實作一下嗎？

就寫了最後一種方法的代碼，用Arrays.sort和lambda表達式寫的，是以大概幾分鐘就寫完了。

不過後來我想了想，其實用hashmap儲存下标的方式不可行，因為當數組中有重複元素的時候會導緻排序出錯。

比如:

[5,2,3,-4,5,-6]

和

k=4

，這樣最後由于hashmap會覆寫掉原來的下标導緻最後的結果是

[2,3,5,5]

而不是

[5,2,3,5]

。是以我到現在都還不知道最好的解法是什麼。

感謝陶總給出的最優解，我陶總一槍秒了，有什麼好說的。

開辟了一個2n的二維數組用于儲存原來的值和下标，然後對值進行排序，然後選取前k個，最後再按下标排序，由于是數組是以不存在重複問題。

public static void fun1(int[] arr, int k){
    int[][] nums = new int[arr.length][2];
    //儲存原來的值和下标
    for (int i = 0; i < arr.length; i++) {
        nums[i][0] = arr[i];
        nums[i][1] = i;
    }
    //按值排序
    Arrays.sort(nums, ((o1, o2) -> (o2[0] - o1[0])));
    int[][] sout = Arrays.copyOfRange(nums, 0, k);
    //按下标排序
    Arrays.sort(sout, (o1, o2) -> (o1[1] - o2[1]));
    for (int i = 0; i < sout.length; i++) {
        System.out.print(sout[i][0] + " ");
    }
}
           

閑聊

寫完代碼之後，問了我項目中遇到過最大困難是什麼?

最近在學校裡忙嗎？主要在幹什麼？

後記

總的來說這次面試其實感覺自己發揮的不太好，面試官也說我用過的東西居然不知道原理。

其實說實話我并沒有想到會問我C#的東西，是以我并沒有準備，之前做項目的時候也确實不求甚解。不過吃一塹長一智，履歷上寫的東西和技術一定要知道其原理。之後的面試中也會對履歷内容進行壓縮，然後把一些核心技術的原理給搞明白。

最後，其實我剛面試完的時候面如死灰，感覺這次應該是真涼了，但是沒想到第二天上午hr小姐姐告訴我面試通過了，人生的大起大落來的有一些快。

不過還是不能停止學習的腳步，是以說不要停下來啊。