Massive Algorithms: Google Interview Misc Part 10

Google Interview Misc Part 10

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

给一个文件，每一行算一个词，请把整个文件读出来排序，排序按照先freq，如果一样的freq就按照string排。很快写完以后开始follow up，如果有50G的文件，但是只有1G内存怎么做，当然文件系统是无穷大没有任何限制的，基本就是一个类似extenal sort的东西。

Onsite:
1. 烙印director, 上来非常友好的聊天，问背景，说他觉得google 的interview很难，很多牛逼人都进不来，擦我真不知道怎么接这个话，就说两年前我就没过。。然后写了一个巨简单的程序（我真忘了）但是我保证大家都可以写的出。。

之后又来了道小设计，说如果你有一个base class比如叫user, 有id, name，然后你有两种user extend这个base user，每个不同的user class里面有一些不同的fields, 问如果要用数据库存，要怎么设计， trade off是什么，很显然可以存两个表，也可以存一个表。一个表很难maintain，如果之后有更多更多不同的field，但是一个表的好处是如果其他表要join这个user的话一个join够了

  2. 感觉ABC小哥，short distance to all buildings.. 这题我刷过，四五十行的代码写出来改都不用改，感觉小哥有点石化。。
  3. 难的来了，设计一个ranking的东西，描述很简单，如果有一个单循环赛的结果List, 每一个就是一个Result, 里面有两个player id，和一个boolean，表示结果谁赢，请给所有的player排一下rank，这题实际上开始我理解不对，然后经过各种讨论，比如先排胜率，那么胜率都一样的人怎么排？看互相胜负关系，怎么看？后面归纳到做成一个有向图，每个边表示一个player胜另一个的概率，这个时候注意在build图的时候可以只考虑胜的概率多的边，比如1和2打成3比2，所以1到2有条边，权值2/5，所以如果能build成DAG这就可以解决，继续follow-up，如果有环怎么办＝＝》卡死
  4. n-ary tree iterator, tree node有sibling和parent，其实很简单的一题

5. 给一个grid, 里面有m * n个pixels, 给一个函数getWidth(char c, int charset), 和另外一个函数getHeight(char c, int charset),返回对于每一个字符，一个特定的charset下需要多少长和多少宽的pixel,
最后给你一个string，返回能够把这个string放到这个grid里面的最大的charset, 其实这题不难，核心就是写一个valid函数return一个boolean, 然后外面套个BS去找到最后一个是True的valid, 但是巨多edge cases, 大家可以自己写一下

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

第一题给一个complete tree但不一定是full tree，求这个tree里的node个数。leetcode 原题，不过一下子没想出来。上来先拿brute force写，然后面试官说没有用到complete tree这个fact，问怎么improve，这里卡了很久，然后在一点提示下写了binary search的解法。问了time complexity。

http://massivealgorithms.blogspot.com/2015/06/leetcodecount-complete-tree-nodes.html

第二题是给一个number, 还有一个数组包含这个number所有prime factors, 问这个number的dividers的个数

求有多少个dividor，是不是和求质数个数的经典算法类似？

应该是这样的，这题应该是求combination的数目，其实很简单，比如72=2^3*3^2，那么实际就是求3个2和2个3有多少种组合，对吧

差不多，可以先根据给的数组求出每个质数最高有多少次幂，然后求combination, 比如120 = 2^3 * 3 * 5, 一共有4 * 2 * 2 - 2 = 14个.

时间复杂度是多少？我做了一下是logn ＊ logn。

求n有多少个divider, 比如24就有1 2 3 4 6 8 12 24这些，给的数组是2 3表示其中的质数

先求出对于n的每个质数最高能有几次幂，然后把求出来的数做combination。比如24 ＝ 2 ^ 3 * 3 ^ 1, 那最后24有 (3+1) * (1+1) - 2 个divider, 2,3,4,6,8,12 (不包括1和n本身)

public static int getDividerNumber(int[] primes, int num) {
if (primes == null || primes.length == 0) {
return 0;. From 1point 3acres bbs
}
int[] count = new int[primes.length];
while (num > 1) {
for (int i = 0; i < primes.length; i++) {
if (num % primes[i] == 0) {
num = num / primes[i];
count[i]++;
}
}
}
int multed = 1;
for (int i : count) {. from: 1point3acres.com/bbs
multed *= (i + 1);
}
return multed - 2;//??
}

Subarray Sum 和 Subarray Sum II. 第一题给一个array, 找一个最长的 subarray使得和为0。第二题上来先问我brute force的时间复杂度是多少，LZ算了半天说是n^6 (假设是正方形matrix)，三哥说是对的。。每次LZ一说话三哥就会疯狂摇头然后说yeyeye, 阿三摇头点头跟我们真是反过来的。。。然后具体解释了怎么算sum matrix, 然后怎么算是不是0。

第一题是写一个class simulate一个病人吃药。一个bottle里有half pills 或者 whole pills, 随机拿一个，如果拿出来的是half pill就吃掉，如果是whole pill 就弄成两个half pill吃一个放回去一个。初始给的pills不一定全是whole的。一开始用了array list，跟面试官的思路有点不同，交流了一下改用两个integer又写了一遍。

第二题是假设一开始给的pills是start state，然后给一个end state. 求一个病人随机吃药，从start state吃到end state的概率。比如一开始2 whole, 1 half, 求吃成 1 whole, 1 half的概率。LZ一开始说build一个search tree这样直观点，他表示不需要把tree专门建起来，LZ就直接一边搜一边算没有用extra memory。

从初始状态作为一个root，按一个search tree做dfs/bfs计算，每次有两个child, 把达到parent时候的概率带到child里去计算，遇到目标状态就停止，还要判断终止状态，就是到了一个不可能达到目标状态的情况。最后把所有到达目标状态时候的概率加起来。

概率比如你有2half pill, 1 full pill, 那么你有1/3的几率变成3 half pill, 有2/3的几率变成1 half 1 full, 这个是个二叉树，到每个node都有个概率，把最后到Leaf的概率加起来就行。

给一个directed graph 的start node，这个graph里可能有cycle，如果remove一些edge可以使这个graph不含有cycle，并且从start node依然能访问到所有这个graph里的nodes，这些edge就是back edge。要求打印出所有的back edge。写完拍了照又follow up了一下，问存不存在这种graph，你可以remove 不同的 backedges 使得这个graph valid。LZ一开始觉得是不存在的，但是想不出来证明的方法。后来画了个图发现是存在的，但LZ自己没一下子看出来。。被提醒了下。

我的第一感觉是一边DFS一边标记访问过的点，如果循某边访问到一个已经访问过的点就是back edge

有个问题是remove backedge的时候选择remove哪一个edge都行吗？

我感觉就是dfs，同时往下传前一个访问的点，测试当前点是否已访问，如果是，那么前一个点到当前点就是一条back-edge。伪代码大致像这样：

visited = dictionary
func dfs(start, prev):
if start in visited: 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
print prev->start
return
visited.add(start)
for next in neighbours of start:
dfs(next, start)

然后第二题是给一些类和function：
class Point{int x, y;}
class Rect{Point p1, Point p2}
class Shape{
int inside(Rect r){}; //shape是不规则的图形，给了一个function判断这个shape和rect的重叠关系，
//如果rect完全在shape里 return 1. 如果rect和shape有overlap， return 0，如果rect 完全在shape外面，return－1
}
draw(Rect r){};
以上是已经有的function，
给一个长方形的screen，再给一些shapes，要求写一个function在screen上画出这些shape。
写完后又问了一题，如果有A和B两个shape，A和B有overlap，用给的inside function写一个新的inside function，判断一个rect和这个overlap area的关系，同样返回－1， 0， 1
然后问这个关系是什么，LZ一开始没看出来，其实就是min(A.inside(rect), B.inside(rect));
然后问如果把min换成max的话这个算的area是什么样的。应该是A和B的union

第四轮的第二题我大概画了个真值表
-1 0 1
-1 -1 0 1
0 0 0 1
1 1 1 1
是这个意思么？
是不是max(A.inside(rect), B.inside(rect))

面完聊了很久，白人大叔介绍了Google的20% time rule. Google每个员工可以花20%的时间做自己想做的事，比如自己学习或者去别的组做一些小项目，这样跳组也会简单些。然后还介绍了他和他的其他一些同事的跳组经历

楼主对于最后一题的话，min(A.inside(rect), B.inside(rect))，然而，虽然A和B都与rect重叠，但也不能一定推出A与B重叠。但你提供的公式min(A.inside(rect), B.inside(rect)) =》 min(0, 0) = 0, 认为A与B在都与rect重叠时，彼此会重叠。

这个overlap是给定条件里有的，判断的是这个rect和重叠部分的关系，所以不考虑A和B不重叠的情况，或者如果A和B重叠部分为null的话认为和null也是重叠的

前三轮面试官都是一边看我写代码一边往本子里敲的，只有最后一轮是拍照。。

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

第二题可用leetcode388题来练但要注意改动三个要求：1. oa题设定了一个root directory 故计算长度时要加一 2. leetcode题要求计算上image长度而oa有可能不用 3. oa里没有‘\t’而是' '
第二题有规定时间复杂度o(n) 第一题忘了但记得有句话是什么“base on correctness but not...” 感觉是以做对为主
楼主两题都o(n)，第一题做了遍历，第二题用dfs
强烈推荐oa前自己写好代码并测试

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

首先题目讲解了五分钟，说的是有很多sorted data streams，其中有disk的数据， memory的数据，还有network的数据，然后让设计interface，返回sorted data stream（在disk中）。看到题目后瞬间懵逼，然后就merge sort开始编，最后返回了路径。中途不知道各种怎么call，然后就整了一堆不知名函数。
最后又问有N个elements， K个data streams，问complexity。我问能不能fit it memory，毕竟写数据到disk的花费还是很高的，他说does not matter。我就日了狗了。最后说NlogK。他说他能不能更好，我想了半天胡诌了一遍说可能，看数据格式，但一般来说是NlogK是最好的。他说I agree。你都agree了问那么多干嘛

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

1. Interleaving Iterator，这道题两个面试官都有提到说要考，因为第一轮已经考到了所以后面的面试官临时换题了。这应该算是高频题目了吧
input就是一个arraylist of String iterator， alternatively的打印出来结果
比如说三个string iterator，第一个string是ABC，第二个是DE，第三个是FG，iterator的最终output应该是ADFBEGC
要implement两个function， next和hasNext
这轮答得相当的不好，因为hasNext理解有误，到最后测试test case的时候才由面试官指出。实在是不应该

第一题是LC 281 zigzag iterator

2. LC 406
没有刷过这道题，以为是topological sort，所以各种的twist。其实greedy就好

3. Lowest common ancestor of a family "tree" LCA的变种。有parent pointer。不一定是binary tree，意思就是两个父母可能有多个孩子。非常简单的一道题，瞬秒

第三题有parent直接从child往上走就行了？

嗯是的这道题input不是root就是要找LCA的两个child node。所以一路往上找就好啦～

4. Edit distance

http://www.1point3acres.com/bbs/thread-208782-1-1.html 第一轮：烙印小哥，两道LC水题，一个是给了一堆字母选一些出来组成最长的回文串有多长，说了下思路，没写code，还有一个是143，写完跑test cases。
第二轮：国人/ABC小哥+白人傻豆，小哥是ads组搞NLP的，问了一个相关问题：一共k个ads id，n（比k大）个event，每个event有一组ads id。任何两个有共同ads id的event可以归为一个group。如此重复直到不能合并，输出所有的group。优化了之后，本质是一个建图然后DFS的问题，说完算法写了建图的code就没有时间了。小哥貌似很满意
第二轮感觉更像union find
第三轮：老墨小哥，问了+和-的string game，每次可以吧--变成++，不能走了就算赢。要求写naive的search方法，写完了问followup我表示可以DP，小哥满意。

第三轮dp怎么做
dp思路基本就是先做起始string全是-的，然后再推广到一般情况

第四轮：国人大姐，问了一个简单题，然后问了个背包。面完了跟我说起了中文，说她这轮肯定不会差，但是让我小心烙印面试官黑我（着实让我担心了一下第一轮只有一题写了code
http://www.1point3acres.com/bbs/thread-204501-1-1.html
1. 给一个array，找出这个array 的local minimum。 Local minimum的定义是小于左边并且小于右边。
2. 给一个tree, 求所有root to leaf 组成数字的和。比如
   3
/ \
  3 1
/  \
1  2       就是 331 + 332 + 31

其实就是想成一个weighted tree, 然后求weight最大的root->leaf 的path~

3. 给一个string，求一个permutation让没有两个相邻的char相等. 比如 abba -> abab
第二轮：
1. 给一个tree，一滴水从root到leaf，每段edge都有一个时间，是水滴穿过的时间。求问多久整个tree都会变湿。
其实就是想成一个weighted tree, 然后求weight最大的root->leaf 的path~

2. Given a large file (larger than computer memory), file contains many integers.所有integer都是(0-10k). Get the smallest k integers. 要求O(n)

我开始想把large file分割成一个一个subfile 后来面试官hint下想到可以用Bucketsort的方法, 建立一个10k size的bucket 然后面试官说好给你一个hasNext() 和 next()的函数来traverse这个file
当时也有提到min heap，不过好像不符合O(n)的要求
另外string permutaiton那个题应该是假设有valid解的

http://www.1point3acres.com/bbs/thread-175734-1-1.html
1. 给一堆interval 算出total cover的区间，输出list
2. 二叉树找closest value。注意有可能要返回一个以上。
LZ，请问你interval的题用的是sort+merge吗？还是建了interval tree？. more info on 1point3acres.com
然后第二题可能返回多个结果的意思是不是：如果都是int，target=0，并且元素中有-1和1，那这两个都得返回？
2. 找floor和ceil就行
http://www.1point3acres.com/bbs/thread-143308-1-1.html
1. 华人大叔。题目：Given a large integer array, count the number of triplets whose sum is less than or equal to an integer T.
一开始猛然间以为是3-Sum的题，仔细想想不太一样，细节问题挺多。最后写了一个O(n²lgn)的算法，然后问大叔更简便的有木有，大叔迟疑了片刻说应该有数学相关的取巧办法。。
估计LZ的做法是，穷举两点，然后二分找第三个点

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 timespan.
先说了穷举法O(2^n), 然后说了贪心法（不是最优解），最后用DP解决

先按照end_time升序排列，然后列DP方程：f(i,t) = max{ (f(i-1,t), f(i-1,start) + profit) }. more info on 1point3acres.com

其中i是当前考察的Ads数组元素下标，t是当前可用的结束时间，递归函数代码如下：
. more info on 1point3acres.com
不我觉得复杂度只是O(N * T)， N是广告个数，T是时间跨度。我们需要求的最大利润是f(N-1, T)。后面优化说了用哈希表记忆已经求出来的子结果，避免重复计算。. visit 1point3acres.com for more.
我写了一段测试代码，试了一些比较简单的情况，暂时没发现问题。欢迎大家指正~. From 1point 3acres bbs

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);. more info on 1point3acres.com
if(end <= t) {
int tmp = f(i-1, start, start, end, profit) + profit;. visit 1point3acres.com for more.
if(tmp > max) max = tmp;
}
return max;
}.

第二题可以这样：
1. 先对所有的ad按照结束时间，从小到大排序；
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）
第二题应该是类似背包问题，先把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);
            }
         }
      }
      int max = 0;
      for (int i = time; i >= 0; i--) {
         max = Math.max(max, profit[i][ads.length]);
      }
      return max;

