http://www.1point3acres.com/bbs/thread-175731-1-1.html
第一题写了一个parser和copy file， follow up是readbuffer的size对performance什么影响，第二题写了一个leetcode的generate all unique BST，第三题是design和code combine，给三姐跪了，题目是怎么design一个family tree的data base，然后要不停的insert delete find LCA，楼主用了Nary tree做，三姐要optimize，结果楼主歧途到prefix tree上最后发现每个node的prefix不unique（T……T），第四题最简单，基本上就是一个recursion＋BFS。。。然后由于第一个面试官迟到，所以之后被加面，加面的问题是：如何implement一个randomfunction。。。。
http://www.1point3acres.com/bbs/thread-177919-1-1.html
1. 大整数加法，追问如何用并行计算优化。我说按8位切片，在每个片里转成整数做加法，然后等更低位传过来进位。不过听烙印的反应似乎不太好。_(:з」∠)_.
2. 一个整数数组，找sum最接近0的一对数。2Sum Closest Pair。
排序两端夹击
第一题 实际上你的并行策略并没起作用。如果有carry in 你的MSB得重新算。等于说整个MSB的计算都depend on LSB的计算的结果。 我觉得应该用个类似carry selection adder的方法。 suppose你分2个进程， 你的MSB要计算有carry in的， 也要计算没有carry in的 最后根据是有还是没有把预测错误的那个结果抛弃就行。
http://www.1point3acres.com/bbs/thread-147270-2-1.html
1） 一个int的unsorted arrary，remove all duplicates；
2） Two Sum；
3） Two Sum变形题：找一对pair, the sum of which is closest to the target.
以上三题均问了time complexity， space complexity和自己写几个test cases。
http://www.1point3acres.com/bbs/thread-147278-1-1.html
題是Longest Substring with At Most m Distinct Characters
其實這題算有難度！Leetcode上有類似的題目，就叫"Longest Substring with At Most Two Distinct Characters"，難度被列為Hard
基本上一開始想到就是用 sliding window 法，用兩個 pointers 去記錄 substring 的 begin 和 end indices；可惜最後還是有小bug 因為緊張得腦袋空白而沒de出來。
他還建議我variable name不要取太 general，邊coding時要邊告訴對方自己現在在寫的是什麼功能，他才有辦法follow (如果心中有解的話我可以，但現在是連解都還在想，我真的也不知道能講什麼)
第二關，白人，很nice，大概知道我會緊張，還蠻有耐心在帶我、解說。
他要我implement 一個 moving average的 class，做以下的事
1. constructor時設定一個window size = k
2. insert(x)
3. avg() 取最後 k 個數的平均
當然要問一下time/space complexity
一開始我直覺的先建一個 array 用來存所有insert的值，avg再用sum(array[-k:])/float(k) 的方式來解，time complexity: insert = O(1), avg = O(k)；space complexity = O(n). 1point 3acres 璁哄潧
後來他點我一下，我改成用一個變數記錄最後k個數的sum，在insert的時候就順便算這個值(未滿k個數時，累加即可；超過k時，每加一個值要扣掉最舊的值), avg和insert的time complexity可以達 O(1)
space complexity我只想到是 O(n)，因為我認為所有data都要留；不過後來結束後再想，如果沒有delete operation，其實根本只需要 O(k) 的空間記錄最後k個值就夠了；反正太舊的值也不會再用到
接著開始考follow up：
1. testing，有哪些cases是我們可以test驗證code正確的？我想到的有，negative values, k <= 0, overflow；negative values基本上不會有問題，k<=0 可以用exception解，overflow在python下也不會是問題.
2. concurrent execution, 如果多個 threads同時run這個code，會有race condition嗎？(會) 可以用什麼解? (mutex或 semaphore) 所以要lock哪個部分? (insert 算總和的部分要lock住，確保它是 atomic)
http://www.1point3acres.com/bbs/thread-147447-1-1.html
map和bst, 列举API, time complexity, 如何实现，还追问了一些什么问题忘记了，反正都是basics
2) 一道热身题:
就是一串字符串里面只有0和1，但是给的是这种形式：V1L3V0L1V1L4 它可以转化为11101111，V代表是0还是1，L代表长度。然后给你两个这样的string，问如果转化过来后两个字符串对应位不同的位数是多少。比如：110和101，不同的位数是2。当然不能转化过来做啦！
bitmap镜面对称的题。给的是一个byte型的一维数组，但是bitmap是二维的，告诉你长和宽（就是bit的个数），假设宽能被8整除，让你沿中线对称。
我想的是V*L*为一组，进行比较，每次比较后剩余的放到下一组继续比较
最好是直接给出最优解，然后写代码的时候bug free
http://www.1point3acres.com/bbs/thread-147377-1-1.html
implement一个cache, 这个 cache要求实现get(id), set(i), remove(i), cache的基本特性就是要能够保证out of date 的 cache要不停的被kick out
hashMap + 多线程
多线程就是因为考官要求要不停的把过期的CACHE删掉，不只是CALL INSERT或者REMOVE的时候，所以能想到的就是BACKGROUND RUN一个线程不断的扫HASHMAP。
A Beautiful Race Condition，里面专门提到Java的HashMap不能在多线程情况下当作cache。当然文章里提到的情况和楼主碰到的不太一样，有可能楼主写的这个Cache只是供给单线程使用？
这题应该先和考官确认，cache是在单线程环境下使用，还是多线程？如果是多线程环境下使用，并且能passively expire（没被access的情况下expire），我想到的合理做法是用异步，写个event loop。每个iteration里检查有没有expired keys，有的话删除，然后继续处理队列里的set／get请求。在这个设计下cache应该是C/S模型
这个event loop是化多线程为单线程，event based parallel. 确实是redis的设计理念，赞一个。
这样remove expired其实跟单线程是几乎一样的，大大简化代码复杂。不过redis其实也不是纯单线程，在一些计算较重的业务时也是用常规多线程的只是封装的比较好。
关键在于你设计的cache必须得thread－safe
这个设计基于的假设是 bound 不在 CPU业务处理上，而是在IO（network I/O or disk I/O）
因为我们要做的是cache，basic assumption就是不会是一个cpu intensive的程序
题目很简单2 SUM CLOEST, 开始写了个暴力的，然后让优化成O(N)，继而就SB了，花了十多分钟才憋出来了O(N)解法，感觉俩人都踢我捏把汗
然后没啥时间了就出了个SYstem DESIGN, 很常规的MAIL SYSTEM找TOP K% IP, 提了MAP + HEAP, 在用什么HEAP有了争论， 我说MIN HEAP不断更新TOP就可以， 面试官似乎偏执于为什么我总是在讨论TOP 元素她要的是TOP K%, 我说如果当前某一IP frenquency比TOP大就REPLACE TOP 最后HEAP里的就是TOP K%，最后又说用MAX HEAP不是MIN HEAP。。我心想不对啊。。然后就时间到了
mail stream
实现一个围棋盘里是否有 deadend的method(就是如果白子可以把黑子围住或者黑子可以把白子围住就return true),dfs
leetcode 原题 closest binary search tree value
设计一个Set类实现 insert, remove, getRandom in O(1) 面经题
leetcode 原题 encoding and decoding strings
http://www.1point3acres.com/bbs/thread-147581-1-1.html
1. Two sum, Three sum
2. 字符串重新排列，让里面不能有相同字母在一起。比如aaabbb非法的，要让它变成ababab。给一种即可
贪心算法找重复最多的先排
3. 设计2d数据结构，要set(i, j)和query(a,b,c,d)来修改里面的数值，和查询以（a, b,c,d）为四个顶点的矩形里面数字的和
http://www.1point3acres.com/bbs/thread-147330-1-1.html
题目是Merge k Sorted Lists， leetcode原题，不过要求merge数组，总体上讲是一样的，实现起来数组稍微麻烦些，需要在堆中记录元素属于的数组(我用的ArrayList，第一项存数组index，第二项存值)以及每个数组的首指针。问了时间复杂度(O(nk logk))，额外空间复杂度(O(k))。follow up: 空间上能不能优化。一开始没明白什么意思，感觉已经没法优化了，然后面试官提示ArrayList和int[]的空间分配有什么区别，这里ArrayList在add操作时如果元素数量超过了capacity，会重新申请大概1.5capacity的空间，所以ArrayList会更费空间。问在不将ArrayList替换为int[]的情况下怎么优化，只要在新建ArrayList实例时构造函数加参数initial capacity就行。后来面试官表示他只是想了解下我对Java的了解程度.......
第一题，Zigzag Iterator，leetcode原题，需要subscribe，我没有开，所以也是第一次见，不过反正也没什么难度，想个方法把hasNext()接口的复杂度下降到O(1)就行。分析下时间复杂度：next()接口是O(n)，n是子iterator的数量，其实想点办法自己手写双向链表是可以达到O(1)的平均复杂度的。
第二题，Path Sum，follow up为Path Sum II，但只需要返回任意一条路径即可，需要加剪枝提高效率。代码没什么难度，但是要写简介感觉挺难，面试没时间代码重构代码丑的自己都看不下去。
PS. 有同学的面试题是现场写一颗线段树。其实第一轮面试我本来想想用那15分钟手撸一个堆来着，面试官表示不用，PriorityQueue就行......
http://www.1point3acres.com/bbs/thread-147554-1-1.html
两个等长度string S T, swap S里的一对字符让两个string的海明距离最少。
四个点判断是否正方形（思路不用code）。
a的b次方模p。
第一题用hashmap key是char pair然后value是index，扫一遍string,如果char相等就continue，然后如果当前两个char不等比如是ab看是否存在key“ba”如果存在就返回两个index否则就放到map里。一遍扫完以后扫hashmap的key，放到另一个map里key是原来key的第二个char，然后再扫string如果S是a然后第二个map里存在key“a”的话返回两个index。最后否则返回{-1，-1}。
找不匹配的pair，用hashset保存，比如ab，然后遍历hashset看有没有逆序对，有的话swap海明距离就能减2.没有的话看有没有哪个pair的第二个字母是a，有的话swap，海明距离减1.再没有就不用swap了，swap不能减小海明距离。
2：3 sum smaller
一个二维矩阵，有start，end，wall，ground。可以一次走一步，n次机会跳跃机会可以隔一个跳一个。不都走或者跳到墙。求最短步数。本来想用曼哈顿距离做heuristic function用A*结果好像不可以因为这题用曼哈顿距离不是consistent的。小哥挺好的说不确定可不可以然后是否有一种search肯定对我说bfs他说对写bfs吧。。。
就是找到start然后bfs，每个位置有八个neighbor，四个走过去的四个跳过去的，然后如果是墙就continue。跳过去的要记录用了一次跳跃。所以在search tree里面每个node存的信息要有步数，还剩下的jump机会，位置。
一开始我是把所有点都展开了没剪枝然后问我优化他说可以从下往上，然后我说从上往下也行只留着每个点最大的就好了。但是没时间写代码了。按他说的方法从下往上应该也是52 N^2的
4：公司有很多office，你可以每周末飞到别的office。只有在比某个数字小的hours内能飞到才可以飞。每个office有很多假期。怎样获得一年内最多的假期。（这轮印度小哥好像很不想让我读懂题似的不往板上写然后信息都是挤牙膏问出来。然后还迟到了十几分钟因为他迷路了最后没时间写剪枝。）
最後一題我只能想到O(n^2)的解法：每週去更新該office的最大可能假期數
譬如說，在wk i+1，traveler待在office j可以得到的累計最大假期數為 vacations[j][i+1] + max(vacations[x][i] if hour[x][j] < k else 0)
這樣算下去，更新每週的累計數需要O(n^2)，總共有52周，所以是O(52 * n ^ 2) = O(n^2)
最后一题每周不是固定日子假期。我用的bfs，从第一周开始把上周每个可能的office都展开然后记录到当前有多少假期，然后可以剪枝比如A和B都可以飞到C那么下一层C只留着最大的就行。在最后一层找最大值。.
http://www.1point3acres.com/bbs/thread-147510-1-1.html
1. 给一个linkedlist，但是Node定义为：
class Node{
Node next;
Node other;
}
next指向下一个，other指向链表里任意一个，或者null。让写一个method实现copy这个linkedlist. from: 1point3acres.com/bbs
楼主直接两遍，第一遍完成copy next的值，所有other为null，并且用HashMap存下来所有老Node和新Node的关系，然后再来一遍赋值other
2. 实现两个method
addNum() 和 getMedian().
一开始是空的，通过addNum添加数字，然后通过getMedian取得当前数组里的元素的中值
这题楼主一开始没想到最佳办法，用的ArrayList，然后每次addNum就BinarySearch去添加，由于插入操作是o(n)，所以其实并不太好，不过面试官还是让我实现这个。
后来想到可以用两个堆去解决，就能实现O(long n)了
http://www.1point3acres.com/bbs/thread-143685-1-1.html
1. APPDEISGN 做一个小应用，用户按完按钮可以返回当时的步速，API任意，界面设计任意，自己想一个设计出来，写出按按钮时候的function.
2. Clone Graph, Add list
3. 面经原题 给一个字符串，重新排列成相邻字母不能相同
4. a. 用C语言实现 strrch b. 给四张牌 返回四张牌的expression可以算出24点 （带括号）
5. a. 一个sorted array 只有0和1，返回第一个1的index
b. 有一个2D Array，行和列是 非递减。找到这个array的smallest Kth element
5的话，维护一个heap 然后每一次走 都搜当前candidates的邻 ...
http://www.1point3acres.com/bbs/thread-143308-1-1.html
Given a large integer array, count the number of triplets whose sum is less than or equal to an integer T.
第一题给的array里面有重复吗？有重复的话，感觉只能O(n^3)做啊
要不然就和Leetcode 3Sum Smaller一样，是求number of index triplets, 可以O(n^2)做
Given an array of Ad (profit, start_time, end_time) and a timespan [0, T], find the max profit of Ads that fit the the timespan
先说了穷举法O(2^n), 然后说了贪心法（不是最优解），最后用DP解决
我当时也是这个思路~ 先按照end_time升序排列，然后列DP方程：f(i,t) = max{ (f(i-1,t), f(i-1,start) + profit) }
第二题可以这样：
1. 先对所有的ad按照结束时间，从小到大排序；. visit 1point3acres.com for more.
2. dp[i]代表排序后前i-1的广告的最大收益，那么dp[0] = 0；
3. 对于第i个广告，有选和不选两种可能，如果选的话，就要从第i-1个广告往前，找到和第i个广告不重合为止，假设找到了j，那么dp[i] = max(dp[i-1], dp[j]+profit[i])
时间复杂度的O（n^2）,如果第3步用二分，就可以变成O（nlogn）. W
第二题 应该是类似背包问题，先把ads按照endTime排好序，然后两层for循环，i，j， i代表时间，j代表ad，dp[i][j]一开始设为dp[i][j - 1], 第j个广告取不取，取决于，是否它的endtime小与i的时间，并且加上他的profit大于现在dp[i][j - 1]的profit
for (int i = 0; i <= time; i++) {
for (int j = 1; j <= ads.length; j++) {
profit[i][j] = profit[i][j - 1];
if (ads[j - 1].endTime <= i) {
profit[i][j] = Math.max(profit[i][j], profit[ads[j - 1].startTime][j - 1] + ads[j - 1].profit);acres
}
}
}
int max = 0;
for (int i = time; i >= 0; i--) {
max = Math.max(max, profit[i][ads.length]);
}
return max;
其中i是当前考察的Ads数组元素下标，t是当前可用的结束时间，递归函数代码如下：
int f(int i, int t) {
if(i < 0 || t == 0) return 0;
int max = f(i-1, t);
if(end <= t) {
int tmp = f(i-1, start) + profit;
if(tmp > max) max = tmp;
}
return max;
}
不我觉得复杂度只是O(N * T)， N是广告个数，T是时间跨度。我们需要求的最大利润是f(N-1, T)。后面优化说了用哈希表记忆已经求出来的子结果，避免重复计算。
int f(int i, int t, int start[], int end[], int profit[]) {
if(i < 0 || t == 0) return 0;
int max = f(i-1, t, start, end, profit);
if(end <= t) {. visit 1point3acres.com for more.
int tmp = f(i-1, start, start, end, profit) + profit;
}
return max;
}
int main()
{
int start[] = {0,0,1};
int end[] = {1,2,3};
int profit[] = {1,3,1};
int T = 3;
int len = sizeof(start) / sizeof(int);
cout << f(len-1, T, start, end, profit) << endl;
return 0;
}
M x N large board, with only white and black blocks, all black blocks are connected (vertically or horizontally), find the minimum rectangle boundary that contains all black blocks.
还好心地给了提示和假定。感觉交流互动非常好，可惜最后差了一点，没能想出O(n^2)以内的算法。
第三题貌似是遍历玩board 记录 最left，最top，最bottom，最right坐标就可以了吧。。。。 应该是O(n*m).
如果n*m很大，还有一种方法是先指定一个黑点（如果不让指定，可以随机猜），因为黑点都是connected的，所以可以用递归搜索黑点，搜索的同时记录最left，最top，最bottom，最right坐标
就像图像填充里的floor fill，如果黑点的个数是K，复杂度就是O(K)
对，你这个方法我想到了，俄罗斯妹子直接说那就随机给你一个黑点好了~~然后我用BFS的复杂度就是O(K)，但是极端情况假如全都是黑点，一样是O(M*N)了。感觉这个有点博弈，看黑的多白的多。如果黑的多就从外侧包围更快，白的多从黑的开始搜索更好吧。。总之感觉这题很有意思，妹子中间给我画了一个宽度为1的黑格子螺旋线，那叫一个美。。。
感觉是不一定都得把所有格子访问一遍，但是极端情况全黑或全白仍然要都访问
不是原题吧，maximal rectangle求的是黑色点包含的最大矩阵，找个求的时能包含所有黑色的最大矩阵，不一样
我的理解是：从第一行开始往下扫，一行一行扫，遇到第一个不是纯白的行的话，就停止，因为就算找到了所求矩阵的顶，同理找到底、左、右。还是说我理解错了？O（M*N）
你没理解错~我最开始就说的这种“四面包夹”的做法，这算法是最坏情况（全白）就是O(MN)。所以接着就一直在分析更简单的算法。。
Design a algorithm to initialize the board of Candy Crush Saga. With M x N board, Q types of candies. (Rules: no 3 for run after initialization, must contain at least one valid move at the beginning)
小哥说话很和气，先让我介绍了一个project，于是兴致勃勃地讲了做过的一个游戏。他于是拿出手机给我看了这个，说那就出一道游戏题吧。。游戏可以参考（
http://candycrushsaga.com/how-to-play），这道题很开放，没有固定模式和答案，感觉答的还不错
先把Candy简化成数字，类型数组就成了[0, 1, 2, ..., Q-1]。规则一共三条：随机（至少玩家看上去是）；不能一开始就有3个共线的；开局至少有一步能保证有消除（不然没法玩。。）
1. 我首先关注的是前两条规则，因为觉得第三条只是小修改（尽管如果初始化完成后，再修改成符合第三条，可能导致连锁反应）。因为“随机”一直在我心头挥之不去，所以首先想到的是遍历所有格子，每次随机挑一个Q放进去，但立刻意识到这样很有可能导致死锁，尤其Q很小的时候，然后举了个死锁的例子
2. 因为之前考虑过Q很小，所以最简单就是{0, 1}两种，立刻想到国际象棋棋盘：两色相间一定能填满而且无冲突。然后想到能不能先按照国际象棋棋盘填满，然后在这个基础上进行”随机化“。假如我有个遵循前两条规则的函数random()，对棋盘进行随机化。因为是在01棋盘改，所以第一遍下来可能还是很”假“，但既然这个函数是遵循前两条规则的，那么大可放心的多执行几遍。就像PS的滤镜叠加使用~ 然后开始讨论这个random()函数，大体思路是遍历棋盘，对每个格子有0.5 的概率进行”尝试修改“。(随机化就是一个慢慢tweak的过程，这个参数后面提到要根据实际效果调整）。尝试修改的算法就是：q = random(0, Q); 以q为中心向上下左右四个方向，一共有6条长度为3的线会造成潜在冲突，因此逐个检查一遍，假如无冲突就把当前位置替换为q。最后根据实际效果决定是否再来几次~
3. 然后就剩第三条规则：开局至少有一步能走。我上面阐述的时候就一直有个感觉，每局开始看似随机但一定有定势。然后让小哥打开手机游戏开了两局看了下，果然，每局开头一定会有{V型, _/型} 中的一种或两种排列，保证挪一步就能消除。跟小哥聊了这个想法之后，我的做法就是01棋盘生成后，随机选一个排列，比如V型，然后在棋盘上随机选一个（也可以多个）位置，把这个位置画出的V全部mark成不可修改。然后在这个基础上跑上面提到的random()算法。第三条规则也可以有很多随机性，必须类型选择，类型对应位置、个数的选择。
http://www.1point3acres.com/bbs/thread-142659-2-1.html
给一个字符串s由单词组成， 比如“i have a dream”。 要求把这个字符串添到一个m x n的网格里，同一个单词不能被cut off，每一句之间空格相连。问最多添满多少个整句。follow up （m and n are much larger than the length of s, 怎么办）
第二题：就相当于左对齐的排版一样，重复的吧一句话排列到版面上，问最多能排多少次。
有一个2维数组A。实现两个函数：1) void update(int x, int y, int v), 就是更新A[x][y]的值(v). 2) int regionalSum(int x1, int y1, int x2, int y2)：就是求（x1, y1）和（x2, y2）构成矩形的所有元素和。
follow up: 如果系统很少用带update而经常使用reginalSum, 如何设计减少复杂度。.
3. followup：pre-computing, 然后数学图形中的计算面积（减去重复计算部分
这题很难描述，关于数字的Palindrome. 想象电子表的数字1的Palindrome是1， 2的Palindrome是5， 3的Palindrome啥也不是。。。如果两位的话 11的Palindrome是11， 25的Palindrome是52， 69的Palindrome是96。。。。。 问题是：
返回给定level的所有的Palindrome number。
level代表了位数， 比如：
level = 1: 返回0 1 8
level = 2: 返回 11 88 25 52 69 96
4。想象电梯里的数字显示屏，只有2 和 5， 1 和 1， 8 和 8。可以DP / recursion
第4题level2的时候还有21和15，28和82之类的吧？
第四题感觉不用太刻板的套LC上的那个，可以用个hashset来存是pali的数字，然后按照，LC上那样，判断首尾是否相等，然后中间的数是不是在set里面就行了。
这个是G家经常考的peek iterator.
http://www.fgdsb.com/2015/01/25/peek-iterator/
这个是Zigzag。
http://www.fgdsb.com/2015/01/30/zigzag-iterator/
这个是nested，最近很高频。
http://www.fgdsb.com/2015/01/19/nested-iterator/
这个是归并排序的iterator，G家考过几次。
http://www.fgdsb.com/2015/01/15/merge-sorted-stream/
Given an iterator A of iterators B's , alternately output the contents in all the B's
也就是说我现在有一群iterator B1, B2, ... Bk，分别是Collection C1, C2, ... , Ck的iterator. 但是不把这些iterator的引用直接给你，而是把这些iterator再放到一个Collection （比如记为B）中，然后给你的只是B的一个iterator BI。输出方式就是按楼主所说的zigzag形。
我当时说可以用BI先把B遍历一遍，把所有的iterator B1, B2, ... , Bk先拷贝到一个能够随机访问的Collection中，然后用楼主上面给出的方法。但是面试官似乎不太认可这个答案，但是也没有明说到底哪里应该改进。我觉得他可能是想让我找一个不用预先遍历的方法，或者是甚至不需要用到额外O(k)内存的方法。但是我到最后也没想出来。
http://www.1point3acres.com/bbs/thread-135449-1-1.html
两个链表 求最大的公共后缀
我是直接把链表遍历一遍，然后倒过来求公共前缀
求一个数组的 h index
h-index 就是这样的一个数 如果数组中有n个数的值大于n，并且没有n+1个数的值大于n+1，那么n就是h-index
具体思路如下，其实就是binary search。 首先根据start和end得出mid，看A[mid]值是否大于数组长度减去mid（假设A.length-mid = distance），如果是那么distance有可能成为h index. 因为数组有序，如果distance小于A[mid]，那么有distance个元素的值大于distance。 此时如果A[mid]值小于distance，那么继续向高位找，start=mid+1。如果A[mid]值大于distance，那么继续向低位找end=mid-1。如果低位找到更大的distance，那么返回低位的，如果低位没找到更大的，就返回现在的distance。
round 3
设计一个作业调度的API，我写了一个类似os里面线程调度的scheduler
给一个数，要求把这个数分解成一些平方数的和，并且要求使用最短的平方数list 如 13 = 9 + 4 而不是 13 = 4+4+4+1
貌似这题leetcode有类似的题目，好久没做leetcode新题都没关注。
round 4
给一个字符串，该字符串由一些可能会重复的字符组成，重新排列这个字符串使得没有相邻的字符是相同字符。如aab变成aba.
最终在stack overflow上看到了一种贪心法。还是把字符出现频率统计出来，扔在一个堆里。每次取出前两个频率高的字母，配成一对，次数减一，扔回堆。（只要写的时候注意下相邻字母不要一样就好）
首先贪心的思路是对的，我的实现方法是，首先统计各个字母出现的概率，然后存在一个map里面，key是字母，value是出现次数。然后取出最多出现的字母从map里面删掉，然后把剩下的字母按照出现的次数，每次都把map里面出现次数最多的字母取出来一个，插到前面删除的字母组成的字符串的空隙当中，直到没有空隙（这个过程是动态的，例如此时map里面有a出现3次b出现3次，那么先插个a，下一次要插个b，一直保持拿出最多的字母）。然后递归，把map传到下一次调用，直至map里面只有一个字母，如果剩下的一个字母出现的次数为1那么把它取出加到结果最后，如果出现次数大于1那么无解。
这种用大根堆的算法更简单易懂，我实现完之后跟面试官解释了很久，然后又演示了几个case他才明白
第一题写了一个parser和copy file， follow up是readbuffer的size对performance什么影响，第二题写了一个leetcode的generate all unique BST，第三题是design和code combine，给三姐跪了，题目是怎么design一个family tree的data base，然后要不停的insert delete find LCA，楼主用了Nary tree做，三姐要optimize，结果楼主歧途到prefix tree上最后发现每个node的prefix不unique（T……T），第四题最简单，基本上就是一个recursion＋BFS。。。然后由于第一个面试官迟到，所以之后被加面，加面的问题是：如何implement一个randomfunction。。。。
http://www.1point3acres.com/bbs/thread-177919-1-1.html
1. 大整数加法，追问如何用并行计算优化。我说按8位切片，在每个片里转成整数做加法，然后等更低位传过来进位。不过听烙印的反应似乎不太好。_(:з」∠)_.
2. 一个整数数组，找sum最接近0的一对数。2Sum Closest Pair。
排序两端夹击
第一题 实际上你的并行策略并没起作用。如果有carry in 你的MSB得重新算。等于说整个MSB的计算都depend on LSB的计算的结果。 我觉得应该用个类似carry selection adder的方法。 suppose你分2个进程， 你的MSB要计算有carry in的， 也要计算没有carry in的 最后根据是有还是没有把预测错误的那个结果抛弃就行。
http://www.1point3acres.com/bbs/thread-147270-2-1.html
1） 一个int的unsorted arrary，remove all duplicates；
2） Two Sum；
3） Two Sum变形题：找一对pair, the sum of which is closest to the target.
以上三题均问了time complexity， space complexity和自己写几个test cases。
http://www.1point3acres.com/bbs/thread-147278-1-1.html
題是Longest Substring with At Most m Distinct Characters
其實這題算有難度！Leetcode上有類似的題目，就叫"Longest Substring with At Most Two Distinct Characters"，難度被列為Hard
基本上一開始想到就是用 sliding window 法，用兩個 pointers 去記錄 substring 的 begin 和 end indices；可惜最後還是有小bug 因為緊張得腦袋空白而沒de出來。
他還建議我variable name不要取太 general，邊coding時要邊告訴對方自己現在在寫的是什麼功能，他才有辦法follow (如果心中有解的話我可以，但現在是連解都還在想，我真的也不知道能講什麼)
第二關，白人，很nice，大概知道我會緊張，還蠻有耐心在帶我、解說。
他要我implement 一個 moving average的 class，做以下的事
1. constructor時設定一個window size = k
2. insert(x)
3. avg() 取最後 k 個數的平均
當然要問一下time/space complexity
一開始我直覺的先建一個 array 用來存所有insert的值，avg再用sum(array[-k:])/float(k) 的方式來解，time complexity: insert = O(1), avg = O(k)；space complexity = O(n). 1point 3acres 璁哄潧
後來他點我一下，我改成用一個變數記錄最後k個數的sum，在insert的時候就順便算這個值(未滿k個數時，累加即可；超過k時，每加一個值要扣掉最舊的值), avg和insert的time complexity可以達 O(1)
space complexity我只想到是 O(n)，因為我認為所有data都要留；不過後來結束後再想，如果沒有delete operation，其實根本只需要 O(k) 的空間記錄最後k個值就夠了；反正太舊的值也不會再用到
接著開始考follow up：
1. testing，有哪些cases是我們可以test驗證code正確的？我想到的有，negative values, k <= 0, overflow；negative values基本上不會有問題，k<=0 可以用exception解，overflow在python下也不會是問題.
2. concurrent execution, 如果多個 threads同時run這個code，會有race condition嗎？(會) 可以用什麼解? (mutex或 semaphore) 所以要lock哪個部分? (insert 算總和的部分要lock住，確保它是 atomic)
http://www.1point3acres.com/bbs/thread-147447-1-1.html
map和bst, 列举API, time complexity, 如何实现，还追问了一些什么问题忘记了，反正都是basics
2) 一道热身题:
boolean[] array = new boolean[N];
for (int skip = 1; skip < N; skip++) {
for (int i = 0; i < N; i += skip) {
array = !array;
}
}
问你 array[k] = ?
第二题是 array[i] = ！array[i]吗？ 问array[k]，是要推导出一个关于k的公式吗？
=
求k的因数个数的奇偶
http://www.1point3acres.com/bbs/thread-147425-1-1.html
直接给我出了一个二进制转十进制的题。。。应该是我面试碰到最简单的题了，之后是leetcode那个excel的题目，相当于26进制。
直接给我出了一个二进制转十进制的题。。。应该是我面试碰到最简单的题了，之后是leetcode那个excel的题目，相当于26进制。
就是一串字符串里面只有0和1，但是给的是这种形式：V1L3V0L1V1L4 它可以转化为11101111，V代表是0还是1，L代表长度。然后给你两个这样的string，问如果转化过来后两个字符串对应位不同的位数是多少。比如：110和101，不同的位数是2。当然不能转化过来做啦！
bitmap镜面对称的题。给的是一个byte型的一维数组，但是bitmap是二维的，告诉你长和宽（就是bit的个数），假设宽能被8整除，让你沿中线对称。
我想的是V*L*为一组，进行比较，每次比较后剩余的放到下一组继续比较
最好是直接给出最优解，然后写代码的时候bug free
http://www.1point3acres.com/bbs/thread-147377-1-1.html
implement一个cache, 这个 cache要求实现get(id), set(i), remove(i), cache的基本特性就是要能够保证out of date 的 cache要不停的被kick out
hashMap + 多线程
多线程就是因为考官要求要不停的把过期的CACHE删掉，不只是CALL INSERT或者REMOVE的时候，所以能想到的就是BACKGROUND RUN一个线程不断的扫HASHMAP。
A Beautiful Race Condition，里面专门提到Java的HashMap不能在多线程情况下当作cache。当然文章里提到的情况和楼主碰到的不太一样，有可能楼主写的这个Cache只是供给单线程使用？
这题应该先和考官确认，cache是在单线程环境下使用，还是多线程？如果是多线程环境下使用，并且能passively expire（没被access的情况下expire），我想到的合理做法是用异步，写个event loop。每个iteration里检查有没有expired keys，有的话删除，然后继续处理队列里的set／get请求。在这个设计下cache应该是C/S模型
这个event loop是化多线程为单线程，event based parallel. 确实是redis的设计理念，赞一个。
这样remove expired其实跟单线程是几乎一样的，大大简化代码复杂。不过redis其实也不是纯单线程，在一些计算较重的业务时也是用常规多线程的只是封装的比较好。
关键在于你设计的cache必须得thread－safe
这个设计基于的假设是 bound 不在 CPU业务处理上，而是在IO（network I/O or disk I/O）
因为我们要做的是cache，basic assumption就是不会是一个cpu intensive的程序
题目很简单2 SUM CLOEST, 开始写了个暴力的，然后让优化成O(N)，继而就SB了，花了十多分钟才憋出来了O(N)解法，感觉俩人都踢我捏把汗
然后没啥时间了就出了个SYstem DESIGN, 很常规的MAIL SYSTEM找TOP K% IP, 提了MAP + HEAP, 在用什么HEAP有了争论， 我说MIN HEAP不断更新TOP就可以， 面试官似乎偏执于为什么我总是在讨论TOP 元素她要的是TOP K%, 我说如果当前某一IP frenquency比TOP大就REPLACE TOP 最后HEAP里的就是TOP K%，最后又说用MAX HEAP不是MIN HEAP。。我心想不对啊。。然后就时间到了
mail stream
实现一个围棋盘里是否有 deadend的method(就是如果白子可以把黑子围住或者黑子可以把白子围住就return true),dfs
leetcode 原题 closest binary search tree value
设计一个Set类实现 insert, remove, getRandom in O(1) 面经题
leetcode 原题 encoding and decoding strings
http://www.1point3acres.com/bbs/thread-147581-1-1.html
1. Two sum, Three sum
2. 字符串重新排列，让里面不能有相同字母在一起。比如aaabbb非法的，要让它变成ababab。给一种即可
贪心算法找重复最多的先排
3. 设计2d数据结构，要set(i, j)和query(a,b,c,d)来修改里面的数值，和查询以（a, b,c,d）为四个顶点的矩形里面数字的和
http://www.1point3acres.com/bbs/thread-147330-1-1.html
题目是Merge k Sorted Lists， leetcode原题，不过要求merge数组，总体上讲是一样的，实现起来数组稍微麻烦些，需要在堆中记录元素属于的数组(我用的ArrayList，第一项存数组index，第二项存值)以及每个数组的首指针。问了时间复杂度(O(nk logk))，额外空间复杂度(O(k))。follow up: 空间上能不能优化。一开始没明白什么意思，感觉已经没法优化了，然后面试官提示ArrayList和int[]的空间分配有什么区别，这里ArrayList在add操作时如果元素数量超过了capacity，会重新申请大概1.5capacity的空间，所以ArrayList会更费空间。问在不将ArrayList替换为int[]的情况下怎么优化，只要在新建ArrayList实例时构造函数加参数initial capacity就行。后来面试官表示他只是想了解下我对Java的了解程度.......
第一题，Zigzag Iterator，leetcode原题，需要subscribe，我没有开，所以也是第一次见，不过反正也没什么难度，想个方法把hasNext()接口的复杂度下降到O(1)就行。分析下时间复杂度：next()接口是O(n)，n是子iterator的数量，其实想点办法自己手写双向链表是可以达到O(1)的平均复杂度的。
第二题，Path Sum，follow up为Path Sum II，但只需要返回任意一条路径即可，需要加剪枝提高效率。代码没什么难度，但是要写简介感觉挺难，面试没时间代码重构代码丑的自己都看不下去。
PS. 有同学的面试题是现场写一颗线段树。其实第一轮面试我本来想想用那15分钟手撸一个堆来着，面试官表示不用，PriorityQueue就行......
http://www.1point3acres.com/bbs/thread-147554-1-1.html
两个等长度string S T, swap S里的一对字符让两个string的海明距离最少。
四个点判断是否正方形（思路不用code）。
a的b次方模p。
第一题用hashmap key是char pair然后value是index，扫一遍string,如果char相等就continue，然后如果当前两个char不等比如是ab看是否存在key“ba”如果存在就返回两个index否则就放到map里。一遍扫完以后扫hashmap的key，放到另一个map里key是原来key的第二个char，然后再扫string如果S是a然后第二个map里存在key“a”的话返回两个index。最后否则返回{-1，-1}。
找不匹配的pair，用hashset保存，比如ab，然后遍历hashset看有没有逆序对，有的话swap海明距离就能减2.没有的话看有没有哪个pair的第二个字母是a，有的话swap，海明距离减1.再没有就不用swap了，swap不能减小海明距离。
2：3 sum smaller
一个二维矩阵，有start，end，wall，ground。可以一次走一步，n次机会跳跃机会可以隔一个跳一个。不都走或者跳到墙。求最短步数。本来想用曼哈顿距离做heuristic function用A*结果好像不可以因为这题用曼哈顿距离不是consistent的。小哥挺好的说不确定可不可以然后是否有一种search肯定对我说bfs他说对写bfs吧。。。
就是找到start然后bfs，每个位置有八个neighbor，四个走过去的四个跳过去的，然后如果是墙就continue。跳过去的要记录用了一次跳跃。所以在search tree里面每个node存的信息要有步数，还剩下的jump机会，位置。
一开始我是把所有点都展开了没剪枝然后问我优化他说可以从下往上，然后我说从上往下也行只留着每个点最大的就好了。但是没时间写代码了。按他说的方法从下往上应该也是52 N^2的
4：公司有很多office，你可以每周末飞到别的office。只有在比某个数字小的hours内能飞到才可以飞。每个office有很多假期。怎样获得一年内最多的假期。（这轮印度小哥好像很不想让我读懂题似的不往板上写然后信息都是挤牙膏问出来。然后还迟到了十几分钟因为他迷路了最后没时间写剪枝。）
最後一題我只能想到O(n^2)的解法：每週去更新該office的最大可能假期數
譬如說，在wk i+1，traveler待在office j可以得到的累計最大假期數為 vacations[j][i+1] + max(vacations[x][i] if hour[x][j] < k else 0)
這樣算下去，更新每週的累計數需要O(n^2)，總共有52周，所以是O(52 * n ^ 2) = O(n^2)
最后一题每周不是固定日子假期。我用的bfs，从第一周开始把上周每个可能的office都展开然后记录到当前有多少假期，然后可以剪枝比如A和B都可以飞到C那么下一层C只留着最大的就行。在最后一层找最大值。.
http://www.1point3acres.com/bbs/thread-147510-1-1.html
1. 给一个linkedlist，但是Node定义为：
class Node{
Node next;
Node other;
}
next指向下一个，other指向链表里任意一个，或者null。让写一个method实现copy这个linkedlist. from: 1point3acres.com/bbs
楼主直接两遍，第一遍完成copy next的值，所有other为null，并且用HashMap存下来所有老Node和新Node的关系，然后再来一遍赋值other
2. 实现两个method
addNum() 和 getMedian().
一开始是空的，通过addNum添加数字，然后通过getMedian取得当前数组里的元素的中值
这题楼主一开始没想到最佳办法，用的ArrayList，然后每次addNum就BinarySearch去添加，由于插入操作是o(n)，所以其实并不太好，不过面试官还是让我实现这个。
后来想到可以用两个堆去解决，就能实现O(long n)了
http://www.1point3acres.com/bbs/thread-143685-1-1.html
1. APPDEISGN 做一个小应用，用户按完按钮可以返回当时的步速，API任意，界面设计任意，自己想一个设计出来，写出按按钮时候的function.
2. Clone Graph, Add list
3. 面经原题 给一个字符串，重新排列成相邻字母不能相同
4. a. 用C语言实现 strrch b. 给四张牌 返回四张牌的expression可以算出24点 （带括号）
5. a. 一个sorted array 只有0和1，返回第一个1的index
b. 有一个2D Array，行和列是 非递减。找到这个array的smallest Kth element
| 5B，lintcode http://www.lintcode.com/en/probl ... r-in-sorted-matrix/ |
http://www.1point3acres.com/bbs/thread-143308-1-1.html
Given a large integer array, count the number of triplets whose sum is less than or equal to an integer T.
第一题给的array里面有重复吗？有重复的话，感觉只能O(n^3)做啊
要不然就和Leetcode 3Sum Smaller一样，是求number of index triplets, 可以O(n^2)做
Given an array of Ad (profit, start_time, end_time) and a timespan [0, T], find the max profit of Ads that fit the the timespan
先说了穷举法O(2^n), 然后说了贪心法（不是最优解），最后用DP解决
我当时也是这个思路~ 先按照end_time升序排列，然后列DP方程：f(i,t) = max{ (f(i-1,t), f(i-1,start) + profit) }
第二题可以这样：
1. 先对所有的ad按照结束时间，从小到大排序；. visit 1point3acres.com for more.
2. dp[i]代表排序后前i-1的广告的最大收益，那么dp[0] = 0；
3. 对于第i个广告，有选和不选两种可能，如果选的话，就要从第i-1个广告往前，找到和第i个广告不重合为止，假设找到了j，那么dp[i] = max(dp[i-1], dp[j]+profit[i])
时间复杂度的O（n^2）,如果第3步用二分，就可以变成O（nlogn）. W
第二题 应该是类似背包问题，先把ads按照endTime排好序，然后两层for循环，i，j， i代表时间，j代表ad，dp[i][j]一开始设为dp[i][j - 1], 第j个广告取不取，取决于，是否它的endtime小与i的时间，并且加上他的profit大于现在dp[i][j - 1]的profit
for (int i = 0; i <= time; i++) {
for (int j = 1; j <= ads.length; j++) {
profit[i][j] = profit[i][j - 1];
if (ads[j - 1].endTime <= i) {
profit[i][j] = Math.max(profit[i][j], profit[ads[j - 1].startTime][j - 1] + ads[j - 1].profit);acres
}
}
}
int max = 0;
for (int i = time; i >= 0; i--) {
max = Math.max(max, profit[i][ads.length]);
}
return max;
其中i是当前考察的Ads数组元素下标，t是当前可用的结束时间，递归函数代码如下：
int f(int i, int t) {
if(i < 0 || t == 0) return 0;
int max = f(i-1, t);
if(end <= t) {
int tmp = f(i-1, start) + profit;
if(tmp > max) max = tmp;
}
return max;
}
不我觉得复杂度只是O(N * T)， N是广告个数，T是时间跨度。我们需要求的最大利润是f(N-1, T)。后面优化说了用哈希表记忆已经求出来的子结果，避免重复计算。
int f(int i, int t, int start[], int end[], int profit[]) {
if(i < 0 || t == 0) return 0;
int max = f(i-1, t, start, end, profit);
if(end <= t) {. visit 1point3acres.com for more.
int tmp = f(i-1, start, start, end, profit) + profit;
}
return max;
}
int main()
{
int start[] = {0,0,1};
int end[] = {1,2,3};
int profit[] = {1,3,1};
int T = 3;
int len = sizeof(start) / sizeof(int);
cout << f(len-1, T, start, end, profit) << endl;
return 0;
}
M x N large board, with only white and black blocks, all black blocks are connected (vertically or horizontally), find the minimum rectangle boundary that contains all black blocks.
还好心地给了提示和假定。感觉交流互动非常好，可惜最后差了一点，没能想出O(n^2)以内的算法。
第三题貌似是遍历玩board 记录 最left，最top，最bottom，最right坐标就可以了吧。。。。 应该是O(n*m).
如果n*m很大，还有一种方法是先指定一个黑点（如果不让指定，可以随机猜），因为黑点都是connected的，所以可以用递归搜索黑点，搜索的同时记录最left，最top，最bottom，最right坐标
就像图像填充里的floor fill，如果黑点的个数是K，复杂度就是O(K)
对，你这个方法我想到了，俄罗斯妹子直接说那就随机给你一个黑点好了~~然后我用BFS的复杂度就是O(K)，但是极端情况假如全都是黑点，一样是O(M*N)了。感觉这个有点博弈，看黑的多白的多。如果黑的多就从外侧包围更快，白的多从黑的开始搜索更好吧。。总之感觉这题很有意思，妹子中间给我画了一个宽度为1的黑格子螺旋线，那叫一个美。。。
感觉是不一定都得把所有格子访问一遍，但是极端情况全黑或全白仍然要都访问
不是原题吧，maximal rectangle求的是黑色点包含的最大矩阵，找个求的时能包含所有黑色的最大矩阵，不一样
我的理解是：从第一行开始往下扫，一行一行扫，遇到第一个不是纯白的行的话，就停止，因为就算找到了所求矩阵的顶，同理找到底、左、右。还是说我理解错了？O（M*N）
你没理解错~我最开始就说的这种“四面包夹”的做法，这算法是最坏情况（全白）就是O(MN)。所以接着就一直在分析更简单的算法。。
Design a algorithm to initialize the board of Candy Crush Saga. With M x N board, Q types of candies. (Rules: no 3 for run after initialization, must contain at least one valid move at the beginning)
小哥说话很和气，先让我介绍了一个project，于是兴致勃勃地讲了做过的一个游戏。他于是拿出手机给我看了这个，说那就出一道游戏题吧。。游戏可以参考（
http://candycrushsaga.com/how-to-play），这道题很开放，没有固定模式和答案，感觉答的还不错
先把Candy简化成数字，类型数组就成了[0, 1, 2, ..., Q-1]。规则一共三条：随机（至少玩家看上去是）；不能一开始就有3个共线的；开局至少有一步能保证有消除（不然没法玩。。）
1. 我首先关注的是前两条规则，因为觉得第三条只是小修改（尽管如果初始化完成后，再修改成符合第三条，可能导致连锁反应）。因为“随机”一直在我心头挥之不去，所以首先想到的是遍历所有格子，每次随机挑一个Q放进去，但立刻意识到这样很有可能导致死锁，尤其Q很小的时候，然后举了个死锁的例子
2. 因为之前考虑过Q很小，所以最简单就是{0, 1}两种，立刻想到国际象棋棋盘：两色相间一定能填满而且无冲突。然后想到能不能先按照国际象棋棋盘填满，然后在这个基础上进行”随机化“。假如我有个遵循前两条规则的函数random()，对棋盘进行随机化。因为是在01棋盘改，所以第一遍下来可能还是很”假“，但既然这个函数是遵循前两条规则的，那么大可放心的多执行几遍。就像PS的滤镜叠加使用~ 然后开始讨论这个random()函数，大体思路是遍历棋盘，对每个格子有0.5 的概率进行”尝试修改“。(随机化就是一个慢慢tweak的过程，这个参数后面提到要根据实际效果调整）。尝试修改的算法就是：q = random(0, Q); 以q为中心向上下左右四个方向，一共有6条长度为3的线会造成潜在冲突，因此逐个检查一遍，假如无冲突就把当前位置替换为q。最后根据实际效果决定是否再来几次~
3. 然后就剩第三条规则：开局至少有一步能走。我上面阐述的时候就一直有个感觉，每局开始看似随机但一定有定势。然后让小哥打开手机游戏开了两局看了下，果然，每局开头一定会有{V型, _/型} 中的一种或两种排列，保证挪一步就能消除。跟小哥聊了这个想法之后，我的做法就是01棋盘生成后，随机选一个排列，比如V型，然后在棋盘上随机选一个（也可以多个）位置，把这个位置画出的V全部mark成不可修改。然后在这个基础上跑上面提到的random()算法。第三条规则也可以有很多随机性，必须类型选择，类型对应位置、个数的选择。
http://www.1point3acres.com/bbs/thread-142659-2-1.html
给一个字符串s由单词组成， 比如“i have a dream”。 要求把这个字符串添到一个m x n的网格里，同一个单词不能被cut off，每一句之间空格相连。问最多添满多少个整句。follow up （m and n are much larger than the length of s, 怎么办）
第二题：就相当于左对齐的排版一样，重复的吧一句话排列到版面上，问最多能排多少次。
有一个2维数组A。实现两个函数：1) void update(int x, int y, int v), 就是更新A[x][y]的值(v). 2) int regionalSum(int x1, int y1, int x2, int y2)：就是求（x1, y1）和（x2, y2）构成矩形的所有元素和。
follow up: 如果系统很少用带update而经常使用reginalSum, 如何设计减少复杂度。.
3. followup：pre-computing, 然后数学图形中的计算面积（减去重复计算部分
这题很难描述，关于数字的Palindrome. 想象电子表的数字1的Palindrome是1， 2的Palindrome是5， 3的Palindrome啥也不是。。。如果两位的话 11的Palindrome是11， 25的Palindrome是52， 69的Palindrome是96。。。。。 问题是：
返回给定level的所有的Palindrome number。
level代表了位数， 比如：
level = 1: 返回0 1 8
level = 2: 返回 11 88 25 52 69 96
4。想象电梯里的数字显示屏，只有2 和 5， 1 和 1， 8 和 8。可以DP / recursion
第4题level2的时候还有21和15，28和82之类的吧？
第四题感觉不用太刻板的套LC上的那个，可以用个hashset来存是pali的数字，然后按照，LC上那样，判断首尾是否相等，然后中间的数是不是在set里面就行了。
这个是G家经常考的peek iterator.
http://www.fgdsb.com/2015/01/25/peek-iterator/
这个是Zigzag。
http://www.fgdsb.com/2015/01/30/zigzag-iterator/
这个是nested，最近很高频。
http://www.fgdsb.com/2015/01/19/nested-iterator/
这个是归并排序的iterator，G家考过几次。
http://www.fgdsb.com/2015/01/15/merge-sorted-stream/
Given an iterator A of iterators B's , alternately output the contents in all the B's
也就是说我现在有一群iterator B1, B2, ... Bk，分别是Collection C1, C2, ... , Ck的iterator. 但是不把这些iterator的引用直接给你，而是把这些iterator再放到一个Collection （比如记为B）中，然后给你的只是B的一个iterator BI。输出方式就是按楼主所说的zigzag形。
我当时说可以用BI先把B遍历一遍，把所有的iterator B1, B2, ... , Bk先拷贝到一个能够随机访问的Collection中，然后用楼主上面给出的方法。但是面试官似乎不太认可这个答案，但是也没有明说到底哪里应该改进。我觉得他可能是想让我找一个不用预先遍历的方法，或者是甚至不需要用到额外O(k)内存的方法。但是我到最后也没想出来。
http://www.1point3acres.com/bbs/thread-135449-1-1.html
两个链表 求最大的公共后缀
我是直接把链表遍历一遍，然后倒过来求公共前缀
求一个数组的 h index
h-index 就是这样的一个数 如果数组中有n个数的值大于n，并且没有n+1个数的值大于n+1，那么n就是h-index
具体思路如下，其实就是binary search。 首先根据start和end得出mid，看A[mid]值是否大于数组长度减去mid（假设A.length-mid = distance），如果是那么distance有可能成为h index. 因为数组有序，如果distance小于A[mid]，那么有distance个元素的值大于distance。 此时如果A[mid]值小于distance，那么继续向高位找，start=mid+1。如果A[mid]值大于distance，那么继续向低位找end=mid-1。如果低位找到更大的distance，那么返回低位的，如果低位没找到更大的，就返回现在的distance。
round 3
设计一个作业调度的API，我写了一个类似os里面线程调度的scheduler
给一个数，要求把这个数分解成一些平方数的和，并且要求使用最短的平方数list 如 13 = 9 + 4 而不是 13 = 4+4+4+1
貌似这题leetcode有类似的题目，好久没做leetcode新题都没关注。
round 4
给一个字符串，该字符串由一些可能会重复的字符组成，重新排列这个字符串使得没有相邻的字符是相同字符。如aab变成aba.
最终在stack overflow上看到了一种贪心法。还是把字符出现频率统计出来，扔在一个堆里。每次取出前两个频率高的字母，配成一对，次数减一，扔回堆。（只要写的时候注意下相邻字母不要一样就好）
首先贪心的思路是对的，我的实现方法是，首先统计各个字母出现的概率，然后存在一个map里面，key是字母，value是出现次数。然后取出最多出现的字母从map里面删掉，然后把剩下的字母按照出现的次数，每次都把map里面出现次数最多的字母取出来一个，插到前面删除的字母组成的字符串的空隙当中，直到没有空隙（这个过程是动态的，例如此时map里面有a出现3次b出现3次，那么先插个a，下一次要插个b，一直保持拿出最多的字母）。然后递归，把map传到下一次调用，直至map里面只有一个字母，如果剩下的一个字母出现的次数为1那么把它取出加到结果最后，如果出现次数大于1那么无解。
这种用大根堆的算法更简单易懂，我实现完之后跟面试官解释了很久，然后又演示了几个case他才明白
