Google Interview Misc Part 5

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=141633&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
题目大致是BACCBBAAA -> ABABACABC，就是输出相邻字母不能相同的string，这题要用到heap第一题估计是用贪心法，每次把出现最多的字母解决，我试着用priority_queue写了下：

1. unordered_map<char, int> map;
2. string noSameNeighbor(string & s){
3.         string ans = "";. 1point3acres.com/bbs
4.         for (char c : s). more info on 1point3acres.com
5.                 map[c]++;                .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
6.         
7.         auto comp = [](char char1, char char2){return map[char1] < map[char2]; };
8.         priority_queue <char, vector<char>, decltype(comp)> pq(comp);
9.         for (pair<char, int> p : map)
10.                 pq.push(p.first);
11. . 鍥磋鎴戜滑@1point 3 acres
12.         while (!pq.empty()){. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
13.                 char c = pq.top();
14.                 pq.pop();
15.                 if (pq.empty()){
16.                         ans += c;
17.                         break;
18.                 }
19.                 char d = pq.top();
20.                 pq.pop();
21.                 ans += c;
22.                 ans += d;
23.                 map[c]--;
24.                 map[d]--;
25.                 if (map[c] > 0) pq.push(c);
26.                 if (map[d] > 0) pq.push(d);
27.         }
28. 
    
29.         return ans;
30. }

2. 用尽量短的string生成4位数密码的所有组合.
http://www.mitbbs.com/article_t1/JobHunting/32604357_0_1.html
4位的密码，遍历完所有0000-9999的可能性后，锁就能打开。 -De Bruijn sequence?

把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
连续四位肯定能够能解开锁。

上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。

This is not gray code.  No need to formulate it as TSP.  Also, debrujin 
graph only gives you a problem formulation.  

You can solve by finding an Eulerian tour.  Each node is a 3-digit number eg
100, and two nodes 100 and 001 are adjacent if they can be combined into 
1001.  Now every node has equal in-degree and out-degree, thus an Eulerien 
tour exists and can be found using the standard algorithm.

现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。

把所有的3个数字看成1个节点，点与点之间连有向边当且仅当第一个节点的后两个数字等于第二个节点的前两个数字，每一条边就表示一个4位数字，如1234表示成123->234这条边

节点的移动表示新加了一个char，遍历所有边即包含所有串，该图显然满足有向图欧尔回路存在条件，求一遍欧拉回路即可

欧拉回路代码就几行 网上随便找

我能想到的就只有暴力的生成这个10000个密码，一边生成一边在我的解里面查是否已经contain了，不contain才append上去。 这样既慢，又不能保证得到最小的解

3. 生成palindrome number， 然后寻找最相近的palindrome number，最简单的了，不过要注意奇数个digits和偶数个digits, 

4. 黑白2D array表示的image。边长是2^n。设计一个class来存它，用尽量少的space。提示是可以不断把图形分割成四块，分完继续分。如果其中一块里面所有格都是黑，那一块就是黑。
   然后连个相同大小的的image相交生产第三个image，遵循黑黑得黑，其他都白的规则。
第二题：就是把所有4位数字的密码存在一个string里面，比如123456 = 1234和2345和3456
第四题：我还真没想到还有quadtree这种东西.. 我最后用map和数列推导做了一个东西，现在想想和quadtree是一个意思，我相当于用map把tree给表示出来了.. 准备还是不充分啊

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=147906&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
第一轮： 给一个 M * N的screen，和一个String,比如“Hello World", 请问整个screen能放下多少个string。
note: 如果有一个词在一行放不下，放到下一行。 
然而虽然是原题LZ还是写了好多bug...不过貌似人家不在意。这里大约用去了10分钟。
然后人工跑test case，这里用去了15分钟，然后找到了3个bug :(
Follow up是如果M和N巨大（比如1M)怎么办。。。。电面感觉的到对面想法设法的提醒可是楼主还是不会。最后瞎猜了一个好像猜对了也没听清，电话吵得不得了。所以上来问问大家，这个题怎么做，复杂度不希望是基本的O(MN),而是希望更小，比如O(NL) where L = # words in the string.

好像可以达到 O(L log L)， L = number of words : 算法是用DP: 存两个L长的数列 第一, i th entry：一行如果从第i个word开始能存多少个整句  O(L) i.e. a_1,......,a_L  第二, i th entry：一行如果从第i个word开始会到第几个word ( binary search ? ) O(L log L) i.e. b_1,......,b_L   接下来有点像recurrent decimal, 每行开始的word i 会重复，比方说： 1 ， 3，5，7，1，3，5，7。。。1, 3 找重复的cycle length:  这个例子是4...  O(L).鐣欏璁哄潧-涓€浜�-涓夊垎鍦� 最后算total:  O(L) number of lines = (M/4) * ( a_1 + a_3 + a_5 + a_7 + 3) + a_1 + a_3 + 1 不确定这方法有没有错，请大神帮忙看看^^

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=147450&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311