潧-涓€浜╀笁鍒嗗湴
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)以内的算法。

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），这道题很开放，没有固定模式和答案，感觉答的还不错。
http://massivealgorithms.blogspot.com/2016/12/game-board-init-google-interview.html
http://www.1point3acres.com/bbs/thread-137068-1-1.html
5/4/2015 Phone Screen:
http://www.1point3acres.com/bbs/thread-133611-1-1.html
6/8/2015 Onsite @ Youtube San Bruno office:
第一轮：
面试官上来先问了个high level design：假设有这么一个给用户注册账户的service，让你加一个feature使得每次用户注册成功给用户发一个欢迎的email，大概该怎么设计这个feature的工作流程？这种题也就凭感觉，感觉面试官就是想看看你有没有一些system design的基本概念。我就说嗯我们应该在准备将用户信息写入数据库前取出用户的email信息给用户发email, 不需要等用户完成注册账户流程后再去数据库里取啊，那样肯定慢。面试官又问那好，你觉得这么设计有什么问题？

我就说哎呀要是server在还没发email的时候down掉了就傻眼了呗，解决方案就是搞台back-up server然后和main server一直保持发送heartbeat来track status，main server down掉了换back-up server上，当然要保证用户信息同步啥的。。。总之就是一顿扯，面试官看上去还挺满意。。

给一个List，里面存着一些一个双向链表上的结点，这个List里面所有在双向链表上邻接的结点组成一个strong component，求List里strong component的个数。我就很快解释清楚做法，得到面试官同意后把代码写了出来，因为写的时候没有考虑太多用了两个HashSet，follow-up是把代码改成只用一个HashSet来做。改完后又来个follow-up：什么样的恶意输入会让我的代码crush? 我看着代码想了下就跟面试官说如果传进来的List里面包含的ListNode都是一个circular double linked list上的结点的话我的代码handle不了。然后面试官就露出了一种很满意但是又努力不想让我看出来的表情。。接下来就是提问环节了。

第一题只要把list里的nodes放到set里然后traverse doubly linked list就ok了吧 2个hashset是什么做法？？
对，第一题就是那么做，我当时有点紧张，多建了个visited set，每次遍历到一个结点不是从原set移除而是加到visited set。。所以写完就又改了一下。

第一题准确来讲是list里面所有在双向链表里邻接的结点组成一个strong component，比如说
给你个双向链表 1 <-> 2 <-> 4 <-> 7 <-> 9 <-> 11
给你个List里面有1,2,7,9,11, 那么 1,2组成一个strong component，7,9,11组成一个strong component。
解法就是建个HashSet然后把List里面的结点全丢进去，遍历一遍List，遇到一个在HashSet里面的结点就从这个结点开始把所有能到的在List里面的邻接结点从HashSet里面删掉，count++。换言之就是简易版的图遍历

第二轮:
这轮面试官还带了一个shadow小哥，让我很惊讶的是面试官一进来就跟我说他去看过我简历上写的用MEAN stack做的个人网站，觉得设计得挺棒的，一下我就high起来了，大概跟他聊了聊当初自学MEAN stack写这个网站的感想。然后面试官又出了道面经里出现过的题。。

让你设计个matrix class，提供两个方法：update(x, y) & query(x1, y1, x2, y2)，update方法是update matrix上一个cell的值，query方法是查询matrix上用(x1, y1)和(x2, y2)确定的矩形内所有值的总和。有三种scenario，
第一种是update方法调用的次数远大于query方法的调用次数，第二种是query方法的调用次数远大于update方法的调用次数，第三种是两种方法调用次数一样多。我很快给他讲清楚三种scenario下两个方法的最优实现，然后他让我写了最后一种实现的代码。面完这题还有20分钟，面试官说这就是我的main question了，咱们可以再来研究道难题，你做不出来没关系，来一起想想，然后给的题是一道和4 sum类似的题，但是是求所有和小于一个给定target值的组合个数，有个条件是给的数组size相当大。他跟我说这个问题有复杂度小于n^3的解法，但是他忘了怎么解了。。最后当然是想破脑袋也没想出来。。还剩5分钟的时候就进入提问环节了。总的来说这轮给了我相当大的信心。

第一种情况，因为update次数多，那就不用对matrix做任何预处理，这样update是O(1)，query是O(N^2)。

第二种情况，因为query次数多，那就预处理一下matrix，新建一个辅助二维数组dp,使得dp[y][x]等于以(0,0)和(x,y)两点确定的矩阵内的值的总和。这样update是O(N^2), query是O(1)

第三种情况，我们可以改变辅助二维数组dp的构成，使得dp[y][x]等于(0,y)到(x,y)的所有值的和，这样update是O(N)，query也是O(N)

第三种情况用二维线段树，或者二维树状数组，可以做到update和query 都是O(logN^2)的复杂度

第三轮：
上来就让我实现linux的diff命令，我就好好的问清楚了她期望的输入和输出，然后用java开始写，期间写遍历文件系统的function的时候一时半会想不起来java里相关的API了，就跟妹子问咋办，妹子说不要求非要死记硬背API，你自己想想有什么API比较make sense的在白板上注明一下就行了，我正好这段时间上班就是写python干类似的事，就一股脑把python的相关API在白板上注明出来，然后接着写代码。。写完后又大概跟妹子提了提如果给的路径下如果有symbolic link该怎么处理，妹子表示很满意。。follow-up是怎么判断两个文件内容是否相同，文件太大怎么优化。

第三题主要思路就是遍历两个输入路径，把路径树中的所有叶子结点找到（包括file和empty folder），把对应的相对路径拿出来放进对应的两个set里，然后就是同时遍历两个set，找第一个set里没有的而第二个set里有的（+），以及第一个set里有的而第二个set里没有的（-），遇到相对路径相同的file就转化为绝对路径读file content用md5算下hash value，比较看看内容是否一致

第四轮：
这轮面试官又给了个面经里出现过的题。。设计一个SparseVector class，包含set(long idx, int val), get(long idx), dotProduct(SparseVector otherVec)三个方法，没什么特别要注意的地方。写完面试官表示满意，拍照走人。。
第五轮：
这轮的题有点意思，大意是给这么一个情景：有一排数量无限的object，每个object有两个状态，可以用true和false来表示，object的状态是可切换的，初始情况下所有object的状态都是false。让你设计一个class，实现两个方法：isToggled(long idx), toggle(long start, long end)。这题没记错的话之前面经里也出现过。

我最后给出的方法是维护一个list of intervals, 每次执行toggle时都要新加入一个新interval，然后把这个新interval merge进已有的interval list里面，这个解法的问题在于实现起来非常复杂，因为做merge操作时你需要反转所有和新interval重叠的interval的状态，最后才把新interval里不重叠的部分加进list里面。最后代码也没写完，但是写到中间我突然想起来之前看到一个面经里的比较类似的题，可以只记录每个object的toggle操作的次数，最后根据操作次数的奇偶来判断object的状态，如此一来就不需要实际记录状态，只需要维护一个balanced interval tree，每次toggle就把新interval加进tree里，执行isToggled(long idx)时计算所有包含给定idx的interval的数量就能决定对应的object的状态了。跟面试官提了提这个做法，面试官表示这就是他的解法，但是他觉得我给的解法也不错，查询的复杂度要比他的方法低，就是难实现
最后那个状态切换题，或者说开关灯的题目
可以用每个bit表示每个灯的状态，然后用一个int或者long数组表示全部灯
然后对于切换状态，只要计算出start和end实际覆盖了哪些数字即可
对于完全覆盖的数字，只要按位取反，对于两端局部覆盖的数字，作“局部取反”

局部取反，实际就是设计一个mask，然后与数字作异或操作
整个方法在时间和空间上应该都是非常理想的

unsigned int mask_range(int low, int hi)
{
return (~0U << low) & (~0U >> (sizeof(int) * 8 - 1 - hi));
}

int reverse_part(int i, int low, int hi)
{
return i ^ mask_range(low, hi);
}

class ToggleManager {. Waral 鍗氬鏈夋洿澶氭枃绔�,
TreeSet<Long> set = new TreeSet<>(); .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
public boolean isToggled(long i) {
// assume i >= 0
return set.subSet(0, true, i, true).size() % 2 == 1;
}.1point3acres缃�
public void toggle(long start, long end) {
if (set.contains(start)) { 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
set.remove(start);
} else {. more info on 1point3acres.com
set.add(start);
}
if (set.contains(end+1)) {. 鍥磋鎴戜滑@1point 3 acres
set.remove(end+1);. Waral 鍗氬鏈夋洿澶氭枃绔�,
} else {
set.add(end+1);
}. 1point3acres.com/bbs
}
}

2) F家
5/11/2015 Phone Screen:
很水的两道题：1) move all non-zero elements to left. 2) find first buggy version 面完HR通知我总部没坑了，就把我扔给seattle office的HR了。。
6/15/2015 Onsite @ Facebook Seattle office:
第一轮：
JEDI，这轮没什么好说的，瞎扯淡，给的算法题是给一个string由一堆单词加上不等的空格分隔而成，让做一下处理使得最后输出每个单词间只相隔一个空格。
第二轮：
给了个copy random list的题，我一看我嚓原题啊，肯定是拿来warm up的，快速给三哥讲一遍用hashmap的解法，准备开写呢，只见三哥蛋蛋的看着我，来了一句：“恩，很好，但是有木有更好的解法？“我一听，整个内心就顿时是崩溃的。。这是要我写O(1) space解法的节奏啊。。。我虽然leetcode刷了好几遍，但是这题的O(1) space解法早就忘得一干二净。。原因在于之前面试也遇到过几次这道题，但是面试官都是只要hashmap的解法，我后来准备的时候也觉得O(1) space的解法也算是一种比较tricky的解法，实际面试的时候上来就写这种解法很明显就是背题啊。。也就再没写过这种解法了。。所以当时我很想给面试官做出一种”你特么是在逗我么“的表情，但是还是忍住了。。最后还是自己YY出了一个解法，但是是那种不能处理random pointer指向之前的结点的解法。也把代码写出来了，三哥看了看觉得木有BUG，然后就蛋蛋的跟我说恩挺好，时间到了，你下去再好好想想能完全解决这个问题的O(1) space的算法吧，有啥问题要问我？
第三轮：
题目是给一个string,一个set of string, 问string里面是否包含一个substring，使得这个substring的任意一个prefix + suffix能组合成set里面的任意一个string，能就返回true，否则返回false。写到最后写出了个小BUG，而且三哥提醒后找了半天没找出来。。。最后发现是有个substring()没给end index。。。三哥表示强烈不满，问题也没让我问就闪了。。
我少说了个条件，输入除了一个string和一个set of string,还有个整形变量len表示set里面每个string的长度（也就是说set里的string长度都是一样的）。比如input string is "whoisyourdaddy", input set 包含两个 string "whu" and "ddy"，那么function应该返回true，因为给的input string里面的substring "whoisyou" 的 prefix "wh" 和 suffix "u" 组成了 "whu"，而另一个substring "daddy" or "ddy" 的 prefix "d" 和 suffix "dy" 组成了 "ddy"，因此这个例子里set里面所有的string都可以在input string里面找到一个substring的一个prefix+suffix组合构成
从头遍历string "whoisyourdaddy"，然后依次比较每个在set里面的string，如果发现set里面的string是以string里面一个字母开头的，例如这里"wh" 与"wh"相等，我们就check if "u" in "oisyourdaddy", 如果存在，就把whu从set string里面删除，如果最后set stirng为空，就返回True。但是这样的话，就不清楚为什么题目给出length of string in input set？

第四轮：
问了道large scale下怎么设计一个根据关键词查询status的service。我自然又是一顿瞎扯，神马invert index, consistent hashing, 想到什么扯什么。然而这并没有什么卵用。。不论扯到什么大哥都要刨根问底，我到最后就完全招架不住了。。大哥的表情也就越来越蛋疼了。。这轮结束后我觉得基本就没戏了，design面这么烂基本是硬伤，弥补不了了。
第五轮：
上轮被虐的奄奄一息，马上就又来了两个geek大叔补刀了。。一道determine if there is a subarray in the given array that sum up to a given target，一道trie上面的regex search。。。我第一道写得其实还挺快，但是举例test case给geek大叔讲通代码花了不少时间，最后第二道题只剩15分钟，真是风一般的速度把第二题写了个差不多。。geek大叔看上去态度模棱两可，也是一副冷冷+蛋蛋的表情。。。

http://www.1point3acres.com/bbs/thread-207983-1-1.html
第一面，三哥：第一问：如何存储一个电话簿。追问：如果要求输入一个子串，如何给出所有包含该子串的所有名字。第二问：标准LRU实现。

这题还算基础，没啥难点。第一问本问直接用trie就行，追问直接用suffix array＋二分查找。LRU实现没出什么其他问题。

第二面，俄罗斯大叔：第一问判断一个数是否中心对称，比如101，818这样的；第二问给定一个n，求n位数以内所有的中心对称数。

记得好像做过类似的题目，leetcode上可能有，但是忘了。第一问我的做法是生成中心对称然后比较是否相等，有个corner case是生成对称数的时候要用longlong存，因为可能会有166666666这样倒过来超界了的。第二问分奇偶讨论，奇数seed：0 1 2 5 8，偶数seed：11 22 55 69 88 96，然后放队列里，每次出队一个，然后两边加上0 1 2 5 6 8，其中6和9要注意一下。
http://massivealgorithms.blogspot.com/2015/08/like-coding-leetcode-246.html
http://massivealgorithms.blogspot.com/2015/08/leetcode-247-strobogrammatic-number-ii.html
http://massivealgorithms.blogspot.com/2015/08/leetcode-strobogrammatic-number-iii.html

第三面，国人大哥：如何只通过shuffle和remove构造最长的回文串，第一问能做出来就行，第二问要求除了新串之外只能用一个额外变量。

LC409 拓展，输出回文数版。本问不难，直接用hash统计每个char出现的个数，然后偶数全进去，奇数删一个再全进去就行，输出纯粹体力活，没啥说的。然后重点来了，这尼玛第二问是怎么回事,一个变量没有hash你特么逗我？后来在提示下想到一个非常妙的解法：

用一个int32（可以看成是一个32位bool数组）记录每一个char是否出现过，然后开始读input，如果当前字符没有出现过，通过位运算在bithash里把这个字符对应的位mark为1表示出现过了；如果该字符出现过，清空该bit，然后加入输出。读完input之后看我的bithash是否为0，如果不为0，随便拿出一个mark了的bit对应的char append到输出，否则跳过这步。最后一步是翻转现在的输出串（要注意一下，如果之前一步加入了某个char，这里要从倒数第二位开始翻转）append到原输出串，操作完成。

看一个样例：
ababca

读到ab之后，这两位在bithash里被mark了；读到第三位a的时候，因为a已经被mark了，所以unmark并且加入输出；第四位b同理；第五第六位都只在bithash里mark，不加入输出。这时候的输出串是：
ab
而且bithash不为0。所以这时候我们取出最低位1对应的char加入输出，于是输出变成 abc。由于加入了新字符，所以从倒数第二位开始翻转，于是得到最终输出abcba。

这个做法全程只用一个额外32位int作为hash，是原本开 int hash[26]的1/26。

第四面，越南小哥：给两张手机上长网页的截图，输出一整张合并后的截图。

先解释一下题意，比如一个网页非常长，然后我想用手机把整个网页截下来。于是我分几次截图，每次截图一部分，但是为了让我的读者明白两张图的连接点在哪，所以我会截一些上一张图的底部，这样读者能通过对比两张图的相同部分来进行拼接。现在的问题就是我想用一个程序完成这个操作，怎么办。

