onsite
F：1.find bad version, 比如isgood(version 1) = true, isgood(version 30) =
false, 找出第一个出错的version
   2.BST inorder tranverse
   3. 把string转化成floating number(stof)
behavior question的最后烙印来了一道按列打印tree，follow up是不用hashmap存
node的水平距离，用vector存，如何做，onepass，不准先求树的width
   4. system design: 每个record有个很大field，比如年龄，性别，爱好等。给一个
field的组合，比如小于25岁，爱好体育，query满足这些组合条件的用户个数

L:
1.max point on line/ (如何不是整数坐标如何处理，需要改写hashmap的compare）
2.special container add/remove/removeRandom at O(1): array + hashmap

3.k-way sort given a stream iterator, vector,
4.product of other elements; 考虑1个0 和2个0 的情况
5.实现movemem( void* src, void* dest)

6.system design: tiny url
7.host manager那轮最后问了一个，如何在不影响功能的情况下，把一个data center
的数据复制到另外一个新的data center去。

G：
1. find all rotation symmetric numbers less than N digits,  16891 -> 16891,
2. give integer, 12345, 返回 32154
    give a target  string and list of strings, find the longest string that
has target as prefix, follow up, stream of target string, 用trie，每个节点保
留最长string信息。
3. integer array add one
    rotation abc->bcd->cde, give a list of strings, group them if them are
rotations.
居然给我laptop，然后直接上面写，然后debug通过，给test case通过

4. given grid of colors, coordinate of a point and its color, find the
perimeter of the region that has the same color of that point.
    print all morse code given the length constraints, short “*” takes one
, long “——“takes two. (find a bug in the code) 就是排列组合的典型题
5. design: chromecast, how to know which app can be supported? There is a
cloud that can give the information to the chrome cast, appID, deviceID,
cache design. 

No offer。发面经供大家参考，5轮
1：（1）：写一个bool Palindrome(string s)，就是测s是否是Palindrome。
      （2）：已知bool Palindrome(string s)方程，写一个 int howmanyPalindrome
(string s), 输入s，返回s中包含多少个Palindrome的单词。 例如abbbac返回10，有a
,b,b,b,a,c,bb, bbb, bb, abbba.

2: 给一个树root的pointer，树包含多个分支，树结构要自己创造。求一条最长[连续]
路径。
例如（括号对应上面node）  [修改：还有条件是 连续]
   树：                     2
                 |            |            |                |
                5            7          3                 6
         （|       | ）（   | ）   （|）         （|       |）
            6       3         2          4             5       8
                                 |
                                  3

返回3因为 （2-3-4） 这条线。优化要求时间O(n)


3.时间区间合并问题，leetcode上有相似题，关键词interval

4.(1)一个sorted array，如果其中有一个数重复超过array里面总数的1/4 return
true。就是说{2，2，3，4} return true
{1，1，2，3，4，5，6，7} return false。
（2）优化第一部分用O（log2(N)) 时间复杂度
(3)完全平方解集，做一个：int minsol（int i）。
比如1=1^2 所以minsol(1)返回1,
2=1^2+1^2 返回2,
4=2^2或者4个1^2,1比4小， 返回1，
12=2^2+2^2+2^2或者3^2+3个1^2返回3.

5.有一个游戏，他说是fishing game，给一个数组vector Basket, 比如里面元素
是{2，3，5，1，3，4，7}
有A，B 2个player，规定只能从Basket2端选数字，意思就是A开始的话一开始A只能选2
或者7，然后B选，同样只能2端选。所以比如一开始A选了7，B只能从2和4中选。问给定
数组A能取的最大值。B的策略已知，是greedy，就是总会取最大的那个数。
写一个 int maxA（vector& Basket）；

 一个BST, 给你一个区间, 返回结点值全部在区间内的子树的结点个数.
比如:
2
1 3
区间 [1,2], 只有子树1,
返回结点个数1 .