1 5轮 过了地址
1. 在一个巨大字符串流中找第一个unique char
solution: 简单题，跟leetcode解法差不多。但是面试官的expectation很高，
我基本把我能想到的各种解法(one pass, two pass, hashmap, linkedlist)都写出来了。
最后面试官还问我怎么用一个HashMap<Character, Boolean>去做，我当时没做出来，比较tricky。
后来面试官又跟我说了下做法，这样的话得two pass，没有我说的optimal solution one pass好，blabla
2. input是一个矩形，生成矩形里的随机点。followup 1: input有很多矩形，不会重叠; followup 2: input很多矩形，而且会重叠。
之前面经也出现过，典型题。followup2没有要求实现，我大概说了下思路，中心思想就是分割成一个个竖矩形。
先把矩形分成左右edge，然后edge根据x coord排序，然后左边扫描线扫过去。事前可能还需要做下discretization，
把所有坐标对应到不同的integer index; 扫描过程中可以运用线段树优化，使每次query和update控制在logN. 大家可以参考Atlantis这道POJ的题，是求重叠矩形的总面积, 很经典的扫描线+线段树.
3. dp题，类似于path count，不过稍微复杂一些，followup比较繁琐，我就不说了。
4. 生命游戏, 利扣得 而把就, 这题跟leetcode不一样的地方是input 是二维boolean数组。我首先new一个新matrix存放结果；面试官要求降低空间复杂度，不能new matrix；input是boolean不能用来像int那样利用一些冗余bit，后来我搞了个滚动int数组, 保存当前行和下一行的count，对于每个cell center给下面三格和右边一格 +1, 反过来也+1. 这样的好处是cell不会访问之前已经处理过的结果。面试官说that might work.
5. 利扣得起散斯 起散起，注意有些变化。起散起跟题目不一样的地方就是，原题是A->B, A->C能推出B->C，我被问的时候，面试官说不能推出B->C。所以这道题只能保证transitive, 没保证symmetric. 所以这个图是有向图，有向图不能用Union Find做，只能老老实实用DFS.
2 5轮 北极熊大哥 跪了
1. 求byte stream里面“10”的个数。 自己定义input，楼主脑残用的char[]，写了个bug是右移会补1。
另外一题是给n个点的pairwise distance，假定所有点走在x轴上（一维），求它们的坐标。可以假定第一个点在原点。
这一题后来想到了一开始分析以为upperbound有2^n，后来提示发现只有最多一个解。
2. 给一个二维数组，里面的值代表可以到四个方向的跳的距离，问能否从左上角到右下角，followup最短距离。
第二题range sum 1D的变形. array里面每个值是宽度，要求写两个function，setindexwith(int index, int width), getpos(int x).
就是说一维的array存的是宽度,比如[1,3,2,4]， 然后getpos(int x）就是给一个x，比如5，返回的index是3 。
给了个提示后用segment tree做，没写code
3. 给一个AST，求表达式，要求支持+-*/，followup code maintainable。应该考的是设计模式factory method之类的，
然后是zigzag iterator
4. 给一个list of edges，求所有reciprocate 的edges数量。read4k。估计是看我写过，又出了个题，大意是给n个选手进行比赛，
一个 bool canbeat(int a, int b)可以return a 是否能beat b。
要求返回一个sequence，这个sequence只要求相邻两个中前面能beat后面。
就是 假设 1 beat 2 , 2 beat 3, 3 beat 4, 3 beat 1， 4 beat 1 你可以return "1234"，就是虽然3，4能beat 1，
但是不相邻就无所谓。 这个给了提示，merge sort 可做，没写code
5. 问了版上猜单词的那题。不知道正确解法是啥。
3 4轮 摩托车小朋友。 跪了
11.15 昂赛
听说G家内部题库一千多道，就没怎么刷题准备。吃吃喝喝倒是挺爽的，强烈推荐san jose的韶山印象，不错的湘菜哈哈哈。
G家昂赛感觉没有FB那么形式化，比较casual。地点在tech corners
十点半刚到building，一个俄罗斯小哥招呼我面试。
喝了杯咖啡，小哥看看表，问我想不想提前开始，我说好～
1. dp题。给一个grid的宽和长，求得从左下的点到右下的点所有可能的路径之和。
起点当然是左下，要求每次只能走三个方向， ➡↗↘
follow up: 2d dp -> 1d dp
第二轮面试官是一个在G工作7年的美国大叔。
题超级简单。
2. 假设我们有一个数组「0,0,0,0,3,3,3,2,2,5....」
设计一个class，封装成 「{4, 0}, {3, 3}, {2, 2}, {1, 5}」
basically把所用重复个数和value本身封装在一起。
第一问写一个function input是一个idx，找出相对应的value，比如5->3 / 8->2
第一问我就写了一个O（n）遍历
follow up如何封装一个extra参数，优化时间。
{4, 0, x}, {3, 3, x}, {2, 2, x}, {1, 5, x} 答：binary search
中午吃饭，越南小哥要吃粉，据说很好吃。没敢吃怕下午太困。
第三轮，中国小哥。
扫地机器人面经题，基本dfs解决，给了两个api，turnLeft/Right。方向问题比较tricky
小哥极其pushy，写一行就问我在干什么，接下来怎么做，到底对不对。
打断思路n次，最后写出来了。有几个bug，他说已经good enough.
第四轮，中国大叔。
全程高能，一道简单题没想到思路，全程hints。写出来code发现极其easy
给一个公式2^i*5^j
给一个上限N，求得所有可能的数(i >= 0, j >= 0) 并且increasing order输出
这题想了几种brute force，backtrack，不认可。
始终没想出如何优化空间，最后这题提示下想到用priority queue.
这题楼主没做过，后来发现就是ugly number ii。我花了45分钟勉强写一个O(nlogn)，面试官心里的答案是O(n)
挂的妥妥的。
总体来看题并不难，怪自己刷题不够。恶补基础了
4 5轮，没头像小哥。挂了
1. 白人大哥。首先瞎聊聊了好久，然后给出排好序的一个list如【2，3，7，9】经过二次变换ax+b之后重新排序 ---
挺简单的讨论了一下a的三种情况，算出极值点x0=-b/2a 然后就On写出来了。事后问不算x0可不可以，说可以，从后面往前排，
还是On。白人大哥满意拍照走人。
2. 国人小哥。上来直接做题， 给出一个长一个宽，问从左下角往右下角处走有多少种方法。
每一点只能往右，右上，右下走。DP挺简单的小哥也很耐心，做完后小哥说solution出来了，ok然后拍照走人。
3. 午饭后白人胖子大叔迟到15分钟，问了一个typeahead的算法实现（后来才知道这是个经典系统设计题）。题目完全自由设计，
给出prefix和k值，问输出头k个最大可能性的词。我说了用trietree，找到prefix的最后一个字母作为入口然后dfs遍历所有节点
找到头k个频率最高的词，其中设计时我说每个点记录所有子节点的最大频率。大叔说这个设计可以，但要求不遍历的来找出近似的最大k值，
然后讨论了一下子，没太搞明白什么为之近似的头k个值，反正就让我先写，最后写到dfs部分时间也不够了就结束了。没有拍照就走人了。
4. 国人小哥，全程中文并且放水。0变01，1变10。第0行是0，第一行是01，第二行是0110，第三行01101001。
一直下去问求第k行第j个数是什么，递归On时间On空间搞定拍照走人。
5. 国人女孩，全程很nice。问了一个设计题说主要考software engineering的能力。设计get（key）和put（key， value，timestamp-delta）。
要求get key是返回value值但得确保是有效时间内，同一时间内可以put多个相同的key但不同的value不同的timestamp，
每次只要最后输入的有效即可。我设计了一个node来保存value和时间（该时刻系统时间+delta）然后put的时候用了hashmap Integer key和stack<node>作为value。
最后很快写完了国人女孩满意，说假如是她她也应该是这么写。最后followup问了假如一段时间内大量的put没有get或只有get没有put然后记录了中间很多已经expire的怎么办。
这一点我说了好多数据结构，两个stack同时进行或者一个stack一个queue，还说了priority queue一大堆拿出来讨论不断的检测，发现过期的扔掉。反正是个开放的题，
事后问她她也说没有标准答案。不知道这算不算没答好。貌似这题在实际生产中很常见，也只能怪自己经验不足。
总体来说这次狗家题目偏简单并且第一次感觉离狗家如此近，结果一周后收到最不愿意听到的unfortunately电话。问细节说不能透露太多直说coding什么implement的要提高。。。说了等于没说。。。很好奇为什么大家都能听到breakdown和一些更具体的分数而我感觉没有这种feedback。连HC都没进啊啊啊。
Anyway只能move on了，还有就是求大米求安慰。
class Solution():
def ways(self, n, m):
if not n or not m:
return 0
dp = [[0]*m for _ in range(n)]
for i in range(n):
dp[i][0] = 1
for j in range(1, m):
for i in range(n-1, -1, -1):
up = dp[i-1][j-1] if (i-1)>=0 else 0
down = dp[i+1][j-1] if (i+1)<=(n-1) else 0
dp[i][j] = dp[i][j-1] + up + down
print dp[-1][-1]
s = Solution()
s.ways(3, 3)
5 4轮 一言难尽哥 4轮 跪 果然是一言难尽，而且东西也说不清楚。
我是十月初决定面试 gg 的。 之前各种原因一直没有面过onsite。 十月的时候工作变动导致要relocate.家庭原因没有办法，所以失业了。
名校，phd 排名很靠前，然后叫同学投了，直接onsite 面的。 因为很久以前phone interview 过， 当时可能没有合适的 position.
然后有七年工作经验。 一直都说gg 面试很technical. 所以我花了很多很多时间把所有统计知识巩固了一遍。 但是感觉面下来 ，
问的具体的概率统计这种有definitely answer 的题目没有多少。 多数还是openended , A/B testing 的题目。然后有些题目，
版上的面经都有的。 这个onsite 有NDA我就不具体讲了。 我发现， 工作过的同学， gg 会大量的问你关于你在工作上面写的简历经验。
至少有两轮我被狂问这些细节。 这个和大家说的面经是有些出路的。
然后很重要的一点是。 Gg 改了QA 的面试流程。 现在有个专门的engineering 来考你coding. R, python, C++ 都行。
而且题目是挺长的那种engineeringapplication 的题目， 关于machine,id, time
等等。 题目其实并不难， 但是题目有点长， 加上lz interview紧张， 反正是做的磕磕碰碰的。是这四轮中面的最烂的。 面完这个， lz 整个人都不好 了。 其实我觉得有点挺frustrated.
楼主从东岸飞过去面的， 然后schedule都说好了， 午饭前两轮， 午饭后再两轮。 然后楼主当时没有吃早饭， 前天也没有休息好。 面完前面两轮， 那个要陪吃饭的老美进来了， 我拿着包就要和他去吃饭。
然后他说， 不吃饭了， 改schedule了，我来加面你 coding . 各种仓促。 急忙跑去上完厕所， 回来自己和老美说饿的不行， lz 自己从包里拿初剩下的水果肯了两口。 开始面， 发现没有chrome book, 然后后来发现有chrome book ，
但是不work.然后要白板code.楼主就开始紧张了。 然后就不行 了 。 我觉得这轮面的时间都不到45 分钟， 有点愤怒 。
第一轮是个印度人，是个小的hiring manager. 然后做和ggwallet 有关的。他自己面完楼主另外问了一个项目问题时介绍说的。 就是一开始问了楼主写关于背景没有细节。 然后就问了一道A/B testing 的题目。 A/B testing 问的非常具体。
第二轮是个中国mm. 问了具体楼主工作的project. 然后问了一道概率题， 楼主给了答案。感觉并不是她要的， 然后问了到A/Btesting 的题目。 这里我建议大家看google 的unofficial Data Science blog. 她问的和其中一个文章内容差不离。
第三轮就是这个悲催的老美engineer 了。 其实本来面第三轮的也是一个有统计背景的 QA. 我不知道是这个人真的临时有事情， 还是就是gg 换了standard, 专门叫engineering来面coding.
第四轮。 这个是午饭完的时候面的。 是校友， 以前做过 faculty. 后来聊天了解到的。 各种问工作经验还有googlequestionnaire 上面的问题， 就是你面试前叫你写答案的那个。 然后也是问A/B testing 的题目。 楼主强调下， 统计概念一定要弄懂啊。
啥type I ,type ii, 啥是confidence interval.整个面下来还是A/b testing, open end question 占了大多数。70% 至少。
A/B testing 的题目， 楼主自己觉得答的挺不错的。 特别是第一个印度人， 他也表现的各种满意。最后还加问了他自己项目的一个小问题。 就是这些了。
吃饭的小哥特别nice, 楼主面完那个coding 各种分心， 吃饭的时候也走神。 小哥各种安慰还给留了email,说有问题问他。 是个刚进 gg 几个月的新人 。
知天命尽人事吧。 楼主努力过了， 求各种bless. 我知道其实拿 offer希望并不大， 因为coding 做的极烂， 做出来了一题，另外一题没有做完， 吃饭小哥在外面等了。
然后就是其中面试的老美，自己发给楼主题目， 自己用laptop可能写review, 可能做事情， 感觉没有太多interaction.
一周后知道已经跪了。 Hc 没有过。