于是难点就是，如何甄别一张图底部和另一图头部重叠的部分。这题本身不难，我先把每一行算一个hash出来，然后就相当于对两个数组进行比对。但是蛋疼的是corner case。有这么几个corner case需要考虑：
1. 加入两个截图算出来的行特征值是 [3,4,1,2,1,2], [1,2,1,2,5,6]，这时候如果你从第一张图底部开始做match就会出事，因为会过早判定出现内容相同；
2. 如果一个网页有恒定的漂浮物，header或者footer，怎么办。我这里是直接把两张图相减，对于一个区域内0值超过阈值的部分标示为common part不做处理，然后只处理非common part；
3. 如果header footer或者漂浮物99%相同，但只有略微区别怎么办。用2的办法直接干。

第五面，老三哥：给一棵树，每个节点有一个颜色，RGB中的一个，或者是empty，规定一棵树合法必须满足：1.一个颜色节点直接和empty相连，或；2.一个颜色节点通过相同颜色的节点和empty相连。验证一棵树合法。

到了这里我已经晕了，而且面试官似乎没有办法理解我的做法让我感到略微尴尬。而且这题到最后我发现了我code一个明显的bug，甚至可能是算法设计的问题，但是面试官似乎没有发现。

我首先提出可以先找到所有的empty node，然后对相同颜色的node做floodfill然后check是否覆盖了整棵树。然而面试官直接shutdown了这个做法，说这棵树非常大，先找empty node太慢了。我说找empty node可以在读图的时候就做，面试官强行说不可以make the assumption。好吧，换做法。

想了老半天，感觉面试官觉得我是个连递归都不知道用的sb，开始提示说要不试试递归？我说肯定要递归但是怎么个递法我特么还没想好😂这里我有点急了，感觉最后一面不要崩，但是越这样想越头疼。然后大概过了好一会吧，我自己都不知道过了多久，可能是1分钟，也可能是5分钟，我想到了一个解法：
如果该节点不是空，那么以该节点为根的子树合法必须：
1. 和该节点不同颜色的儿子节点所在子树必须全部合法，并且；
2. 和该节点相同颜色的儿子节点所在子树中至少有一棵包含直系空节点。（这点在面试的时候做错了，完全没想到，太慌了）
http://www.1point3acres.com/bbs/thread-206618-1-1.html
印度小哥，第一题，add two int，类似#2，不过是array。
第二题，两个string，有相同的characters，除了其中一个string会多一个char，return那个char。string中会有重复的character，所以用了一个map。例：“abcde” 和 “bdexac” 就 return ‘x’

http://www.1point3acres.com/bbs/thread-206734-1-1.html
1. 两个大文件，分别存在两台机器上，通过网络连接，带宽有限。只有一小部分不同，如何同步。
刚开始说读取每一行，传过去比较。后来给了点提示说做些运算。后来回答切成几部份，然后计算MD5,传过去比较。他说可以。
- merkle tree

2. copy-on-write 设计 lazystring类。
实现
const char* get()
LazyString(const char*)//allocate new storage.
LazyString(LazyString& str)// does not allocate new storage
void copy_from(const char*str)// allocate new storage

example: LazyString("asdf"); //allocate new storage
LazyString b(&a);// shares storage with a
assert(a.get()==b.get()); //they have smae sotrage
b.copy_from("asdf"); //modifei b, allocate new storage
assert(a.get()!=b.get());// they have different sotrage
第一轮第二题就是定一个class里面一个char*存cstr，一个size_t*存reference_count，每次发生拷贝构造函数就把俩指针赋值一下然后reference_count++，析构函数或者copy_from的时候把原来的reference_count--，如果减到0就delete [] cstr, delete reference_count就行了吧？感觉是纯问你c++的基础，完全没有算法和数据结构

第二轮：
第一道easy，判断string T的所有字符是否都出现在String S中。
第二道是 minimum window substring
http://www.1point3acres.com/bbs/thread-124980-1-1.html
1. Implement HashTable with get,set,delete,getRandom functions in O(1).

重点在于2个hashmap+arraylist. Waral 鍗氬鏈夋洿澶氭枃绔�,

2. Given a source word, tsart word and an English dictionary, transform the source word to target by changing/adding/removing 1 character at a time, while all intermediate words being valid English words.

没有要求实现（时间问题）
类似Word ladder II
问了时间复杂度

http://www.1point3acres.com/bbs/thread-209410-1-1.html
1. 设计一个简单的文件系统，没有redirect，给定一个文件夹名称A和一个文件名b，返回所有A文件夹下的文件b，直接暴搜，被问了dfs和bfs比较，如何写测试（正好想问问大家这种问题到底怎么答才好？），最差情况下的复杂度，如果完全不关心空间怎么优化。面试官吞音，楼主这轮交流不好，最后一个问题他的意思应该是多次query怎么优化，楼主答存两个hashtable，但答到最后时间已经有点不够了（面的最差的一轮）

2. 两个字符串，一个字符串比另一个多了一个字母，如果删掉以后两个字符串相等，找到那个字符。先假设知道长度，写了一个暴力，但是我的方法有可能交换reference，面试官不太满意，又写了不交换的。再假设不知道长度，同样暴力。再假设知道长度，问还有没有别的解法，答二分，开始写的时候有bug，被指正不是完美二分，最后改完
3. LC391，楼主答做过，换了LC298，楼主说也做过，不过记不太清了，于是让我写。楼主脑抽犯蠢，优化了半天，分析了半天复杂度，没优化到n，面试官最后说应该有线性的，于是那天唯一一次要提示，结果面试官说自己也记不清了。。。
http://massivealgorithms.blogspot.com/2015/10/leetcode-298-binary-tree-longest.html

4. 找一个图里最小degree为k的induced subgraph，http://stackoverflow.com/questions/10205191/graph-how-to-find-maximum-induced-subgraph-h-of-g-such-that-each-vertex-in-h-h，楼主写了一半，发现还是用queue最简单。这轮面试官似乎没准备太多follow up，大概跑了跑简单的测试，问了复杂度，之后问如果图很大怎么办，答基本思路如mapreduce

5. 设计deque，实现基本所有deque的功能。说了可以用vector或者double linked list，问比较，然后让实现了后者。之后问了LC239，被问了如果是stream怎么办。

http://www.1point3acres.com/bbs/thread-138432-1-1.html
第一轮是顺时针旋转一个正方形矩阵
2d matrix as image

visit every pixel of an image in a clockwise spiral pattern without visiting the same pixel twice.

第二题说起来有点复杂，但是也就是用hash/贪心就能搞定的

Give a list of numbers:
3, 5, 9, 2
Generate a signature for the list of numbers:
i, i, d

Example:
6, 8, 3, 5, 2
i,d,i,d

Question is:
Given a signature for a list of number, trying to print out a list of number that fits the signature, with lowest value of the highest number, and at the same time, no duplicated numbers.
Numbers[1, N]
http://www.1point3acres.com/bbs/thread-188731-1-1.html
大概就是取一个array里的任意n个不同的值,得到一个随机的组合，不能取同一个index的数，但是可以取数值相同的不同index的数
给一个array：[5,1,3,3],
再给一个数字n：2，
求这个array里的任意num个数：比如可以得到[5,1] or [5,3] or [1,3] or [3,3] ，但是不能得到[5,5]

再比如[5,1,3,3], 1 ===> [5] or [1] or [3]
http://massivealgorithms.blogspot.com/2016/12/smallest-permutation-from-signature-id.html

LZ就是先判断如果n>array.length或者n<=0或者array是空,返回一个空array
否则就是一个loop，每一次生成一个random的index数字，还用了一个hashset来存之前访问过的index，如果生成的random index之前已经get了，就再继续生成一个random index。
loop n次，每次取到的值放进新的结果array里。
然后说了说也可以用一个boolean array存每个值有没有已经取到。。
写完后再写了写unit test什么的，还有问道怎么检测得到的结果比如[5,1]确实是[5,1,3,3]里的
可以优化一下。要不然每次random index都得check用过没有。可以用个array 存 0到n-1 的index，用一个for loop，然后每次 rand mod n-i，每次拿到的random index move到结尾。这样下次可以保证不会用到之前的index

http://www.1point3acres.com/bbs/thread-202363-1-1.html
第一轮~ Encode string
举例："aaaabb" --> "4xa2xb"
解码规则：pattern是 <数字 + x + 一个字符>，比如"4xab"，解码后是"aaaab". Follow up 如何test

第二轮，白人姐姐
第一题 Next Permutation, follow up 如何test
第二题 Rotational Equivalent
规则："abbd" 和 "cddf" 是等价的（相当于把abbd按照字母表整个右移了两位，a->c, b->d, d->f）经提醒才注意到 "ab" 和 "za" 等价。
题目：给一个 list of string，把 rotational equivalent 的放在同一组。私以为是Group Anagram的变种~

第三轮 Decode & Encode
先让decode "2[ab]c" -> "ababc"，当然输入可能是多层的比如"2[a3[bc]]d"，似乎是leet原题。
Follow up 让说encode的思路。

一开始想这题的时候觉得按照他们那个格式嵌套压缩很蛋疼，可能的压缩嵌套方式很多，而且要追求最短的话不可避免要扫完所有 input string 几遍才行要么自己也不知道后面会出现啥。。。顺着这个扫完所有 input 再压缩思路的话还有 Huffman coding，建立在已知后面读取的 text 出现的 word pattern 都是独立分布并且分布已知的情况，去把出现概率最大的 pattern 用最短的 code 表示出来，也有各种优缺点。

后来查了点资料觉得 LZW 算法算是比较通用又 make sense 的，这个算法的各方面资料也很多。简单的实现可以让 encoder 和 decoder 共享一个 dictionary；严格正确的实现可以做到双方自行根据 input 维护 dictionary 进行 stream 处理，这两个 MIT 的课件讲的很好，共同维护字典的实现用 hashmap + trie 也不算特别复杂，面试 google 这种肯定够用了。

http://ocw.mit.edu/courses/elect ... s/unit-2-lecture-1/
http://web.mit.edu/6.02/www/s2012/handouts/3.pdf
主要问题是找到最大重复pattern，leet有这道题（幸好面试出门前刚看过
是用KMP求next数组的方法~
找到重复pattern以后bottom up建树就好了~

个人看地里面经 + 我认识的人去面 google 被问到这题的时候，一般都是先从 decode 开始，把 encode 这步做一个 followup 之类的去问你的思路。。google 挺喜欢这么干，出几个好写 code 的之后，后面出一个不太好当场写完的问题让你描述怎么做看你的分析过程，我 onsite 的时候没被问到这题，但是我有几轮 code 写完之后的画风都是这样。

前段时间准备面经题的时候考虑过如果面试官一开始就直接扔 encode 怎么办，我当时准备的做法就是说一下查循环节的思路之后，开始说一下其他常用的字符串压缩，然后写这个 lzw 的 code 出来。我记得 GFS / Bigtable 的 paper 里也有提到过他们的实现里有一个 variant of lzw 去做压缩的步骤。. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴

encode 的话顺着找循环节的思路是可以做的，虽然说会很繁琐。。面试官坚持这么要求的话就让时间复杂度随风去吧

第四轮 Subtree
判断一个binary tree是不是另一个binary tree的子树。
一开始想复杂了以为要在一个树里找另一个树的pattern，没想到只是个清新脱俗的subtree……

http://www.1point3acres.com/bbs/thread-170778-1-1.html
楼主不知道是电话通话质量不好还是耳机有问题，总是听不很清楚，结果第一题小哥说了题目，语速好快，我愣是一个字都没听懂。然后问小哥能不能paste题目到google doc上。。囧。。接着就感觉小哥口气明显不太好了，sigh..

第一题是Given a float array, 如果有两个duplicated element的index之差小于等于给定的X就返回TRUE. 其实题目很简单，但是小哥问的很细，HashMap的每一步操作都问的很明白才罢休. 还问了时间复杂度什么的

1，用float作为key, 面试官想问hashmap实现
你的意思是面试官的point在于，浮点数采用哪种hash函数？

第二题是Given a int array, find a local minimum. 我说直接scan一遍数组就行，他问复杂度，我说O(N)，他让我prove the worst case is O(N), 我就是说肯定要扫描整个array, 但是他不满意，要让我优化，，楼主隐约感觉可以用binary search，但是就是想的不是很明白，然后中途冷场了一会。。我直接问小哥可不可以先让我写代码，我边写边想。结果小哥义正言辞说：No, you can not code until you tell me your clear thoughts.. 好在最后的确想到了，然后我说用contradiction可以证明，他说good，然后就草草写了代码
http://www.1point3acres.com/bbs/thread-173619-1-1.html
// Return sum of integer 1..N, excluding multipliers of any single integers in X.// Example: N = 10, X = {2}, return 1 + 3 + 5 + 7 + 9 = 25.
// Example 2: N = 10, X = {2, 3}, return 1 + 5 + 7 = 13.
// Assume 1 < N <= 2^31. 1 <= K = X.size() <= 10. X contains only distinct positive prime numbers.

想不到有什么快的方法，先写了个解法O(kn)。然后问可不可以improve，想好久才想到用等差数列求和公式
就是totalsum - 有一个1prime的那些数的sum + 有两个primes的数的sum - 有3个primes的数的sum + 有4个primes 数的sum。。。。。。一直到k个primes的数
主要就是combination(k, i), i=1,..k

请问楼主的等差数列方法是什么？是（1+N）N/2 减去集合里面的数以及他们的倍数这个吗？
是的，记得把重复减掉的数加回去就好了。重复的数就是集合里的数两两的乘积。最后还有一个tricky的地方就是要把集合里全部数一起的乘积减掉。这样出来的复杂度是O(2^k)。看起来没有更快，但是他最后给的那个条件很关键。

inclusion-exclusion principle
不是。是2^k, where 1 <= k = x.size() <= 10

In combinatorics (combinatorial mathematics), the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as

|A\cup B|=|A|+|B|-|A\cap B|,

http://www.1point3acres.com/bbs/thread-209203-1-1.html
input是一组string, 找到这里面的由相同字母组成的单词组成一组并输出。比如bat 和abt，但是a 和aa这样字母个数不一样的不算。
例子： input[could, bat, dog, said, tab, cloud] output: [[could, cloud], [bat, tab], [dog], [said]]

然后小哥就问我怎么Handle input 里有重复的情况，比如input[could, bat, dog, said, tab, cloud, bat]，output就应该是[[could, cloud], [bat, tab, bat], [dog], [said]]
我就又加了一个dict来记录出现次数，当append到result里时按次数加进去。
然后小哥就问我假如有punctuation能不能handle，我看了一下说能。

接下来我问有没有可能会有大写字母的，比如Could，说有可能。我又改了一下代码。

接下来问了个follow up，说有没有可能在多台machine上同时处理这program。我按照MapReduce胡扯了一通
http://www.1point3acres.com/bbs/thread-173970-1-1.html
Considering there are N engineers in one company with id from 1 to N, Each of the Engineer has a skill rate R_i, we want to select one group of engineering whose ids
have to be continuous. The size of one group is the number of engineers in it and the skill rating of the group is the lowest rating of all the members in the group. Now given N and array R, for each group
from size X from 1 to N, we want to know the highest skill rating of all the groups whose size is X.吭哧吭哧写暴力法，还出了bug，被提醒才差不多弄对，问了时间复杂度
然后又要优化到n平方的复杂度，思路说对了，代码没来得及写完时间到了。。全程很方。。。脑子一片空白。。。

就是说：员工id 1-n 每个员工都有个rating值，存在数组里 R［1］－R［N]对应每个员工的rating.
现在要把这些员工分组，分组规则就是员工的id必须连续，例如1，2或者4，5，6 为一组这样，每一个组有一个性质（组rating取决于该组里员工rating的最低值），返回一个数组，得到不同size＝1-N的各种组中，每种size组的最高组rating
第一轮是一个X的window一直向右移找最小值么。。如果用heap的话复杂度貌似是nlogk,不知道可不可以更优
嗯，感觉是那道sliding window的变体，以及X从1 到N都要弄一遍