Q. Define a binary search tree, how would you find the median in a binary search tree. 第一题不知道可不可以recurtion inorder tree node, 存储在一个list里，然后找list中间那个数就好了，时间复杂度O(n) 可以将空间复杂度降为O(1),如果不考虑循环时的栈空间的话，先数下个数，然后再一个inorder中得第size/2个 Q.Return the top 10 most frequently used words in a text document.

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=147885&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
There is a museum organized as NxN room. Some rooms are locked and inaccessible. Other rooms are open and some rooms have guards. Guards can only move north, south, east and west, only through open rooms and only within the museum. For each room, find the shortest distance to a guard。

可能是第一轮的问题吧 按照面试官的解法，时间复杂度是NxN 先把所有距离设为INT_MAX 然后把(each guard,distance=0)放到queue里 每次pop出来一个，检查周围的格子，不是INT_MAX就设为distance+1,然后把这周围几个格子再放到queue里 如果dp最后写对了，复杂度也是最优

. 鍥磋鎴戜滑@1point 3 acres
我说用BFS，从每个guard开始搜，更新distance矩阵。面试官说有更优的解法。我提议dp, 被否了。提示说把guards都放进queue里，不要一个一个搜。我没有理解到。所以他就让我按老思路写了。估计是这轮挂了
但是保证了每个node只enqueue一次

(1)Set A - B
(2) 有一个村庄，流传着两种statement：
1. A 死了之后 B出生。
2. A和B有overlap。
现在有很多这样的statements，要你判断有没有inconsistency.
这题隐藏两种inconsitence：
1. statementI有环
2. 如果 A 和 B 有 overlap， 那 A 就不能跟 B的 ancestors （generated from statement I）有 overlap， vice versa。
我的做法是DFS找环，同时maintain一个ancestor的set。找explore children节点的时候，check他们是不是跟ancestors有overlap。 
改成:　如果 A 是 B 的 child
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156487&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
1. 理论题： Flaky test: It's a test which when run many times fails a few times. 

Reasons?

2. coding: give a list of string, define product as:

product(s1, s2) = 0 if s1 and s2 have character overlap

                          s1.length * s2.length if s1 and s2 are distinct

find the max product of the list.

. From 1point 3acres bbs
刚开始直接想到 string permutation,就说了sort和hashmap求frequency的两种办法，但阿三似乎都不满意，一直问能不能减少operation
实在想不出，厚颜无耻的问 can you give me a hint， recruiter很不错的提示说bitmap，眼前一亮呀！最后就是用bit operation 处理的
overlap是指只要s1 有字符存在s2中就可以？ 是映射到256bit上么？
对的，只要有重复字符，product就为0.
它规定了是word，所以52bit就够了
第二题做法是不是对每一个string建立一个new int［8］这样就生成了一个array（new int［8］），然后循环之，找到最大？
每个int是32bit，所以不够，可以用一个long来表示一个string，所以只需要long[list.length]就是表示所以的string
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=146043&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
第一轮答了三道题。第一题给一个行和列递增的矩阵，找一个target number。

第二题，将一个正整数分成若干个数的和，求这些数的最大乘积。
我写了个dp, dp表示把i分解后最大的乘积
int maxProduct(int n) {
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i / 2; ++j) {
            dp[i]= max(dp, dp[j] * dp[i - j]);
        }
        dp[i] = max(dp, i);
    }
    return dp[n];
}
感觉很像leetcode total count of bst那个题。。是这样做的吧，楼主？
更正下:dp[i]表示把i分解后最大乘积。。
j不需要走到i啊，走一半就可以了，因为后一半和前一半是重复的。。

把数一直拆成3，3，3，3，3，3，3，最后如果剩4，就拆2，2 。。。因为3*3=9>2*2*2. 所有一个数要尽可能的拆成3.最后实在没有3个就带2.

1.         public static long maxProduct(int n) {
2.                 if (n == 0) {
3.                         return 0;
4.                 }
5.                 long[] dp = new long[n + 1];. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
6.                 dp[1] = 1;
7.                 for (int i = 2; i <= n; i++) {.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
8.                         long res = i;
9.                         for (int j = 1; j < i; j++) {
10.                                 res = Math.max(res, (i - j) * dp[j]);
11.                         }
12.                         dp[i] = res;
13.                 }
14.                 return dp[n];. From 1point 3acres bbs
15.         }
16.         public static long maxProductN(int n) {
17.                 if (n == 0) {
18.                         return 0;
19.                 }. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
20.                 long[] dp = new long[n + 4];
21.                 dp[1] = 1;
22.                 dp[2] = 2;
23.                 dp[3] = 3;
24.                 for (int i = 4; i <= n; i++) {
25.                         dp[i] = Math.max(2 * dp[i - 2], 3 * dp[i - 3]);
26.                 }
27.                 return dp[n];
28.         }

