創新工廠/塗鴉移動超詳細面經（附答案）

• 2019 年 10 月 4 日
• 筆記

辣條走起，原創不易~

前言

創新工廠/塗鴉移動，李開復創辦的

筆試

我沒有走提前批，走的秋招，筆試是對方給我發一份郵件，裡面有一份word文檔，然后里面有兩道編程題，需要這份word文檔的後台回復 創新工廠

題目一

• 1.你能在多大程度上將一疊卡片懸置在桌子上？如果你有一張卡，你最多能創造半張卡片長度的懸置（假設卡片必須垂直於桌子）。使用兩張卡片，你可以讓頂部的卡片在底部卡片的基礎上懸置半張卡片的長度，且底部卡片在桌子上懸置1/3卡片的長度，這疊卡片的最大懸置長度一共為1/2 + 1/3 = 5/6卡片長度。一般來說，你可以讓n張卡片的懸空長度達到1/2 + 1/3 + 1/4 + … + 1/(n + 1)卡片的長度，即頂部卡片在第二張卡片的基礎上懸置1/2，第二張卡片在第三張卡片的基礎上懸置1/3，第三張卡片在第四章卡片的基礎上懸置1/4，以此類推，底部卡片會在桌子上懸置1/(n + 1)。正如下圖所示。

• 請實現函數 int number_of_cards(float length) 測試用例： 1.00 => 3 3.71 => 61 0.04 => 1 5.19 => 273

題目一解答