你是是要不断的移动，不断的往heap中添加元素和删除元素吗？java普通的priorityqueue删除是O(n)的啊，如果要做到O(lgn),需要时hash heap啊，“we want to know the highest skill rating of all the groups whose size is X.”是说每个window中找最小值，然后求的是整个过程中的最大值吧

public static int getMaximumInMinimumInWindowK(int[] arr, int k) {. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
if (arr == null || arr.length == 0) {.1point3acres缃�
return Integer.MIN_VALUE;
}
int res = Integer.MIN_VALUE;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int i = 0; i < arr.length; i++) {
pq.offer(arr[i]);
if (i >= k - 1) {
res = Math.max(res, pq.peek());
pq.remove(arr[i - k + 1]);
}
}
return res;
}

常规题：1. remove duplicate from an array
一开始说了先sort再干啥干啥，问了时间复杂度，没让code
然后说想想有别的方法没，脑抽了半天想到了hashset，问了时间复杂度，写了代码
2.given an array ranged from［0，N］，missing 了一个找出来。。
继续脑抽。。说我能求和么。。然后问这个求和有啥问题，有可能和会overflow
如果这个是sort的呢？
结果人家都sort了。。突然脑抽想到那个什么b^b=0 不断xor的方法。。
http://www.1point3acres.com/bbs/thread-202190-1-1.html
1. 一个房间，有个入口，有个出口，出口和入口在不同的边上。在这个房间里，有n个sensor，每个sensor有个中心，从这个中心辐射出一个圆型的探测区域。人走到这个区域里就会发出警告，表示不能通过。要求写一个函数，check人有没有可能通过这个房间

input:

一个sensor的list, list中每个object是一个三维的list（x, y, r）x和 y是坐标，r是半径；

房间的长l和宽w。

在对角线，比如出口是（0 ，0），入口是（L, W）

2. 给一个binary search tree和一个target数，找出这个tree里和这个target最相近的那个 node

http://massivealgorithms.blogspot.com/2015/08/like-coding-leetcode-270-closest-binary.html

http://www.1point3acres.com/bbs/thread-209911-1-1.html
-写一个方程返回浮点数组平均值（各种发散）
-在unsorted array里找一个数的时间复杂度，sorted array? BST?
-工作中遇到程序运行返回out of memory的错误，你会怎么来找原因？（我说了infinite while loop和infinite recursion, 提了stack/heap 然后他一直问我怎么用电脑上现有的tools来判断问题出在哪？看起来这是一个open-ended的问题，但我觉得他在寻找某个特定的答案，而我并没有答出来）
-一些琐碎的基础题，cs 101，不记得了
-最后一个问题(~10mins)，给一个array of strings, remove duplicates （我先说了O(n^2), 然后说了可以hashmap算出现次数，后来改成hashset）

http://www.1point3acres.com/bbs/thread-209212-1-1.html
问的是一个控制设备向GPS发送信号。怎么基于给定的void wb(byte d)和boolean ready()实现一个void writeByte(byte d)的方法。其实前面都是简单扯淡，最后绕出来的是用一个固定数组实现queue操作enqueue, dequeue, isfull, isempty

2. perfect square，lc原题。可惜我没有看，呆在现场。虽然想到排序x坐标，然后用扫描线，但是没想到如何在y轴检查overlapping（归根结底恨第一轮面试官扯故事太久，把我搞的七荤八素）。后来面试官看不下去了，让我写个检查rectangle overlapping的方法，我还miss了交叉的情形。心中一凉。

http://massivealgorithms.blogspot.com/2016/08/leetcode-391-perfect-rectangle.html
http://massivealgorithms.blogspot.com/2015/09/perfect-squares-leetcode-training.html
3. 给定直接血缘关系，检查两个人是否有血缘关系。
就是每个person有两个分别指向父母节点的指针，看成查找两个二叉树是否有公共节点
把两个人的祖先放进两个hashset。逐层访问更上一代的祖先，把新发现的一代祖先放进hashset，并和另一个人的hashset+新发现的一代祖先作比较，如果有同一个人就返回真。
4. 设计题，怎么找过去10年的top k stories
就是要多问面试官问题，这样才好讨论下一步
http://www.1point3acres.com/bbs/thread-209141-1-1.html
判断toeplitz maxtrix, follow up 是矩阵很大怎么办
http://massivealgorithms.blogspot.com/2016/08/find-if-given-matrix-is-toeplitz-or-not.html

http://www.1point3acres.com/bbs/thread-205789-1-1.html
第一题不要求写code，要求说数据结构：
假设每天都给一个employee list，里面有id，如果有一个id存在第二天的list但不存在前一天的list，表示是新加入的，离职同理。要求找出哪些是新加入的，哪些是离职的。楼主回答用两个hashset，前一天与后一天的比较，共有元素直接删除，最后留在前一个的表示是离职的，留在后一个的表示是新加入的。以及问了时间复杂度。
follow up:
如果list非常大，那我这个存储量很大，要怎么优化楼主第一个idea: 如果employee id 存在一些共性的话，可以用trie tree来存储，问了时空复杂度。
楼主第二个idea: 如果employee id是数字，且有range的话，可以用bitmap来存储，后来补充了如果不是数字的话，可以用hash function计算出hash code再用bitmap，问了时空复杂度。大概到这里用了二十分钟吧。

前一天的用一个hashset来存，第二天加两个新的hashset，一个存新人，一个存和前一天重复的（从前一天的里面删掉），算完以后没删掉的是离职的，再把两个新的hashset合并用于下一天计算。
我上的dbms课要求implement hash join，当时是这么做的，所以一下子就想到了~

如果list很长的话可以分成多个hashset，比方讲分10个，那就是hashvalue %10来决定存在第几个hashset里面
请问bitmap是如何存储达到节省空间的呢
bitmap就是用一个“bit [] barr”来代替一个"hashset<int> harr"，其中若一个int x在harr中，那么定义barr = 1，否则barr = 0. 这样对于一个长度为N的harr，本来占用内存=N*sizeof(int) = 4*N bytes = 32*N bits. 但如果数组值的范围比较小跨越0~M个int的化，那么就可以把barr的长度定为M+1，这样barr占用内存=(M+1)*1 bit = (M+1) bit. 这样对于数组长度远远超过int的个数的情况下bitmap肯定是节省空间的。. from: 1point3acres.com/bbs
Crack Coding Interview 4th Ed 的Chapter 12有一些处理memory limits的题目。这个好像是个处理大数据节省内存惯用的技巧。这就相当于把一个32bit int type的值如果只看成一个1D的数比较浪费，应该看成是一个32D的0-1 vector

实际不行的。在later Visual C++中，在内存bool是1byte (不是1 bit)，所以bool[] 比真正意义上的bitmap要占用8倍的空间。

给一个list的digit，给一个maximum number，要求返回所有由这些digit组成的且不超过max的数字，一个digit可以重复使用
http://massivealgorithms.blogspot.com/2016/12/return-all-numbers-lesser-than-maximum.html

http://www.1point3acres.com/bbs/thread-206769-1-1.html
所有四轮问题都是实际问题抽象出来的，没有lc上原题（也可能我没刷到，但不会像lc那样直接）。我的策略就是复述一遍题目，举例子（同时更好的理解题目），然后说想法，类似于把每一步怎么想的都告诉他，然后写代码。我刷题不够境界而且属于需要反复做才能记得住的那种类型选手，所以面试之前很虚，但是发现每个面试官都很好，会和你把问题做完，不会有题目很难不能理解或者你卡在哪块儿，然后他就瞪着你在那儿想的情况。都是交流的过程，所以感觉很好，不会特别紧张。

第一轮（白人大胡子小哥）：给一个Task类，包含用户名（name），开始时间（start），结束时间（end），以及这个Task这段时间所用的资源（usage）。输入时一个Task List，然后写一个函数，可以找到某一个特定用户的peak usage。

第二轮（国人小哥）：一个包含N个东西的pool，每个东西的重量不等。每个东西被抽出来的概率和他的重量是相符的，给你N个东西，返回抽出来东西的序列。（这轮差一些没写完，但面试官说知道我咋想的了）

这个应该是给定物体i的重量为w_i，而且随机取到物体i的概率p_i:=w_i/totalWeight. 每次取到某物体后就把该物体删除。然后重复再从剩下的物体中再取（O(N)）。注意：每次取完物体后概率分布也就变了。所以每次要重新计算概率分布（O(N)）,随机取的过程可以用0, p1, p1+p2, ..., p1+..pn=1区间和看一个[0,1]均匀变量落到哪个子区间来模拟（binary search O(logN)）.最终时间为O(N^2)

用一个[0,1]随机变量看落到.1, .3, .6, 1中的那个子区间里就模拟出随机取出哪个物体了。关键每次取出后必须重新更新cdf，所以最终时间为O(N^2).

vector<int> pickRandomObjectsByWeight(vector<double>& ws) {
list<INTD> id_w; // list of pair(id, weight)
unordered_map<int, list<INTD>::iterator> pos; // id's position in list
vector<int> res; // object ids stored in returned sequence
// use 1, 2..., N as object's id: O(N)
int id = 1; double totalW = 0.0;
for (auto w:ws) {
id_w.emplace_back(id, w);
pos[id++] = --id_w.end();
totalW += w;
}. more info on 1point3acres.com
// randomly pick an object id by weight: O(N)
int N = ws.size();
while (N-- > 0) {
// create vector of cumulative probability function
double cdf = 0.0;
vector<INTD> id_p = { make_pair(0, cdf) }; // pair of (id, cdf)
for (auto& x:id_w) id_p.emplace_back(x.first, cdf += x.second/totalW);
// randomly pick an object
double randx = rand()/((double)RAND_MAX); // uniform [0, 1] distribution
auto comp = [](INTD a, INTD b) { return a.second < b.second; };
auto idp = lower_bound(id_p.begin(), id_p.end(), make_pair(0, randx), comp);. 鍥磋鎴戜滑@1point 3 acres
// remove the picked object
int id_remove = idp->first; if (id_remove == 0) id_remove = 1;
res.push_back(id_remove); totalW -= pos[id_remove]->second;
id_w.erase(pos[id_remove]); pos.erase(id_remove);
}
return res;
}

每个月你可以去一个国家出差，出差的时候赶上这个国家的节假日，你就可以放假，问在一年的时间里怎么出差能最大化放假的时间。自己设计Country类。输入是一个Country列表，输出是一年里出差去的国家的行程。（这轮面之前就说有两道题，但是不相关，然后我根本没做到第二题哈哈，做完第一题时间就差不多了）

第四轮（国人小哥）：一个int，比如2，转换为bit，前面都是0，只有后面最后两位有个1和0（0000.......00010）表示是2，所以前面那些0占的空间就很浪费。小哥要设计一个protocol（写两个function，一个serialize，一个deserialize），给一个int，然后把这个int转换成另外一种形式，这种形式是一个List<Byte>，Byte总共8位，第一位是0/1，用作flag表示后面还有没有后续的Byte，剩余7位是这个数字记得值。比如输入是2，输出就是一个list<Byte>，里面只包含1个Byte，这个Byte从头到尾是 0|0000010。如果输入是个很大的数(比如他转换为32位是0000..000001000001000000000)，那输出就是list<Byte>，里面包含多个Byte，头几个Byte可能是1|0000000， 1|0000100，最后一个是0|0000010. 好心的面试官给了不少关于位运算的提示，要不就做不完了。

每个面试官感觉都很nice，就是他们会和你以商量问题的方式来面试，所以即使我很渣我也不太紧张。除了最后一轮碰上bit慌了一下。

还有就是很多题的条件是比较开放的，所以可以按照自己怎么方便怎么设计，或者自己对哪个比较熟，就用哪个。

所有题我都是用最普通的方法，没有优化，然后写完代码（能写出来我都谢天谢地，不敢相信自己了）就基本到时间了，然后问问题就结束了，没有follow up，按理来说都是应该有的，而且有加分的。这些题可能本身不是很难，或者我没get到面试官的点，也可能我就没做对，所以才觉得不难，总之，我面完感觉很奇怪。

这道题可以重复去同一个国家，那就只能你这样做了
爆破做法，没测试…不确定所有情况都cover了…写一个函数，获取某一个月中有假日数量最多的国家，这个函数里就便利country列表，然后维护一个max记录哪个国家有最多假期。然后主函数里面就一个for，跑十二个次，获取十二个月每个月假日最多的国家…这十二个返回的国家就是要去的国家

地里有一道高频的题目，是对于每个site而言，下一周能去的site集合是有限的，而不是想去哪就去哪。可能面试官想把这个作为follow up来出？
一。类似给你一个数组，问你某个范围的最大值/和。那我会想到dp 和 segment Tree.
三：像是graph search 。 bfs /dfs

http://www.1point3acres.com/bbs/thread-205525-1-1.html
第一题，五子棋，给一个棋盘状态，判断有没有人赢。
http://stackoverflow.com/questions/22087006/using-arrays-to-detect-a-win-in-a-gomoku-game
第一题就横，竖，斜找有没有5个一样的。

楼主第一题是不是就是 lc上的Design Tic-Tac-Toe, 然后告诉你下棋的row, col, 和player然后返回到底是谁赢?

第二题，五子棋，找到一个没棋子的位置，每个位置概率相同。
第二题把空的位置取出来做成一个object，存在list中，用random取一个

第二题难道是传说中的水塘抽样？

pair<int, int> blank_pos(vector<vector<int>>& board) {
int m = (int)board.size(), n = m ? (int)board[0].size() : 0;
int count = 0, y = -1, x = -1;.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {. 鍥磋鎴戜滑@1point 3 acres
if (board[i][j] != 0) continue;
++count;.鏈枃鍘熷垱鑷�1point3acres璁哄潧
if (count % rand() == 0)
y = i, x = j;
}
}
return {y, x};
}

复制代码

不好意思, rand() % count 写反了

第三题，系统设计题？直接看图吧，我没太看懂题意，没写代码，写了一点思路。主要是用户在点击按钮后计数时间，用户A先点击的话，在53秒，传给服务器，服务器传给其他用户，假设总共需20秒，用户B在52秒（无效）点击的话，等服务器信息传给B，B的无效时间变为33，所以B点击后过了19秒，服务器传给B的时候，有效时间是40秒，那么B点击的有效时间是59秒，然后53和59比较确定谁赢。之后又问有多个用户的时候，服务器怎么设计？又没懂，随便说多线程

其实就是个最大堆？每次从堆顶pop出来最大的，然后这个值应该等于60 - (pre - cur)，最开始pre设置成60, 然后取其中的最小值....如果最小值没到0就每隔60秒reset一次
会有不确定数目的users啊

http://www.1point3acres.com/bbs/thread-174400-1-1.html
给一个函数hasObstacle(Point point, Direction direction)，告诉你在某个point时往某个direction推一个球可否推动（若推得动，表明前方无障碍，若推不动，表明前方有障碍）。
然后给一个start point和一个end point，求出把球从start推到end的最少步数。（题干内容就这些，然后自己定义Point和Direction等）
第二轮：
给一颗普通binary tree，求出其中所有的相同的子树，并返回这些子树的根结点。List<Node> findCommonSubtrees(Node root){
Map<String, List<Node>> map = new HashMap<>();
helper(root, map);
List<Node> ans = new LinkedList<>();
for(String str : map.keySet()){
if(map.get(str).size() >= 2){
ans.addAll(map.get(str));
}
}
return ans;
}