第三题，平面上有很多点，找一条平行于x轴的直线使这些点到该直线的距离之和最小，并证明。是中位数的那个点。证明：你可以把点按照y轴排序好，把所有点group成pair，比如（－1，0，3，6，7）, 然后－1和7一组，0和6一组，3一组。 然后就好证明了

第二轮是面试官听口音应该是国人，比较nice。题目是给一个字典，里面全是string，字典很大，可能有几百万个string。然后写一个方法判断输入是否有一个typo，否则返回false。比如，字典有google，facebook，amazon等。输入google返回false，因为没有typo。输入geogle，返回true，因为有一个typo。输入geogla，返回false，因为有多于一个的typo。
字典那个最简单的做法就是挨个char替换过去，然后找是否在字典里出现吧，这样复杂度是O(26n), n是word的长度
我是用的字典树，然后逐个往下找，如果有一个不match，就拿别的替换继续向下找。
http://instant.1point3acres.com/thread/144285?from_discuz=1
第一轮，设计一个类似于消方块的游戏，通过滑动交换items, 每行每列都是凑够三个相同的item就消掉，然后让你初始化一个board,初始化后的board要能使用户能够做出firstmove 意思就是你不能一开始通过移动消掉任何方块。而且也不能产生三个连在一起能直接消掉的方块。
楼主用的方法比较二逼，反正最后就是说你可以用dfs来产生这个方块，如果遇到违例的backtrack换另外一个item来产生。

第二轮，这是楼主感觉挂定的一轮。。 说你有三台接啤酒的机器，分别是small，medium, large. 这三种size的机器按一次button一次分别能distribute, say 100 - 150ml, 200 - 250ml, 300 - 350ml的啤酒，每台机器出来的啤酒量是区间里的任意一个数不确定。说现在一个顾客自带一个“杯子“，这个杯子任意大小但是有两个限制 就是min和max volume意思就是 你最少要接到min(ml)在杯子里，最大能只能接max(ml)，然后你要想让顾客满意必须接在这个区间里面的那么多啤酒。比如说我有一个下限min是300ml 上限max是400ml, 那么我按一下small是接不够的， 我需要在按一下midium才能接够。但是有的时候我按midium可能也不行，比如说我midium的区间换成200 - 300ml, 那么我按一下small再按一下medium就可能接出（100 + 200）- （150 + 300）ml的酒，which is not valid cause (150 + 300 = 450) might exceed the max volume(400ml) of the cup。这种个情况或许你需要连续摁记下small或者摁一下或者记下small再摁下large解决。

Anyway,楼主觉得这道题肯定是要递归回溯的，当时有点紧张，加上case实在有点多，关键是leetcode真心从来没做过类似，瞬间智商不够用了。总之这轮基本上只写出了basecase然后最后说了下我想大概怎么解决。。。
输出就是你能不能找到通过按任意size啤酒机button的组合，例如（小，或者小中大， 小小小，中大大），最后使顾客能满意的,就是接的酒落在顾客杯子的min-max区间内。能找到这样的组合返回true,找不到false.

感觉像凑硬币题，给你无限多的1,2,5硬币，问能不能凑出某个钱数，这个题1,2,5变成了range, 某个钱数也变成了range了

第三轮算简单，类似于LRU的感觉，说不断地给你push data stream你需要打印出这些data,但是呢如果当前data在过去十秒内出现呢就wait and skip to next，但是跳过不代表不管你仍然需要somehow记录他在这个时间点出现过，因为接下来十秒内可能又出现这个data, 而你要是用旧的最开始的那个data的话可能此时他已经在十秒外所以你就没管就把他打印出来了， 但其实你第一个十秒内遇到duplicate的时候应该记录一下那个时间点，所以说有可能不需要打印最新的这个repeated data。时间点的话假设你可以直接用一个什么Time.getTime()之类的方法get这不是重点。

楼主基本上就是用一个queue来维护时间和data,然后没新来一个加到队尾同时把队首超过十秒的都通通poll, 同时用一个hashmap来不断更新data以及其出现的时间，如果超过十秒的就要随着queue一起也将超时的data从hashmap里删掉（必须删因为可能每秒的数据量非常大，你不删光保存并更新时间到最后内存会不够，这儿更新是个小trick我就懒得具体说了，我提到了更新大家应该都能知道什么意思）, 没超时直接更新。基本就是这样其实不难。.鏈枃鍘熷垱鑷�1point3acres璁哄潧

你有一个sidewalk（你可以想成一段距离或者一个range 比如说一米），然后有一个raindrop随机生成器，没滴raindrop都有一个宽度比如说1cm 然后开始随机下雨，雨滴之间可能会compeletely or partially overlop,  or totally seperate，三种case, 然后问你下多少滴雨才能让这个sidewalk完全淋湿，就是雨滴完全覆盖那1m。

