Snapchat Onsite

Snapchat(15)
36 Valid Sudoku 30.5% Easy
39 Combination Sum 30.9% Medium
44 Wildcard Matching 17.4% Hard
96 Unique Binary Search Trees 37.4% Medium
127 Word Ladder 19.6% Medium
140 Word Break II 19.7% Hard
146 LRU Cache 15.8% Hard
151 Reverse Words in a String 15.7% Medium
155 Min Stack 22.0% Easy
161 One Edit Distance 28.4% Medium
206 Reverse Linked List 39.4% Easy
269 Alien Dictionary 22.9% Hard
270 Closest Binary Search Tree Value 34.3% Easy
289 Game of Life 34.2% Medium
314 Binary Tree Vertical Order Traversal 30.3% Medium

面经题

• Minimum Window Substring (Sliding Window 经典题)
• Group of Friends (3) - Union - Find : 发现matrix[j] == 1 就union两人在一`起，最后遍历parent数组找独立的subset个数即可
• Meeting Room I : 简单的排序，根据meeting的开始时间升序排，从做到右找 meetings.end 和 meetings[i+1].start 有没有overlap
• Meeting Room II (2) : 难一点的排序，start 升序排，用heap排end时间，从头遍历meetings，冲突就开一个新room，否则merge两个meeting的时间
• Meeting Room III : room带有weight怎么排能出最大的weight ？？？？？？
• Game of Life (2) : LC-289主要注意的是不要直接修改cell上的数，否则会影响之后的计算。
• Valid Palindrome : two pointers经典
• Detect Cycle in a Directed Graph : Union-Find / DFS / BFS
• One Edit Distance : LC-72 : 注意两个词相同的时候返回false
• Reconstruct Itinerary: LC-332 : Backtracking
• Copy List with Random Pointer : LC-138
• Remove digits from a number to construct lowest number LC-402

  public class Solution {
    public String removeKdigits(String num, int k) {
        if(num == null || num.length()==0 || k==0) return num;
        if(num.length()<=k) return "0";
        char[] digits = num.toCharArray();
        int len = digits.length;
        Stack<Character> stk = new Stack<>();
        int cnt = k;
        for(int i=0;i<len;i++){
            while(!stk.isEmpty() && stk.peek() > digits[i] && cnt>0){
                stk.pop();
                cnt--;
            }
            stk.push(digits[i]);
        }
        StringBuilder rst = new StringBuilder();
        while(!stk.isEmpty() && stk.size() + k > len) stk.pop();
        while(!stk.isEmpty()) rst.append(stk.pop());
        while(rst.length()>0 && rst.charAt(rst.length()-1) == '0') rst.setLength(rst.length()-1);
        return rst.length() == 0 ? "0" : rst.reverse().toString();
    }
  }
  

• Valid Sudoku
• Sudoku Solver
• Find Minimum Path between two points in a matrix with walls : 给定起点和终点，找到从起点到终点的最短路径，如果走不通则返回-1。 BFS Follow up :墙可以打破 求最小COST
• Edit distance into Palindrome (对string 和它的 reverse 做Edit distance 左下到右上对角线的值的min 如果是奇数则取对角线和对角线上下一个格的最小值）
• Is prime number
• Count Primes : LC-204
• Pow(a, b) : LC-50

  public class Solution {
    public double myPow(double x, int n) {
        if(n==0) return 1.0;
        double half = myPow(x,n/2);
        if(n%2==0){
            return half*half;
        }else{
            return n<0 ? 1/x*half*half : x*half*half;
        }
    }
  }
  

• Sqrt(x) : LC-69
• Number of Islands I (2)
• LRU Cache
• Burst Balloon
• Word Pattern I
• Word Pattern II (2) Backtracking 暴力解 用hashmap维护当前的mapping, hashset判断是否重复
• 给一个数组，求index使得该index左侧和右侧sum相等。
• House Robber : LC-198, DP
• Combination Sum IV : DP = Sum(DP[i-nums[j]] for all nums[j] <= i)
• Word Finder : 给一个字典，chat, ever, snapchat, snap, salesperson, per, person, sales, son, whatsoever, what, so 找出所有非复合词， 比如snapchat = snap + chat。
• Log Parser (2) :problem1 prob
• Course Schedule II (2)
• Implement TreeMap
• IPFilter : 一定要注意字符串到binary string之间的转化，非常容易出BUG
• Delete Kth node from a Linked List from back : LC -19 Dummy node + two pointers
• Multiply Strings : 遵循乘法的概念可解 开一个m+n长度的array 从后往前乘
• Implement Queue using Stack LC-232 : 维护两个stack, 一个用来input另一个用来Output
• Word Break
• Reverse Words in String : 翻转整个string再翻转每一个单词
• BigInt + - * (N)
• Evaluate String
• Repeated DNA Sequence
• Frog jump
• Find Duplicate number (3) HashSet, Sort, Binary Search
• Word Ladder I / II
• Coins in a Line II
• Construct tree from Inorder & preorder
• Min Stack
• 走迷宫，给起点终点 和一些墙问能不能从起点走到终点 DFS 第二题 单词加复数形式
• Reverse integer
• Least Important Boss : LCA的变形版本
• Binary Tree Vertical Traversal : LC-314 BFS 2 Queues
• Basic Calculator (3)
• N Queues (3)
• 构建BST
• Amicable Number
• ZigZag print (3)
• Substring Anagram (3)
• 24点游戏
• k-snap point BFS
• Build Tree from given string input and print it inorderly
• Reverse Linked List
• Excel Column Conversion LC-168 LC-171 注意从数字转到字符串的时候要先-1再%26得到当前位置的字母
• BST ZigZag Traversal LC-103 s
• Symmetric Tree Iterative
• Closest BST Value LC-270
• Closest BST Value II

Onsite

Onsite 1

一轮

• 3 sum
• Design: 然后问如果有一个web based的email app，打开的latency很高，应该怎么办，如何test哪个部分， 如何Improve. 如果有准备过what happened after type an URL，因为没有太大问题，无非就是按照那个过程，DNS, proxy server, cache(这是重点)

二轮

• closest point.
• 我们有一个data sets, 然后有一个graph是类似10 * 10的grid,写一个function, input是一个query point，求出离它最近的点，brute force是每个点distance求一下，后来改成了类似quad tree分成四个area的做法.

三轮

• snap with weights, snap has next snaps list
  input是(start snap, max steps)求出一个max total weights
  BFS的方法做就可以.
  follow up: start snap是一个list怎么办
  follow up: 如果每个snap都可以是start snap怎么办， memorization search

四轮

• valid bypart: bypart的意思就是一个图里，value只能是0或1，相邻的都是与自己不同的就是一个valid bypart
  Bipartitle
• buy and sell stock I

Onsite 2

第一轮

• 白人小哥白人shadow，project diving deep, coding题目是queue using stack, follow up 是多线程版本，最后让我自己实现mutex那些，自己写测试，问了我如何设计测试等等。

第二轮

• 东欧大叔，project diving deep, 题目是手机上的通讯录，每条记录只有(name, number)这种pair,有些记录名字重复，有些记录号码重复，让我返回一个list<list<Record>>，将所有记录按人分组。比较tricky的点在于(ABC,123), (ABC, 456), (BCD, 456)三条记录，第一条和第三条也属于同一个人。要求时间复杂度尽量小。(hashmap，<name, array index>, <number, array index>)

第三轮

• 美国小哥，how to test. why snapchat. coding题目是XML parser，follow up是一开始我们假设xml是well-formatted,如果不是的话，比如有不成对出现的

  或者

第四轮

• 中国小哥，project deep dive. coding 题目是有一条路，路两边可以想象为 y = 0 和y = 1两条直线。现在给你list of radar，每个雷达为(横坐标，纵坐标，辐射半径)。问你一辆车能否通过这条路。这轮一开始没见过有点懵逼，感谢小哥给了提示。

Onsite 3

1. word search, product of array except self.
2. implement bloomfilter, construct, add, mightcontain, delete, extend(if near full, extend)(Using Bitset)
3. 两个人从1-N里面不重复地取数出来加在同一个sum上，第一个超过target的人赢，求先手是不是能赢。 写的暴力recursive(flip game II)
4. repeated DNA sequences, leetcode 原题
5. XML parser, build a map to represent XML given tokenizer.Next() -> (open,name), (inner,content), (close,name), 就是一个 tree transversal given a string, return whether can use the character to construct target string, 裸hashmap(stack)

Onsite 4

一轮

• 大概在1：15的时候，开始了我的第一轮面试。这一轮是一个美国人，反正听起来像是美国人。问了我第一个intern proj。出了个2Sum，3Sum，4Sum，稍微不一样的是，需要找出第一个pair，triplet。。。。第一个的定义随便你，可以是按pair里小的或者大的index取，比如按小的取[1,2,3,4]，target=5,那么返回[1，4]，因为1 < 2。基本都是瞬间给出答案。 就是4SUM的时候受到面试大哥的提示，才给出了O(n2)的解法

二轮

• 问了我第二个intern proj。 开始想出Bigint，我说已经在电面做过了。 然后他就另外出了一个找最大值的题。给一个数组[1,1,2,1]，然后用+ * （）三个操作求出这个数组的最大值，这个题返回6。 很简单，DP解决。我开始写了个用res[i][j] 表示的solution，然后写完代码，测了几个用例，都过了。然后他问如果数组里面有负数和0咋办呢。 我说维护两个表max[i][j] 和 min[i][j]。然后他很满意。我说其实还有复杂度更低的方法，可以用一位数组做。他说不用了，这个方法已经够好了，不要求写那么复杂。 然后面完还有10分钟，他问我有什么问题没有，我一听慌了，连时间都没有用完是不是不好，我就问他这个是不是没面好的征兆。他说不是不是，因为我已经很快给出solution，而且代码也没有问题，还给出了follow up的思路，就够了，说有时候时间没用完也是面的好的表现。 我听完心里放松了一些，然后和他唠了唠team之间的工作什么的，只是为了把时间耗完。

    public int maxValue(int[] nums){
        if(nums==null||nums.length==0) return 0;
        int len = nums.length;
        int[][] DP = new int[len][len];
        for(int i=0;i<len;i++) DP[i][i] = nums[i];
        for(int i=1;i<len;i++){
            for(int j=0;j<len-i;j++){
                for(int k=j+1;k<j+i+1;k++){
                    DP[j][j+i] = Math.max(DP[j][j+i],DP[j][k-1]+DP[k][j+i]);
                    DP[j][j+i] = Math.max(DP[j][j+i],DP[j][k-1]*DP[k][j+i]);
                }
            }
        }
        return DP[0][len-1];
    }
  

三轮

• 然后一上来就出了一道twitter系统的设计，幸亏我之前准备过system design，而且在其他面经上也看到别人提到过这个，然后给他讲了讲各个方面的设计。 比如消息推送的机制，push和poll。还有怎么样用hybrid方法。 然后他笑了，说对对对，我们现在snapchat就是这么干的。这个题好像答得还挺好的。聊的也不错。 然后我以为就结束了，但是还有10分钟的时间。他就说我们来coding吧，请听题，“树上一只猴，地下七只猴。。。”，串了串了。。。然后让我coding一个单机的web 服务器的消息处理机制。 我先说如果是单机的话，就不用考虑scale的问题。说了好多乱七八糟的system design的问题，但是他不是这个意思。后来搞了两三分钟才讲清楚是要实现一个类。说当访问量大的时候，怎么handle request，我说线程池。 他说yes， that's what i want。 然后其实就是实现线程池类。我不知道是怎么实现的，自己想了一个方法。然后说了思路，但是还没把代码写完，第四个面试官就开始用木头桩子撞门，额，轻轻地敲门。然后中东小哥说再给5min，第四个面试官说ok。然后这个题关键的是要用到wait和notify方法以避免繁忙等待。 我说了思路，最后还是没有时间写代码了。弄完他问我有没有什么问题，我说我没有写完这个代码会不会有影响，他说不会，反正solution你已经知道了。然后说完握手扬长而去。留下一个华丽的身影。 搜push 和poll机制，然后到时候被问到了，记得考虑两种结合起来，也就是hybrid的思想。

四轮

• 面试官进来了，他是director，进来就开始behavior question，我边答他边敲键盘，感觉超级忙得样子。然后我看他好像太忙，自己发起话题说我有好多snapchat改进的点子，还有一个new feature thought。 他说good，那就是他接下去要问得，让我说。我花了15min讲了这些东西，过程中他比之前要更投入了，还不时的记录我的点子。好像挺感兴趣的样子。说完之后，他说要不我们来个coding吧，我说 cao！ 好吧！。 然后问我知不知道non attacking queue problem，我问这是n皇后问题吗，他说是的，问我做过没有，我说以前写过。然后他说ok，给你一个n，我需要你把所有情况打印出来。我说好，这不就是n皇后吗。他说恩，你是第一个说什么什么什么的面试者。没听懂，我只是笑笑。应该是说我是第一个说这个题做了，还问他是不是确定要出这个题的人。 然后我用iteractive写了个DFS，然后把isvalid和print两个函数独立出来，让代码模块化和增加可读性。 写完一遍过， 他看了看输出，让我walk through代码，我就给他讲，怎么回溯，怎么迭代，感觉他反应不是特别快，我讲完代码结构，还一行一行的给他解释，他看完后说这个解法有意思。。。。。。。。然后让我输出按我这种解法出来8皇后的解的个数。 也就是92，我输出来，对了。 然后他就说有没有什么问题问他，问了个可不可以选team的问题，然后我就说没有问题了，因为我太他马累了。 他很惊讶说，ok，笑笑的跟我握手，带我到main building里面见了HR。
• n-queen
• n-queen II

HR问了我有么有其他offer deadline，其他面试，还问我如果给offer， snapchat会排在第几（我说至少第一吧）。。。。然后说offer只给一周时间考虑，明天就给你答复，我说我cao这么杰宝快，他说恩，我们的pace很快的。我说好的，然后就回家了。

面试之前被内推我的帅哥提醒代码命名要规范，不要int i temp什么的，我写的时候特别注意，虽然有点不习惯，但还是避免了这个坏习惯。希望大家也能注意。

Onsite 5

先被一个人带着去食堂吃了午饭，聊聊了mobile development，带我的是一个加拿大的intern。人挺nice，我感觉我好老＝ ＝。吃完饭就去面试，四轮，一轮一小时左右。自己带着自己的电脑，可以自己选择在白板上写或者在自己电脑的eclipse上写。那个房间的白板太小，我四轮都选择在我的ide上写的。

（1）一个有8年微软经验的中国人面的，感觉他是个神牛啊，anyway，先问我好多project的东西，然后我做过os的project，就详细问了问memory，heap什么的。这个半小时过去了，然后写code。让我写了个binary search，很快写出来了，然后就是一大堆的follow up。。。让我自己想test cases，然后怎么test code。。不知道他是不是bar raiser。

（2）一个刚入职半年的sde面我，上来让我做个自我介绍，然后让我做leetcode上面的一道题：给preorder和inorder(hashmap 存 下标索引)，重建bst。好久没刷过这题了，当时想了想还是用递归做出来了。然后给他解释，自己写了test case，最后问了问复杂度。。

（3）一个白人小哥，很活泼，问了问实习和之前的项目和machine learning，因为我的android的项目里面用到了machine learning。然后写code。wiki一下amicable pair就知道了。给一个数n，返回所有amicable pair，要求pair中第一个数小于第二个数，然后问了问复杂度。

（4）最后一轮也是个美国人，他感冒了，有些萎靡不振，跟我说话显得很低迷，让我自我介绍之后就写code。在一个8*8的棋盘上给两个坐标和一个integer k，返回一共有多少种不同走法，走k步从一个坐标到另一个坐标。用dfs，然后问复杂度。然后follow up怎么降低复杂度。

最后出去的时候跟hr聊了聊，问了我都面过哪些公司了，然后有没有deadline，说这几天就会告诉我结果。然后说snapchat不会有offer extension，而且就给两周时间考虑。 以上给大家做参考，顺便攒下人品，保佑我拿到offer啊。。。也祝大家找工作顺利！

Onsite 6

1. 给一个数组，判断里面是否有duplicate。扩展1，判断是否有相隔较近的duplicate。扩展2，判断是否有相隔较近的，作差不超过某个上限的数对。
2. 给一个dictionary，两个单词。求最短的以这两个单词为首尾的单词链，使得每两个相邻的单词都恰好有一个字母不同。这个是在电脑上写的，需要compile需要写test case。
3. 给手机的画图app写个屏幕旋转的method。同样问了许多design问题。
4. 设计一个比较简单的Google doc。同样是design向的问题。 HR chat就是简单聊一下，问问喜不喜欢Snapchat之类的问题。面完之后当晚说下周电话答复，目前还等结果中。

Onsite 7

1. word ladder 1 和 返回一条路经
2. xml parser
3. dulplicated nums 返回是否有重复数字 follow up 是否有重复数字相距小于k 和 如何解决网页打开慢
4. steam nums 返回 median

Onsite 8

onsite很大部分时间是聊简历和behavior question

1. 白人， 聊简历和背景 snapchat中的一个应用为背景，扯了很久，最后意思就是一段视频中有一些可以放广告的位置，长度不同，有一堆可以选的广告，长度也不同，问怎么放最多和最长的广告
2. 国人，聊简历和背景 snapchat的一个应用，拍视频时可以对视频进行处理比如变形，加各种表情装饰等，问怎么实现这个系统，这轮不用coding，纯design， 这哥从头到尾一直板着脸都没怎么笑过，答得不如他意的时候就拿着手机让我玩那个app应用感受感受，看着自已头像心中一万头草泥马奔过，我这特么的是来面试的还是来玩应用的啊
3. 白人，聊简历和背景 实现一个buffer管理系统，不断的存入图片，图片大小不同，然后另一边不断的读出图片，类似于实现一个blocking queue, 但是要求底层实现，连list都不能用
4. 不知道哪国人，看起来像亚裔， 继续聊简历和背景 给一个string abbcba 按字符出现的频率编码，b->1, a->01, c->001，输出编码后的串 snapchat discover/moment 的一个应用抽像出来的，怎么判断发monment所属在自己的圈子里，就是相当于给一个多边形，怎么快速找到一个点在不在多边形里

不知道是因为我工作了几年，简历问得很细， 都是提前看了简历带着问题来问的，每个人都会问为什么想来snapchat，以及对snapchat的看法。最后都有10分钟左右问问题。 另外感觉比较重视test case, 电面要求编译通过并跑了基本所有可能testcase， onsite也要写testcase而且漏了会指出来 最后挂了，没给feedback，问了内推的朋友说可能我做的太底层了（EE背景），anyway, 只能move on了

Onsite 9

1. 有一个外国字典，里面的字母都不认识，随机抽出足够的单词，让你重构字母的顺序。拓扑排序解
2. 有一个task stream with value，实现一个class with member function 可以求出过去10s 的平均值，最大值，最小值。每个task生成按时间顺序。注意window是时间10s，不是task个数。 queue/deque解
3. 任意没有排序的数组，求第三小的数，求中值，求第k大的数
4. 安装程序 with dependecies，求出任一正确的安装顺序，follow up 求出安装顺序但是需要dependecies少的程序先安装(拓扑排序加heap)

Onsite 10

1. 半轮culture fit, 问我N-Queen见过没，我说见过，就出了一个bipartite graph的题。
2. Coding：题目是以Snapchat自己的feature的形式给出的，经过分析抽象出来就是一个图的题，图里的每一个节点都有一个score。给定一个节点，找到从这个节点出发，长度少于等于N的路径里面，Sum(Score)最大的那个路径，并且打印出来。解法用BFS就可以
3. System design. (1) Sort large set of numbers (2) Design Snapchat Story feature
4. 半轮Design，半轮coding. Design Snapchat Discover feature. Coding: 剩了没多少时间开始问我算法题。先问我见过BigInt这个题没，我说见过，但是没写过。于是就开始让我写，我写了没几行，面试官就说OK，知道了，你不用写了。换了一个题，给一堆(name, phone#)的记录，把属于同一人的记录group到一起打印出来。name一样的，phone一样的都属于都一个group。跟面试官讨论了一下如何用两个map解决的想法，然后时间就到了。这半轮的coding基本没写代码。

Onsite 11

第一轮的面试官是个国人小哥，长得还挺帅，上来先让我自己选了一个项目介绍了一下，就开始做题。第一个热身的很简单，leetcode上的Product except itself，大概给他讲了一下思路就开始写了，写代码的时候他没看我，好像还在改他自己的代码。写完了他说我的代码习惯很好，注释很清楚，然后就第二个题。第二个题还是leetcode上的一个变体，二维矩阵的有些格子有障碍，一个人从左上往右下走，只能走下和右两个方向，求到右下的最短距离。这个很典型的一个动态规划，所以很快就写完了。然后小哥发现，咋这么快又写完了，于是就follow up出了第三个题，把第二个题变了一下说这个人可以上下左右都走，还是找最短距离。这个用dp就做不了了，于是就换成了bfs来做，还写了一点小bug，没有维护visited的set，小哥最后给我指出来了，然后时间就到了。

中午吃饭是推我的学长带我吃的，我一开始以为有吃饭的cultural fit面，然后看到学长推门进来简直要哭，以为运气咋这么好。结果学长说，我们公司都这样，如果有人推，就是推你的人带你吃饭。然后就跟着学长去吃饭了。事实证明我的运气是很好，吃饭的时候学长带着我跟另外几个小哥一起吃饭，其中一个也是我的直系学长，之前不认识，吃饭的时候就在聊。后来，事实证明他就是我的第二个面试官，吃完饭后等着看到他进来的是有一次简直想哭。

所以第二轮就很轻松，学长进来直接跟我说中文，说没关系的，我们不聊了，直接做个题吧。于是就做了一个meeting room II的变体，不是求需要多少个room，而是要把schedule打出来，输出哪些meeting在同一个room里进行。很轻松就写完了，然后学长说，那我们变一下，现在只有一个room，然后每个meeting都有权重，要求在不冲突的情况下使得最后安排下来的权重和最大。但是真是困，这个题上来的时候有点懵，没太想清楚dp的动态转移，就大概说了一下。此时，就体现了校友的厉害，学长说，没关系，来我带你想，于是就一步一步的带着我把动态转移写出来了。本来我以为他会让我把代码写了，结果他说没关系你就再把整个思路给我串一下就好了，不用写了。所以第二轮其实还是有点难的，但是运气太好，学长也没有为难我。

然后第三轮，是带shadow的面试，一来就是两个人，一个主面一个shadow，进来还是让我介绍项目，这个小哥很挑剔，很多技术的细节都让我解释了。shadow小哥一直在微笑不说话，还搞得我挺紧张。然后主面小哥开始出题了，说我们先写个简单的，的确是挺简单的，就是leetcode的那个找有多少个island的题。这一轮我是懵逼了，本来这个题很容易的bfs写的，但是当是我也不知道到底那根筋搭错了，说我给你写个UnionFind吧，小哥显然有点吃惊，说那你写吧。结果我也是的确就写出来了，然后小哥说那你说时间复杂度和空间复杂度是多少，于是我就说了。结果小哥说那UnionFind要额外的空间去记录，不太好，你现在就在原矩阵上走怎么做。当时还是有点二，一直纠结没太想清楚，然后小哥就说你想一想不是bfs就是dfs吧，然后突然就想通了说bfs。然后小哥说对对对，但是没时间写了，本来这一轮我给你准备了两个题，我没想到你第一题上来就写UnionFind，所以花了很多时间，第二题就算了。我当时就吓到了，以为我就跪了。但是shadow小哥给我吃了一剂定心丸，我问他你有没有什么feedback，他说我觉得很厉害，之前我也是学过UnionFind，但是自己没写过，今天看你bug free的一下子写出来，让我很震惊。所以感觉适度装逼也是可以的，其实我当时是真的没想到bfs。

第四轮是一个白人小哥，上来就上了个厕所，然后就让我介绍了一下自己，介绍了一下自己对snapchat的印象，介绍了一下为什么要选择snapchat。然后就开始做题。第一个不是很难，就是给了两个text文档，去parse第一个文档中的每个字符，然后去判断能不能组成第二个text。很简单，用hashmap做就好了。小哥后来让我优化，说怎么样可以提前退出而不用走完第一篇text，我就给他写了一个flag，记录到第二个text结束的时候就直接退出，小哥很满意。然后就第二题，第二题也是之前地里有的，外星人词典，判断这个addressbook对不对就行了，其实就是一个有向图判断有没有环，或者用拓扑排序也可以做。写完跑了一下test case也都过了就结束了。

完了之后跟recruiter聊了一下就让我回去等消息了，然后snapchat家是真的很快，第二天早上就给消息了，直接打电话给的offer。

感觉snapchat的整体bar还是挺高的，主要考图和dp，要求代码速度很快，每一轮要聊20分钟左右然后还要做2-3个hard左右的题，基本要求自己写test case测。当天感觉发挥不错，代码都是test case一次跑过bug free的。记得第三轮写完UnionFind跑出来没有问题的时候，shadow小哥在我背后感叹了一句 ‘哇’，还把我吓了一跳。

Onsite 12

第一轮，ABC小哥，给两个string的数组和一个pattern数组，判断将两个string数组分别和pattern转化后的结果是否相同。例如s1={“abc”, “a”, “ccc”}, s2={“bc”, “aa”, “d”}, pattern={1, 0}，则s1和p的转化结果是“aabc”，s2和p的转化结果也是是“aabc”，则返回true。如果pattern是{0, 1}，则转化结果分别是“abca”, “bcaa”，则返回false。followup是，如果给定s1和s2，判断是否存在一个pattern使得转化结果一致。 过程中要求分析算法复杂度。

第二轮，韩国大叔，Leetcode的symmetric tree。这题我一开始上来用了最精简的方法，然后似乎大叔不太能follow，要我从最简单的BFS做一遍，然后又从DFS做一遍。现在回过头来总结，其实面试的时候不要一开始给出最优解，给出一个相对naive但是直观的解，然后逐步改进，这样可以向面试官展现你的thinking process，一上来就最优的，很多面试官都不是很喜欢的。followup就是各种DFS和BFS的tradeoff，主要是在social app的应用中。

第三轮，华人小哥，就是大家现在看到新OA 其实算法不是很复杂，按照长度和尾字幕分成bucket，然后没个bucket建trie，用trie来生成缩写。但是在讨论算法复杂度的时候我脑子犯浑了，不知道怎么搞的跟面试官为一个无所谓的复杂度讨论了半天，然后写代码的时间就所剩无几，写完了代码，面试官就问了问打算怎么测试就结束了。本轮面试官是manager，估计跪在这里了。

第四轮，华人小哥，一个矩阵表示的迷宫，1表示有障碍，0表示没有，求一条从A点到B点的路径。第一遍，我忘了写用visited matrix，所以复杂度很高，在面试官提示下，增加了visited matrix，但是时间没有多少了。followup是如果迷宫不是联通的，问怎么remove障碍，使得可以从A到B。这一轮是reverse shadow interview，感觉面我的小哥比我还紧张，各种交流不顺，写完代码后问我是想向他问问题，还是做个follow up，我问能不能介绍一下你的工作，结果他说，看来你不是很有兴趣问问题，那我来问你followup吧。。。心中万匹cnm飞过。。。唉，感觉如果面试遇到reverse shadow，就自认倒霉吧。。。

第二天收到的结果，悲剧。。。第一个onsite面试，感觉失败也很正常，现在面了几个onsite之后回过头来想想这次的onsite，觉得当时太缺少经验了，面试还是有很多技巧的，并不是想得出最优算法就一定会面的好，感觉最好的模式是能够跟面试官慢慢交流，逐步导出最后的解答，即便最后的答案不是最优的也不要紧，重要的是在这个过程当中可以向面试官展现你自己方方面面的能力，而且可以避免很多不必要的麻烦。

关于snapchat公司再多说两句，感觉这个公司目前几乎是个纯前端的公司，后端基本上都包给google了（这也是为什么前段时间google的cloud service挂了，导致snapchat直接也挂了），比较适合喜欢做前端的同学。

Onsit 13

第一轮 印度哥哥 先在白板上写了关于linkedlist的题目，把linkedlist拆成两个，odd一列，even一列。 在电脑上写的employee的class （class里有一个directreport的list， string name， name是相当于id，独一无二），然后实现method， input是employee ceo， string emp1, string emp2， 找到emp1和emp2共同的manager。

第二轮 美国哥哥 bloomfilter， 支持add， mightcontains，resize，remove

第三轮 两个国人哥哥， 给一个double array， 让输出能使用＊，＋， 以及（）得到的maximum。 follow up，如果有小于0的怎么处理

第四轮 abc director， 先问了问background，然后出了magzine里找massage的题目，之后又问了design的题目，类似于google doc，如何保证大家拿到的 信息是一致的，在同一个version.

Onsite 14

回馈地里，奉上snapchat的onsite面经。感觉地里面的面经基本上都能cover他们家的题，大家认真准备机会还蛮大，他们家monetization在扩招。

一轮：会议室，国人小哥先提出各自优化，晚上没睡好反应有点慢，一开始没注意到heap里需要存储<会议，结束时间>数字对, 我只存了结束时间导致，最后才发现错误，为时已晚啊。。followup的会议室dp问题没有时间做了（地里帖子有提到）。跪在这里真是不甘心。

    public int meetingRoomDP(Interval[] meetings){
        if(meetings = null || meetings.length==0) return 0;
        Arrays.sort(meetings,new Comparator<Interval>(){
            public int compare(Interval room1, Interval room2){
                return room1.end-room2.end;
            }
        });
        int[] DP = new int[meetings.length];//DP[i]表示选了 i room的最大的权重值
        DP[0] = meetings[0].cost;
        int max = DP[0];
        for(int i=1;i<meetings.length;i++){
            DP[i] = meetings[i].cost;
            for(int j=0;j<i;j++){
                if(meetings[j].end>meetings[i].start) break;
                DP[i] = Math.max(DP[i],DP[j]+meetings[i].cost);
            }
            max = Math.max(max,DP[i]);
        }
        return max;
    }

二轮：外星人词典，原题

三轮：给一个数组，A,B轮流从头尾处选出一个数字，求当B使用（1）贪心和（2）最优策略时，A能取到所有数字之和最大。我使用的recursive写的，优化用的是hash 存储从子数组（i, j）上能得到的最优解。写了几个test跑过了。

四轮：给一个n*n 的chess board, knight可以跳 2*3的格子的对角线，就是国际象棋的规则。求给出一个起始点，knight能否跳到给定的重点。BFS搞定。followup print出来路径，backtrace就可以了，把每个格子上个格子的方位存下来，允许使用额外空间。写完后跑了test，小哥说：you did a good job

Onsite 15

第一轮.亚裔小哥自我介绍，对项目经历问得挺细的，问了实习过程中遇到过的困难有什么，详细说一个

1.给我看了一个snapchat给好友群发消息的功能，可以任意选中和删除想要投递消息的好友，并显示群发好友的list(按先后选中的顺序)，设计一个数据结构，实现 toggle(String username); getList(); LZ给的hashmap + doubly linked list的设计，类比LRU cache, 详细解释了一下，分析了时间复杂度。小哥说是最优解了，不coding

2.给如下结构

    class ChainSnap {
         List recipients; 
         boolean hasCycle(); 
         } 

让实现其中的hasCycle()。实际就是有向图判断有没cycle，用dfs加两个hashset判断globally visited 和 temporarily visited。 小哥问能不能不用额外的数据结构（那两个hashset）,但可以把以上的class修改一下。LZ说可以加两个boolean变量在class里。小哥问了两种方法在空间消耗上的差异，然后问能不能再减少空间的开销。。后来提示说那两个变量可能的值只有几种组合，然后提示用enum类型。然后让LZ写了用enum的那种方法的代码。

import java.util.*;
public class Test {
    Status st;
    public Test(){
        st = Status.UNSEEN;
    }
    public enum Status {
        UNSEEN, VISITED, VISITING
    }
    public static void main(String[] args) {
        Test test = new Test();
        System.out.println(test.st);
    }
}

第二轮.美国小哥 小哥说话挺慢的，先让自我介绍，问了why snapchat, 实习经历里面最exciting的事是啥以及实习过程中有没有不开心的事 题目问了XML parser, LZ不熟悉XML，就改成了HTML Parser, 本质上一样 输入是一个tokenizer对象，可以调用其getNextToken()函数获得下一个token, token结构包括name和tag，name就是具体的文字，tag有open,close,text三种，让把所有的token建成一棵树

比如： aa bb 得到的token就是

(“html”,“open”)
    (“user”,“open”) 
        (“id”,“open”) 
            (“aa”,“text”) 
        (“id”,“close”) 
        (“meta”,“open”) 
            (“bb”,“text”) 
        (“meta”,“close”) 
    (“user”,“close”) 
(“html”,“close”)

LZ的方法是用stack来存parent, 遇到open和text建新node, 并把新node加到stack顶部node的child list里面，如果是open就把新node压栈，遇到close就pop掉stack顶端的node 写完以后小哥的follow up是如果输入的token有问题，比如close tag和open tag不匹配，如何做verification。LZ加了几行判断的code以后，小哥说他木有follow up了，于是开始聊天。。

第三轮. 两个人，主面试官有口音，但是看不出是哪里人 问了简历+why snapchat+最喜欢的feature 主要面的是unique paths I + II, 加了面试官自己的follow up, 就是如果给定的grid里面有三种情况，0能走，1不能走，2表示弹簧，可以走到2右边2格的位置，求结果 对于I, LZ直接说用dp做了，面试官表示其实直接一个公式就能算出来- -。但还是让LZ在白板上画了图，讲了思路，然后coding, 以及写test case测试 然后问LZ代码可以怎样优化让其更reliable更readable…LZ没啥概念，瞎扯了下…然后又问如果grid很大，如何encapsulate input, 依旧有点答非所问。。然后开始聊天。。

第四轮. 中国小哥 下午三轮是连着的，看到中国小哥简直热泪盈眶 问了简历+why snapchat+最喜欢的feature 1.反对角线打印矩阵，电面面经题 2.给两个string判断是不是anagram follow up, 给一个长string一个短string, 判断长string里是否存在substring和短string是anagram,要求O(n)时间，n是长string的长度 LZ用了移动窗口+hashmap存出现次数的方法，好像不是小哥想到的方法，纠结了一段时间此法是否work, 小哥想到了overfit的问题，好心提醒了一下可以在hashmap存负数，然后coding解决，闲聊了一会 *overfit指的是当前substring某个字母出现个数多于短string里面该字母的出现次数 面完以后回到lobby,本来要跟hr聊天，幸好有hr出差了人手不够，这个环节就省了 每轮面试都是1个小时。上午11点让到，11点15才开始面，12点半吃饭，1点半开始下午的面试，下午连着3轮，面完还是很累的，不过面试的房间里就能看到海景，确实很漂亮

Onsite 16

Round 1

Introduce yourself

Talk about 1 or 2 past projectsWhy snapchat?What do you like about snapchat?How can snapchat improve?

Coding:

BigInt add(BigInt &other)

Follow upsupport adding floating numbers Do you have question for us?

What do you like about working for Snapchat?

What cutting edge stuff you have? (The interviewer ask me what do i mean by cutting edge?

I said google has self-driving cars.

Which sound arrogant and stupid to ask)

Round 2

Metric Collection System Design and implement the apis below: void addRecord(double value, long timestamp) double getAverage double getMax double getMin

Round 3

    //Employee, Manager, ItemsSold
    //A, , 5
    //B, A, 3
    //C, B, 2
    //D, B, 3
    //E, A, 7 

for each employee, calculate the number of items sold by himself and his org(all the employee reported to him)

print the results

Round 4

Given some points on a grid and point X, find the closest point to X

Onsite 17

dream company就这么挂了，十分忧桑，写下面经求大家分析下原因TwT

一到公司就直接第一轮，感觉还木有反应过来，也不给个tour啥的，哎 第一轮是个国人大哥，题目是amicable number，分析了下思路直接开写。写完再添了一些test case。感觉第一轮状态非常差，写的过程中出了几个很低智商的bug，虽然自己都解决了。 然后分析了下复杂度，从O(n^2)优化到O(n^3/2)，我觉得并木优什么用，十分虚，但是大哥看起来还挺满意的

    public static List<Integer> findYakuSu(int intNum)
    {
        List<Integer> listYakuSu = new ArrayList<Integer>();
        listYakuSu.add (1);
        int intRoot = (int)Math.sqrt(intNum);
        for(int i = 2; i <= intRoot ; i++)
        {
            int intPart = intNum/i;
            if(intPart * i == intNum)
            {
                listYakuSu.add (i);
                if(intPart != i)
                {
                    listYakuSu.add (intPart);
                }
            }
        }
        return listYakuSu;
    }

然后就是lunch，和两个认识的师兄一起吃饭，感觉还比较放松，调整一下继续后面

第二轮是个亚裔小哥，题目是input一个text file，里面是last name, first name, mm/dd/yy, manager's full name这样的格式，按照他的要求parse然后按照hierarchy print出来。题目不难，但是细节讨论了蛮久，写了一半，最后时间都木有写完。。。虽然小哥说没关系，毕竟这题毕竟难（？有咩？我觉得其实不难，是自己时间没掌控好没写完，我的错，哎），但是我觉得没写完还是很糟糕。

第三轮是个亚裔mm，设计题，一些snapchat功能的设计，如何pre-load的strategy。题目很细节，我一开始完全木有概念，但是她给了很多信息，所以一点点也就答出来了了。然后就是很多聊天，聊得比较开心。。。

第四轮是个小印gg，上来就聊了很多经历和公司的事情，聊得特别开心，导致我还以为是behavior轮正好那个时候已经面了四五个小时脑子已经转不动了，开始反应迟钝。。。结果聊了蛮久以后小哥说行吧我们来做道题。。。orz 也是设计题，设计数据结构来完成snapchat的一个具体function，我设计的类似于LRU cache的东东，实现了代码，小哥看起来十分满意。。。

他家流程非常快，第二天就出结果。挂了还不给feedback，问了也只是说你很优秀然而我们非常selective，看来是套话罢了。。。心塞。

Onsite 18

第一轮是个中国小哥，人超级好。题目是你要举办一个party，给你一些人和他们的上下级关系，如果你邀请了一个人就不能邀请他的直接上级或者直接下级，问怎样邀请能使邀请的所有人的级别加起来和最高（比如CEO是10级然后VP9级这样，类似每个人有一个分数）。小哥差不多提示得已经快把解法告诉我了才想明白，然后开始码代码，写完小哥看了看说感觉是对的时间不够了不用跑了- -然后聊了聊，小哥说，在这里大家之间都很nice，因为来了就做好了呆满四年拿够RSU的准备……= = 吃饭那轮貌似习惯性在附近某个咖啡厅吃，反正见到了好几个当天面试的小伙伴，而且因为下雨所以店里全都是snapchat的员工/面试官/来面试的，感觉中国人比例真是高啊。。。反正其他人都是跟中国员工吃饭，给我安排了个校友，美国小哥，于是聊了一中午中国和美国的教育差别外加吐槽母校的食堂有多么难吃- -

第二轮还是个中国小哥，题目有点类似wall and gate，就是一个二维迷宫，0表示可以走，1表示障碍物，问从其中某点到另一点有没有通路。用BFS+染色法做了。follow up是打印出这条路（不必是最短路径）是什么，但是我没时间写这个了。就把之前那个找不找得到的写了testcase跑过了。另外这轮的小哥问了不少我想做什么方向啦之类的。其他轮基本上就是简历大概聊聊就开始做题了。

第三轮是个外国小哥，给了一个class如下

     class Task { 
             public: void exec() {};
             set getDeps() {} 
             }; 

然后写一个函数，输入是一堆Task，每个task可能有一些dependency，必须先执行完dependency才能执行这个task，输出是这堆task的正确执行顺序。follow up是如果有环，需要报出错误信息。同时可以补充给的这个class。依然是用递归写的。。。跑的时候出现了奇怪的编译错误小哥说他不会C++解决不了就这么着吧就没有再跑

第四轮是个国人大叔，先写个reverse linked list，follow up如果有环怎么办，然后是level order traversal，最后还有时间就问了一个如何用4G内存sort 100G数据，假设CPU速度很快可以忽略，瓶颈是硬盘读写速度（50M/S），问只有一块硬盘的话估计要用多少时间，如果有两块硬盘如何优化。

最后跟HR见一下说第二天通知结果，拒信就是邮件，offer就是邮件约时间打电话。然后第二天早上收到了约电话的邮件……pkg就是标准的吧(或者比标准低一点？反正觉得自己表现也挺一般的)，110k base + 10 signon + 322.56k RSU，还问了想去哪个组可以安排跟director聊天，ddl给了两周但是说需要可以延。hr说一般一天面七八个人能发一个offer就不错了，但我觉得应该没有这么难吧，毕竟他家今年是冲着翻倍去招的……按这速度得招多久才能招够啊…… 另外他家零食的那个BBQ味道的薯片真心好吃啊，还有瓶装的茶也很好喝！千万别喝苏打水就行（但是给我的袋子里是苏打水T T）中午吃饭那个地方的薯条好好吃（我的关注点真是奇怪。。。

Onsite 19

1. Amicable pairs: Given a number n, return all amicable pairs (a, b) with a < n and b < n. The definition of amicable pairs is in http://mathworld.wolfram.com/AmicablePair.html 这个就写了O(sqrt(N) N)的暴力做, 但后来告知有O(NlogN)的... 不过真心没什么意思, 一共amicable pairs没几个.. 应该打表的...
2. 2Sum, 3Sum, 4Sum 稍微有点变化的是, array中数字是0-10, target也是0-10的. 要求输出在数组中最先遇到的 满足条件的pair (triplet...).
3. 其他就是design problem和data science problem. 由于我的背景是machine learning, 比较有意思的是最后有一个面试官: 先问我知道neural network吗? 知道.. 好, 你来derive一下back propagation algorithm. 然后问我知道kernel trick吗? 知道.. 好, 你来explain and derive一下kernel trick.. 我就写了derivation of dual, 然后解释了一下. 我的感受是..在不给任何objective function或者提示的前提下, 回答这些基本问题当时还是有点一身冷汗的..

然后过3天收到了据信.. 不过差不多也意料之中, 在最后一面时就被告知所有team都是做infrastructure的, 目前还没有data之类的职位, 问我 有没有兴趣做infrastructure. 我很呆的说.. 这个方面我不是强项... (据说6个月之后会有data science之类的job了..).

Onsite 20

第一轮是一个大胡子白人，扎着马尾辫。看起来还是挺严肃的。先聊简历，聊了很多。他问到有个我做过的项目，如果想再做一遍的话，问我想怎样改进。编程题是给定一个有向关系图，在给定2个名字，求出这两个人的共同朋友（即2个点能达到的共同节点，类似树的共同祖先）

第二轮是一个白人小哥，人很nice。简单的聊了一下简历后就开始编程。题目是如果通讯录里从某一个名字开始翻转了，请把这个名字找出来。类似leetcode这道题：。这题我二分搜索算法犯了个低级错误，大概被扣分不少。

第三轮是一个印度小哥，这轮开始题目就有点飘了。题目是这样的，通过二维数组来建一颗四叉树。四叉树的叶子节点来自二维数组相邻的上左下右四个方块的值。建树规则是，四个节点的都是0，则父节点也是0，如果四个节点都是1，则父节点也是1.如果四个节点既有0，又有1，则父节点是2.如果四个节点都是2，则父节点是1.(规则有点复杂，一些细节我可能忘记了，但大体是这样）我是用递归的方式建树的。但因为代码量太大，导致我这一轮没完成编码。所以大概挂在这里了。

第四轮，国人小哥。我也不知道他后来有没有放水，反正是挂了。但过程中他给了很多的提示。题目是这样的：一棵树，代表上司和员工的关系，然后每个节点都有一个对应的权值。然后公司开了一个party，为了让员工们更好的交流，有个规定，如果上司去参加party，那么他的直接下属（直接孩子节点)就不去（同理，如果下属去了，直接上司，父节点就不去）。然后设计一个算法，参加party的人的权值总和最高。这是一道动态规划题，思路是每次计算一个员工去的权值之和与不去的权值之和，从叶子开始。

结束之后HR会简单的和你聊会儿天。当然，第二轮和第三轮面试之间有一个午餐，帮忙内推你的人会带你去吃饭。Snapchat专门租了一个地方当餐厅。然后就回家啦。很遗憾，木有见到传说中的CEO。 PS：snapchat的办公室位于洛杉矶 Santa Monica海滩，海滩本身很漂亮，但海滩上各样怪咖，流浪汉都有。还有国内各种卖T恤和纪念品的店，里面的商品大概是义乌进的货吧。如果喜欢这样自由而略带混乱的环境的话，可以考虑去snapchat工作，我是没机会了，就算吃不到葡萄就说葡萄酸的吐槽一下吧。

Onsite 21

第一轮： 面试官：亚裔妹子，人很nice很可爱，好像是broadcast组的，就是题一出我就有点懵了。 题目： ternary expression paser （三目运算符）， input是一个string，其中 ‘T’ 表示true， ‘F’ 表示false， 要求返回最后运算的结果。 乍一看题目很直接， bool expression ? first result : second result ，但实际上我们通常都用的都是非常简单的形式，但每一部分都可以无限嵌套。例如： T ? T : F ? T ? 1 : 2 : F ? 3 : 4; 会转化成T : 1 : 4，然后返回1 原本妹子没让我考虑bool expression部分也嵌套的情况，结果我本着把问题分析清楚的原则，成功把问题弄的复杂了，她后来觉得这可以作为follow up。。。 说了两三个简单的solution，然后举例发现有问题。在妹子的提示下，写出了 “不考虑 bool expression”的情况，但是因为已经说出口了，妹子指出我还需要继续考虑。最终时间不够，没有运行代码。 过后发现，确实应该多在纸上找一下规律，理清逻辑在写解法。string的变式题对我来说比较tricky，完全在脑子里思考容易变成一团浆糊。。。。妹子对我我说，没事她比较看重逻辑。我心里只能说谢谢你的安慰。。T.T

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        System.out.println(evaluate("T ? T ? 1 : 2 : F ? 3 : 4")); // 1
        System.out.println(evaluate("T ? 6 : F ? T ? 2 : 3 : F ? 4 : 5")); // 6
        System.out.println(evaluate("T ? F ? 1 : 2 : 3")); // 2
        System.out.println(evaluate("T ? T ? F ? 1 : 2 : F ? 3 : 4 : T ? 5 : 6")); // 2
        System.out.println(evaluate("F ? T ? F ? 1 : 2 : F ? 3 : 4 : T ? 5 : 6")); // 5
    }

    private static String evaluate(String s) {
        Stack<Node> stack = new Stack<>();
        int start = 0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (ch == '?') {
                String sub = s.substring(start, i);
                stack.push(new Node(sub, Type.Expression));
                start = i + 1;
            } else if (ch == ':') {
                String sub = s.substring(start, i);
                processLeftOrRightPart(stack, sub);
                start = i + 1;
            }
        }

        String last = s.substring(start, len);
        processLeftOrRightPart(stack, last);

        return stack.pop().s;
    }
     private static void processLeftOrRightPart(Stack<Node> stack, String sub) {
        if (stack.peek().type == Type.Expression) {
            stack.push(new Node(sub, Type.Left));
        } else {
            while (!stack.isEmpty() && stack.peek().type == Type.Left) {
                Node leftPart = stack.pop();
                Node expression = stack.pop();

                sub = expression.s.trim().equals("T") ? leftPart.s : sub;
            }

            if (!stack.isEmpty() && stack.peek().type == Type.Expression) {
                stack.push(new Node(sub, Type.Left));
            } else {
                stack.push(new Node(sub, Type.Expression));
            }
        }
    }
}

enum Type {
    Expression,
    Left
}

class Node {
    public String s;
    public Type type;
    public Node (String s, Type type) {. 1point 3acres 璁哄潧
        this.s = s;
        this.type = type;
    }
}

午饭： 美国小哥，Seattle土生土长，UW毕业直接来snapchat工作，感觉很开朗很厉害的样子。去了其中一个食堂发现好多国人，但是地方比较小比较挤，饭菜还行。我们带着饭去了另一个snapchat租的小阁楼的楼顶聊天吃饭，那风吹得我简直冷洒比。。。从面试地点和食堂来回聊了蛮多，从他们data组聊到篮球足球dota2。我俩都表示足球太难碰到球了还是篮球好好玩，并且两人对dota2辅助的重要性深有同感，同时鄙视网上自私自利只喜欢玩carry的玩家哈哈哈。

第二轮： 面试官：挺厉害的国人小哥，原谅我忘记你是哪个组了。。。去过大公司，换过start up，最后来的snapchat，逻辑很清晰。聊了好一会project，问得很详细，花了不少时间。 题目： Alien dict （感谢面筋。。。） 具体就不说了，写了topo sort。之后小哥详细问了怎样test保证能在product work，扯了下unit test + modular test + system test, 然后具体说了unit test的五六种case，然后test发现有个小bug，改之。再问如找不到valid sequence咋办，以及写exception。小哥不太熟unordered_map，问我有个地方是否会出现out of bound问题，我说map会直接新建一个value不会有问题，他表示惊奇并且说还是要注意下。

第三轮： 面试官：白人manager，手下两个team，team主要做internal tool， UX之类。10+年工作经验，很nice很耐心。问了会project之后开始做题。 题目： construct string from web page + XML paser，再次感谢面筋，不过有一点不同是需要设计data structure保存paser后的结果。 每个token有如下结构，然后给了个API getNextToken()获取下一个token, 我表示应该还有个 hasNextToken()。 and

    token { 
        string name; // e.g. story, id, snaps 
        string tag_type; // {open, close, test} 三种type 
        }; 

第一题没让写代码，就讨论，用hash map。 第二题说了用stack 保存状态来解析，但是在设计结构的时候纠结了一会。最近缺乏运动，因而下午有小睡的习惯，结果在这个问题上卡了一会。说用nested hashmap，他表示make sense，就是想了半天没想到用下面这个结构，他提示我可以用vector>的结构，表示恍然大悟，然后发现应该并不需要vector。写完之后follow up就是如果tag不匹配怎么检测。 Node { string name; string value; unordered_map; };

第四轮： 面试官：比较腼腆的国人小哥，刚从google跳槽过来，但是中途话比较少不太主动给提示，但你跟他交流他还是很愿意跟你解释。表示我们可以skip introduction和project直接coding，LZ表示当时脑子快累洒比了，欣然同意。 题目： tic tac toe的m*n版本，也就两个人是在一个m*n的board上玩。（LZ最讨厌玩游戏了。。。） 规则如下：

（1）获胜方式依然是横竖对角线有三个连在一起的symbol。

（2）每次movement不能任意放置，只能放在 每一列 的 最下方的空白处，也就是说每个玩家每轮最多只有 n （行数）个选择。 要求实现以下API：

（1）valid()。检查当前board是否有效，有效board必须满足 
    (i) 没有人获胜 
    (ii) 不能违背第二条规则。 
（2）nextMove()。返回当前玩家的任意一个movement，
    要求对手无法获胜，如果找不到报错（我选择了返回-1） 

脑子实在累了，讨论了一下给出了bruteforce的方案。

1. valid主要难点在怎么判断已经有人赢了，LZ用check8个方向一共16个格子的方法，于是O(16*N^2)。跟小哥交涉，表示常数可以减小，不过16也合理可以写。

2. 假设当前为player A， 则枚举A的n个选择，每个选择会对应B的n个选择，复杂度依然是O(16*N^2)。但实际上如果不保存board state，不管是A还是B都得先找到每一列放置的位置，每次都扫描一遍就会多出O(N)的时间，总时间会变成O(N^3)，所以需要保存一下状态。 加上一些细节的调整，最后写完但依然没时间测试debug了，两人一起表示过了一遍应该work。。。。

总结： 刷面筋依然高效。遇到思路不清晰的问题，还是在纸上多举几个例子跟面试官讨论一下，思维清晰了反而能节省时间。继续保持coding，并且坚持运动增强体力。。。move on。。。。

Onsite 22

估计要挂了，感觉发挥太差

1）给一个target串，判断另外source串中有没有substring满足edit distance of target and that substring <= 1，讲下思路然后写，没写完整

2) design query suggestion system, implement trie tree's seach function.

3) quad tree, 写的一对bug，改了半天才改完，没时间下一题了

4）meeting room ii， 然后 1 room with 带权重的meeting

Onsite 23

第一轮 n叉树判断是否有回路，dfs, 但是不希望一直维护一个祖先节点的哈希表，所以可以设计一个类，里面存一个布尔型的变量，访问过的设为true，回溯之后设为false

第二轮， rotate过的数组排序，nlogn找出最小值，o(n)时间构造新的数组

第三轮， 高精度加法，follow up可以是负数，多加一个高精度减法

第四轮

1. 一堆数，中间插入*，+或者括号，求最大值，dp就可以， 但是如果数字全部是正整数的话，只用通过判断1的个数是奇数还是偶数来求最大值，0(n)就可以了Solution
2. merge n个排序过的数组，优先队列或者divide and merge都可以
3. 简单的regax判断是否match

Onsite 24

第一轮国人小哥中文面的，给一个List of meetings, meetings有起始时间，求meetings的arrangement，返回的是哪个meeting Room被排了哪些面试。

第二轮

1. c

    class Throttler {
      int qps;
      public Throttler(int qps) {
      }
      pubilc boolean allowAccess() {
      }
    }
   

给这么一个class实现rate limiter，allowAccess()返回的事当前时间的access能不能被批准 举个栗子：

    qps是2
    request1 time 0.0 return true;
    request2 time 0.5 return true;
    request3 time 0.6 return false;

1. Given List, String para, 返回包涵所有word最短的一段话,返回String 先把word简化成character来做的，就是LC的minimum window substring，最后时间不够没写完，感觉gg在这里了

第三轮 1.给一个单核CPU的log，parse log，每一行log三列分别是jobname(String) start/end(boolean) timeStamp(long)

    上面log的意思是我们在0开始做f1
    在2的时候切换到f2,
    4的时候开始做f3，
    5的时候f3结束
    要返回每个function要用的时间
    这个input的返回就是
    f1 ： 3
    f2 ： 5
    f3 ： 1

1. 在terminal里输入文件名的一部分然后按tab补全，求能找到target文件要输入string的最短长度

2. 写一个可以被多线程访问的计数器？？每被访问一次count++，check被访问次数的method并不常用

第四轮，第四轮是我面的最迷的一轮，前半段连写了三道简单题 reverse linkedList, 按层打印树，和LC reverse words in a string 后半部分在讨论如何用4G的RAM sort硬盘里100G文件的问题，可以加额外的硬盘，要尽量使用时尽量短

Onsite 25

今天去Snapchat onsite，体验了一下神级startup的氛围。地理位置非常的好，距离沙滩就几步远，公司隐僻在一堆厂房之中，周围没有任何明显的标志，刚到的时候完全不知道哪里是公司，后来是被保安大哥叫住然后领进“小黑屋”的。和几个工程师聊过天之后，感觉他们非常的有朝气也很有激情，给人一种非常振奋人心的感觉。闲话少说，直接上题，楼主感觉是跪了，不过体验了一次Snapchat也算是值了。

另外提一句，由于今天去onsite的人太多，楼主被挤到一个瑜伽房去面试了，没有白板只有白纸，anyway，反正都是要在电脑上编译再测试。

第一面,一个口音不是很重的三哥。上来先问了简历上的实习的project，问的比较详细。之后做题，给一个Employee类，有一个String name和一个List<Employee> directReport来表示一个公司的组织结构，然后给定一个公司的ceo和两个员工的名字，找到这两个员工的第一个common manager，给的两个员工一定存在。N-try tree的first common ancestor。楼主就用最naive的方法先找到从根到target节点的path然后在两个path中找第一个common ancestor。在电脑上写代码和测试样例，改掉测试样例的一个小bug之后通过。要求优化，说了用postorder traversal的方法来找，这样只需要遍历树一遍，说了一下整体的过程没有coding。之后问在一个很大的social network中，给两个个名字，如何快速的找到名字对应的node然后再去找他们的common friends。楼主提了一下hash，consistent hash然后就没啥了，不熟悉DHT没办法啊。还是自己准备不够充分，好多东西需要了解。

中午是一个韩国小哥带着去吃午饭，聊得很开心。

第二面，一个中年白人manager。一上来先问了问why snapchat, what's your favoriate parts of internshop in Facebook。之后做题，给定一些输入如

    Employee,Manager,ItemsSold
    Alice,,5
    Bob,Alice,3
    Carol,Bob,2
    David,Bob,3
    Eve,Alice,2
    Ferris,Eve,1
    要求打印出这个样子
    Alice 16
        Bob 8
            Carol 2
            David 3
        Eve 3
            Ferris 1

楼主先自己设计数据结构，和第一面那个基本一样，只是多了一个int num来记录数量，根据输入构建树，注意这里每条记录给定的顺序是随机的，所以可能先出来David,Bob,3然后才是Bob,Alice,3。不注意的话可能会有小bug报错。然后postorder算出所有node的child的数量和，然后update自己的，之后preorder打印。写的时候有个小bug，改正之后通过。follow up要求打印成这个样子

    Alice 16
    |-Bob 8
    | |-Carol 2
    | \_David 3
    \_Eve 3
      \_Ferris 1

然后楼主就跪在这里了，怎么改都是有bug，最后也没改出来。最后面试官说，你的大方向是对的，只是你API设计的不够好，你如果把parent需要打印的prefix也传递给child，打印起来就非常方便了。楼主终于醒悟，刷题太多导致思维僵固了，另外这一面全程要coding并且编译运行。

import java.util.*;
public class Test {
    public Map<String, List<String>> map = new HashMap<>();
    public void printLvl(String root, String prefix){
        StringBuilder p = new StringBuilder();
        p.append(prefix);
        System.out.println(p.toString()+root);
        int len = map.get(root).size();
        if(p.length()>1){
            int p_len = p.length();
            if(p.charAt(p_len-2)=='|') p.setLength(p_len-1);
            else{
                p.setLength(p_len-2);
                p.append(' ');
            }
        }
        for(int i=0;i<len;i++){
            if(i==len-1){
                printLvl(map.get(root).get(i),p.toString()+" \\_");
            }else{
                printLvl(map.get(root).get(i),p.toString()+" |-");
            }
        }
    }
    public static void main(String[] args) {
        Test t = new Test();
        t.map.put("Alice",new ArrayList<String>());
        t.map.get("Alice").add("Bob");
        t.map.get("Alice").add("Eve");
        t.map.put("Bob",new ArrayList<String>());
        t.map.put("Eve",new ArrayList<String>());
        t.map.get("Bob").add("Carol");
        t.map.get("Bob").add("David");
        t.map.get("Eve").add("Ferris");
        t.map.put("Carol",new ArrayList<String>());
        t.map.put("David",new ArrayList<String>());
        t.map.put("Ferris",new ArrayList<String>());

        t.printLvl("Alice","");
    }
}

第三面，一个年轻白人。一上来先介绍了一下Snapchat各个team什么的，然后问了问project。然后问说我们有个很huge的social network，你需要design一个system，这个system可以用来evaluate各种我们设计的朋友推荐算法，你要怎么设计。说了一下大概的设计，面试官更看重我如何准备data来做evalution，于是就也说了说这个部分。之后做题，就是根据计算机网络里面那个CIDR然后来做IP address filtering。比如给定一些rule: "7.0.0.0/8", 那么所有前8位是7的address应该全部被filter掉。楼主用hashset来存rule然后用一些位运算的方法来做filter。写完代码改了一个小bug之后测试通过。

第四面，一个年轻白人。一上来也是问了问project。然后做题，给定一个grid matrix，就是类似围棋盘那种东西。然后某些grid（放棋子的地方）上面有点，给定一个query点的位置，返回k nearest点on this grid matrix。第一开始我assume给了个list，里面是自己设计的一个结构体，记录了坐标和距离query点的距离，然后写了个comparator来sort这个list，然后返回k个node。之后要求优化到O(n)，楼主就写了quick selection。之后要求再优化，然后楼主就**了，尼玛这是要让我写kd-tree的节奏，这东西曾经在普利斯顿的算法公开课写过一次，之后就再也没碰过了，果断回避之。就设计了一种逐渐膨胀的正方形的方法，不过这种方法有bug，返回的不一定是k nearest，我也指出了可能哪些情况不work，但是面试官还是让我写了，我也就写了。全程几乎在梦游，感觉这一轮和第二轮面得一样差，面完当场感觉已经和Snapchat say Goodbye了。

最后就是和HR简单的聊了一些东西，比如有什么offer啊，你选择offer的时候最看重哪些方面啊之类的，然后就被送出了building。

之后去沙滩上走了走，这是楼主最后的一个interveiw（其实一共也就3个面试）。感觉不能再天天刷题刷面经了，好多东西不是刷题能够弥补的，还是多去看看书，尝试尝试新技术，做一些自己的小project来增长一些实际的经验更靠谱。

Onsite 26

(1) LRU (2) IP address filter，给一些ip的规则，然后问那些ip复合这些规则 (3) word pattern (其他面经里有) (4) 1. valid BST 2. 添加括号使得表达式值最大，表达式只有+ - *

Onsite 27

Venice海滩真的好漂亮，晚上说脑袋糊涂得不行，去吹海风，结果第二天重感冒； 第一轮：Monetization组Google新跳过来的老美director, 去年12月才来的，感觉他相当relax, 和他聊天一点都不紧张，也让我放松了好多，问了下简历，然后直接上题：

1. 设计一个API, 返回所有朋友看的snap 从高到低的snap, 所有数据结构自己构造，我就想了个Person的class, 里面有friend List, 以及一个hashMap统计各个snap的观看纪录，然后就是bfs, 再一个大的hashmap统计了

最后加了个Node class {private int snapId, private int count}, 用Collections.sort出结果 extra: 他说你20分钟写好了，咱还有时间，你给我写个quicksort的实现吧，啪啪啪， bug free写好了， 说good job 中饭是内推你的人和你一起的， 公司安排了素未谋面的内推的小伙伴一起吃，中饭，感觉还行，中饭共1小时时间，下午1:15开始第二场面试， 还是有点困的

1. 一个蛮年轻的小哥，入职一年半， support paltform的，Big Integer加减，可正可负，听他描述完，有点想抽自己，看到有人说了类似题目的面经，但是说的是电面，就没准备，没想撞上了。题目大意： 传入一个String, 自己定定义BigInteger class的内部变量, 实现加减； 想了一下，本来想直接char arrar处理，发现把符号信息单独拿出来会简单很多， 所以就是BigInteger{int sign, int[] nums}, 然后就是实现， 两个数的符号 ++, --, +-, -+, 分情况写，没有全部写完，就写好了＋＋， －－, 小哥说没时间了，你写几个testcase 先跑一下这个吧，testcase 通过， done..
2. 一个华人小哥， 感觉放水了，data metrics的， 聊了聊简历，题目基本就是Leetcode 317, bug free搞定，然后小哥说你来想给足testcase跑一下吧，我想了几组case，凑了好一会，小哥也比较满意； 然后问我有什么问题，我就问了下snapchat 每个snap 信息比较难提取，你是怎么向各个不同用户推荐discovery / stories 里的snap的， 小哥回答了下.

1. 一个不明国籍的中年男, 感觉相当严谨的感觉，面的菊花各种紧, 说是geofilter 主要负责人，我赶紧跪舔说我可喜欢你的geofilter了, 比如什么什么，还能植入广告啥的好牛逼啊： 问了实习时候的简历，每当我抛出一个新概念就各种问，略虚， 题目和regular expression matching 有点像， 除了＊不在表示任意count, 而是1-100 的count， 我说直接暴力枚举各种可能的结果，比如碰到a* 就见一个list 包含所有可能，然后把 s 和 由 p生成的所有可能比较一次， 面试官问有没有更好的方法，细想了下，dp还是能写的，然后就写了下，调了下bug, 测了各种testcase， 过了

面完第二天就通知要了，还说我culture fit 方面每个面试官都觉得很好

经验就是多刷leetcode + 面经， 发现snapchat 目前题库还不是很大， 多刷几题也算给自己额外的安慰，面试的时候不太紧张；然后各种culture fit， 后面要面的人要取巧的话，看一下snapchat 的wiki, 然后看几篇技术报道，最后youtube上搜一下网红们怎么用的snapchat, 基本就能“看着” 很fit了

Onsit 28

第一轮电面：实现 linux command line中的tab completion功能（其实就是让实现一个trie，但是要注意一下有多个可能结果时的情况。小哥当时要求实现的效果跟command line behavior一样。平时没注意过这点，蒙圈了，被加了一轮电面）

第二轮电面：Big integer addition and substraction。S家的电面高频题

Onsite: onsite前一晚和当天都在发高烧，有些细节记不清了还请见谅. from:

第一轮：Binary tree level order traversal，LC原题，早上吃药退了烧，状态还行秒掉了

第二轮：Team manager小哥。Given a M X N grid, a random cell in the grid (coordinate <a, b> for example), find number of ways you can reach top-left corner in k steps, assuming you can move in any direction. 这轮又开始发烧，明明是个3D DP昏昏沉沉硬是用2D DP来写，被小哥的edge case challenge好多次 QAQ。最后他说you actually started very close to the right solution, only if you added number of steps as a dimension的时候LZ简直要哭出来了T_T.

第三轮：做安卓端的小哥。问题是假定给个屏幕和一些屏幕坐标和渲染单个像素点的API，要求设计一个渲染class, 能实现当手指点下去的时候开始渲染，手指拖动过程中渲染以屏幕一角和手指作为对角线的一个长方形（这个长方形可以根据手指的运动扩大缩小），最终当手指离开屏幕的时候，以手指最后位置为准，留下most recent的那个长方形。小哥在整个过程中除了回答clarification以外一直不出声，edege case都是LZ一边写一边找出来的。。。

第四轮：面试官没来，LZ在趴桌半小时后才意识到自己被放了鸽子。。。

Onsite 29

周五Onsite,周一下午收到拒信。也是意料之中吧，毕竟onsite的表现实在不好。S家确实如传说中那样，很注重culture match，一小时一轮的onsite，每轮都至少聊了20分钟culture fit才开始做题，最后还有五到十分钟的Q&A

第一轮，word pattern，面试官 叫奥斯汀 李（俩e的那个，估计是ABK，其它面经曾经提过。。。）。小哥迟到了至少20分钟，上来又先聊了10分钟简历，以至于后面的时间并不多了。。。s1，s2，s 分别代表string list1，string list2 和index list。两者根据index list，match就return true，不match就return False。我一上来先提出了直接历变的解法，集创建两个空string，根据index不断把两个string list里的string往两个空string里面写。小哥问我时间复杂度，我说O(n)，他说太general了，具体咧？懵逼了，真没了解那么深。后来提醒我说每次空string叠加也是耗时的，耗的时间跟被叠加的string有关。。。就是O(mn)。再问我空间复杂度，我说O(n)，还说general，最后也是O(mn)，让我改进我的算法用O(1)的空间复杂度。。。好吧，在不断交流和提醒中，写完了，用pointer，四个pointer，两个指现在的string，两个string里面的字母。但是时间也到了，我明白后面还有follow up，我没做成，第一轮扑街。

第二轮，task management design（考官塞巴斯汀，某个组manager）。比方说给你50个task，有个API假设已经有了，是用来run这些task的，但是这个API最多每次只能同时run3个。并且run的顺序根据priority level来定，让实现。具体包括 get，change priority 和run，get就是新的task，change priority就是把已有的还没运行的task更改priority level，run就是运行同时保证运行完一个马上推入下一个运行，楼主现在想了想，今天写了写，写出来了，当时扑街，面试官说他看中的是怎么样思考。。。

第三轮，life of game，面经很多，不多说。不能用in place来做，用hashmap来记下一轮会发生变化的点。考官布兰登，刚刚入职不到一年，他自己说自己是个小本科。follow up是如果board很大，大到根本存不了，咋办，我说那只记录边界和是活细胞的点的位置，挺满意，提前15分钟搞完，跟我说我没啥问题了咱俩谈谈逼吧。。。

第四轮，中国小哥，跟了一个shadow也是中国人，问了25分钟简历，还挺详细。完事之后让写一个Bigint class，面经很多人说到过bigint，但是你们为啥不说是bigint class？！反反复复跟小哥交流，感觉小哥都无奈了。最后终于把同号相加的写完了，异号相加确实没有时间了，这轮基本也是扑街。 总体来说不难，或者说很简单，只是这是楼主第一个onsite，实在是没有技巧还紧张。。。当天晚上6点他们就开完会投完票了。。。我内推跟我说估计反馈不是很positive，而且反映follow up不好。是不好，都没来得及做。。。最后他去帮我问hr，hr说的就是风格不匹配。。。什么才叫风格匹配？在线等。。。 最后，希望大家都有好offer，希望下面的面试能有好表现。。。加油

Onsite 30

第一轮：白人小哥Will，Discover组。小哥上来先介绍自己，然后我开始介绍我自己以及我的项目经历，然后问我why snapchat，然后我说我自己在用很喜欢Discover，楼主面试前作了功课，听说snapchat会直播今年奥运会的highlights就提了一下，之后就是做题：地里面经Basic Calculator多位，double，带括号，没空格, 没有follow up。之后问问题，我问了一句关于3V广告和视频的问题。小哥最后还问我一个问题：discover应该如何改进。。。

中午吃饭：内推大哥和另外一个姐姐带着我和另外面试同学一起吃饭，很开心。

第二轮：Manager Sebastian，上来问为啥Snapchat，为啥这个职位。面经8x8走K步多少种走法，我开始本着循序渐进的原则，写了BFS然后大BUG又来了，找8个邻居有出错了，又调了好久总算过了，然后问时间和空间复杂度，我分析完他说提高一下，我说DFS可以减低空间复杂度，没让写，然后一看不行啊，得挽回一点BUG的硬伤，马上说觉得可以DP做，然后讲了一下思路，他说：那你写一个DP吧，很快写完了，然后他说你把DP和BFS结果都运行，对比一下。结果不一样:(，眼巴巴地瞅着经理，他说你这pre.swap(cur)啥意阿？我说交换赋值，他问难道交换完不要清一下cur么？我恍然大悟，改完，过。

import java.util.*;
public class Test {
    private int[][] dirts = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};
    public int numWays(int size, int steps){
        int[][][] DP = new int[size][size][2];
        DP[0][0][0] = 1;
        DP[0][1][1] = 1;
        DP[1][0][1] = 1;
        DP[1][1][1] = 1;
        for(int k=2;k<=steps;k++){
            for(int i=0;i<size;i++){
                for(int j=0;j<size;j++){
                    DP[i][j][k%2] = 0;
                    for(int[] dirt : dirts){
                        int prev_x = i+dirt[0];
                        int prev_y = j+dirt[1];
                        if(prev_x<0||prev_y<0||prev_x>=size||prev_y>=size) continue;
                        DP[i][j][k%2] += DP[prev_x][prev_y][(k-1)%2];
                    }
                }
            }
        }
        return DP[size-1][size-1][steps%2];
    }
    public int numsBFS(int size, int steps){
        Queue<Integer> qe = new LinkedList<>();
        qe.offer(0);
        int ways=0;
        while(!qe.isEmpty()){
            int cnt = qe.size();
            while(cnt-- > 0){
                int crt = qe.poll();
                int crt_x = crt/size;
                int crt_y = crt%size;
                for(int[] dirt : dirts){
                    int next_x = crt_x + dirt[0];
                    int next_y = crt_y + dirt[1];
                    if(next_x<0||next_y<0||next_x>=size||next_y>=size) continue;
                    qe.offer(next_x*size + next_y);
                    if(next_x == size-1 && next_y == size-1 && steps == 1) ways++;
                }
            }
            steps--;
            if(steps<=0) break;
        }
        return ways;
    }
    public static void main(String[] args) {
        Test t = new Test();
        System.out.println(t.numWays(3,3));
        System.out.println(t.numsBFS(3,3));

    }
}

第三轮：国人大哥，直接聊项目，很感兴趣我会OpenGL，然后给我个codepair地址，说咱俩在codepair上做，Wildcard Match，讲了DP的解法，写完，又忘记namespace了，不过这次很快发现了，大哥问：你咋这么快就发现了？我说：上午也忘了。运行完大哥follow up说你这个p[j] == '*'的情况，你写了三个L(i - 1, j),L(i - 1, j - 1)和L(i, j - 1)能省一个，你给优化一下告诉我为什么。后来想想说L(i-1, j-1)可省，因为一个可以算成多个，大哥说解释的太通俗，算你过了。然后就是聊天

第四轮：国人大哥，聊他的工作，我开始跟他说Android设备太慢的问题，然后聊得很开心，他说看来你对android还挺有了解，我说不，我不太会，就知道一点点。 题目：一个tunnel， 范围是[0，1]中间有各种尺寸的雷达，(x, y, r)，一个小车只有不被雷达监测的地方可以通过，问给定一个List<Radar>判断小车能不能过去。这轮最成功，一点点和大哥分析出需求，做出来的。最后做完题，边走还边和大哥聊天，指出了在snapchat使用中有个小bug，大哥表示会反映一下。

最后HR就说了一下，我们很快48小时内就给你消息，没事你可以走了。楼主出门直奔大海，眼泪差点掉出来，这一路以来压力太大，投了很多家，都没有消息，要不就是简历跪，只有snapchat给了面试一直到最后onsite，周五就毕业了，要是跪了不知道以后该怎么办。 晚上基本没睡觉，早上十点多收到Recruiter邮件，问我啥时候有时间电话聊聊，然后offer就到了。 总结来说：bug free更好，不然其实也无伤大雅，我四轮都都没有bug free，主要是看你culture fit程度，觉得交流其实很重要。 谢谢大家，找工作找得太晚了，就面了这一家，明天pocket gems店面准备推掉了。努力看看面经和刷题还是非常有希望的，祝大家都有offer！！！

Onsite 31

来补个面经吧。onsite体验还可以，就是下午三轮到最后有点懵，不过和面试官交流的都比较开心吧。culture fit不错。第二天拿到offer。

第一轮，挑了我一个简历上的project问，然后问我如何改进。感觉自己答的没有很好，不过中国小哥感觉人很不错，除此之外应该聊的还可以。题目是两个人是否能通过6个人认识。一步步改进着做，期间纠正了一些小错误，然后也会提示着我需要改进，最后写完代码没用IDE跑，用例子在纸上跑了跑，然后说了说testcase。

第二轮，manager，不知道哪国的人，随便听了听我简历，然后问了k*k，先dfs，再优化用dp，最后问了如果坐标是负数或者棋盘很大怎么办。都写了代码，运行看了结果（心好虚，生怕出来结果不对）。写的比较顺利，最后我问了一个问题，提前就走了，让我休息了会。

第三轮，shadow面，问了我一个项目，问的比较细，还让我说了下里面某个算法到底怎么运行的。题目是假设1T的硬盘，内存只有200G，你怎么排序。其实就是merge k sorted list。写完之后又问如果很多数重复怎么办，经过提醒，国人大哥告诉我应该在merge的时候，对于每次从priorityque中poll后的那个对应的sorted list，对比下自己这个sorted list里后面的数是不是和当前的一样，一样的话直接加进总的list中就可以了。出了点小bug，后面改改也可以了。之后随便问了会问题。

第四轮，中国小哥，问了简历，也和我聊了很多我一些背景的东西。出了个开放性的问题，说的是随便交流一下。我给了个自己觉得可以的解法，当时脑子浆糊了，也想不出其他的了。不过感觉和他沟通的比较开心，所以估计放了我一马吧（题目我就不说了，感觉也没什么参考价值）。

每一轮，提出的每个算法都会要说出复杂度，不是特别麻烦的题目，都会运行。还有聊天环节都会或多或少问对于他们app的看法什么的，我之前做过一些功课，所以感觉聊的比较开心。运气不错，三轮国人面，而且很多题都见过。

祝大家找工作顺利~多尝试，总会成功的。

补充内容 (2016-5-12 00:25): 第二轮是8*8走k步0 0

Onsite 32

发面经回馈地里。楼主是10月末的onsite，面试体验还是很好地。面试地点就在沙滩旁边，每人一个小房间，在里面有准备好的interview survival小袋子，以及墙上的欢迎语。看到了感觉还是挺暖心的。楼主因为当时比较忙，只看了一部分地里的相关面经，如果下面有碰到之前的面经题目但是楼主没提出来，还请见谅。

楼主当天去的比较晚，到那里才发现第一轮的面试官已经在等我了，被领到房间里直接开始，电脑还临时抽风了耽误了十分钟，结果面试官在旁边安慰我说没事没事，电脑就是时不时会出问题 = =！面试官人很好嘛~~ 当天一共四轮，上午两轮下午两轮，每轮一个小时。感觉楼主运气比较好，碰到了三位国人，以及很多leetcode的题目。

第一轮

1. find all amicable numbers. more info on 1point3acres.com 输入一个正整数，找出所有小于这个数的amicable pairs。讨论了一下时间空间复杂度以及如何tradeoff，最后写了时间复杂度O(nlogn)，空间复杂度O(n)的算法。

2. leetcode原题 basic calculator II， 不需要考虑空格， 但是除法结果不限制是整数。 follow up：如果可以有括号怎么做（这个说一下思路就好，没要求我在电脑上写出来运行）

第二轮

1. 有点类似leetcode里面的 valid anagram， 直接可以用hashmap解决的那种。
2. 基本是leetcode里面的 alien dictionary，不同的要求是如果排序结果不唯一，则直接报特殊错误（在原题基础上加一个if 判断就可以啦）。

第三轮

1. leetcode unique paths II
2. leetcode find median from data stream （国人小哥这轮放水提前结束，让我可以多休息一下，感谢~）

第四轮

1. 输入是一串不断更新的数据流，要求输出是其中k个随机数据，每个出现过的数据被输出的概率相同。 楼主之前做过随机输出一个数据的类似题目，当时跟面试官交流的也不好，就直接照搬过来把一个随机输出复制了k遍，然后被告知输出数据不能重复。。。然后思路就卡住了，被提示后知道分两步走，第一步用随机函数得知每次一个新数据来了之后是否使用，第二步如果要使用该数据再用一个随机函数得知替换掉哪个原来存在的数据。 之后要求在电脑上自己写出来各种test case来检测函数的正确性
2. leetcode word break II， 只需要输出一种结果就可以.

Onsite 33

电面： LeetCode原题 Jump Game 1和2 onsite:

第一轮是个外国小哥，算术式Evaluation, 要求支持+-*/()。

第二轮是个国人大哥，一个2D平面有一堆雷达（雷达有x, y坐标，以及能探测到的范围r半径）然后又一辆小车要从y=0和y=1的区间里面通过并且不能被雷达探测到。让写一个function看小车能不能通过。Solution

第三轮是个印度小哥，Game of Life原题。

第四轮是个外国大叔，基本上纯behavior，最后问了一个很简单的题目，就是Leetcode Unique Path ii.

他家聊天会聊很久，大家要注意点聊天技巧。聊得开心就好

Onsite 34

1. shortest distance from all building,

2. android unlock

3. string pattern number,
4. 还有两道面经和leetcode
5. 是关于给一组string sort，规则是除了正常的按ascII字母排序，纯数字的比较需要看完整数字。这里有一些细节需要搞清楚，比如overflow以及首位为0的情况特殊处理

Onsite 35

本来不打算面snapchat，被同学一通说教就去面了。面了之后感觉很开心。。。

1. 第一轮面了道shortest path sum in matrix, follow up 打印路径, 问有多少种最短路径 从左上角到右下角
2. 第二轮 不够言笑的manager,问了道六边形构成的图，问怎么存这六边形，以及如何返回他的六个邻居，。。然后假设有个中心，然后它是ring1 就是第一行的输入， 第二行是它的邻居，第三行是第二行的外层邻居有十二个。。。问你要怎么存这样的结构，然后通过坐标对应的某个元素 输出它对应的六个邻居。。。。。。不过给你的格式是第一行是ring1, 第二行是ring2 第三行是ring3，每一行开始的位置在一条直线上……如果要这样存就要先找出邻居数学关系式。。。怎么存其实不重要，因为总是要找出给你输入格式下邻居的位置的数学关系
3. 第三轮是个健谈的小哥，各种聊，超级哈皮。。跟我一起坐着看着海滩感觉好惬意。。问了game of life 然后问steam 输入的情况下怎么处理。
4. 第四轮 一个permutation 加第k个permutation f