String helper(Node root, Map<String, List<Node>> map){
if(root == null) return "#null";
if(root.left == null && root.right == null) return "#" + Integer.toString(root.val)+"#null#null";
String leftTree = helper(root.left, map);
String rightTree = helper(root.right, map);
String ans = "#" + Integer.toString(root.val) + leftTree + rightTree;
if(!map.containsKey(ans)){
map.put(ans, new LinkedList<>());
}
map.get(ans).add(root);
return ans;
}

feels should be solved in this way. we serialize subtree using preorder, the recursive call returns preorder serialization of subtree. if the serialization are the same, we know they are the same subtree, then return the root itself

class Ans{
Node node;
String serialization;
public Ans(Node node, String serialization){
this.node = node;
this.serialization = serialization;
}
}
boolean haveSameTree(Node root){
Ans ans = helper(root);
return ans.node;
}
Ans helper(Node root){
if(root == null){
return Ans(root, "#null");
}
Ans left = helper(root.left);
Ans right = helper(root.right);
if(left.node == null){
return Ans(right.node, "#" + Integer.toString(root.val) + left.serialization + right.serialization);
}
if(right.node == null){
return Ans(left.node, "#" + Integer.toString(root.val) + left.serialization + right.serialization);
}
if(left.serialization == right.serialization){
return Ans(root, "#" + Integer.toString(root.val) + left.serialization + right.serialization);
}
return return Ans(null, "#" + Integer.toString(root.val) + left.serialization + right.serialization);
}
第四轮：
给一个log file，里面记录两类函数: start(int processId, int startTime)和finish(int processId, int endTime)，分别记录系统调用某个进程的开始时间和结束时间以及该进程的ID
给了2个条件：（1）时间是递增的，（2）对于每个进程，每一个start总有一个对应的finish。
问题是：当遇到一个finish(int proc1, int time1)函数时，如果有排在proc1之前还有进程没有结束的话（i.e., 开始时间在proc1之前的进程），就不打印任何内容；否则打印出所有已经结束的进程，并且按照他们的开始时间顺序打印比如：
-start(1,1)
-start(2,2)
-start(3,3)
-end(2,4)
-end(3,5)
-end(1,6)
遇到end(2,4)和end(3,5)时不打印，因为进程1的开始时间在进程2和进程3之前，直到遇到end(1,6)时，才能打印，打印顺序如下:
1: 1, 6
2: 2, 4
3: 3, 5。
分别是进程ID：开始时间，结束时间。

Round 4: use a priorityqueue and hashmap to implement

class Solution{
class Process{
      public int id;
      public int start;
      public int end;
      public Process(int id, int start, int end){
         this.id = id;
         this.start = start;
         this.end = end;
}
}

class void printFile(String fileName){
Map<Integer, Process> map = new HashMap<>();
PriorityQueue<Process> heap = new PriorityQueue<>(new Comparator<Process>(){
public int compare(Process p1, Process p2){
      return p1.start-p2.start;
}
});
Scanner scanner = new Scanner(new File(fileName));
while(scanner.hasNextLine()){
String line = scanner.nextLine();
//isStart is used to parse the line and check if it's start or end
boolean isStart = line.substring(0, 5).equals("start");
int[] idAndTime = isStart ? line.substring(6, line.length()-2).split(',') : line.substring(3, line.length()-2).split(',');
if(isStart){
map.put(idAndTime[0], new Process(idAndTime[0], idAndTime[1], -1));
heap.offer(map.get(idAndTime[0]));
}else{
map.get(idAndTime[0]).end = idAndTime[1];
while(!heap.isEmpty() && heap.peek().end != -1){
Process temp = heap.poll();
System.out.println(temp.id + ": " + temp.start + ", " + temp.end);
}
}
}
}
}

第五轮：
给一个MxN的board，里面存有一些整数，各整数代表一种颜色，如果是0，则表示该格子没有颜色。相同颜色并且相邻的格子可以组成一个component，求出该board里面最大size的component。题目跟number of islands很类似。
http://www.1point3acres.com/bbs/thread-207346-1-1.html

和html element相关的一个题目。考察的点是图的遍历，要用iterative的方法遍历。
2.
和树相关，一种用来表示黑白图的方法。每个cell有一个value，黑或白，四个child，每个child都是一个cell。3.
经典的decode string
2[ab2[x]] ->abxxabxx, 数字代表重复的次数，括号是可以嵌套的。
4.
很灵活的运用数据结构的题目，具体不记得了。可以用binary search tree来做，但是要改结构。每个node要记住自己左边和右边分别有几个nodes。
5.
leetcode上面的，类似于zigzag iterator，但是包装了一下。

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

http://www.1point3acres.com/bbs/thread-209852-1-1.html
1. 给一些商品的数量K[]和价格P[]，和手里总共有的钱B。要求输出所有把B花完的case。感觉有点像cc150里面那个分硬币的题目，找个那个思路给了recursive的解法，中间磕磕碰碰有几个bug都被指出来，最后一个大bug他提出来，我没反应过来，就这么过去了（takeaway：题一定得上手练啊，看了很多题，只能帮助我知道大致解法，但写起来又不一样了）
2. 还剩10多分钟，给了个test的题目。给一个void sort(float buf[], int n) ，如何写个test函数去测试。没见过这种题，就写了个最傻最天真的版本：把sort后的buf逐一check下是不是下一个小于上一个，如果是就return false。但小哥说信不信我一个反例干到你

1.有一个类似test的题。给我一段stringtranspose的代码，让我看为何无法编译。代码大致如下：

char ** stringtranspose(char ** old){
char** new[3][3];
for(int i=0;i<3;i++). 1point 3acres 璁哄潧
for(int j=0;j<3;j++)-google 1point3acres
new[i][j] = old[j][i];
return new;
}

复制代码

他指出是new没法return，因为new的空间在stack上会被destroyed掉。然后问我c++两种分配内存方式，我太菜只知道malloc。然后之支支吾吾半天我也搞不出来就move on了。
二面1题：原题Line 02应该是"char new[3][3]"吧，不然首先类型就不匹配了。然后这个名字"new"在C++中是keyword，不能用于普通变量名。最后就是返回local variable address的问题了。因为local variable定义在stack上，出了scope以后它的memory就被释放了，所以函数返回的pointer所指向的就是一个corrupted/undefined的address. 其实最后一个并不是“编译”错误（有的ciompiler会给warning），而是使用错误。之前2个倒是真正意义上的“编译错误”。
将Line02改成“char** res = new char*[3];”，然后每个res[j] = new char[3]这样所以空间在heap (dynamic memory)上建立就可以了。

char ** stringtranspose(char ** old) {
char** res = new char*[3];
for (int i = 0; i < 3; i++) res[i] = new char[3];
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
res[i][j] = old[j][i];
return res;
}

2. void writer(vector<string> list, File *file) 和 reader(vector<string> * input, File *file) 直线两个函数，把string array写进文件，然后又读出来。被上一题暴击以后，我已经缴枪了。花了几分钟清楚这题的意图以后，开始给各种好不单纯好不做作的傻X例子，e.g.,用空格隔开。。。。还好大哥脾气好没砸电话，都给我丢反例了。后来终于想到写一个header，把所有string的length以逗号隔开放进去，然后换行开始输出所有string。大哥说行吧。
然后follow up 如果想直接读出第i的string咋办，如果string有成千上万个，我这个方法就不高效了。想不出来求他hint，他表示拒绝说一hint我就都知道了

是标准的File。我后来想到，只要O（1）找到string的开始（header的结束）就可以了，他说是的。时间来不及了，我想到把header的长度放在开头。但脑子想到了，代码写错了（没练手的悲剧）

http://www.1point3acres.com/bbs/thread-194262-1-1.html
1）给一个n大小的list，这个list全是interval，interval是包括首尾的。返回一个同样为n大小的array A，其中A的值是i在这些intervals里出现的次数比如
n= 5
L = [(1, 3), (2, 4)]
返回[0, 1, 2, 2, 1]
follow up是如果区间的end可以无限大怎么办。
int[] getTimes(List<Interval> intervals, int n){
      int[] ans = new int[n];
      List<int[]> events = new ArrayList<>(intervals.size()*2);
      for(Interval i : intervals){
         events.add(new int[]{i.start, i.start, i.end});
         events.add(new int[]{i.end, i.start, i.end});
}
      Collections.sort(events, new Comparator<int[]>(){
public int compare(int[] i1, int[]i2){
if(i1[0] != i2[0]){
return i1[0] - i2[0];
}else{
return i2[1] - i1[1];
}
}
});
int time = events.get(0)[0], index= 0, count = 0, prev = time;
while(index < events.size() && events.get(index)[0] == time){
count++;
index++;
}
ans[time] = count;
while(index < events.size()){
time = events.get(index)[0];
for(int i=prev+1; i<=time-1; i++){
      ans[i] += count;
}
while(index < events.size() && events.get(index)[0] == time && events.get(index)[1] == time){
      index++;
      count++;
}
ans[time] += count;
while(index < events.size() && events.get(index)[0] == time){
index++;
count--;
}
prev = time;
}
return ans;
}

2）
给一个类似以下的输入
www bb cc fffff
如果给出六行空间，greedy会返回这样的
www bb 剩下: 0
cc          剩下: 4
fffff    剩下: 1
平方和的结果是0^2 + 4^2 + 1^2 = 17.

目标是排列以达到最优，最优是平方和最小的时候。比如这题最优解能达到3^2 + 1^2 + 1^2 = 11:
www 剩下: 3
bb cc    剩下: 1
fffff    剩下: 1
假设dp[j]是到第j个词的最优解，对于每个i<=j，如果第i到j个词容纳在一行内，计算cost(i,j)，这里是每个词的平方和，别的地方也有说立方和的, 再加上dp[i-1]。注意i从j开始维护一个sum,j-1,j-2...直到一行容纳不下。并不需要像gfg中那样提前计算并存储所有的lc(i,j)吧

dp[j] = min(cost(i, j)+dp[i-1]) , for every i, if i through j fit one line
http://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/
http://www.1point3acres.com/bbs/thread-206535-1-1.html

第一次电面是一个拒镇旋转的问题，
以及给定一个矩阵判定是否是从N个给定矩阵中的某一个旋转得出的如果这个题这么变一下：给定一个vector<Matrix> smalls, matrix维度为N1 (vector长度为M)。
再给定一个大矩阵Matrix big维度为N2 (N2 > N1)。问smalls中有没有一个是big的子阵(submatrix)。
那么这个题的显然时间上界O(M*N2^2)就不一定是最优的了。
因为光判断一个N1维小矩阵是不是N2维大矩阵的子阵就至少O(N2^2)，
暴力和每个小矩阵单独比较的话就会有浪费（因为小矩阵彼此之间可能有相似之处），
需要将vector按照"Trie"之类思想的预处理一下。这样可以走捷径的原因是固定的大矩阵N2会远远大于N1.
但对于LZ本身这道题就不存在这个问题了

1 给定一个字符串，只有两种字符，左右括号，写一段代码统计有多少种配对方案???
数valid括号：One pass O(N) time complexity and O(1) space complexity.
Note: 每个valid pair都有一个右括号，总的valid pair个数就是数每个')'之前有多少个'(', 然后叠加起来即可。

int numValidPairs(string& s) {
int res = 0, nLeft = 0; // number of '(' up to current index position
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') nLeft++;. 1point 3acres 璁哄潧
else res += nLeft; // current char is ')' which can pair with any previous '('
}. 1point3acres.com/bbs
return res;.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
}

2.从map reduce开始讨论了一些和大数据处理有关的问题

http://www.1point3acres.com/bbs/thread-209659-1-1.html
给一组objects，每个对象2个属性分别是id和父id。要求给这组objects排序保证所有父id都排在id的前面
给的是：1->10, 2->20, 3->30, 10->200, 20->100
排好应该得到：3->30, 10->200, 20->100, 1->10, 2->20
因为10是1的父id，所以10->200一定要在1->10的前面，如果没有父id关系的话就按id排就好了
函数是
List<Object> sortObject(List<Object> objects){}

另外父id一定比id大且给的数组元素不重复

lz当时第一反应就是感觉这是图的题，但是往托普排序上想方向错了，天竺哥也一直憋着，我说了大概托普排序的思路就让我实现，完了再拿出各种case告诉我是错的，还有XXXX没排对。
lz后面发现这题可以用并查集+mergesort解

无论用拓扑还是unionfind，只要保证各个图是一层层按顺序输出就行。
图是一层层按顺序输出就行这个要求就是典型的拓扑排序了呀0.
你跟我犯了一样的问题，前面没问题，后面往res里放的时候，需要每次放入的是所有图里当前最父节点的最小值。所以需要你去比较当前所有ingree为0的节点的id，找到最小的放入答案，然后最小的那个图再继续往下走，继续比较。ls说的minheap是个好方法来实现这个
如果没有父id关系的话就按id排就好了这句话的意思是同一个level的点要按照大小来的意思呀
http://www.1point3acres.com/bbs/thread-205267-1-1.html
题目叙述很简单，就是遍历多叉树，但要先遍历孩子，再遍历当前节点，感觉就是多叉树的POST-ORDER，我记得当时楼主用的RECURSION,但是面试官说不行，说这个会OVERFLOW，然后非要他用ITERATION，但传统的ITERATION也需要用STACK啊，我想那个面试官是不是想说不要用STACK的ITERATION，然后我上网研究了一下MORIS后续遍历，但不知道怎么改成多叉树的形式

http://www.1point3acres.com/bbs/thread-203928-1-1.html
1. String Decompression，把"a2b3c4"->"aabbbcccc"
Follow Up: 输入是个Iterator，输出也是Iterator2. a. 给一个int array，找一个数，左边的和与右边的和相等，O(n)
b. n/4 Popular Element，找Quartile，用binary search
3. LC399，dfs
4. 给一个String，问到"a*b*"的edit distance，O(n^2) -> O(n)/O(n) -> O(n)/O(1)，计数就行了
Follow Up: "a*b*c*"，要求O(n)/O(1)，提示之下用了DP
第一问为例，要将一个长度为n的字符串修改为由i个a在前和j个b在后组成的字符串，i+j=n，i>=0，j>=0，比如
aaaaaabbbbb，输出是0，不用改
babbbbbb，输出是1，把a改成b
aaacaabbbb，输出是1，把c改成a
第一问就是相当于找a和b的分界线，在何处能使修改次数最小
第二问复杂一点，35楼提了一下

edit distance那题你最后说你是用o(n)时间，o（1）空间做的么，DP不是o(1)空间啊
另外*号是跟LC regular expression里一样可以匹配0次或者n次前面那个字符，还是wild card里那样和前面那个字符没关系，*本身可以匹配任意字符串，如果是后者的话是不是就是看给的STRING，第一个是不是a如果是a，就edit distance是1，中间如果有b,c就edit distance就不管，如果没有b,c就edit distance分别+1，其他字符因为有*可以不用管
只存当前的三个数就是O(1)
*号是匹配前边一个字母，题里就是a, b, 和c

两问都可以用dp，第一问还可以先扫一遍如果都是b需要改多少，然后设定一个分界线，认为分界线左边都是a，右边都是b，将分界线从左扫到右，根据上一个位置的修改次数和当前字母得到分界线在当前位置时需要修改的次数，就可以得到最小值。
第二问从最右开始，看当前位置是a，b还是c，就根据前一个位置三种情况的最小值，得到新的位置的最小值，具体关系忘记了，懒得再推一遍了...不过注意一下顺序，先算哪个

第二问用dp，不用开数组，从右向左，每次只需要存三种情况前一位修改次数最小是多少就行了，三种情况就是最终使String符合c*或b*c*或a*b*c*，从右向左扫的时候每一位是a,b,c或者其他，这三种情况的最小值有递推公式
a*代表0-n个a