我一开始的思路是leetcode上longest consecutive numbers in a array那道具体名字我忘了，反正就是个hashmap维护一个边界和长度。我随意写了点基本上就是写了一个data structure维护一个雨滴edge x坐标，以及长度，通过最新产生的雨滴overlap情况选择新创建一个雨滴加入list（其实本来应该用某种排序的list按edge x排序的方便后来两两raindrop range之间合并) 还是与之前的某raindrops range合并（这个合并其实情况也蛮多 楼主当时都没时间说完了）。最后的话一直到这个list里所有raindrop range的总length >= length of sidewalk(1m) 那么就算完全覆盖了。

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156606&page=1#pid2100576
1. 3sum smaller
2. 给一个textbox， 知道它的长度和宽度，一个string， 问最大的font size能让这个string fit进textbox里，已知两个function：getheight（fontsize），getwidth（fontsize，char），在同一个fontsize时，所有字母高度一样，但是宽度不一样
3. sorted array X，f(x) = a * x ^ 2 + b * x + c, 求sorted array Y={f(x) | x belong to X}4. word break 2
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=143202&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
上来就聊social newtwork，讨论里面的connection怎么去assign weight，没什么经验，直接各种脑洞，也不知道说得有没有道理。然后让写一个从一个social graph中找出N个朋友的function，这里我一直以为要用着那个edge的weight，结果开始往最长路径上去想，结果就GG了。后来就写了一个BFS到N个的时候就停止，结果被指出来一堆bug，比如visit的节点忘记加入set了，没处理null的情况，没处理N为非正数的情况啥的。主要还是一上来就被问懵了，这一面感觉就跪了。
第二面，一个中年白人。第一个题返回一个字符串中出现次数最多的字符，然后把这个题用MapReduce重新写一遍。
1. 没有mapreduce的经验，写的代码不用严格按照mapreduce的语法格式去写，但是要写出个大概的样子.

第二个题写二叉树的最深深度。第三个题是leetcode上那个把二叉树每一层的节点水平的连接起来。第四个题写N！中0末尾0的个数。这一面感觉没什么bug的地方，感觉一般。.鏈枃鍘熷垱鑷�1point3acres璁哄潧
第三面，一个很geek的三哥。实现SQL里面的group by的functionality，用最直接的方法实现后，更改一下文件的存储方式从而实现更快速的方法。最后拓展到distributed storage上面去，有多个machine在运行你的database，问怎么设计文件存储的方式，从而使你的query尽可能快的完成。这一面感觉一般。
对的，用hashmap是最基础的方法，之后他要求改变文件存储的方式从而更快的获得

第四面，一个年轻白人。自己设计接口，使得支持两个funciton：onUpdate(timestamp, price) 和 onCorrect(temistamp, price). 可以理解为有一个时间流，每一个timestamp都对应一个股票的时间，每次调用一次onUpdate的时候，就对我们设计的那个类更新对应的timestamp和price， onCorrect就是修改之前的一个timestamp的price。最后，我们的类要能返回latest price， max price 和 min price。一开始题目描述的太模糊了我都不知道到底要干啥，墨迹半天才知道是想设计一个类，然后中途也写的乱七八糟的，用了两个Deque来存储一个递增和一个递减的序列，类似窗口题的方法。当onCorrect的时候就去看队列里面有没有对应的timestamp，有的话移除然后重新入队。感觉这面面的也不是太好。
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=139392&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
一堆人参加比赛，最开始谁和谁先比是确定的，比赛是两两配对，一轮一轮进行，print出若有round和可能的组合。比如 有 ABCD四个人比赛， 那结果是：
1  A - B
1  C - D. from: 1point3acres.com/bbs 
2  A - C
2  A - D
2  B - C
2  B - D

但是要考虑一个情况，就是有五个人比赛，比如 ABCDE五个人， 那么E这个人可能是在C和D比完后和他俩的胜者比，或者E 和 AB的胜者比。或者E 和 ABCD的胜者比。
问题：1.用什么数据结构存比赛者。 就说二叉树就行了，把比赛者存在叶子节点，怎么构成不需要你考虑。
          2. print出结果（应该就是postorder traversal了）

第二轮：1. largest substring with at most M distinct characters，但是输入的string是以stream的形式;    2: word abbreviation那题，给个字典，判断有没有和输入的词的abbreviation相同的词。

第四轮：给了一个双链表，在给一个list，list里面装的是双链表里面的某些node，面试官说可以通过list里面的node直接访问双链表里面的node。  然后根据list，求双链表中有多少个components。
example：  A-B-C-D-E.  list：[A E D]  那么就有两个components: A 和 D - E
第五轮： 给了N个城市，和N-1条road，且这些road可保证城市间均两两互通。 比如 SF--SD--LA ， 每个road都有长度，求所有两两之间的path的和，然后除以所有的path数得到平均值。。。（也就是: SF到SD + SF到LA+ SD到LA 再除以3）。  当时有点晕。。写了个brute force = =
1 先求出每个城市的“连接度”，即有多少个城市和当前城市相连。
2 把连接度==1的城市看作是 叶节点。和叶节点相邻的节点看作是第二层， 和第二层相邻的是第三层，以此类推，直到最内层的节点即为根节点。

