创新工厂/涂鸦移动超详细面经（附答案）

辣条走起，原创不易~

前言

创新工厂/涂鸦移动，李开复创办的

笔试

我没有走提前批，走的秋招，笔试是对方给我发一份邮件，里面有一份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搜一下。