听说谷歌是如果想法和沟通很好，就算代码写得差一点也可以得到很好的feedback。
另外最后一问的follow up从左往右应该也是一样的吧？用A[i], B[i], C[i]分别表示第i个字符改成a, b, c的minimum edit distance,有
A[i] = A[i-1] + (s[i-1] != 'a')
B[i] = min(A[i-1], B[i-1]) + (s[i-1]!='b'). From 1point 3acres bbs
C[i] = min(A[i-1], B[i-1], C[i-1]) + (s[i-1]!='c')
最后返回A, B, C中最小的。由于recurrence formula中只依赖前一个，所以可以是O(1) space
这个思路不错，这个思路应该也可以用在第一问中吧，就是不知道在面试过程中是不是好说明，B 可以说是第i位为b时，满足a*b*c*的最小编辑距离。C为第i位为c时，满足a*b*c*的最小编辑距离，这样表述可以吗？

http://www.1point3acres.com/bbs/thread-207354-1-1.html
第一轮的interview感觉有点严肃，互动不是很多，问了一个给一个binary tree，但是知道这个tree structure里面有一个edge让它变成不是一个合法的binary tree，找这个edge....这道题本来就不是很严谨啊！来来回回和她讨论condition讨论了蛮久。基本就有两种情况，一种是有loop，一种是某个node有三个children之类的....最后DFS和BFS都写了，又optimize了一下下也没有什么significantly better的结果，各比较了一下利弊。感觉自己从头到尾都蛮晕的，并不是抱很大希望....

第一道是找到一个array of integers的equalibrium point。Equalibruim的定义是左右数字的和各相等。

第二个是给一个sorted array，找most popular element。只要数量超过N/4就算most popular，N是array的size。两道都是写了两三种不同的方法，不断optimize。在轻松愉快的氛围里结束了面试。

http://www.1point3acres.com/bbs/thread-209426-1-1.html
题目不难，只是细节比较模糊，很多东西可以经面试官同意之后自己假设。题目是实现Tab功能，用户输入一个命令的前面部分，按下tab之后，提示用户所有可能的match。直接用trie实现，唯一难点是trie的遍历，要找出所有可能的match

http://www.1point3acres.com/bbs/thread-207690-1-1.html
1. 给个int array，找它subarray（中间indexes连续的那种）里满足 min(array)*2 > max(array)的那些，return最长的subarray（的长度）。

有点像lc239，确实可以用deque，或者就用two pointers标记头尾

第一题可以O(n)? 用min/max queue, 类似two poitners
from collections import deque
class minMaxQueue:
def __init__(self):
      self.minq = deque()
      self.maxq = deque()
      self.q = deque()

def push(self, i):
      self.q.append(i)

      while self.maxq and self.maxq[-1] < i:
         self.maxq.pop()
      self.maxq.append(i)

      while self.minq and self.minq[-1] > i:
         self.minq.pop()
      self.minq.append(i)

def pop(self):
      i = self.q.popleft()

      if self.maxq[0] == i:
         self.maxq.popleft()

      if self.minq[0] == i:
         self.minq.popleft()
      return i

def getMin(self):
      if self.minq:
         return self.minq[0]

def getMax(self):
      if self.maxq:
         return self.maxq[0]

def solve(array):
q = minMaxQueue()
ans = 0
for n in array:
      q.push(n)
      while q.q and q.getMin() * 2 <= q.getMax():
         q.pop()
      ans = max(ans, len(q.q))
return ans

int longest_subarray(vector<int> &nums)
{
int max_len = 0;
int n = nums.size();-google 1point3acres
for (int i = 0; i < n; i++) {. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
int min_num = nums[i];
int max_num = nums[i];. from: 1point3acres.com/bbs
for (int j = i + 1; j < n; j++) {
min_num = min(min_num, nums[j]);
max_num = max(max_num, nums[j]);
if (min_num * 2 > max_num)
max_len = max(max_len, j-i+1);
}
}
return max_len;

我做的是O(n^2)。。二维的dp。。
min(array[i:j+1]) 其实是等于 min(min(array[i:j]), array[j]). max的情况同理。所以可以用O(1)时间填充一个二维dp matrix的一个cell。。你要存的是i th 到 j th 的subarray的min和max，一行一行从对角元素填充。还可以发现这个递归关系只用到了前一个的信息，所以能优化到O(1)空间复杂度。。
楼主这道题能不能直接nested for loop做呢？固定起始位置，然后一直往后找，更新min，max就好了？然后同时update最大长度？是不是也是O（n^2)？
对 iterative就行了。。当时一开始是recursive，后来改成iterative了。。

第一题DP我写了一个2D版本的，就是dp[j]存着从i到j的最大值和最小值。
然后优化空间就是这二维数组里面的i其实都没有用直接去掉就行了哈

def max_subarray(nums):. more info on 1point3acres.com

n = len(nums)

dp = [[{"min":float("inf"), "max":-float("inf")} for i in range(n)] for j in range(n)]

ans = -1

for i in range(n):

      dp[i][i]["min"] = nums[i]

      dp[i][i]["max"] = nums[i]

for i in range(n):

      for j in range(i+1,n):

         dp[i][j]["min"] = min(dp[i][j-1]["min"], nums[j]). from: 1point3acres.com/bbs

         dp[i][j]["max"] = max(dp[i][j-1]["max"], nums[j])

         min_tmp = dp[i][j]["min"]

         max_tmp = dp[i][j]["max"]. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴

         if dp[i][j]["min"] != float("inf") and min_tmp*2 > max_tmp:



            ans = max(ans, j-i+1)



return ans.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�

2. 一些tree的简单问题。。比如，给个tree，还有should_delete()，删掉某些node 把这个tree 分解成若干个tree，返回各个root。
写个treenode class，判断两个tree是否“logically the same”, 之类的很基础。。然后那个delete_node题, should_delete() 输入是一个tree node，输出boolean，可以判断是否要删这个node，然后让你把一个tree 分解：删掉该删的node，返回一个root的list

如果这个node该被删掉，你得记得把它的parent的对应的child(left或right)设为NULL。我不太明白为啥有 if (orig_root == root) roots.push_back(root); 如果一开始的root本身就该被删掉的话这样会把root放进roots里的。其实delete_nodes(,,)第三个参数是第二个参数的parent，我一开始搞了个dummy node，作为root的parent，这样就少点麻烦

反正一开始的root算是个corner case，我是递归前先处理了
我上面的code是post-order traversal的，如果root本身要被删掉，就会进入if(should_delete(root))，也就是不会执行到if (orig_root == root) ...，

当递归回到原root的时候，如果它没有被删掉，就要放进vector roots里

TreeNode *delete_nodes(vector<TreeNode *> &roots, TreeNode *orig_root, TreeNode *root)
{
if (!root)
return NULL;
root->left = delete_nodes(roots, orig_root, root->left);
root->right = delete_nodes(roots, orig_root, root->right);
if (should_delete(root)) {
if (root->left)
roots.push_back(root->left);
if (root->right)
roots.push_back(root->right);
return NULL;
}
if (orig_root == root)
roots.push_back(root);
return root;
}

第一个是个中国人，一开始闲聊了好久（大概10～15min？）简历上project还有为啥不想读phd啦之类的。。（他说他当年也没有接着读博可能有点共鸣）然后做题。。当时一开始挺紧张的，所以就先brute force了。。recursive那种，写着写着觉得应该dp，他说是的，然后就加了个hashtable。然后改成了iterative的那种，用2d array存中间结果。后来他说可以改进一下memory，发现其实只需要存O(1)的信息即可。没问问题（没时间了），直接结束。。说实话挺慌的，当时有点小磕绊，还好国人照顾些，有很多hint和交流，人也特别nice。

第二个是个美国人（应该是白人男），他貌似感冒了，全程除了说题几乎没怎么出声，我就一直边码边讲以免场面过冷。。还好题很基础，他也没准备很多问题，最后一看时间还有点干脆让写几个test case。。少有的一些交流也还算顺畅。

如果要总结一些经验的话就是，千万不要冷场吧。。边码边讲说思路，这样人家一听觉得你思路不对可以避免走弯路。说实话这两轮都挺幸运的，遇到的面试官都很nice
http://www.1point3acres.com/bbs/thread-209920-1-1.html
十月底面的昂赛特，李特扣得漆拾酒，武拾溜（变体，没面好），伞把六。还有给一个list of double linked list，求连在一起的list 的团数，应该也是lc 有一题的变体，做过忘了哪题。
还有一题忘了，也是medium 水平dfs解决的
http://www.1point3acres.com/bbs/thread-192582-1-1.html
给一个tree，每一个treeNode多2个指针pre next但是是空的。要求按inorder的顺序把指针连起来。
followup是怎么实现insert方法。还问了时间复杂度和空间复杂度。
就是问你怎么维护链表的顺序。。。

void convert(TreeNode* n, TreeNode* &last){
if(n) {.
convert(n->left, last);
if(last){
last->next = n;
n->prev = last;
}
last = n;
convert(n->right, last);
}
}

http://www.1point3acres.com/bbs/thread-205034-1-1.html
第一轮：算法
给出 wifi 发射点的覆盖距离，和一些 1D 的房子坐标，求需最少要几个 wifi 发射点（one pass 就能解出来）
follow up：给出最多可以安装的发射点的数量，求发射点最覆盖距离（用房子总长除以发射点数量得到最大覆盖距离，用二分法套到第一个解写出来的函数里不断尝试从1到最大覆盖）
第二轮：

第一题：上了一段写的很烂的代码，让你简化，把一些写的烂的地方变成可以理解的。这个就是考大家平时写代码的习惯，比如不该用 loop 的时候别用 loop，可以用 if else 的时候别用 swift。
第二题：求两个 string 的 common prefix（从头开始比较即可）
follow up：怎么优化（用二分法）

第三轮：
考察简单的用 JS 处理数据的思路。说给一个网页，跟一个 getHash 函数，求返回页面里所的 img，要求用 hash 去重。就用简单的 DOM API，中间需要用到 promise（或者 callback）来获取 image data 给 getHash 用来计算 hash。用什么不重要，主要看你习不习惯 JS 里面的 async flow control。

第四轮：

要求实现 querySelectorAll。没思路，没答好，感觉应该看看 jQuery 源代码就没问题。

第五轮：

Decode string，输入 2[ab]2[c3[d]]，要求输出 ababcdddcddd。只考虑重复的部分是 letter 的情况。但是就像大家已经看到的，[ ] 是可以套多层的。用 stack 或者 recursion 都可以做。懒得设计 stack 怎么存了，就用了 recursion。

感觉谷歌对细节的要求很高。出题做起来很容易在小地方犯错误导致出不来。偏算法。面试官不太爱说话，场面有时候会很尴尬……也不知道是对了还是错了。还没出结果，答案不能用来参考嘿嘿

http://www.1point3acres.com/bbs/thread-198684-1-1.html
第一轮: Print BST Kth level alternatively
http://massivealgorithms.blogspot.com/2016/12/print-bst-kth-level-alternatively.html比如  5 ,k = 2的话，打印结果1 8 3 6
/  \
2 7
  / \  / \
  1 3 6  8
比如  5 ,k = 2的话，打印结果3 8 6
/  \
2 7
\  / \
3 6  8

第一题从空间complexity来说确实是他的小。stack就是前序遍历非递归算法那个stack，栈内元素照理说是不超过树的高度的k。但是BFS需要维护每层所有元素，空间上是2^k。
另外对DFS来说假设树是BST是有意义的。因为两个指针有可能会相互错过对方。BST可以用来判断终止条件（左指针指向的元素<右指针）。

第一题用dfs的话space complexity只有O(k)

第一轮确实是应该双向DFS，我当时把自己绕晕了

第k层的node数量不是o(k), 是2^(k-1)个

第二轮： Merge Two Sorted Array
一个白人大叔+亚洲shadow。
因为第一轮多耽误了些时间，大叔就问了一个简单的问题。然后跟我一直聊天。

第三轮： LeetCode No.42 Trapping Rain Water当时突然忘了Two Pointers的做法，用的stack的做法。代码写得不够简洁。感觉面试官随便抽了一道题来的，我阐述完stack的做法后，他说挺好的，也没有提示说有没有更简洁的做法就让我写代码了。

第四轮:
http://massivealgorithms.blogspot.com/2016/08/google-manager-peer-problem.html
实现一个class支持三个API:
peer A, B
manager A, B
isManager A, B

比如
peer Tim, Bill
peer Bill, Mike
manager Lucy, Tim
isManager Lucy, Tim -> True
isManager Lucy, Mike -> True
manager Amy, Lucy
isManager Amy, Bill -> True

具体的来说，如果给两个人添加peer关系，他们就成为一个peer group。
如果其中一个人已经在某个peer group，另一个人没有peer group，就把后者添加到前者的peer group。
每个peer group都只有一个manager。
所以不会出现
peer Tim, Bill
manager Lucy, Tim
manager Amy, Bill
这种情况
但是, 如果两个人已经在不同的peer groups，这种情况call peer API会返回错误。manager Lucy, Tim
manager Amy, Bill
peer Tim, Bill -> error
每个manager可以有自己的peers以及manager。
每个manager的manager也是其下属的manager。
我觉得可以用类似union-find的思路来做
第四轮可以用trie来代替hash table来节省空间，面试时也忘了提了

这轮的问题属于比较开放性的，我觉得思路不难，但是做起来比较繁琐（或者我的思路比较繁琐，有更好的思路我没有想到）。
最关键的是，我一开始没有考虑好所有的情况，写到peer function一半时，发现有所遗漏，又开始打补丁。总体上我把我的思路阐明给了面试官，他也觉得没问题，但是代码并没有写完就到时间了。

bool peer(string p1, string p2) {
auto it1 = p_to_m_.find(p1);
auto it2 = p_to_m_.find(p2);
//if both peers show up first time, assign a dummy manager to them.1point3acres缃�
if (it1 == p_to_m_.end() && it2 == p_to_m_.end()) {
employee* dummy_m = new employee();. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
p_to_m_[p1] = dummy_m;
p_to_m_[p2] = dummy_m;
m_to_p_[dummy_m].push_back(p1);. 1point 3acres 璁哄潧
m_to_p_[dummy_m].push_back(p2);
return true;
}
if (it1 == p_to_m_.end()) {
auto m = p_to_m_[p1];
p_to_m_[p2] = m;.鏈枃鍘熷垱鑷�1point3acres璁哄潧
m_to_p_[m].push_back(p1);. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
return true;
}
if (it2 == p_to_m_.end()) {
auto m = p_to_m_[p2];
p_to_m_[p1] = m;
m_to_p_[m].push_back(p2);
return true;
}
//if both peers showed up before and have dummy managers, merge their peer groups
if (it1.second->name == "" && it2.second->name == "") {
auto m1 = it1.second;
auto m2 = it2.second;
for (auto& p : m_to_p_[m2]) {
p_to_m_[p] = m1;
m_to_p_[m1].push_back(p); 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
}. 鍥磋鎴戜滑@1point 3 acres
m_to_p_.erase(it2);
delete m2;
}. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
//if both peers showed up before and p1 has dummy managers, merge their peer groups
...
//if both peers showed up before and p2 has dummy managers, merge their peer groups
...
//if both peers showed up before and have different real managers, return false
...
}
. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
void manager(string m, string p) {
... . Waral 鍗氬鏈夋洿澶氭枃绔�,
}
bool isManager(string m, string p) {
auto it = p_to_m_.find(p);
while (it != p_to_m_.end()) {. more info on 1point3acres.com
if (it.second->name == m) {
return true;
}
it = p_to_m_.find(it.second->name);
}
return false;
}
private:
struct employee {
string name = "";
} unordered_map<string, employee*> p_to_m_;
unordered_map<employee*, vector<string>> m_to_p_;
}