1. 
   
2. 如  A -- B -- C -- D
3.               |
4.               E    
5. 
   

这种情况，A, D, E为叶节点，B或C为根节点。

3 在每个节点处储存以其为根的子树中的节点数目。如上例中，A，D，E的子树就是自身，所以节点数为1；. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
选C做根节点的话，B的子节点数为2（A和B），C的子节点数为5。

4 从叶节点开始，逐层删除节点和其与之父节点相邻的路径。如果一个节点的子节点数目为k，那么有下列规律：.鏈枃鍘熷垱鑷�1point3acres璁哄潧

每一个节点与其父节点的路径被走过的次数 = K * (N - K)

这条结论我没有严格证明，但应该是正确的。. visit 1point3acres.com for more.

这样每删除一条路径，就能在O（1）时间内知道其总共被走了多少次。最后取sum(路径走过的次数 x 路径长度）/ 路径总数即得答案。时间复杂度为O(N)

如上例 
先删除叶节点A D E，可知，路径AB，DC，EC均被走了1* (5-1) = 4次
再删除第二层节点B，因其子节点数目为2，可知路径BC被走了2 * (5-2) = 6次。
. from: 1point3acres.com/bbs 
这道题， N 个结点， N-1 个path 而且两两互通。
我感觉就是一个 无环的连通图的遍历， 用BFS遍历就可以解决了。
不知道我是否想的过于简单了
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156565&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
1. longest substring with at most m distinct characters。问了一堆怎么优化。最后面试官问我是不是见过这题，我说见过类似的，他似乎很不开心，说你应该一开始就提出来。
2. travelling sales man。暴力解。问了很多特殊条件下的优化，比如怎么存图，如果每个城市连接5个城市，复杂度
3. 中国姐姐问的问题，比较2个DOM tree，设计数据结构。注意tag当中有可能包含text。dfs解。姐姐又问怎么节省空间，python的yield关键字会不会。我说不会。
她就找了个网页，给我看了些yield的例子，让我写。最后没写出来，她说写得比较接近了。这么短时间学会，可以了。

就是树的结构啊，DOM就是个树啊。每个node有个children list，表示子节点。因为有可能有text的，我用的方法是把text也放到一个特殊的node里。

比如<html>hello <p>world<p></html> 就是：

   <html>

      <text> hello </text>

      <p>world </p>

   </html>

4. 计算 + 7 (* 8 19) (* 12 (+ 1 2))这样的表达式，就是 7 +（8*9）+（12* （1+2））.

鐣

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=154263&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311

手机键盘的马走日，给定起点和步数，问有多少种可能。
递归，复杂度太高。加上memoization。

当时他让我优化的时候我还问他DP行哇。然后我们就开始讨论DP了，他问我DP的核心思想是啥，你要用DP的话状态是啥，这题如果要用DP的话实际上解决的是另一个和优化有关的问题。然后我跟他讲，其实呢我这个memoization也算是DP的一种，lazy update嘛，recursive DP，然后他也算是同意，如果我真要用DP来做的话，做出来跟我现在的实现是很像的

但跟我描述的时候是说什么每个cell的bottom和right或者 两边全部有wall，这样就和平时遇到的.和x这样的输入有点不一样了。需要转换一下。
因为各种听不懂他的意思，我就不知道他到底想给我啥输入。期间他提了下怎么存输入，我没听明白，再问他，他又说don't care。。。诶哟。。存路径这个问题我没想明白，应该存一个current->pre的map，最后反向打印

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=148592&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311

给一个doubly linked list，再给一个array of list node，求这些list node组成的separated connected component个数大概就是 1<=>2<=>3<=>4<=>5<=>6
给的array是[1, 3, 5, 6], 那么component就有 (1)， (3)，（5<=>6） 3 个

我的思路是假设array长度是n，于是假定一开始有n个component，把array里面的node放到一个set里面，然后对每个node，看它的前驱和后继是不是在set里，如果在的话component总数减一。
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156185&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
第一轮表现一般，又面了一轮： 中国小哥，1.anagram string group ，2. 找到二叉树每层第一个元素，3 candy

onsite 四轮：
1.美国白人，perfect square ： 给一个数n，找到最小的数目的平方数组成这个数。 输出为list2.亚裔小哥，find peek num（先增长后递减的数组），然后是 zigzag iterator ，设计就好，讨论的很开心

3. 中国小哥，随便一个数组，找出local max。 秒杀。 然后问如果给出是二维怎么办。我先说dfs，说复杂度太高，然后提示二分，脑袋笨没想出来。大哥直接告诉我算法怎么实现，然后我灰溜溜的实现了代码，当时就感觉跪了。。。。

4.印度小哥，张口英语有点不适应，给出一堆interval，和一个range，问最少几个interval覆盖range。 我先想到了dp。小哥说复杂度高了，提示了我一下，我想到了greedy。 类似于jump game2. corner case 挺多，但还好没bug。 然后还有五分钟实现了一个LRU. 
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=154225&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
有一串 edge pair list ，ex (1, 2), (2, 3) 代表 1->2, 2->3 ，然后需要我去算出有多少 bi-directional graph in the list … 
嗯，我真的没见过这题，直接尝试解解看吧，一开始跟他说我可能会尝试用 topological sort 来解，但是小哥在此打住我，说尝试简单一点的解法，然后我提议用 python dict 来储存这些关係，然后再根据 key & value 这些关係来找出这个数目，然后我就绕进去了，现在想来简直就是悲剧的开始，这麽简单的题目被我搞得这麽复杂．．．总之写完第一个解法之后小哥提醒我有问题，我跑完自己的 test case 之后发现到我会重复算两次，然后最后改出一个 O(N^3) 的解法，后来就在跟小哥讨论 brute force 的解法跟一些实际状况之后，因为前面 technical issue 的时间就结束了，问建议的时候小哥有叫我 take care every detail of the questions first & familiar with one programmnig language，后面有些话听不是很清楚，因为接下来还有一面就先掰了．

虽然我觉得我没做出最佳解，但整体的交流还是不错，不过最后还是跪了，后来发现根本就不用想得这麽复杂，只要确认有没有前后互换的 pair 就好了，只能说一开始自己把题目想得太难了，然后也没有一次写出 bug free 的 code，以及有些条件没有先确认好，只能说自己实力真的还是远远不够啊（叹. Waral 鍗氬鏈夋洿澶氭枃绔�,

第二个面我的是一个三姐，感觉英文不是很好，话非常少，只好我一直讲话，为了保持跟他的互动我常常问他说 does this make sense to you? 之类的问题，还好他给的题目蛮简单的，就是两个字串比对，然后找出多出来的那一个字元，先写了一个 sorted 版本的，然后三姐追问 unsorted 怎麽解，我讲了时间换空间，空间换时间的两套方法，看他希望我做哪一个，然后他要求再做一个空间换时间的解法，写完之后讨论一下，发现有点 bug，很快地改完，然后又聊了很多特殊的 test case ，分别检讨了之前提过的几个解法可能会有哪些问题，最后发现最后一版的解法是最好的，皆大欢喜之下结束
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156327&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
给一个数组，一个sliding window size，求sliding window size里的平均数
e.g. input:[3,2,1,2,3], 2; output: [2.5, 1.5, 1.5, 2.5]. visit 1point3acres.com for more.
=> 扫一遍数组，维护一个sum和两个pointer. From 1point 3acres bbs
第二题，给一个数组，实现next()函数，是的数组里数出现的概率和它的值成正比
e.g. input: [1,2,3,4] if next() is called, 0.1 chance to return 1, 0.2 chance to return 2, 0.3 chance to return 3, 0.4 chance to return 5
=>hashmap.
Integer -> Integer
e.g. 0->1,1->2,2->2, 3->3, 4->3, 5->3, 6->4, 7->4, 8-> 4, 9->4 ==> not efficient. Use partial array + binary search
然后Ramdom得到一个【0，sum)的整数，用这个整数去hashmap里get valueFollow up: 如果给的是double array呢 => TreeMap


