hulu面经

   2013年5月17号参加hulu前端面试，面试时间为下午1点，走进hulu就能看见一个会议室的门上贴上了一个印有你名字的白纸，表示这间会议室是你面试的地点，很人性化，也标志hulu对任何一个面试者的重视。

     一面：1点面试开始，首先是一个年轻的面试官。hulu面试早就听说会是各种算法，果然如此，即使是前端面试。面试官gg首先是问了一下我做的项目，balala。然后就是算法面试。第一道题，给出一个整数序列，判断他是否是二叉排序数的后续遍历。首先我给的算法是，假设它是正确的后续遍历，且知道二叉排序数的中序遍历是该整数序列的递增序列，所以解法是看能否找出矛盾，面试gg说他不太清楚我这种做法能不能求解，希望我能给出一个不要利用额外空间，在原有的整数序列上判断是否正确，又是一段思考后，我又给了一个nlogn的解法，面试官gg表示很满意，并让我在纸上写好代码，代码似乎也没什么问题。然后问我如果给我o（n）的空间复杂度这道题能不能优化，想了一会，面试官gg也给了一些提示，不过本人很笨，没有想出解法。然后是第二题，题目是给出因子为3，5，7至少一个的第k大的数，想了半天，面试官gg也给了提示，表示不会做，只好第三题，题面是给定一个n*n的二维数组，数组条件，二维数组的行是递增的，列是递增的，且整数都不重复，然后给一个数判断这个数是不是在二维数组中，因为之前有看过这道题，便很快给除了解法。然后时间差不多了，面试官gg说在给你一道题，看看能不能5分钟做出来，两个人A，B仍硬币，A扔n次，B扔n+1次，A x次正面朝上，B y次正面朝上，问x>y的概率是多少，想了大概5分钟，没有想法后，面试官gg表示，算了，这道题给的时间太短，怪我了。

     二面：然后就是二面了，二面也是一个面试官gg，看一面没有逻辑推理题，就说那问我一道简单的逻辑推理题吧，不过现在我也没觉的那题简单，题目是这样的，给100个白球，100个黑球混在一起，每次取两个，如果取出的颜色相同，就放回一个黑球，如果取出的颜色不同就放回一个白球，求最后剩黑球的概率。这题一出来我就没感觉是个简单题，想了有一会，面试官哥哥给了提示说可不可以把它变成一种模型，提示很有用，瞬间就有了想法，将黑球用0表示，白球用1表示，这样抽象出的模型就是100个0和100个1，两两异或，最后结果是0，说明最后剩下黑球的概率是1，我说了我的解法，似乎与面试官gg的解法不太一样，简单给了我他的想法，不过最后说恩，还可以，然后这题就过了。下一道题仍是一道算法题，给一个整数数组，求出这个数组绝对值和最小的连续子序列，然后说这道题和网上常考的求子数组最大和的那道题很像。我想了一会，然后面试官gg问我有没有思路，我说和求子数组最大和的思路差不多，每次遇到正的就舍弃，负的留下，面试官gg问我你觉的这个思路可行吗，说完我就瞬间意识到不可行，我说最笨的就是n（n2）穷举每个连续子数组，当然我知道这道题肯定是能优化的，所以一直在想优化的方法，面试官gg提示，因为题目要求是连续的，你看看能不能通过这个条件把原有问题转化一下，想了想没有思路，然后面试官gg接着提示，既然是连续就可以用一个大数组的和减去一个小数组的和就能得到剩下连续数组的和了，这个让我突然想起算法导论DP那章求矩阵相乘最少次数那道题，于是向面试官说了自己的想法，用DP解决，面试官想了想说那你这其实还是o(n2)的解法，我想了想也是，于是接着想，面试官gg很nice，接着提示我，你可以将这个连续数组用另外一个数组表示，一趟遍历就能构造这个数组，然后他又在纸上给我写了公式，这样这道题就转化成了求一个数组任意两个数之差的绝对值最小，然后我想了想只要nlogn的时间复杂度排序一下，然后用n遍历，就能找出来，最后的时间复杂是n+nlogn，面试官很赞同，说让我在纸上好好写一下，这道题要拿出去，于是我先打草稿，然后非常整洁，小心翼翼的写到了准备拿出去的白纸上，最好检查了一下，确定没有bug，就教给了面试官gg，然后面试gg说咱们休息一下，你要不要上洗手间，那个我说要，然后去了趟洗手间，回来就是三面了。

     三面：三面仍就是一个面试官gg，上来就问了下我简历上的实习，看我曾在BAT上都实习过的经历，似乎很感兴趣，又简单问了下项目，我给他讲了一个从头到尾差不多都是我一个人写的项目，因为项目已经上线，就用他的电脑展示给他看了看，给他讲了讲需求，他说这个挺好的，然后接着仍然是算法题，第一道题两个有序的数组，如何找出两个数组合并后的第K大的数，很快我就给了一个o(k)的解法，似乎面试官gg也知道我能很快给出这个解法，并马上问我能不能优化，我说在优化的话只能是o(logk)了，他说恩，于是我就朝着这个方向想，参考二分查找的思想，简单给他讲了讲一个我不成熟的思路，似乎方向是对的，但是和他讨论了一下，没有什么太大的进展，他说那这道题就算了，我们换一道题，题目是一个人知道未来n天的每天股票的价格，请你给出一个算法，使得这个人从哪天买入，哪天卖出能获得最大的收益。这道题转化一下就是求数组后面的数减去前面的数的差最大，如何找到这个两个数，o(n2)的做法就不说了，想了一会我和他说可以把数组分成两部分，每次取出前部分的最小值，是o(1)解法，后半部分取最大值，因为每次后半部分都要缩小，所以可能把最大值删掉，可以将后半部分变成堆，这样每次取最大值就变成o（1），但是每次要用一下维护堆的那个算法，时间负责度为o(logn),所以总的时间负责度为o（nlogn），然后用一个max的变量表示每次获得的最大值，面试官gg很满意，说答案就是o(nlogn)，剩下的时间就是问我如何评价BAT这三家公司，为什么要跳槽一下话题了，说了很多，然后就说你等一下，我问一下hr有没有什么问题然后hrmm就进来了，问我有没有什么问题，我就问了下hulu和美国那边有没有项目一起在做，有没有可能去美国那边交流学习，hrmm耐心的给我讲了很多。然后我接着问hulu每次的技术交流都是在清华，北大，有没有考虑去其它学校做技术交流讲座，hrmm说今年hulu将陆续在北邮，北航等学校开展活动，我听了还是很欣喜的，然后hrmm说我们会尽快出结果，然后在约manager面试。

    总结：就这样hulu的第一次面试结束了，不管结果怎样hulu的面试正如我想的那样非常有难度，学到了很多东西，要知道我应聘的是前端工程师，但是没有问我一点前端问题，希望有面试hulu的同学，看到我的面试经历会有帮助。
   
    最后：5月20号中午如我所料的收到了hulu的Thank you letter。不过自己已经很满足了，知道自己还有很多东西要学，找工作是个艰难的过程，需要自己踏踏实实的准备，耐心的总结每一次面试失利的原因，并及时弥补，最后祝愿每一个2014年毕业的同学都能收到自己满意的offer。