第五轮：
也是一个比较开放性的问题。
先问我还记不记得vector dot product。
然后说用什么数据结构表示sparse vector好，并写一个function返回两个sparse vectors的dot product。
我就想用vector<pair<int, int>>存，记录value和其原本的index。
比如[0, 0, 0, 3, 4, 0, 0, 5]就是[(3, 2), (4, 3), (5, 7)]。
然后dot product function写了一段类似merge two sorted array的代码。 time complexity为O(s1+s2)
面试官又问如果一个vector特别大，另一个特别小咋办。
我说可以用小的在大的上做binary search。time complexity为min(s1,s2)*log(max(s1,s2))。
其实问到这里，应该很容易想到用hash table来解： unordered_map<int, int> //key:original index, value:value。time complexity为O(min(s1, s2))
我之所以没想到，一是脑子抽风，二是我觉得用hash table会破化原本index的顺序。但对于做dot product来说，我们根本不需要原本的顺序，只要知道两个vector有哪些相同的indexes就好了。
而且面试官也没有说要再把我们的数据结构还原成sparse vector。赖我自己没有精确的理解面试官的意图。
然后面试官又问我如果是matrix的话，怎么表示。我这个时候又特别跳的说不知道可不可以用quardTtree。面试官微笑的说，因垂丝汀，用quardTree的话，space complexity是什么？我，。。。
不过也没有过多的询问我，最后让我用别的数据结构表示。我就告诉面试官类似的思路，不过是two d array。

vector product 如果一个特别大一个特别小，那只要把小的算了就行了吧。。。反正其余的为0，大的后面都不用算了

但还是面试经历太少，自己有点儿跳，板书也有点儿慢。

http://www.1point3acres.com/bbs/thread-206950-1-1.html
第二题：input(int A, int B, Tree T),  return int
给一个binary search tree，返回满足范围是[A,B]的最大subtree的size（node个数）
比如［A,B］= [10,30]
Tree:
            15
   12          20
10    13 18    31
返回3，因为根为12的子树（10，12，13）是满足范围的size最大子树。
这题我的解法是新建一个Result类包含了subtree的size以及是否满足范围的boolean，用递归divide and conqur不停返回左右子树的Result类以进行判断。

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

找工作基本结束，发面经攒下人品吧，细节就不说太细了，皮子堡上周面的，还没结果，希望不大。不过应该也不去他家了吧。
感觉从面经来看皮子堡难度相对弯曲简单一些，但因此要求可能也会比较多，简单题写完dfs，写stack版，写bfs版。。。
刷题时候最好各种方法都学一下
（但是感觉用stack实现dfs确实蛮有实际意义的。。。虽然感觉工作中。。maybe能遇到吧）

1. 给棵树，深度遍历形XML，注意用栈方法如何实现的吧（用个map之类的）

2. 地图找最近的车，以为药我写广搜，后来发现只是想让我把矩阵表示的地图表示成node和边的形式，具体怎么玩，完全取决于你自己的设计。。

3. 二分搜索一个已拍緒叔祖里初现次数大于1/4的

4. 设计一个扫累的游戏棋牌，然后实现扫雷功能，反正就是深搜加广搜

http://www.1point3acres.com/bbs/thread-210663-1-1.html
给定一个数字，把相邻的两个数字求和取平均值并代替原有的两个数字，从所有可能性中选出最大的可能举个例子， 635 可以有以下两种可能：
(i) (6+3)/2 = 4.5=> 5 用5代替6和3 最后数字变成 55
(ii) (3+5)/2 = 4 用4代替3和5 最后数字变成 64
最后应该返回 64.

这道题由于题目给的function signature 里 input 和output 都是int，所以我答题的时候一直用mod 来找需要取代那个两个数字
其实最简单的办法就是把int 转化成string，然后用string 来操作，最后把string形式的整数转化为int形式，然后再返回。

第二道题和leetcode 388 的find longest file path。只不过最后只要求找到图片类的文件名。
（只需要在leetcode 388 答案基础上，加上一个if 条件句来判断后缀是不是 jpg png 即可
https://www.glassdoor.com/Interview/-Three-coke-machines-Each-one-has-two-values-min-and-max-which-means-if-you-get-coke-from-this-machine-it-will-load-you-a-QTN_272568.htm

Three coke machines. Each one has two values min & max
, which means if you get coke from this machine it will load you a random volume in the range [min, max]. Given a cup size n and minimum soda volume m, show if it's possible to make it from these machines.

- dfs

http://www.1point3acres.com/bbs/thread-210657-1-1.html
1. 一列int输出mode和average
2.给两个str，输出在字典里的先后顺序
3.LC297
http://massivealgorithms.blogspot.com/2015/10/serialize-and-deserialize-binary-tree.html

http://www.1point3acres.com/bbs/thread-210030-1-1.html
第一题，给一堆有向边，[1,2], [2,1],[3,4]这样，找到有多少是reciprocal的。给的例子的话就是1.因为1,2两个点有双向的边。把edge先排序，[1,2] => [1,2], [2,1] => [1,2]，然后放到hashmap里，最后返回value=2的key的个数。
第三题，第一题如果边超多，怎么处理。用 (edge[0] + edge[1]) % N_MACHINE，分布到每台机器上做。

第二题，给一个2d矩阵，每个位置有值，
1 1 2 2
0 0 2 0

这样，给一个i，j坐标，比如[0,2] (左上是0，0)，计算周长。周长是一个connected component，里面所有的值都等于[0,2]的值。这个例子就是那三个2，然后周长是8. 1的话就是俩1，周长6.
保持一个visited的matrix，访问一个点的时候，如果这个点==value[j]，那么先记下来最多给周长加4，然后看当前点上下左右是不是访问过了，如果访问过了，每个访问过的点往总周长-1，然后当前点能贡献的周长也减1.查看过上下左右之后，把剩下的能贡献的周长加进去。

.鏈枃鍘熷垱鑷�1point3acres璁哄潧http://www.1point3acres.com/bbs/thread-210240-1-1.html
给你一个一维array，标明一个区域内的山峦起伏（比如0位置上是1就代表这个地方的地面高度为1），然后再给你一个int 代表海平面（比如说这个数是4的话就代表海平面高度是4，因此之前讲的高度为3的地面实际就相当于海拔高度-3）。这样图中就会生成几个连续的水体，如图：

求：将图中几个连续的水体各自的大小记下来，并return为一个array。

第一道题只需要把array走一边，然后用几个变量顺着记一下就可以了。

然后面试官讲这道题follow up了一下，说有可能在某个地方，大洋底部，可能会有一个drain hole，会抽干周围所有的水（假设那个地方就是一个吸水的黑洞）。同样，让你把连续水体的size生成并且return回来。如图：

这个第二道题最后思路是这样，建立一个array写sea_level，这样海平面不是一个固定值而是一个随位置不一样的数。initialize 海平面为那个固定值，然后根据每一个drain hole把海平面抽到适当的位置，然后再把类似第一题的走一遍的写法重新跑一遍。
第一轮第二个那个follow up的思路我是想说这样的：首先有一个sea_level_array = [5,5,5,5,5,5,5,5,5,5,5]，然后在根据底下的黑洞来防水，最后形成一个sea_level_array = [5,5,4,4,3,2,0,3,4,5,5]，然后再套用第一题

我觉得第一题 followup 的话可不可以这么做,扫那个terrain 的 vector, 遇到-1就把海平面设为0然后左右扫,遇到的山如果比当前海平面高就把山当做当前海平面,直到遇到和初始海平面一样高的山停下,因为水不会漫过去.所以第二题给的那个 [1,5,1,4,3,2,-1,3,4,5,6] 得出的海平面就会就会变成[5,5,4,4,3,2,0,3,4,5,5]然后用第一题的算法根据新的海平面 vector 跑一边.

基本上是这样。只是有一点关于复杂度的问题：如果你左右扫到了另外一个黑洞，就不要再继续扫了，这样的话可以把时间复杂度控制在O(n)

Q1.Write a function: given a vector of numbers, find out the 2 smallestelements.

基本上来说第一题就是找一串数当中最小的两个。

只要控制好condition就可以了，不多解释。

Q2.Moving Window Average

{1, 2, 3 ,4 ,5…}