HashMap<Integer, Integer>
TreeMap<Double, Double>
用TreeMap的floorEntry(K key)找到对应value
TreeMap=Red Black Tree+Binary Search Tree用法和hashmap一样，就是O(lgn)而已


第二轮 白人小哥 通话质量很差，我说啥都听不清，都是回音。。小哥说尼再忍忍，再过几分钟就结束了。。
先聊简历
第一题，find majority element in a sorted array, whose occurance is more than 1/4
=> binarysearch find quarter point, binarysearch for start and end point
第二题，design greedy snake
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=148741&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
函数签名为 int countChunk(String input)， 给定一个字符串，找出最多有多少个chunked palindrome,

正常的palindrome是abccba, chunked palindrome的定义是：比如volvo, 可以把vo划分在一起，(vo) (l) (vo)，那么它是个palindrome。求实现返回最大的chunk 数量。

voabcvo的话就是算3个了，分法就是按照你的说的一样：(vo)(abc)(vo)-google 1point3acres

(vo)(l)(vo)(l)的话就不能这么分了，因为他不是回文，正确的划分为（volvol），函数返回1.
(vo)(l)(vo)(l)(vo) 就是这么分的，函数返回5。

因为最多只能分成这三块，让它“以块为单位”是回文：相当于A=vo，B=abc，原字符串=ABA。