int number_of_cards(float length)  {      if(length <= 0)          return 0;      float i = (float)1.0;      float sum = (float)(1.0 / (i+1));      while(sum < length)      {          i++;//就是上面標註字體的實現，每次都加1/（i+1）,題目已經給出公式          sum = sum + (float)(1.0/(i+1));      }      return (int)i;  }

題目二

• 愛德華有1個包含N個整數的數組A，他定義1個數組的美麗值為數組中所有不同整數的和。現在愛德華想知道數組A的所有連續子序列的美麗值之和。
• 請實現函數： int beauty_of_array(int[] array) 測試用例 1 => 1 1, 2 => 6 1, 1, 2 => 11

題目二解答

int beauty_of_array(int[] array)  {      int sum = 0;      int length = array.length;      for(int i=1;i<=length;i++)//i代表子序列的長度從1開始最長是數組的長度      {          for(int j=0;j<array.length;j++)          {//j代表從數組的第幾個數開始找i長度個數，窮舉              Set<Integer> set = new HashSet<>();              int temp = j+i-1;//temp用來記錄從j下標開始，到i長度後的下標為止，比如i取2，也就是子序列長度是2，那麼temp就是j+2-1              if(temp >= array.length)                  break;//如果下標超過數組長度，break掉              for(int k=j;k<=temp;k++)                  set.add(array[k]);//由於是不重複的，加入集合              Iterator<Integer> iterator = set.iterator();              while (iterator.hasNext())//遍歷集合求和                  sum += (int)iterator.next();          }      }      return sum;  }

一面

電話面試，時長半個小時，全程沒問任何項目，一直在問基礎知識點。

• 1.自我介紹一下。 答：答：自我介紹是面試中唯一的自己主動介紹自己的環節，一定要好好把握好，你數據結構學的號可以手撕一個紅黑樹你就說我數據結構掌握地很好，反正就是要把自己的優勢凸顯出來，比如我是保研的以及對於java的知識較熟悉，我介紹完自己的本科經歷以後，我就說我是保送到本校繼續讀研究生，然後最末尾會加上自己熟悉java，然後面試官就會問java的一些東西；(自我介紹完，我以為要照例問我項目，但面試官沒有問,直接開始問我基礎知識點了）
• 2.java的幾種數據類型？ 答：Byte,short,int,long,float,double,boolean,char
• 3.每個位元組的電腦佔用的位數？
  • boolean/1
  • byte/8
  • char/16
  • short/16
  • int/32
  • float/32
  • long/64
  • double/64
• 4.java的這些位元組長度在不同平台會發生變化嗎？ 答：不會，一樣的
• int 和 Integer有啥區別？ 答：1、Integer是int的包裝類，int則是java的一種基本數據類型 2、Integer變數必須實例化後才能使用，而int變數不需要 3、Integer實際是對象的引用，當new一個Integer時，實際上是生成一個指針指向此對象；而int則是直接存儲數據值 4、Integer的默認值是null，int的默認值是0
• 5.然後接著問我，Integer i = 88; Intrger j = 88;比較（i==j）結果是什麼？ 答：true
• 6.那Integer i = 200;Integer j = 200;他兩呢？ 答：false;
• 7、為啥？原因知道嗎？說一下。 答：java在編譯Integer i = 100 ;時，會翻譯成為Integer i = Integer.valueOf(100)；，而java API中對Integer類型的valueOf的定義如下程式碼（我大致描述了一下）：IntegerCache.low的值是-128，IntegerCache.high是127，ava對於-128到127之間的數，會進行快取，所以出現上述的結果。
• public static Integer valueOf(int i) { if (i >= IntegerCache.low && i <= IntegerCache.high) return IntegerCache.cache[i + (-IntegerCache.low)]; return new Integer(i); }
• 8.然後接著問我，char可以存儲漢字嗎？ 答：我說可以。順便說了原因：char型變數是用來存儲Unicode編碼的字元的，unicode編碼字符集中包含了漢字，所以，char型變數中當然可以存儲漢字。如果某個特殊的漢字沒有被包含在unicode編碼字符集中，那麼，這個char型變數中就不能存儲這個特殊漢字。
• 9.然後問我了我電腦網路的知識，https是什麼？ 答：https是在http的基礎上加了ssl，實現了傳輸過程的加密。
• 10.ssl的加密原理是什麼？ 答：我說了ssl是基於RSA原理的加密保證安全，然後說了RSA的握手協議。1.RSA握手協議 第一步，Client給出協議版本號、一個客戶端生成的隨機數（Client random），以及客戶端支援的加密方法。 第二步，Server確認雙方使用的加密方法，並給出數字證書、以及一個伺服器生成的隨機數（Server random）。 第三步，Client確認數字證書有效，然後生成一個新的隨機數（Premaster secret），並使用數字證書中的公鑰，加密這個隨機數，發給Server。 第四步，Server使用自己的私鑰，獲取Client發來的隨機數（即Premaster secret）。 第五步，Client和Server根據約定的加密方法，使用前面的三個隨機數，生成」對話密鑰」（session key），用來加密接下來的整個對話過程。
• 11.RSA原理說一下？ 答：這裡大家如果不懂RSA就在ssl加密原理那裡說RSA的握手協議了，直接把那5步說一下也行。這個RSA由於我本科資訊安全的，經常接觸，所以基本可以把下面的步驟說一遍。 RSA演算法的步驟主要有以下幾個步驟： 1、選擇 p、q兩個超級大的質數 ，都是1024位， 2、令n = p * q。取 φ(n) =(p-1) * (q-1)。 計算與n互質的整數的個數。 3、取 e ∈ 1 < e < φ(n) ，( n , e )作為公鑰對，正式環境中取65537。可以打開任意一個被認證過的https證書，都可以看到。 4、令 ed mod φ(n) = 1，計算d，( n , d ) 作為私鑰對。 計算d可以利用擴展歐幾里的演算法進行計算 5、銷毀 p、q。密文 = 明文 ^ e mod n ， 明文 = 密文 ^ d mod n。利用蒙哥馬利方法進行計算，也叫反覆平方法，非常簡單、 其中（n,e）是公鑰 （n,d）是私鑰
• 12.TCP和UDP的區別講一下 答：主要答了以下幾點。如果自己熟悉擁塞控制，可以把其中的每一塊都詳細說一下。

• 13.TCP三次握手說一下。 答：就是下面這個圖片了，要是現場面試，下面這個圖片，我可以手畫出來，這個必須理解地背下來。

• 14.為什麼要用三次握手，不是兩次呢？ 答：這裡我說了之前的一個連接請求，由於網路阻塞已經被發送端放棄了，然後過了一段時間被接收方收到了，接收方直接就建立了連接，白白浪費了資源。詳細版可以把下圖背下來。

• 15.然後問了我七大排序中，的最好最壞時間複雜度？ 答：就是下圖了，這個得背了，經常問。我沒說基數排序，這個不太了解。

• 16.接著問我，哪些是穩定，哪些是不穩定？ 答：說了歸併，冒泡，插入穩定，其它不穩定。
• 17.接著問了我兩道演算法題，如何判斷鏈表中有環？ 答:我說使用快慢指針，快的每次走兩步，慢的每次一步，看看是否相遇。
• 18.接著問我，如何判斷兩個鏈表是否相交？ 答：先分別求鏈表長度，哪個長久用哪個先進行遍歷長度差的長度，然後在一起遍歷，如果相等，那麼相交。

有一些問題忘了，大體上問的問題都很基礎。

二面

電話面試，時長半小時，感覺創新工廠很卡時間，時間一到，立馬結束面試。面試官讓我準備好紙和筆，然後問了我兩道動態規劃的題目。

• 自我介紹 答：還是上面那些。
• 問我了解動態規劃嗎？ 答：我大體說了動態規劃就是把問題拆分成一個個小問題，然後求狀態方程。
• 然後考了我一道劍指offer的題，連續子數組的最大和。 答：我說思路就是用一個tempmax代表前面的連續數字的最大和，如果這個最大和是正的，那麼加上數組的當前數字，那麼這個連續的和是變大的，這個就是有可能的潛在的最大和。
• import java.util.*; public class Solution { public int FindGreatestSumOfSubArray(int[] array) { if(array.length <= 0) return -1; int realMax = array[0]; int currentMax = 0; for(int i=0;i<array.length;i++) { if(currentMax + array[i] >= array[i]) { currentMax += array[i]; }else{ currentMax = array[i]; } if(currentMax > realMax) realMax = currentMax; } return realMax; } }
• 然後他感覺我沒用動態規劃方程，他說你這個沒有用動態規劃做，然後又給我出來一道動態規劃的題目。

由於這個時間太久遠了，這道題目具體是啥，實在想不起來了，只記得當時我強行套狀態方程，把思路說了一下，然後面試官最後給我講了一下這道題的思路，最後面試就結束了。

hr面

印象中沒有hr面，二面結束然後過了一天通知我面試通過了，然後發了offer，當時看到創新工廠開的offer，還是很吃驚的，感覺相對於其他互聯網公司真的有點少，具體薪資大家可以去offershow搜一下。