Givenwindow parameter 3, {1, 1.5, 2, (2+3+4/3,...}

solutionsol(3);

sol.GetValue(1);-> 1

sol.GetValue(2);-> 1.5

sol.GetValue(3);-> 2

第二题地里面以前出现过，让你写一个class，其中的GetValue() function返回从这个往前k次call的平均数。用类似rotated array的方法即可做。

http://www.1point3acres.com/bbs/thread-210172-1-1.html
11月1号第一次面试，貌似是一个美国大哥。先让我聊了聊实习的project，然后上题目，第一题是给一个String[] of integer和int k(subset的大小), 比如[9,15,3,14]和3, return一个subset，使得subset里面的最大值减最小值是所有subset里面最小的。所以这个例子返回[9,14,15], subset里面的数字不用按照input里的顺序。
请问这题有排序以外的做法吗?

排序完之后第 i 个元素直接和第 k+i-1 个元素比较一下就成了吧

第二题是Leetcode reconstruct itinerary的简单版本。觉得自己答得还不错，结果被通知加面。

第一题让自己定义一个double linked list，node的value是String. 然后写一个function, 给一个head和一个Set<String>, remove list里面value等于set里word的node。
第二题是BST，给一个low bound和high bound, return list of nodes，这些nodes的值在low bound和high bound之间。用iterative和recursion两种方法写

http://www.1point3acres.com/bbs/thread-210211-1-1.html
Problem：一个矩阵，支持两个操作，update一个格子，range query一个子矩阵
答：我经验比较少，直接写了二维树状数组，后来在网上查发现其他有人碰到过这个题，挂在面试官完全不知道树状数组这个结构，有些庆幸我的面试官姐姐很了解
然后让我过了个简单例子，分析了下复杂度O(logM * logN)
Follow up： query多，update少，返回去写了个sum的方法，O(MN) update， O(1) query
写完两题剩了10分钟，聊了聊天就结束了，临走时还祝我good luck on my second interview好暖

3. 听起来是个native的姐姐，也迟到了5分钟左右
Problem：有两个string，一个比另外一个多一个char，其他都一样，如"hello"和"hepllo"，要找出这个char答：简单的一次扫描，一开始忘了考虑这个char在字符串末尾，面试官让我自己出了个数据发现了这个bug，改了
Follow up: 我在写第一个的时候念叨了句好像可以binary search，面试官让我详细思考下，我想了下发现要no consecutive same character才行，他让我描述了下做法
Follow up2: 如果要检查两个字符串是否满足Problem描述的关系要怎么做，我说了找出第一个不同后继续扫描，他让我写了代码Follow up3: 如果可以打乱顺序怎么解，如"hello"和"lelloh"，我说用bucket记录下出现次数，他让我写了
Follow up4: 如果字典太大，用bucket开销太大怎么办，我说用sort再用follow up2里的方法，他没让我写代码Follow up5: 如果不能改变字符串怎么办？我想了30秒想不出很好的方法，他说想不到的话ok，我说我唯一的思路就是brute force一一匹配，开销是O(N^2)time，O(N)space，他没表态（不知道这里有没有更好的方法）
最后他范围follow up4问我sort方法，包括快排worst case，以及稳定的NlogN方法（我说heapsort），然后我嘴贱地说merge sort，他问我空间复杂度，我一想发现需要额外的NlogN space赶紧纠正。

最后一题是想让用xor吧？
精妙！不过xor没办法验证invalidation吧
http://www.1point3acres.com/bbs/thread-210743-1-1.html
1. 給你一個 m x n 的 grid，上面只有整數 1 和 0，其中 1 代表 pixel，0 代表空白，要你找所有的 lonely pixel (一個 pixel 在同行或同列上沒有其他 pixel) 的座標。
時間複雜度要求: O(m*n)
舉個例子：
A 3 x 3 grid:

100
010
101

在 (0, 0) 那個 1 因為在第 0 行有其他 1，所以他不是 lonely
在 (1, 1) 那個 1 因為同行同列沒有其他 1，所以他是 lonely
以此類推。

我是用兩個 array 存每個 row 和 col 的 1 的數量，如果大於 1 就全部不要，反之就要。
- follow up = when the char can be anything
2.
1. Find the last index of target from a sorted array.
Ex: [1, 2, 2, 2, 2, 4], target = 2, return 4
用 binary search

2. Detect cycle in direcyed graph.
用 topological sort
http://www.1point3acres.com/bbs/thread-205819-1-1.html
两道题目，第一道题目是给出一个数字，然后用两个相邻的digits的roound up 的average对replace 原来的两位digits,这样形成一个新的数字，求出所有这种新的数字的最大值，第二道是给出一个描述文件的路径的字符串，然后求出到image file的最长路径，这里不包括file本身的字符。建议最好坐下demo练练手
http://www.1point3acres.com/bbs/thread-210772-1-1.html
GG第一题就是给个数组，让你输出各种排列组合，简单DFS暴力搜索解决。
第二题给你一个从文件读数据的API(offset, bytestoread)，实现一个新的带buffer的API，这个API会多次调用，每次读的数据可以是文件中任意长度连续的一段，内存充足够用

这题扯了差不多十分钟才弄懂面试官的意思。至于用什么数据结构作buffer，写代码时从数组到列表再到双向队列改了好几遍，居然一直懵逼没想到用hashmap，小哥都不耐烦了，幸好在最后一刻还是说出了要用hashmap，然后时间到。明明这么水的题，才勉强做两个，而且第二题代码最后没写完，挂定了。。。
补充下第二题吧，就是给个API，从给定offset开始读bytestoread长度的数据。实现buffer型API让对同一文件多次读取效率提高（每次读也是从给定offset开始读给定长度的数据）

第二题的思路：假设每次读的数据长度是n，然后hashmap的<key, value> = <index, buf> index = 0, n, 2*n, ...
然后以后每次从 x 处读len的数据，只需要取 hashmap.get(x / n) 中 x % n 开始的数据，如果 x % n != 0 则需要再加上 hashmap.get(x / n + 1) 中 0 ～ x % n的数据

大概就是这个意思，但每次读的长度和位置都不定，就用map<index,char>以字符为单位buffer就行了，题不难就是面试的时候费了好半天劲才明白什么意思

http://www.1point3acres.com/bbs/thread-210789-1-1.html
第一轮：美国白人大叔，上来先寒暄两句，问了最喜欢的programming language是什么，还有这个language的优缺点，这部分算是warm up，接下来进入做题阶段。
第一道题是一道简单的关于tree traversal的题，给定一个interval和BST，output出所有在interval里面的数值，比如给定interval是[1,5]，BST包含[1,4,7]，则输出就是[1,4]。因为是BST，每次在traverse到node判断一下是下一步是左树，右树还是左右都要traverse，用recursive的方法check就ok。写完code大概还有20min吧，

又出了第二道。给定四个二维坐标，判断这四个点是否能组成一个正方形。这题在跑test case的时候意识到出现点小问题，没时间改了，就跟面试官说了思路。
http://massivealgorithms.blogspot.com/2016/12/hdu-5365-run-bestcoder-round-50div1-div2.html

第二轮：阿三面试官，不苟言笑，特别严肃。。问了简化版LC128，只是consecutive seq必须是adjacent element组成的

又问了LC298，这两道题都是说思路，看我思路正确，都没让写code。接下来把LC298变化一下，seq不一定要从parent node到children node，还可以从child node -> parent node -> child node，问怎么办，楼主说可以每次返回两个值，即current seq最大值，和current seq最小值，对于current node，比较左右孩子的返回值，看是否能讲左右最长sequence连起来。这部分写了code，最后还剩一点时间，问了complexity，和如果有在distributed setting里面怎么shard DAG来完成上述算法。

第三轮：美国人，LC158。楼主最开始没有考虑到read multiple times。。然后经面试官提示改对的。
http://massivealgorithms.blogspot.com/2014/12/leetcode-read-n-characters-given-read4_4.html

第四轮：也是个美国人，经典题LC139，用dp方法写的，写完被问为什么不用DFS，讨论一下DFS worst case和dp比较，最后还剩15min左右，就各种闲聊
http://massivealgorithms.blogspot.com/2015/09/leetcode-word-break-java.html

总结下来，觉得狗家的面试，主要还是要和面试官沟通，每次问的问题其实都是提示信息。他家的题题设会故意很vague，注意多和面试官clarify一下！
除了stack overflow的问题外，举了个DFS的worst case，证明了DFS其实是exponential runtime，而dp是O(n^2)。

http://www.1point3acres.com/bbs/thread-208432-1-1.html
我抽中的变形是第一个是round up
第二个是求最长的含图片的文件夹的路径（不用算上图片的）
http://www.1point3acres.com/bbs/thread-161349-1-1.html
这是一个为期1年的项目，前3个月，上课，有理论课，也有课教你使用google内部的各种工具，反正培训3个月。之后9个月，每4个半月跟着一个team做project。
工资似乎是介于实习生跟全职之间，可能有少量其他的，应该没有股票跟h1b之类的。
转正的机会有2次（目前而言）：
1. 第一个project做完，2轮面试加team feedback
2. 第二个project做完，不需要面试，只要team feedback

据我的面试官所说，他就是转正的，去年大概90%转正了。

电面题目就不说了，一个简单题加一些follow up，有些东西我都懒得写，不过面试官非要我写出来。因为我面SETI都跪了，所以难度应该是比SETI还低，大家可想而知。
http://www.1point3acres.com/bbs/thread-211121-1-1.html
题目从没见过，粘在下面了，各位自己看。上来读完题以后根本不明白他要我干什么，用了两个例子跟他确认好以后，感觉用queue很简单的就能做出来，但是显然不是他想要的。先写了代码，然后他问我有没有听说过circular buffer，这你妈日了狗，我上哪知道这个去。然后他就开始给我讲这个用circular buffer怎么做，最后follow up，问你知不知道constructor前面的explicit 是什么意思。日了狗了。

Linear regression
The system is receiving pairs of inputs, (xi, yi), at a relatively high rate, e.g. one pair every 10 millisecond, and we like to model the relation between xi and yi. A linear model needs to be fitted over last N pairs. For each input pair (xi, yi), estimate bi as a model for y = b x  over the last N pairs, (xi-k, yi-k), k = 0,..., N-1.

Hint: Try to recognize a module that can be used for computing different terms. Implement that, and use it within your answer.

b =(1/N j=1Nxjyj)  -  x  y(1/N j=1Nxj2 ) -  x2

x=1Nj=1Nxj       y=1Nj=1Nyj

Class MovingLinearRegressor {
public:
  explicit MovingLinearRegressor(int N);

  // Returns |b|, for every new pair.
  float Update(float new_x, float new_y) ;
};

( , ), ( , ), ( , ), …, ( , ), ( , ), ( , )
                     <------------------
                        Last N pairs.

考点是circular buffer
Circular array我店面和onsite都考了还是挺重要的

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

电面1：316. Remove Duplicate Letters我是暴力解的吭哧吭哧写到最后才大概写出来，没有run，赶脚面试官不是很开心=。=

电面2：
找一个array所有有可能的sum，比如{2,3,4}2+3 = 5
2+4 = 6
3+4 = 7
2+3+4 = 9
用dfs写的半个小时不到写完了，中间有个bug卡了半天 sigh
而且神奇的是让我自己打开eclipse来试着跑程序。。破电脑开程序又开了一个世纪= =。。
电面2的返回数组int[]

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

要我自我介绍了下，然后问了最近做的project，然后面试的小姐姐自我介绍了下，说了她大概在干嘛。然后就问了几个问题，最后的10min 就是q&a。整个过程非常的友好。我是个渣渣小硕，反应迟钝然后计算能力渣。面试官一直在我懵逼的时候给我hint。面完后觉得题目很简单，但面的时候一直都是懵逼状态。

1. bayes thm. 算p(disease | positive)

2. 3 个温度计前两个var ＝1 最后一个 var ＝2，怎么测量oven温度。如果最后一个var ＝0.05 呢？

3. 下雨的概率是p，cost function：＝k 如果被淋湿，＝2 带了伞没下雨，＝1 带了伞下雨。怎么决定带不带伞。

http://www.1point3acres.com/bbs/thread-172478-1-1.html
String 求峰值你就每个都比吗？感觉应该有更好的办法把？

比如 1115552244666

1后面是 5 ，那么去掉 1 就是一个好的选择，
5后面是 2，那么去掉 2 就是一个不好的选择，

left to right， find the first good choice, or the last bad choice.

http://www.1point3acres.com/bbs/thread-209185-1-1.html
第一轮：讨论project experience，然后给了一道题目，给定数组A，求数组B，满足b = A所有元素相乘除了a，不让使用除法，问怎么办。
http://massivealgorithms.blogspot.com/2015/09/leetcode-product-of-array-except-self.html

第二轮：给定数组A，和k，求数组B，满足b=a*a[i+1]*...*a[i+k-1]，同样不让使用除法。不知道这个是原题不，反正我也没见过。。。按部就班想，开始暴力算法，O(n*k)，他问能不能优化，卡了，想了一阵，好像O(nlogk)?他也啥话没说，然后我慢慢，卡卡的写完了代码，后面还发现了bug，写的不很顺。
具体想法就是，按照二进制进行优化，如果K=3=0b(11)，那么创造两个数组A1=[A,B,C,D,E,F,G], A2 = [AB, BC, CD, DE, EF, FG]，组合产生[A*BC, B*CD, C*DE, E*FG]

我们有A1=[A,B,C,D,E,F,G,H,I,J], 根据A1，可以有A2=[AB, BC, CD, DE, EF, FG,GH,HI,IJ], 根据A2可以有A3=[ABCD,BCDE,CDEF,DEFG,EFGH,FGHI,GHIJ],然后可以有A4=[ABCDEFGH, BCDEFGHI, CDEFGHIJ] ... 依此类推，就像二进制1，2，4，8，16，有了这些，我们就可以随便产色任意组合，比如说K=5=0b(101)，所以结果就是A*BCDE, B*CDEF, C*DEFG, D*EFGH，所以复杂度就降为nlog(k)了。

就是你按照二进制拆分K，然后preprocess一下，准备好二进制组合方式组合出结果。比如K=5=0b(101)，所以结果就是A*BCDE, B*CDEF, C*DEFG, D*EFGH，所以复杂度就降为nlog(k)了

楼主preprocess 的结果是啥？101组合方式为啥就得到最后的结果了？
我觉得这也可以用TOP-DOWN 的backtracking + memoization
bottom-up 的dp （如下），感觉计算了很多多余的值
dp[i][k] = a[i]*…*a[i+k-1]
dp[i][k] = dp[i][k/2] * dp[i+k/2][k-k/2]
top-down 估计会更快。

http://www.1point3acres.com/bbs/thread-199569-1-1.html
http://massivealgorithms.blogspot.com/2015/09/leetcode-find-duplicate-number-eason-liu.html

输入是一个字符串数组，一个int数组，输入的字符串数组是另外一个字符串数组通过int数组变换得到的，int数组的值代表的是原来这位置上的字符串经过变换后的坐标，然后输出是求变换之前的字符串数组，要求用线性时间，o(1)额外空间

打个比方，比如一个字符串数组是"cat", "rabbit","dog", "mouse"，int数组给的2,0,3,1，意思是string数组第0个词是cat，它本来的位置是在哪呢，我们要看int数组，int数组的0在index 1上，所以说cat之前应该是1号位的，同理rabbit在string数组的1号位，而index数组3号位的值是1，说明rabbit这个词之前应该在3号位上的，依次类推，所以变换前的字符串数组应该是 dog, cat, mouse, rabbit

再打个比方，如果输入是Cat mouse dog rabbit和2,0,1,3，输出也会是dog, cat, mouse, rabbit
再打个比方，如果输入是Cat mouse dog rabbit, tiger, lion和2,0,1,3,5,4，输出会是dog, cat ,moutse, rabbit, lion, tiger

这个题感觉从变换前的数组求变换后的数组很好做，假设string数组是S，int数组是A，直接一位一位循环遍历，当A[i] != i 时候把A[i] 与 A[A[i]]以及S[i] 与S[A[i]]一直调换就可以了

我是一开始用了开数组的方法做，跟他讲了想法他才说这题要是只能用O（1）空间要怎么做。。。感觉就是和他想的不一样，他不想让你从这条路走，所以不断给你加限制条件

比如lz举得第一个例子，从int数组的第0个开始，int[0] = 2, 那么 tmp = string[0], string[0] = string[2], 然后看int[int[0]]也就是int[2], int[2] = 3, 那么string[2] = string[3], 以此类推，再看int[3], int[3] = 1, 那么string[3] = string[1], 最后看int[1], int[1] = 0, 那么string[1] = tmp.

public void reverseMapping(String[] str, int[] map) {. 1point 3acres 璁哄潧
for(int i=0; i<map.length; i++){
int j = i;
while(map[j] != i){
swap(str, j, map[j]);
int temp = map[j];.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
map[j] = j;
j = temp;
}. more info on 1point3acres.com
map[j] = j;
}
}
private void swap(String[] str, int i, int j) {
String temp = str[i];
str[i] = str[j];
str[j] = temp;
}

http://www.1point3acres.com/bbs/thread-208801-1-1.html
第一轮给一个树，算最大的节点差值，递归一下就完了，对于每个节点用他最大的祖先减去他自己
第二轮设计一个游戏。两个player，第一个人心中有一个词让第二个人来猜，第二个人有一个字典，会从字典里选词来猜。每猜一次第一个人会告诉第二个人他猜的词有几个字母和结果一样，只知道个数不知道具体哪个字母是一样的。然后让实现这个游戏，要自己想策略来减少猜词的次数。

第三轮第一题3sum smaller，第二题给了两个接口和一个实现了接口的类，让写unit test去测试这个类。转专业狗没见过unit test，愣了半小时也不会。。。呵呵

第四轮第一题给两个数组before和after，比如before是[1, 3, 2, 4] 把他排序以后就变成了after = [1, 2, 3, 4] 然后要实现一个函数记录这个order  之后再实现一个函数，input是一个string，比如abcd，要先call之前写的函数得到那个order，然后把那个order用在这个字符串上，所以返回acbd。其实这道题就像是给tuple排序，(1,a), (3,c),(2,b),(4,d)按数字排序然后输出旁边的字母，只不过在调用第二个函数之前你不知道这些字母是什么。follow up 是有重复怎么办。
第二题设计一个类支持redo undo之类的功能。

楼主第一问是任意两个节点吗？还是只是和祖先节点的差
第一题是和祖先的差。第二题是因为第二个人那里有个字典，所以可以通过上一次猜词得到的分数从字典里删词
http://www.1point3acres.com/bbs/thread-210600-1-1.html
第一轮比较简单：average of last k numbers in data stream，merge intervals
第二轮是一个hashing的题，从来没遇到过，好悲剧。
首先第一题如果你有一个文件，每一行可能有重复[AB, A, B, A]，问怎样求得不重复的文件[AB, A, B]
然后第二题是如果这个文件很大内存存不下怎么办。然后面试官没怎么让我回答就说我感觉你应该不知道，要不我告诉你答案吧。思路是如果允许犯一些错，把某一行用一些hash function映射到一个数组h1, h2, ..., hk in [1, N]. 然后把每个hi设成true。问我这样会不会有false positive和false negative。我应该答错了。
- bloom filter
如果输出全部是true，那么结果大部分应该是有这一行，不过也有可能没有这一行，所以有fp。如果输出有false，说明一定没有这一行，所以不会有fn。
http://www.1point3acres.com/bbs/thread-208614-1-1.html
binary search， find number in 2D matrix。 Leetcode 原题
第二个人：
C++的问题，static 和 const 用在定义类方法上的问题。
给N个coin，每个coin的正面的prob，算要k个正面的概率
给1T的文字（大小写都是正常的），然后有个系统只输出小写，设计模型来把这个系统里面应该是小写的东西改成大写。怎么测试，用什么metric。

RNN + binary classification。
因为2维binary search没写出来
http://www.1point3acres.com/bbs/thread-206083-1-1.html

http://www.1point3acres.com/bbs/thread-204746-1-1.html
given an array=[1,2,3,4,5], so the sum will be 15 in total.
return random number from the array based on the probability.
e.g. 1->1/15
   2->2/15
所以每次run random(array) output will be different.
2就会有2/15次的机会成为Output

只能用ran() method->returns a number in [0,1). e.g. 0.2345
不可以用random.randint哦~~~~
public class OtherClass
{
  int[] buffer;
  int sum;
  Random rand;
  public OtherClass(int[] numbers){
buffer=numbers;
sum=0;
for(int n:numbers)
      sum+=n;
rand=new Random();
  }

  public int get(){
int tempSum=0;
int randInt=rand.nextInt(sum);//
for(int n:buffer){
   tempSum+=n;
   if(randInt>=sum-tempSum)
      return n;

    }
return 0;
  }

第一个是投硬币，第二个是方差检验，都是蛮简单的问题，但是第二个就全程懵逼，被给hint carry，然后问了两个问题就结束了…
http://www.1point3acres.com/bbs/thread-192001-1-1.html
完了之后问了一个大题目  how to take down a server，让我把能想到的全说出来
还有半个小时的时候  发给我一个google doc的链接写一个coding 题
input是很多很多domain name: 比如说 google.com, godadday.com, amazon.com......
然后让你找出出现次数top 10的domain有哪些。。
http://www.1point3acres.com/bbs/thread-209178-1-1.html
1. 给一个数组，找到比左右邻居都大的element。比如[1,2,3,4,3,5,6,7]，返回4

第一题是lc原题，条件是无重复数，然后两边无限小。
思路是：
if(mid < mid+1)
   left = mid+1;
else
   if(mid > mid+1)
      return  mid;
   else
      right = mid-1;

（纯娱乐）：我想了想为什么加上那两个条件就可以O(logN)时间解决（即使不是sorted），这其实就是一个微积分关于连续函数局部极大值证明题的离散版本啊！
根据离散条件，我可以对等的出这么一道题：（这个题就是用闭区间套定理证明的，相当于binary search）
给定一个定义在闭区间[a, b]上的连续函数f(x), 满足：
1. f(x) > f(a), f(x) > f(b), 对任意 x in (a, b);
2. 对任意 x in [a, b], 存在小邻域(x-d, x+d) 使得f(x)在(x-d, x]和[x, x+d)上分别严格单调（若x=a or b的话只需满足一边）。
求建立一个[a, b]中的一个序列{x_n}使其收敛到一个严格局部极大值。

我觉得这个题的考点肯定就是binary search，不然没任何意义。
”两边无限小“这个并不算关键，甚至算是隐含在题目描述里的（当然要和面试官确认）。
问题的关键是他只需要你随便找一个peak element，而不是所有peak element。随便找就是O(logn)，所有就是O(n)

2. 设计一个Iterator类，构造器input是一个Integer的Iterator, next()返回里面的下一个负数，hasNext()返回是否还有负数……
第二题在类里定义一个iterator存储input, 定义一个int存储下一个负数，hasNext()用来更新这个int

Google Interview Misc Part 10

Three coke machines. Each one has two values min & max

Labels

Popular Posts