int countMaxChunks(string str) {
  int count = 0;. more info on 1point3acres.com
  int i = 0, j = str.size()-1; // scan from the two sides
  int prev_i = i, prev_j = j;.鏈枃鍘熷垱鑷�1point3acres璁哄潧
  while(i<j) {.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
    string chunk1 = str.substr(prev_i, i+1);
    string chunk2 = str.substr(j, prev_j+1);. from: 1point3acres.com/bbs 
    if (chunk1==chunk2) {
      count++;. Waral 鍗氬鏈夋洿澶氭枃绔�,
      prev_i = i+1;
      prev_j = j-1;
    }   
    i++;
    j--;
  }
  count *= 2;
  // if odd string
  if (i==j)
    count++;
  // even string and still has chunk left
  else if (prev_i<prev_j)
    count++;
  return count;
}
. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
思想比较简单，但是从string的两边开始，用i和j记录当前scan到的位置，用prev_i和prev_j记录上一次找到chunk的i和j的位置的下一个字符。最后扫到中间判断一下有无多余的chunk。
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=148775&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
题目是这样的，输入是一个int amount 和 vector<int> coins，分别表示总货币量、各个coin的价值量，要求以最少的coin个数凑齐总货币量。 （大家应该都熟悉吧？入门级的DP题目。。）
然后输出的是每种货币的数目，vector<int> nums。. 鍥磋鎴戜滑@1point 3 acres
举例：  amount  = 40, coins = [1,5,15,25]，输出[0,1,1,1]. 鍥磋鎴戜滑@1point 3 acres
再举例： amount  = 40, coins = [1,5,20,25]，输出[0,0,2,0]

关键是刚开始没怎么听清楚，问了好几遍才确认，自己也是太紧张了。然后先确认了几个细节要求：
都是整数？是的
最后是要凑齐exact的目标数值amount？是的
会有无解的情况吗？默认总会有价值为“1”的coin. Waral 鍗氬鏈夋洿澶氭枃绔�,

我刚开始想着用backtracking+贪心来做，先sort，再用最贵的coin开始凑，后来一想不对，应该bottom up用dp，转移方程就是dp = min(dp[i-1]+1, dp[i-coins[j]]+j) for all j from 1~coins.size()-1;

然后写着写着就迷糊了，忘记目标不是coin的总数而是每个coin的个数。。。事实上，我写完之后(当时是只记录dp，即总数)，他说yes I think this works. 然后follow up问如果amount很大怎么办。
我想着想着发现只要keep tracking dp 里后面 coins.size() 数量的dp即可，only store the dp, dp[i-coins[1]]....., dp[i-coins[coins.size()-1]]. more info on 1point3acres.com
他说好的，很好，又问了总体的时间空间复杂度。（好了到目前为止我们两个估计都忘记了刚开始要的是各个coin的个数。。。）

然后闲聊了几句，他突然问我，噢等一下，我们要求的不是总数。。。我就突然紧张了，想了一会后，在每个dp的循环里加了个stack用来记录插入过的coin index，如果dp更新的话就把前面
的那个pop出来回滚回去，再把新的弄进来，感觉好像可以。。。

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=147464&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
Q1. Given a sorted array of integer and another integer, find a closest number from the array.
Q2. Given a n-ary tree, find longest consecutive sequence. 
Follow up: If you have a graph instead of tree我们说到还是用dfs搜索每条路径，然后要记得标记每个节点，因为会grahh会导致很多重复的访问。其次就是讨论圈，圈的话本质上对这个题没有影响，面试官就是希望我说到需要纪录没个节点，发现圈之后，要从recursion里跳出来，而不是无限循环的做
我的方法是这样的，有节点就进，进去之后判断是不是连续，如果是连续dfs里的len就加一然后继续做dfs,如果不连续len就按0传进去。对于树的话，它到root==NULL 就会return，但是graph不一样，如果graph有圈，你找不到一个null就停不下来。所以就要提前判断是否有圈，然后纪录没个访问的node，这样当所有node都被纪录访时，递归停止。 :)

第二轮，美国纽约白人
1.Find the height of a tree.
2. Implement a function addLandAndCountIslands(x, y) that marks a place on a grid as being “land” where unmarked locations are “water”. Follow up: 方程会被call很多次，如何优化。应该就是用一个变量纪录当前的岛数，如果mark的xy周围都是海，就直接加1，如果周围有有1个以上的陆地，需要分情况讨论。 （最后问了如果这样优化efficiency是多少，这个没答好。）
-- Union Find
3. Given a string of characters s and a character c, find the max substring of s with at most two instances of c. 只说算法，不用写。
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156469&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311

