http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=154493&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
第一轮：国人姐姐，restruct queue题目意思大概是这样。一群人在一点商店的门口排好队站着，每个人的身高都不同，到中午了，大家都去吃饭，吃完饭之后回来，要求按照之前的顺序排好队，给的信息是每个人的身高和原来队伍中在其前面有多少个比他高的人。
想出来一个方法，先把所有人按高到低排序，然后再逐个插入，感觉这样复杂度会是O(n^2).
第一题我觉得可以O(nlgn)解决，先从高到低sort()一下，然后用两个指针traverse，如果前面比他高的有k个，当前index:n, if (k<n) 让array里面的k和n位置的两个数交换就好了。
对，swap不行，得插入。谢提醒
美国小哥，leetcode原题之前面经也出现过，https://leetcode.com/problems/strobogrammatic-number-ii/，改动就是说要求输出所有的小于N的，还降低了难度，像“00”，“010”什么的也合法。做完之后，跑了下test case，发现了点问题及时改正了，follow up 就是如何改进，因为是要输出所有的数字，所以可以在中间用memorization得思想保存中间结果，比如N=3，在求3位的时候会用到1位的数字，这时候保存之前计算过的1位的数字的话就可以减少recursion的次数。
第三轮：美国小哥，上来就说我们做一道软件设计题吧，
首先是问我知道palindrome么，让我写一个函数判断一个string是不是palindrome，然后又问知道什么叫（名词忘了姑且叫allcharha'r）意思就是说这个字符串含有所有的字符（a-z），先说可以用哈希表然后又说可以直接建立个大小为26的数组记录。接着又问给一个字典里面有很多单词，问有多少组合。
接下来就开始放大招了，给一个很大的字典，要求找出这个字典里面既是palindrome又是allchar的组合并且要求最短。首先用最暴力的方法解了一遍，然后讨论如何改进，这轮更像是头脑风暴。
第三轮我会先用allcharrha 的条件把string sorted 后确认有没有包含有包含的且长度小于目前找到最短的在做parlindrome 的check 是这样解吗? 另外LZ有什么地方可以优化呢?
第一道是面经出现过的题目，给一个双向链表和一个存着部分节点的数组，问这个数组里面的节点能划分成几个group。
第二道题目是一个dp题，类似于俄罗斯方块，楼主感觉非常难，大概意思就是问怎么填满一个n*2的区域，只要求写出公式，跟印度小哥讨论着做出来的，给了大量的提示，甚至觉得是他在做
第一轮：国人姐姐，restruct queue题目意思大概是这样。一群人在一点商店的门口排好队站着，每个人的身高都不同，到中午了，大家都去吃饭，吃完饭之后回来，要求按照之前的顺序排好队，给的信息是每个人的身高和原来队伍中在其前面有多少个比他高的人。 这轮本身不是很困难，但是楼主第一轮太紧张了，算法搞定后，在coding的时候卡在了插入的环节，国人姐姐很有耐心也帮助了我不少，最后想想，代码还是有点问题。
第二轮：美国小哥，leetcode原题之前面经也出现过，https://leetcode.com/problems/strobogrammatic-number-ii/，改动就是说要求输出所有的小于N的，还降低了难度，像“00”，“010”什么的也合法。做完之后，跑了下test case，发现了点问题及时改正了，follow up 就是如何改进，因为是要输出所有的数字，所以可以在中间用memorization得思想保存中间结果，比如N=3，在求3位的时候会用到1位的数字，这时候保存之前计算过的1位的数字的话就可以减少recursion的次数。. from: 1point3acres.com/bbs
第三轮：美国小哥，上来就说我们做一道软件设计题吧，当时楼主就懵逼了，设计题！首先是问我知道palindrome么，让我写一个函数判断一个string是不是palindrome，然后又问知道什么叫（名词忘了姑且叫allcharha'r）意思就是说这个字符串含有所有的字符（a-z），先说可以用哈希表然后又说可以直接建立个大小为26的数组记录。接着又问给一个字典里面有很多单词，问有多少组合。接下来就开始放大招了，给一个很大的字典，要求找出这个字典里面既是palindrome又是allchar的组合并且要求最短。首先用最暴力的方法解了一遍，然后讨论如何改进，这轮更像是头脑风暴。
第四轮： 印度小哥，说实话，看见印度人怕被坑，但是这个小哥非常的nice，第一道是面经出现过的题目，给一个双向链表和一个存着部分节点的数组，问这个数组里面的节点能划分成几个group。第二道题目是一个dp题，类似于俄罗斯方块，楼主感觉非常难，大概意思就是问怎么填满一个n*2的区域，只要求写出公式，跟印度小哥讨论着做出来的，给了大量的提示，甚至觉得是他在做。
O(n),n是数组大小，其实意思跟leetcode里面Longest Consecutive Sequence的意思是一样的，只不过现在不是找前后连续的了，原来找前面是cur-1，现在是cur->prev，后面试cur+1变成cur->next，可以看看discuss我再里面写了做法
对于第一题，楼主是用的O(n^2)做的，比较直白， 对于第三题目，主要是和面试官聊了各种想法，并没有让写代码，主要考察思维和知识储备吧，这个看个人了，你说什么面试官都会表示很感兴趣然后深入和你讨论，对于第四题，俄罗斯方块拿到题目 只有两种方块可以使用--- 和|_ _ 问题是让你填满n*2的格子，列出公式，分三种情况，第一种室说没有剩余空格，第二种是由一个剩余空格，第三种是有两个剩余空格，然后把这三种情况整合在一起可以写出个表达式，对了你还得分析什么时候不可能填满 举个例子就是n = 4的时候无论怎样你都是填不满的，这个也需要写出公式，楼主确实是忘了怎么写了，这道题完全是根印度小哥聊天做完的，感觉大部分时间是他在做，过程中会问问我，所以公式真的记不太住了。
static class DoublyNode {
DoublyNode prev;
DoublyNode next;
int val;
public DoublyNode(int val) {
this.val = val;
}
}
public static int nodesGroupNumber(DoublyNode[] nodes) {
if (nodes == null || nodes.length == 0) {
return 0;
}
HashSet<DoublyNode> set = new HashSet<DoublyNode>();
for (DoublyNode node : nodes) {
set.add(node);
}
int res = 0;
for (DoublyNode node : nodes) {
System.out.println(node.val);
if (!set.contains(node)) {
continue;
}
res++;
set.remove(node);
DoublyNode cur = node.prev;
while (cur != null && set.contains(cur)) {
set.remove(cur);
cur = cur.prev;
}
cur = node.next;
while (cur != null && set.contains(cur)) {
set.remove(cur);
cur = cur.next;
}
}
return res;
}
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=148676&extra=page%3D1%26filter%3Dsortid%26sortid%3D311&page=1
就是给一个无重复的排序数组，给一个rand（），这个function返回随机数在[0, 1)之间，然后让你写一个getRandom，返回一个在数组上下界range里，但是又不在数组里的数，每个这样的数必须被返回的几率相同
我已开始说了个brute force的就是类似missing range然后找random，time是O（range of array element），被嘲讽了，说这题好多解法，我这个最差，最优解是O（lgN）的，据说只有一个人做出来过 = =。后来lz灵机一动竟然想出来了。。。说起来有点麻烦，大致就是用missing number的数目来确定每个range的weight，然后随意一个number，用binary search来确定这个number在哪个range里，然后就可以找出randNum是哪个了
先数出每个missing range中的元素个数。比如上下界是[0 10000]，数组是
A =【1 5 7 】. visit 1point3acres.com for more.
那么总共有4个missing range，其中元素个数分别是
Nmiss = [1 3 1 9993].
再对Nmiss的累加求和，得
Ncum = [1 4 5 9998]
用getRandom得到[0, 1]上的数字，再映射到[0 10000]上。比如我们得到的是3，那么就在Ncum中找第一个大于3的元素（即4）的位置。4是第2个元素，也就是说我们新生成的元素将在A的第1个元素1和第2个元素5之间。然后再调用一次getRandom，映射到[2, 4]上。即得最终要求的元素。
补充内容 (2015-11-21 11:33):
不用再调用第二次getRandom了。只要将第一次得到的数字3减去Ncum中“最后一个小于3的数字”，得2，然后取出[2 4]中第2个数字，即3就可以了。
你这个应该是rand生成0到9998之间才行。
其实可以直接存好missing_range_start{0,2,6,8}
然后存个missing_range_cumlength{1,4,5,9998}
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=154570&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
上来什么都没说，直接做题，给出一个n*n的棋盘，每一个格子里有一个数字，规则是从任意一个位置走到相邻的四个中的一个（上下左右），但只能走到比当前位置大数字大的地方，问给你一个这样的棋盘，给出里面的最长路径。（用recursion做就行了）
给一个BST，每一个节点里存有包含自己节点的子节点的个数，让返回nth smallest number, 用binary search就可以了，但是code当时写的很烂，corner case没有处理好
第一题dp记忆优化， 扫一遍就行了。 第二题recursion 每次subproblem 是 左子树找 n 或者 右子树找 n-1-left (left 表示左子树节点个数)
就是加一个 memorization 每个点不需要重复找最长路径
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=148682&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
1. Flip game (allPossible moves, canWin)
2. Find Camel:
Input: "FooBar", "FoBa", "FooBarFoo"
Pattern : "FBF"
Output " "FooBarFoo"
3. Run length string encoding.
4. Array of String Serialization, and deserialization
5. Top K int in a large stream (This can be done in O(n))
第五题O(N)解法: 2K windows, Quick Select, throw K away.
有N/K 个batches， 所以是O(K * N / K) = O(N)
不是一个一个进来，而是一个batch一个batch进来，每个batch的size就是k
你每次select第(total - k)个元素,前面的都remove就好了.
对total = 2K的情况 就是第K个.
少于2K就remove前面那些留下K个就好了.
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=155858&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
1. 判對是不是BST, 秒寫完，follow up BST定義具體講明，時間複雜度分析，面試官覺得我code很新奇
2. 棋盤遊戲，走過的格子不能走，寫出每一條路走到底的組合
提示過後用了dfs 但時間不太夠了面試官讓我講講想法，
(具體解法:hasBeen[i][j] = true;
recurse(i, j);.
hasBeen[i][j] = false;)
最後問問有沒有什麼想問google的呀，我問了CI之類的，還有為什麼taipei office沒有test 工程師等等
http://www.1point3acres.com/bbs/thread-139878-1-1.html
第一轮面试官是一个白人， 先上来一个问题是一串type为double的stream源源不断地流过来，给了window size， 问最近window size中所有数的平均。我的解法是用deque做的，空间复杂度O(n)，不知道有没有O(1)空间复杂度的解法。Follow up：经过很长一段时间之后，可能数据流中的平均值不再是正确的平均值了，请解释一下为什么，该如何解决这个问题。我回答是因为double不是精确的计数，可能产生误差，解决方法是过一定时间重新将整个deque中的所有数据重新求一下平均值。
第一个问题：
既然给了window size。
newAverage ＝ (oldAverage * windowSize - dequeue + enqueue) / windowSize
这样就是O（1）对吧。但每次都会产生误差。
所以每过一段时间重算一次平均值很必要。
第二题给了一个matrix，每个matrix[i][j]有一个价格，给你一个budget，问如何求出最大面积的子矩阵，使得子矩阵的价格之和不超过budget。
一开始我跟他简单讲述了一下O(n6)的brute force， 然后说可以建立一个sum数组优化到O(n4)，然后他说能继续优化么，我说用two pointer可以把时间复杂度优化到O(n3)。然后写code写了好久。我觉得可能是我code写的太慢了吧，因为经常写着写着就要停下来想一想。
private int findMaxLengthIn1DArray(int[] nums, int target) {
int max = 0, i = 0, sta = 0, sum = 0;
while (i < nums.length) {
sum += nums;
if (sum > target) {
max = Math.max(max, i-sta);
}
while (sum > target) {
sum -= nums[sta++];
}
i++;
}
return max == 0 ? nums.length : max;
}
public int getMaxArea(int[][] nums, int target) {
int wid = nums.length, len = nums[0].length, max = 0;
for (int j1 = 0; j1 < wid; j1++) {
int[] tmp = new int[len];
for (int j2 = j1; j2 < wid; j2++) {
for (int i = 0; i < len; i++) {
tmp += nums[j2];
}
int tempMax = findMaxLengthIn1DArray(tmp, target);
max = Math.max(max, tempMax*(j2-j1+1));
}
}
return max;
}
第二轮面试官国人，上来的的问题是问我如果在谷歌搜索框里输入一个查询语句，请描述一下在点击回车之后会发生什么事情。因为自己做过搜索引擎，我当时以为他问搜索引擎的查询过程，然后有点答得不对题，后来才知道他问的是计算机网络的东西。我大概把这个网络部分的回答简化了，然后没有答完整。要是理解清楚题意的话，我觉得我会把应用层到物理层的过程都给他讲一遍。（居然考计算机网络，我去）
第二个问题是说谷歌服务器每个上面都有自己的log，让我做一个log viewer服务器，自己定义接口，能够实现在log viewer查询所有的服务器端整合的log，（因为去一个个服务器上查询log可能太麻烦了）， 可以自己定义log viewer的功能。做完了后面试官说写的很好，然后跟我讨论了一下实现并发等
如果要用time stamp 来view 感觉跟在distributed system 中求top k 有点像
第一轮：国人姐姐，restruct queue题目意思大概是这样。一群人在一点商店的门口排好队站着，每个人的身高都不同，到中午了，大家都去吃饭，吃完饭之后回来，要求按照之前的顺序排好队，给的信息是每个人的身高和原来队伍中在其前面有多少个比他高的人。
想出来一个方法，先把所有人按高到低排序，然后再逐个插入，感觉这样复杂度会是O(n^2).
第一题我觉得可以O(nlgn)解决，先从高到低sort()一下，然后用两个指针traverse，如果前面比他高的有k个，当前index:n, if (k<n) 让array里面的k和n位置的两个数交换就好了。
对，swap不行，得插入。谢提醒
美国小哥，leetcode原题之前面经也出现过，https://leetcode.com/problems/strobogrammatic-number-ii/，改动就是说要求输出所有的小于N的，还降低了难度，像“00”，“010”什么的也合法。做完之后，跑了下test case，发现了点问题及时改正了，follow up 就是如何改进，因为是要输出所有的数字，所以可以在中间用memorization得思想保存中间结果，比如N=3，在求3位的时候会用到1位的数字，这时候保存之前计算过的1位的数字的话就可以减少recursion的次数。
第三轮：美国小哥，上来就说我们做一道软件设计题吧，
首先是问我知道palindrome么，让我写一个函数判断一个string是不是palindrome，然后又问知道什么叫（名词忘了姑且叫allcharha'r）意思就是说这个字符串含有所有的字符（a-z），先说可以用哈希表然后又说可以直接建立个大小为26的数组记录。接着又问给一个字典里面有很多单词，问有多少组合。
接下来就开始放大招了，给一个很大的字典，要求找出这个字典里面既是palindrome又是allchar的组合并且要求最短。首先用最暴力的方法解了一遍，然后讨论如何改进，这轮更像是头脑风暴。
第三轮我会先用allcharrha 的条件把string sorted 后确认有没有包含有包含的且长度小于目前找到最短的在做parlindrome 的check 是这样解吗? 另外LZ有什么地方可以优化呢?
第一道是面经出现过的题目，给一个双向链表和一个存着部分节点的数组，问这个数组里面的节点能划分成几个group。
第二道题目是一个dp题，类似于俄罗斯方块，楼主感觉非常难，大概意思就是问怎么填满一个n*2的区域，只要求写出公式，跟印度小哥讨论着做出来的，给了大量的提示，甚至觉得是他在做
第一轮：国人姐姐，restruct queue题目意思大概是这样。一群人在一点商店的门口排好队站着，每个人的身高都不同，到中午了，大家都去吃饭，吃完饭之后回来，要求按照之前的顺序排好队，给的信息是每个人的身高和原来队伍中在其前面有多少个比他高的人。 这轮本身不是很困难，但是楼主第一轮太紧张了，算法搞定后，在coding的时候卡在了插入的环节，国人姐姐很有耐心也帮助了我不少，最后想想，代码还是有点问题。
第二轮：美国小哥，leetcode原题之前面经也出现过，https://leetcode.com/problems/strobogrammatic-number-ii/，改动就是说要求输出所有的小于N的，还降低了难度，像“00”，“010”什么的也合法。做完之后，跑了下test case，发现了点问题及时改正了，follow up 就是如何改进，因为是要输出所有的数字，所以可以在中间用memorization得思想保存中间结果，比如N=3，在求3位的时候会用到1位的数字，这时候保存之前计算过的1位的数字的话就可以减少recursion的次数。. from: 1point3acres.com/bbs
第三轮：美国小哥，上来就说我们做一道软件设计题吧，当时楼主就懵逼了，设计题！首先是问我知道palindrome么，让我写一个函数判断一个string是不是palindrome，然后又问知道什么叫（名词忘了姑且叫allcharha'r）意思就是说这个字符串含有所有的字符（a-z），先说可以用哈希表然后又说可以直接建立个大小为26的数组记录。接着又问给一个字典里面有很多单词，问有多少组合。接下来就开始放大招了，给一个很大的字典，要求找出这个字典里面既是palindrome又是allchar的组合并且要求最短。首先用最暴力的方法解了一遍，然后讨论如何改进，这轮更像是头脑风暴。
第四轮： 印度小哥，说实话，看见印度人怕被坑，但是这个小哥非常的nice，第一道是面经出现过的题目，给一个双向链表和一个存着部分节点的数组，问这个数组里面的节点能划分成几个group。第二道题目是一个dp题，类似于俄罗斯方块，楼主感觉非常难，大概意思就是问怎么填满一个n*2的区域，只要求写出公式，跟印度小哥讨论着做出来的，给了大量的提示，甚至觉得是他在做。
O(n),n是数组大小，其实意思跟leetcode里面Longest Consecutive Sequence的意思是一样的，只不过现在不是找前后连续的了，原来找前面是cur-1，现在是cur->prev，后面试cur+1变成cur->next，可以看看discuss我再里面写了做法
对于第一题，楼主是用的O(n^2)做的，比较直白， 对于第三题目，主要是和面试官聊了各种想法，并没有让写代码，主要考察思维和知识储备吧，这个看个人了，你说什么面试官都会表示很感兴趣然后深入和你讨论，对于第四题，俄罗斯方块拿到题目 只有两种方块可以使用--- 和|_ _ 问题是让你填满n*2的格子，列出公式，分三种情况，第一种室说没有剩余空格，第二种是由一个剩余空格，第三种是有两个剩余空格，然后把这三种情况整合在一起可以写出个表达式，对了你还得分析什么时候不可能填满 举个例子就是n = 4的时候无论怎样你都是填不满的，这个也需要写出公式，楼主确实是忘了怎么写了，这道题完全是根印度小哥聊天做完的，感觉大部分时间是他在做，过程中会问问我，所以公式真的记不太住了。
static class DoublyNode {
DoublyNode prev;
DoublyNode next;
int val;
public DoublyNode(int val) {
this.val = val;
}
}
public static int nodesGroupNumber(DoublyNode[] nodes) {
if (nodes == null || nodes.length == 0) {
return 0;
}
HashSet<DoublyNode> set = new HashSet<DoublyNode>();
for (DoublyNode node : nodes) {
set.add(node);
}
int res = 0;
for (DoublyNode node : nodes) {
System.out.println(node.val);
if (!set.contains(node)) {
continue;
}
res++;
set.remove(node);
DoublyNode cur = node.prev;
while (cur != null && set.contains(cur)) {
set.remove(cur);
cur = cur.prev;
}
cur = node.next;
while (cur != null && set.contains(cur)) {
set.remove(cur);
cur = cur.next;
}
}
return res;
}
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=148676&extra=page%3D1%26filter%3Dsortid%26sortid%3D311&page=1
就是给一个无重复的排序数组，给一个rand（），这个function返回随机数在[0, 1)之间，然后让你写一个getRandom，返回一个在数组上下界range里，但是又不在数组里的数，每个这样的数必须被返回的几率相同
我已开始说了个brute force的就是类似missing range然后找random，time是O（range of array element），被嘲讽了，说这题好多解法，我这个最差，最优解是O（lgN）的，据说只有一个人做出来过 = =。后来lz灵机一动竟然想出来了。。。说起来有点麻烦，大致就是用missing number的数目来确定每个range的weight，然后随意一个number，用binary search来确定这个number在哪个range里，然后就可以找出randNum是哪个了
先数出每个missing range中的元素个数。比如上下界是[0 10000]，数组是
A =【1 5 7 】. visit 1point3acres.com for more.
那么总共有4个missing range，其中元素个数分别是
Nmiss = [1 3 1 9993].
再对Nmiss的累加求和，得
Ncum = [1 4 5 9998]
用getRandom得到[0, 1]上的数字，再映射到[0 10000]上。比如我们得到的是3，那么就在Ncum中找第一个大于3的元素（即4）的位置。4是第2个元素，也就是说我们新生成的元素将在A的第1个元素1和第2个元素5之间。然后再调用一次getRandom，映射到[2, 4]上。即得最终要求的元素。
补充内容 (2015-11-21 11:33):
不用再调用第二次getRandom了。只要将第一次得到的数字3减去Ncum中“最后一个小于3的数字”，得2，然后取出[2 4]中第2个数字，即3就可以了。
你这个应该是rand生成0到9998之间才行。
其实可以直接存好missing_range_start{0,2,6,8}
然后存个missing_range_cumlength{1,4,5,9998}
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=154570&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
上来什么都没说，直接做题，给出一个n*n的棋盘，每一个格子里有一个数字，规则是从任意一个位置走到相邻的四个中的一个（上下左右），但只能走到比当前位置大数字大的地方，问给你一个这样的棋盘，给出里面的最长路径。（用recursion做就行了）
给一个BST，每一个节点里存有包含自己节点的子节点的个数，让返回nth smallest number, 用binary search就可以了，但是code当时写的很烂，corner case没有处理好
第一题dp记忆优化， 扫一遍就行了。 第二题recursion 每次subproblem 是 左子树找 n 或者 右子树找 n-1-left (left 表示左子树节点个数)
就是加一个 memorization 每个点不需要重复找最长路径
1. Flip game (allPossible moves, canWin)
2. Find Camel:
Input: "FooBar", "FoBa", "FooBarFoo"
Pattern : "FBF"
Output " "FooBarFoo"
3. Run length string encoding.
4. Array of String Serialization, and deserialization
5. Top K int in a large stream (This can be done in O(n))
第五题O(N)解法: 2K windows, Quick Select, throw K away.
有N/K 个batches， 所以是O(K * N / K) = O(N)
不是一个一个进来，而是一个batch一个batch进来，每个batch的size就是k
你每次select第(total - k)个元素,前面的都remove就好了.
对total = 2K的情况 就是第K个.
少于2K就remove前面那些留下K个就好了.
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=155858&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
1. 判對是不是BST, 秒寫完，follow up BST定義具體講明，時間複雜度分析，面試官覺得我code很新奇
2. 棋盤遊戲，走過的格子不能走，寫出每一條路走到底的組合
提示過後用了dfs 但時間不太夠了面試官讓我講講想法，
(具體解法:hasBeen[i][j] = true;
recurse(i, j);.
hasBeen[i][j] = false;)
最後問問有沒有什麼想問google的呀，我問了CI之類的，還有為什麼taipei office沒有test 工程師等等
http://www.1point3acres.com/bbs/thread-139878-1-1.html
第一轮面试官是一个白人， 先上来一个问题是一串type为double的stream源源不断地流过来，给了window size， 问最近window size中所有数的平均。我的解法是用deque做的，空间复杂度O(n)，不知道有没有O(1)空间复杂度的解法。Follow up：经过很长一段时间之后，可能数据流中的平均值不再是正确的平均值了，请解释一下为什么，该如何解决这个问题。我回答是因为double不是精确的计数，可能产生误差，解决方法是过一定时间重新将整个deque中的所有数据重新求一下平均值。
第一个问题：
既然给了window size。
newAverage ＝ (oldAverage * windowSize - dequeue + enqueue) / windowSize
这样就是O（1）对吧。但每次都会产生误差。
所以每过一段时间重算一次平均值很必要。
第二题给了一个matrix，每个matrix[i][j]有一个价格，给你一个budget，问如何求出最大面积的子矩阵，使得子矩阵的价格之和不超过budget。
一开始我跟他简单讲述了一下O(n6)的brute force， 然后说可以建立一个sum数组优化到O(n4)，然后他说能继续优化么，我说用two pointer可以把时间复杂度优化到O(n3)。然后写code写了好久。我觉得可能是我code写的太慢了吧，因为经常写着写着就要停下来想一想。
private int findMaxLengthIn1DArray(int[] nums, int target) {
int max = 0, i = 0, sta = 0, sum = 0;
while (i < nums.length) {
sum += nums;
if (sum > target) {
max = Math.max(max, i-sta);
}
while (sum > target) {
sum -= nums[sta++];
}
i++;
}
return max == 0 ? nums.length : max;
}
public int getMaxArea(int[][] nums, int target) {
int wid = nums.length, len = nums[0].length, max = 0;
for (int j1 = 0; j1 < wid; j1++) {
int[] tmp = new int[len];
for (int j2 = j1; j2 < wid; j2++) {
for (int i = 0; i < len; i++) {
tmp += nums[j2];
}
int tempMax = findMaxLengthIn1DArray(tmp, target);
max = Math.max(max, tempMax*(j2-j1+1));
}
}
return max;
}
第二轮面试官国人，上来的的问题是问我如果在谷歌搜索框里输入一个查询语句，请描述一下在点击回车之后会发生什么事情。因为自己做过搜索引擎，我当时以为他问搜索引擎的查询过程，然后有点答得不对题，后来才知道他问的是计算机网络的东西。我大概把这个网络部分的回答简化了，然后没有答完整。要是理解清楚题意的话，我觉得我会把应用层到物理层的过程都给他讲一遍。（居然考计算机网络，我去）
第二个问题是说谷歌服务器每个上面都有自己的log，让我做一个log viewer服务器，自己定义接口，能够实现在log viewer查询所有的服务器端整合的log，（因为去一个个服务器上查询log可能太麻烦了）， 可以自己定义log viewer的功能。做完了后面试官说写的很好，然后跟我讨论了一下实现并发等
如果要用time stamp 来view 感觉跟在distributed system 中求top k 有点像
http://www.1point3acres.com/bbs/thread-154433-1-1.html
android pin 如果输入一系列密码， 不能有重复，不能少于四个，然后看密码是不是valid。
比如键盘如下：
012
345
678
然后如果你输02。。。是不可以的， 因为1 是obstruction。
我刚开始纠结了一下怎么做，卡了有点久。然后后来想出来比较笨的方法去做，但是跟面试官讨论test case的时候 发现他其实清除obstruction以后你也可以走对角线方向的密码。 但是我之前只考虑了horizontal 和 vertical。 这个时候没什么时间了，跟他讲了一下怎么fix bug 就挂了····
第二个就是binary search tree, 给一个target sum， 看里面包不包含两个数可以达到这个target sum，有duplicate。. more info on 1point3acres.com
follow up：因为我们会有很多可选的组合，找一个pair的差是最大的。因为我inorder， 所以找到的第一个其实就是差最大的。
然后也问了time 和 space complexity。
1、给一个二维字符矩阵，比如
*****
**#**
*?*?*
**?**
*****
表示一个gym的weighting room，其中*表示空地，#表示房间里的柱子，?表示健身器材的位置。要求找出一个可行的点，在这个点放置weights，使得这个点到所有健身器材的距离之和最短。
就是bfs，复杂度是O(k*m*n)，k是健身器材个数，m和n是房间的大小
2、thesis review
3、course schedule
4、The skyline problem
5、第一题是unique paths。然后问如果随机选择一条可行路径，那么第一步往右走的概率是多少。
第二题输入一个二维整数数组，表示一个格点地图，数组的每一个元素表示相应格点的海拔。如果在某一个格点倒水，则水会等概率的流向临近的海拔更低的格点。求在某一个格点倒水，最后水流到地图的最左边或者最下边的比例。
找出每一个格点相应的概率和邻近的格点的概率之间的关系就可以了
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=154369&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
题目是给一个ArrayList，将ArrayList increase 1，比如［1，2，3，4］－>［1， 2，3，5］。
follow up 1: 我开始用递归写的，小哥问递归会出现什么问题，不用递归怎么写。.
写完while loop之后，小哥follow up怎么test
我说测input output，space 和time
follow up2: 怎么测时间是不是超过time limit？
android pin 如果输入一系列密码， 不能有重复，不能少于四个，然后看密码是不是valid。
比如键盘如下：
012
345
678
然后如果你输02。。。是不可以的， 因为1 是obstruction。
我刚开始纠结了一下怎么做，卡了有点久。然后后来想出来比较笨的方法去做，但是跟面试官讨论test case的时候 发现他其实清除obstruction以后你也可以走对角线方向的密码。 但是我之前只考虑了horizontal 和 vertical。 这个时候没什么时间了，跟他讲了一下怎么fix bug 就挂了····
第二个就是binary search tree, 给一个target sum， 看里面包不包含两个数可以达到这个target sum，有duplicate。. more info on 1point3acres.com
follow up：因为我们会有很多可选的组合，找一个pair的差是最大的。因为我inorder， 所以找到的第一个其实就是差最大的。
然后也问了time 和 space complexity。
1、给一个二维字符矩阵，比如
*****
**#**
*?*?*
**?**
*****
表示一个gym的weighting room，其中*表示空地，#表示房间里的柱子，?表示健身器材的位置。要求找出一个可行的点，在这个点放置weights，使得这个点到所有健身器材的距离之和最短。
就是bfs，复杂度是O(k*m*n)，k是健身器材个数，m和n是房间的大小
2、thesis review
3、course schedule
4、The skyline problem
5、第一题是unique paths。然后问如果随机选择一条可行路径，那么第一步往右走的概率是多少。
第二题输入一个二维整数数组，表示一个格点地图，数组的每一个元素表示相应格点的海拔。如果在某一个格点倒水，则水会等概率的流向临近的海拔更低的格点。求在某一个格点倒水，最后水流到地图的最左边或者最下边的比例。
找出每一个格点相应的概率和邻近的格点的概率之间的关系就可以了
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=154369&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
题目是给一个ArrayList，将ArrayList increase 1，比如［1，2，3，4］－>［1， 2，3，5］。
follow up 1: 我开始用递归写的，小哥问递归会出现什么问题，不用递归怎么写。.
写完while loop之后，小哥follow up怎么test
我说测input output，space 和time
follow up2: 怎么测时间是不是超过time limit？