implement a CSV parser.input: a, a'b, c, d'c, b output: a       a'b, c, d'c        .鏈枃鍘熷垱鑷�1point3acres璁哄潧 b 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.  要求是:. more info on 1point3acres.com 1. 用,分隔string 2. 两个单引号之间是一个字符串的一部分 3. 两个单引号相连转义为一个单引号的 ‘’  ->  ‘ . visit 1point3acres.com for more. 我写完这个题之后被面试官指出了一个bug，写完改完bug大约花了20多分钟。 因为这个题目的corner case比较多，所以我也就处理了一些情况，比如两个引号内部有引号的情况等。 之后面试官又开始问简历，问了我的某个DBMS的项目有没有实现concurrency,transaction以及有没有实现SQL parser。 第二轮： 白人，Youtube Music组。 问了一个3 Sum Smaller，10分钟写完了。然后面试官说可以了， 我们做下一个题： Suppose we have a line and M points in this line. If we define the distance of a subset of points which has N (N <= M) points to be the minimum distance of the distance between of each pair of point, write a algorithm to find the maximum distance of a subset which has N points. 举个例子，加入我们有一条直线，上面有x = 1, x = 2, x = 5, x = 10 等等的点，给定一个数字N = 2。那么能让这个距离最大的点的子集就是{x = 1, x = 10}。 经过面试官提示之后可以先实现一个简单的function: 给定一个距离d,如果可以找到一个含有N个点的子集让距离等于d，返回true,否则返回false. 大致意思就是需要一直使用这个简单的function去尝试找到最大的d。 第三轮： 国人， longest substring without repeated characters longest substring with at most two distinct characters follow up: 对于第二个题目，要是传入的不是string而是data stream应该怎么办？ 因为我用的是hash table存的每个字母对应的下标地址，所以面试官又问我怎么优化空间。 第四轮: 白人，Youtube Gaming 组，感觉面试得最好的一轮。. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴 实现一个name query system,是一道面经里面出现过的题目。我用trie写了代码，然后问了一堆follow up: 1. 如何压缩trie的空间？ 2. 在进行prefix匹配的时候，如何在执行用户每个query的时候降低搜索的负载？ 大致就是如何优化auto complete的问题，或者如何防止恶意请求。 3. 在返回搜索结果的时候，怎么决定返回值里面姓名的priority?  四轮里面第一轮的面试官不满意，觉得我写代码的速度太慢。 第二轮的第二题是在面试官给出提示之后才想明白的，面试官也不是很满意

http://www.1point3acres.com/bbs/thread-146696-1-1.html

怎么判断一个按照Preorder traversal serialized的binary tree的序列是否正确呢？不能deserialize成树比如 A） 9 3 4 # # 1 # # 2 # 6 # #是对的，因为表示           9          /   \        3      2       /  \      \     4    1      6  B ) 9 3 4 # # 1 # #就是错的，因为无法反构造回一棵树

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156420&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
面试的题目是说他想写一个text editor，支持左右移动光标，插入字符删除字符的操作。于是用一个双向链表写了，一开始脑子一片空白写的时候卡卡顿顿的，没有很好的处理好null的情况。follow up是怎么样支持undo，楼主答用stack，不要求代码实现，然后第一轮就过去了。
第一题 plus 两个数组，和plus one类似 [1,2,3]+[3,5,6] = [4,7,9] 十分钟写完，进入下一题。
第二题 数独，给一个2d matrix 生成所有可能的数独解。
一开始楼主用和8 queue一样的iterate方法写，写到后面自己写不下去了，三哥也看不下去了，再换成递归。最后递归勉强写完了，但是valid数独是否是合法的这个函数没有来得及写完。

加面是个亚洲姐姐，人非常和蔼，但是有8年工作经验了，应该阅人无数所以大概会很严格。题目是一个花园，大概是长下图这样。
0.00100.001
00.00100.01
10.001.0100
110.00100.0
00.0001000
在每个0的位置可以访问所有垂直方向和竖直方向的格子，直到遇到1的阻拦。问在哪一个0的位置可以访问到最多的「.」。一开始意思理解错了，以为是从某个0出发可以上下左右移动，看最多能收集几个「.」，然后想用和count island一样的dfs做，和面试官讲了一下，面试官说，题目理解错了。然后知道她的意思之后，想了一个暴力做法，一个一个0的算，最后得到最大值。问能不能优化，说可能dp可以，但是不是很确定怎么做。然后面试官就让我把暴力算法写一下，说不定就知道怎么优化了。最后写完，大概想了一个很麻烦的dp算法，先遍历一遍，两个表分别存每一个0位置的水平最大值和垂直最大值，最后再遍历一遍得到总和的最大值。当然代码来不及写了。然后就这么结束了。
http://www.1point3acres.com/bbs/thread-136675-1-1.html

第一题，是找一个array里面的出现次数最多的integer。 第二题是找Binary Search Tree 里面的出现次数最多的integer..... 写完让想test case， 然后感觉面试官对想的test case不太满意。。  我也不知道能有什么特殊的case。