Massive Algorithms: Google Interview Misc

http://www.1point3acres.com/bbs/thread-141623-1-1.html
1. longest consective increasing sequence in binary tree.(start point happen anywhere in the node, not necessary start from root), 白人小哥
2. 中国北大姐，说是和我同一届本科毕业的，人家就是屌，国内直接来工作的。determine binary tree is complete tree. 感觉被low ball了，也怪自己，对complete tree 不熟悉。

3. url list with relevance score sorted in descending order from two difference sources, how to organize and return unique url with descending order. (merge sort with de-duplicate) 简单题，用merge sort的思想就完了。代码里有个list.get(i), get element by index, pre-assume it would be arraylist. 结果在被问到what's assumption 时懵了。别的总体还好。

3. You have two lists of URLs from source A and source B. each URL has score and each list of URL order by score in descending order.
For example:,
source A: (u1, 0.9), (u2, 0.8), (u3, 0.75)
source B: (u1, 0.8), (u3, 0.6), (u4, 0.5)
return : (u1, 0.9), (u2, 0.8), (u3, 0.75), (u4, 0.5). PS: only return unique URL with highest score from two sources.

3. merge sort的同时用hash set记录是否出现URL，如果有就skip，如果没有，加入hash set同时加入到最后的结果中。

Use Iterator.
Conrer Case: 第三题不同source是什么意思会不会出现两组排序中URL相同但是相对排名不一致的情况

4.三哥，迟到15分钟，急匆匆的进来了，给了个generate all possible complete tree with number of nodes is N. 然后中途还电话两次。递归生成所有树，f(n) = { f(n-1) + attach two child nodes to any leaf of tree in f(n-1)}。在递归的时候要de-duplicate,用 serialize tree来保证树结构唯一性，(in-order + pre-order sequence).走了一遍serialization的例子。写的伪代码，因为没有时间写全所有的了，期间还有clone tree的操作。

4. 这个是number of full binary tree，总的tree的数应该是Catalan number，f(n)=sum_{i=1...n-1) (f(i)*f(n-i))

4. 重新定义下题。 given number N which represents total number of leaves in tree.  you need to generate all possible tree, such that each node in tree has zero child or two children. The return type should be a list of such kind of trees. Only tree structure matters, tree node doesn't have any value initially.
My solution: N = 1 and N = 2 are base cases.
For example, N = 3.

   1             1
/ \          / \
  1    1       1    1
/ \                   /  \
1  1                1 1

For N = 4, all possible trees can be generated from f(3) by attaching each leaf node with two children, recursively follow this pattern to return target N. (Note: f(3) indicates a list of trees with 3 nodes in structure described above)

Answer: http://massivealgorithms.blogspot.com/2015/10/binary-tree-with-n-leaf-google-interview.html

5. 中国小哥，CMU毕业的。问了到 number的题。不知道怎么描述， given increase/decrease trend sequence, generate one possible sequence with minimal value.
for example, given sequence order "iddi" ->34215, "iii" -> 1234, "ddd"-> 4321. (solution有空在写，直接慢慢琢磨出来的是O(n2)的solution, 小哥直接给hint说用链表结构能improve 到O(n) ).关于第五题没有描述清楚，digit should be unique. 所以Google Candy 解法不能用。e.g. 1213212 三个1，三个2， not unique.
5. 不知道这样可不可以，从1234...n序列开始，扫描ii...dd，对于连续的i，可以skip，对于连续的d，找到d的起始点和终点，然后reverse这一段
比如iidd, 以12345 开始，前两个ii，skip，然后dd，起始和最后的位置分别在2,3，那么reverse序列12345中的2到3+1的位置，那么序列变成12543. 还有楼主在原帖里的例子:"iddi"结果应该是14325吧？
5. First, "i" represents increase, "d" represents decrease, so for number 123, the sequence would be "ii", for number 87123, sequence would "ddii".
The question is to generate the minimum number follows given sequence "iidd".
解法: while loop,
step1, "" -> [1], next number for step2 is 2
step2 "i" -> [1, 2], next number for step3 is 3
step3 "i" -> [1, 2, 3], next number for step4 is 4
到第四步发现 [1, 2, 3, 4] 不符合 iid, 怎么办呢？把4 与前面的3 交换 [1, 2, 4, 3] match "iid"
到第五步发现[1, 2, 4, 3, 5] 又不符合 iidd 怎么办呢？把5与插到4前 [1, 2, 5, 4, 3].
这样12543 应该是最小的number了.

核心就是每次记录last decreasing point. insert next number before last decreasing point. 本来用string 做的，然后有个小while loop to find last decreasing point. 后来小哥说用一个新的data structure 会快些。链表结构，you just need to keep track of the node which is last decreasing point node.

这题我觉得很像排列组合在leetcode还是geeksforgeeks里的一道题。Anyway，当场写这题的时候,直接当场找规律。

http://www.mitbbs.com/article_t/JobHunting/33072599.html
问的是LCA of DAG. 全程不让写代码, 就一直问follow up, 问复杂度, 问怎
么做, 为什么要这么做, 用那个为什么不好, 后来问要是有很多pair of nodes 求LCA
要怎么做preprocessing.
http://www.mitbbs.com/article_t/JobHunting/33073385.html
https://en.wikipedia.org/wiki/Collatz_conjecture
x_0 = C (integer)
if x_n is even then x_{n+1} is x_n / 2
if x_n is odd then x_{n+1} to be 3 * x_n + 1

这题的复杂度是O(logC)吗？
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=141229&highlight=
给你一个以String形式存储的文件，每行有一些字符串，结尾是\n，然后给你一个offset，问是在第几行。

比如：
abc\n
de\n
efg\n
h\n
offset = 0 的话是a，在第1行。offset = 3 为\n，还在第一行。offset = 8 是f，在第三行。

非常简单的题目，用循环做就行，每次遇到一个\n就加1，注意不要count最后一个字母，因为可能是结尾的\n。

follow up：
接上题，让你设计一种数据结构，用比O(n)快的方法找到line number。

方法：建一个int[]，存每一行字符数的加和，然后binary search，跟之前leetcode insert position的题一模一样。也跟地里之前出现过的“每次调用一个函数，按照数组里面的数字的大小，返回相应的Index”一样。

比如：
abc\n
de\n
efg\n
h\n

就建立一个array：[4， 7，11， 13]，然后按照给的offset搜索。
http://www.1point3acres.com/bbs/thread-142376-1-1.html

第一轮：白人大叔，挺和蔼的。上来先问了一下简历上intern的事情，然后问做过的project有哪些challenge，之后出题：

给一个整数n，返回前n个fibonacci number相邻pair的最后一个digit。听起来有点绕，其实不难，比如：

n = 8

fibonacci: [0, 1, 1, 2, 3, 5, 8, 13]

return: [ (0, 1), (1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 3) ]

很简单，先生成前n个number到list，然后第二遍loop返回pair。

follow up：怎样确定有没有cycle？如果n很大怎么办？

维护一个visited set，每次检查一下。

很多solution: 可以用long，用string，或者cache，或者distributed system。

-- cycle的意思就是出现了之前出现过的pair，这样整个序列又会同之前一样了。

然后问最多需要查多少次就可以确定cycle的存在？

这个自己脑抽了，理解了好久才明白过来，就是计算有多少个可能的pair，10 * 10。

给一颗二叉树，返回重复的subtree。比如：

1

/ \

2 3

/ / \

4 2 4

/

4

结果应该返回[ ( 2 -> 4), (4) ] 两颗树。

也很简单，BFS遍历，存每个substree到list里，然后用双重循坏找。其中需要写一个helper function判断两棵树是否相同。

follow up：time complexity，以及如何优化。

得到subtree list之后提前处理，把root value unique的除掉。

第三轮：国人小哥。开始要出跟上一轮一样的题，我跟他讲题出过了，所以换了一道。

设计一个fraction number 的class，要求实现equals和String toDecimal()。

toDecimal是leetcode原题，equals的话注意先得到gcd，然后除了之后再比较。还有分子分母是否为0，符号不一样等等都需要考虑。细节挺多的。

第四轮：白人大叔。这一轮比之前都难，虽然是面经题，不过之前的面经很简略，没有实现。

给一个二维boolean array， true代表greyed，要找出所有可能的正方形。比如：

0 1 0

0 0 0

1 0 0

一共有8个正方形（边长为1的7个，为2的1个，为3的0个）。注意matrix的边长可能不等。

这道题一开始出来有点蒙，心想完蛋了。面试官也面无表情，坐在那一句话不说，没有任何提示。好在最后经过思索还是搞出来了。用DP对matrix先预处理，方法有点类似之前地里面经出现的计算matrix中rectangle面积的题，dp[j]代表从(0, 0) 到（i, j) 里面所有可用的grid的数量。具体方法大家可以自己思索一下。

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

（1）中年白人：先在手机上演示了一个game, 就是一个球从起点开始沿着通道，看能不能滚到终点。不过有限制，每次球一走到底要不到边界，要不到障碍物，中间不能停留。可以上下左右走，然后让写个function 给定起点，终点，和图，判断是不是solvable. 写出来了，就是用BFS,有个小bug被指出。然后问复杂度，问如何优化。.

（2）韩国人： (a) 给一个dictionary, 再给一个set of coding string （g5, goo3,goog2, go2le.........). return all string from dictionary that can be matched with the coding string. 要求尽量减少dictionary look up 次数。给了个方法，但一直不满意复杂度。

（b)如何用Trie, 把问题(a)解决,要求写code 建一个Trie包括所有字典词和coding string.不是很明白。。。凭感觉写了个。

（3）阿三，非常拽。。。给一个dictionary, 一个string,找出dict 里能全部用string里的letter 表示的所有最长的词。给了算法，死活不满意，不让我写code. 估计被黑了。. more info on 1point3acres.com

(4）阿三。 design google calendar . 要求分析如何存data, 如何invoke user events, 如何handle 100000events per second, 然后要写了一部分thread safe 的code 实现如何invoke event.

(5) 年轻白人： (a)leetcode 上的coin 题，用DP. (b)给你一个password 假定6位，有个function 每call 一次就给你一个triplet 是password 里的随即三位，order不变。比如google, 可能返回， ggl, goe, oog, ool, ........问如何最有效破译这个密码，写code.

question 1:
我会用DFS 每一个node 可以mark 4个directions(因为要block or not way 才能change direction)
tim compleixty is o(4nm)

queiton 2:
我一开始就是想到tries 假g5a(assuming input is only alphabet), 会转成g#####a. # 可以match any character. 用所有的strings 建tries 然后dictionary 扫一遍不知道有没有理解错?
question 3:
我会用两个hashMap. the first is for target string and the second is reused for each string in dictionary. 这感觉面试官要更好的算法?

question 4:
一个
main thread 接受register event 一个thread(synchonized) 平时sleep 会被main threa 叫起来纪录event 不知道考点是data structure 还是？

questino 5-1:
找不到leetcode coin 的题目 LZ 能说说吗?

question 5-2
是用猜数子的brute force 解法吗?

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

Biggest M elements from N sorted lists.Follow-up: Biggest M elements from N reversely-sorted lists.

做一个大小为M的heap，然后每个list查阅最前面的N个数字就好了？log(M) * M * N？

reversed sorted 的话，每个list跑两个距离为M的指针，然后从倒数第M个位置开始，做同样的事情？

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

(1) Give flights with start and end time. Find maximum number of simultaneous flights. 秒杀－先排序start 和 end time(需要标记下类别），maintain一个counter，遇到一次start type的time加一，反之减一，记录遇到的最大值。
(2) Give pairs of {time, word}, design an algorithm that preserves words within past X seconds, removing those expired. Also print CURRENT word. 一开始以为要打印出所有past X seconds的words，直接上了deque和unordered_set。后来才知道只需print出current word，但却忘了更改数据结构。之后改成deque + unordered_map，最后感觉是做到了，但不顺畅。面完后想了下，其实用一个queue就行了（因为只需打印current word)，顿时冒了身冷汗。。。关键是queue里可存 {word, time} pairs，同样的word因为不同的time可以在queue里出现超过一次，因此不需要hashmap。

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

Given a list of Google search queries, such as:

'restaurants in new york',

'yorkie puppy',

'hotels in new england'

'weather in england'
‘new york destinations’
‘cheap new york theater tickets’
‘buy tickets for statue of liberty’

and a whitelist of known place names, such as:

new york, eiffel tower, york, new england, england, statue of liberty.

Find how often each place name occurs in the query logs.

Assume N queries (in the billions at least), P place names (in the millions).
Assume English only (words are separated by spaces).

http://www.1point3acres.com/bbs/thread-140903-1-1.html
https://hellosmallworld123.wordpress.com/2015/07/23/g%E7%9A%84%E5%87%A0%E9%81%93%E9%9D%A2%E8%AF%95%E9%A2%98/
1. 美国大叔。 warm up 问题：求 int(log X). 第二题，给一堆strings 和一个input string, 在input里找出minimum unused char.
2. 国人小哥。特别nice！给一个数字的array，两个数字间只用+或者* 算出最大的值。

public int getMax(int[] input) {
int[] max = new int [input.length];
int[] min = new int [input.length];
for (int i=0; i<input.length; i++) {
if (i==0) {
max[i] = input[i];
min[i] = input[i];
} else {
max[i] = Math.max(input[i] + max[i], input[i] * max[i], input[i] * min[i]);
min[i] = Math.min(input[i] + min[i], input[i] * max[i], input[i] * min[i]);
}
}
return max[input.length-1];
}
3.烙印大叔。给一个array 和一个 target求出 array里有几组tuple相加是小于等于target的。第二题是一个array里面只有0-9的digits, 有一个target，判断是否存在一种组合可以等于target。eg: [6,3,1,0,5] target=78,这个return True. 63+10+5 = 78 如果target= 636 return True. 631+0+5 = 636

4.烙印小哥。 rearrange array，使得相邻两个字符是不一样的。
// if( max count number > n/2) return directly not possible.

5. 俄罗斯小哥？长得像格格巫。。。LRU~~

http://www.1point3acres.com/bbs/thread-141197-1-1.html
http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
Calculate the intersection of two segments.
两个判断漏了条件, 这还能过么?
做法: 叉乘判断是否同侧, 考虑斜率无穷的情况, 求交点, 看是否在线段上.
http://www.1point3acres.com/bbs/thread-141774-1-1.html
Q1: 给了一个map<int,int> int_map, 还给了一个function： bool predict(int val); 函数是判断val是不是int_map的一个key。感觉这个给的很无力啊，用find不就解决了的问题？
      让写一段循环语句，删除int_map里面有val作为key的。
      看上去简单，写的时候漏洞百出啊~大家可以写写看

Q2: 问C++的map 的insert函数的complexity是多少？ O(logN)

Q3: Given 2D matrix, N*N, element ranging from 1 - N^2, no duplicate.
      return the length of longest consective path

Eg.  1 3 5
   2 4 6
   9 8 7
Should return 5 because path 5 6 7 8 9 has the longest path length;
Answer: http://massivealgorithms.blogspot.com/2015/08/find-length-of-longest-consecutive-path.html
http://www.1point3acres.com/bbs/thread-111528-1-1.html
第二题是给一个数组A，找一个数Y使得min(|Y-Ai|)最大.
保证代码clean并且边界也没问题就可以的了
O(n)的解法不常考，用bucketsort，找出每个区间的最大最小值，然后逐个比较下个区间最小值和当前区间最大值的距离，距离最大的那个的中点是返回值。
给的array是是没有排序的，求的是min(|Y-A|)，是离Y最近的一个点的距离
要让这个值最大，而Y又是在最大值和最小值之间，可以推出Y是距离最远的两点的中点

一道是给一个Array表示different type of attractions，分两天去旅游，保证每天每种景点都要有，有几种分法，O(n) Time, O(n) Space

另一道是求比给的n大的最小的happy number，happy number的定义是长度是偶数，前一半和后一半相同，例如: 1313。
http://www.1point3acres.com/bbs/thread-133032-1-1.html
1. 给一个string，内容是数字，让你返回一个比它大的最小的数，这个数字左半边和右半边必须相等，比如给你1004，就要返回1010，给你2345，就要返回2424，这样子。

2. 一串int数组，每一个数值都在1-9之间，但不一定把1-9都包括了，可能只有1234神马的，5678从来没出现也是有可能。数组长度在2-100000之间，要把这串数组一分为二，左半边和右半边都必须包含所有出现过的数字，要返回一共有多少种划分方法。

一串int数组，数值在0-99之间，ascending order，要返回这串数字中缺失的部分，例如，输入是{3, 15, 16, 18, 80}，输出就是 "[0-2, 4-14, 17, 19-79, 80-99]"

1. 一串int数组，ascending order，返回最长的连续的数字串，例如输入是{1,2,3,7,10,11,12,13,16,17}，输出就是{10,11,12,13}.
2. 设计一个data structure用作memory，如果要存新的数据进去，当它没有满的时候，就直接存在最后；当它满了的时候，会取代那个最久以前使用过的数据。如果要peek这个stack，会返回最近使用过的数据。

1. 一串int数组，有正数有负数，会保证至少有一个正数，要返回相加起来和最大的连续的一串数，如果有多串数相加起来都是最大值，要全部返回。（据说是leetcode题目，我能说我没刷到么＝。＝）
2. 假设用一个N叉树存一个员工管理系统，从上到下按照级别一级一级递减，最顶端是CEO，往下是各个级别的经理，再是普通员工，所以每一个节点都是一个员工。现在给出任意一个节点，要得到从这一点开始往上的职位层级，问要怎么做，不用写代码，说一说就行。

问的是System Design：
假设Google有一个内部系统，可以接受来自员工的各种订单，例如定个鲜花，定个蛋糕之类的。内部系统会连到一个外部系统，这个外部系统会处理这些订单，发给相应的vendor去接单。
问，这两个系统有哪些问题需要考虑。

OO Design：
一辆车有Year, Make, Model。假设一个Dealer有很多很多车，如何才能得到每一种unique car有多少辆。unique car的意思是说，Year, Make, Model这三个特征，只要有一个和其他车不同，就是unique car。

http://www.1point3acres.com/bbs/thread-137928-1-1.html
可能是因为我做得慢，总共就做了一道题，就是一个游戏。
input string：“+++--++-+”
游戏规则：每人每次可以 flip "++" to "--"（必须是相邻的）

第一问：generate all possible moves. from: 1point3acres.com/bbs
第二问：determine if this player can will
Extra：这两个问题的implementation的Big-O
all possible moves指的是“从目前的input string开始，仅进行一次flip操作的所有可能”，还是“从目前的input string开始，进行K次交替flip操作（直至有一位玩家胜利），然后返回所有的flip sequence”
Answer: http://massivealgorithms.blogspot.com/2015/10/leetcode-flip-game-ii-jcliblogger.html

http://www.1point3acres.com/bbs/thread-133413-1-1.html
多叉树，每个节点是一个整数，求书中最长递增路径比如5,6,7,8,9

四叉树压缩黑白图片，一个图片递归分成2x2四部分，如果一个区域颜色一样就设为叶子节点，算黑像素比例
follow up是给两个图片，把白色视为不透明，黑色视为透明，重叠在一起，返回一个图片，都用四叉树表示

一堆密码箱，每个密码都是四位0-9之间，算一个暴力破解序列，包含所有可能的四位序列，让这个序列尽量短
给了一个贪心算法，代码写的比较长，而且没bug free
这个问题是一个npc问题。而且应该是求一个Hamiltonian cycle的问题。
因为所有数字是等价的。具体方法是从0000开始维护一个窗口变量，开始设为3，表示和后一个code重合长度为3，枚举第四个得到00001，重复这一步骤。如果发现枚举到的code出现过就缩小窗口大小。判重用hash
DFS方法。这个题的主要问题是你要能说清楚这样做下去能够得到所有的4位数字组成的密码。
我是把这个题想成了一个图的问题。然后可以用dfs放来做遍历图。但是我不能证明dfs遍历的过程中，每个点只被走过一次。
其实是一个等比数列，等比数列有求和公式，当时需要算 x^N, 如果直接N个X相乘就是O(N)，  但是这个没必要，比如 2^4 = (2^2) ^2
矩阵快速幂.

系统设计题，设计google map后端存储, 怎么scale

求sum(n^i) 就是1+n+n2+n3+...+n^N，快速写了一个O(N)之后让我优化，其实这个二分O(lgN)很容易想的，但是当时用了很长时间表现不太好。
第二题是个矩阵，每个节点是一个计算机，计算机之间传一个文件的cost是节点值x路径长度，选择所有计算机为接收端，求所有文件传输的cost
快速写了个暴力方法. visit 1point3acres.com for more.
尝试动态规划无果.

后来想到可以cache所有行列的cost和，正这一边反着一遍，然后状态转移就是O(1)了，但是没时间写了，在他提议下写了一个一维特殊情况的代码，中间有个加号还忘了写，算是sloppy coding吧

http://www.1point3acres.com/bbs/thread-137840-1-1.html
2. Given a list of words, find two strings S & T such that:
a. S & T have no common character
b. S.length() * T.length() is maximized
Follow up: how to optimize and speed up your algorithm

3. Word abbreviation,
e.g. Between=>b5n,  friend=>f4d
Follow-up: implement
Bool checkduplicate(string [] dict, string word)
E.g. {feed }, feed => false;  {door }, deer =>true;  {dare}, deer => false
如果dict里有word 和input word的abbreviation 一样，则return true

abbreviation是一个长度为3的string, [first char, numOfCharsInBetween,last char].
trie里面存的是abbreviation，这个tree的height是3.所以每次query的时间是O(1).
http://www.careercup.com/question?id=5648469500887040
感觉这个map可以进一步简化吧，存成map<Abbreaviation,int>可以不，存abbreaviation出现的数目，只要索引出来大于1就return false
我的理解是trie node还要加一个count的变量，每次加入以该node结尾的单词就count+1。这样和用hashmap的原理是差不多的，好处就是trie用的空间小

When use hashmap for dict, consider whether u can use Trie
http://www.1point3acres.com/bbs/thread-134092-1-1.html
android 图形解锁密码问题，思路就是dfs，注意一些special cases，具体就不说了，有安卓的自己玩玩看。感觉图的dfs bfs g家很喜欢考，之前面经就有很多，这次楼主遇到两题，所以大家准备的时候注意在白板／白纸写一写哦。思路跟小哥边讨论边优化，代码写的还算顺，就是优化之后有个小 bug被指出来了，囧。

上来先问有什么问题，不按常理出牌呀。。。
问了个包装string，搞一个copy on write 的string 类，要跪应该就是跪在这一轮了，会的一定几分钟就秒了，楼主偏底层的东西不熟，c++的玩的也不好，做的很慢，最后deconstructor没时间写了，哎，非常担心这一轮的feedback，不过小哥很nice，不断给hint引导。
c++的注意这种跟memory 有交互的问题，我看之前也有很多包装iterator的题，尤其java的喜欢考，g家还是很喜欢这种问题的，大家关注一下。

  3.2 问了个很简单的image symmetric，楼主刚吃完饭，脑子有点晕，没有秒，哦呵呵呵～我俩都有口音，交流不太好，小哥就直接让楼主code，还好写着写着俩人在一节奏了，有个bug被指出，感觉表现不好
3.3 image connected component，类似leetcode island那题， dfs／bfs 都可解
3.4 如果是symmetric 上一问怎么优化
最后还是表达了满意，不知道总体结果怎样

log requests，有id，server给时间，有开始，有结束，设计实现functions， log到file。
不是很偏设计，不知道是不是自己比较渣，小哥没让考虑concurrency，大数据什么的问题，也可能是简单的弄完时间已经差不多了，楼主想是不是自己太渣，还特意问了还有其他问题吗，小哥说没有了，不知道是不是安慰我，呜呜呜。。。

之前准备的segment tree，index tree，各种iterator，rolling hash，各种字符串matching的dp问题，因为之前挂了微软的bitmap问题，还复习了花式bitwise operation，都没有遇到。但是也没有遇到原题，感觉google出题确实灵活，之前看大家说的google面试会就是会，不会就是不会，诚不欺我。。。。

http://www.1point3acres.com/bbs/thread-107194-1-1.html
1. Wiggle Sort

- there’s a set of marbles

- take turns removing 1 or 2

- winner removes the last one

- you get decide who goes first

我大概解释下，就是有俩人玩儿个游戏，现在桌上有n个弹球，你和你的对手轮流取，一次一个人只能取1个或2个，把桌面清空的那个人胜利。

你来决定谁第一个取弹球，在不同弹球数量n的情况下，请问你是否能制定出一个必胜策略？

OK以下是我的解答：

先枚举一些case归纳（OP= opponent）：

n=1,2 I first (很显然我可以一次拿完直接胜利)

n=3 OP first (让对手先拿，他拿一个我就拿俩，他拿俩我就拿一个，最后一定是我赢)

n=4 =1+3 I first (我先拿一个，然后轮到对手，立马转化为n=3的情况，最后一定是我赢)

n=5 =2+3 I first (我先拿两个，然后轮到对手，立马转化为n=3的情况，最后一定是我赢)

n=6 =3+3 Op first (相当于两个n=3 case的重复，此时应该让对手先)

n=7 =1+3+3 I first （这个不用解释了吧）

所以最后归纳出的策略就是：

n=number of sticks

if(n%3==0){OP first}

else{I first}
http://www.1point3acres.com/bbs/thread-135782-1-1.html
第一题：给两个数组，第一个数组用0和1组成，1表示升序，0表示降序，根据这个数组将第二个数组重新排列，让第二个数组符合第一个数组所表示的规律。比如第一个数组里第二个数是0，那么第二个数组里的第三个数就要大于第二个数

kth element of two sorted array. 我就说俩数组合并再找，但是慢，三哥问你咋优化，我思考（装B）一会后给出了最优解

第二轮，亚裔小哥加白女shadow，问了个设计题，设计灯泡开关控制之类的，总结到最后是一个类似于merge intervals的算法，这时时间不多了，匆忙写完code已经没时间找bug了，中午吃饭时才想起写出了一个比较严重的bug···
第三轮，国人小哥，问的数据结构设计

第四轮，白人小哥，第一题忘了是啥了，比较简单，第二题是设计个小游戏
http://www.1point3acres.com/bbs/thread-70019-1-1.html
1）在地址栏输入url address后整个过程，我说的比较大致，连tcp都没提到，network实在是白学了。说完他问我web proxy server知道吗

2）1枚硬币，来选择出1-3的数字（比如3部电影，选出看哪一部），我想很简单啊，投两次不就有0-3四个数字么，不可以选出来了么，然后他说万一投到0咋办，我说那继续重投，毕竟1/4的概率不是总能遇到的，然后他说可以优化这样，如果投到0，那再投一次，那么就有0-7 8个数字，那么可以：1-2 -》1
3-4 -》2
5-6 -》3
0-7 -》再投一次
真是个好办法（感觉很dynamic），下次实际可以运用了。
int choice()
{
result r;
do {
      throwit(r);
      if(r.r1 == 0 && r.r2 == 0) { continue; }
      if(r.r1 ==0 && r.r2 == 1) { return 1; }
      if(r.r1 == 1 && r.r2 == 0) { return 2; }
      return 3;
} while (true);
return 0; /* something wrong */
}
3）binary tree的max height
0）选一种排序算法解释，我选了MergeSort
http://www.1point3acres.com/bbs/thread-138859-1-1.html
1. longest consecutive numbers
但要考虑重复，而且numbers无序，并且要输出最长的numbers,
2.第1题的follow－up
numbers变成二叉树，找longest consecutive numbers 1

2 3

5 3

→ 1, 2

http://www.1point3acres.com/bbs/thread-133256-1-1.html
1.白人给了个API 一个商品每个quantity的cost给出来了不是linear的关系现在给一定的钱问怎样买最多用binary search做出来了但很多edge cases 比如买一送一的情况呀什么的要提前问好然后问了ood的一些基础问题接着就是谈笑了. 2.白人先问了问web的一些问题 LRU CACHE 但是要求只用一个多余的sentinel node当头当尾做弄个环切来切去玩
3. 白人问了一堆java的问题 abstract class, final, singleton class 然后做题具体记不太清 interviewer表述也不是很清楚大概是一个不断运行的东西一直有各种各样的小interval进来有overlap 一旦某个小interval运行结束了就立刻print出这个完整的interval 我用linkedhashmap做的主要是考queue 后来问interval特别特别多时注意什么之类的
中午吃饭的哥们告诉我他面了三次google才进来。。
4. 白人 DP 这轮完全跪了给了一个长方形的版面和很多CSS小板块假设这些小板块都一样宽但长短不一怎样排列这些小板块使整个长方形版面占用的总共长度最短不熟DP一紧张无法思考了5. 国人+shadow，放水给了两道Leetcode稍微变形的题
http://www.1point3acres.com/bbs/thread-138233-1-1.html

Onsite interview

1.

[ 0 2 1

1 0 1

0 是障碍物，2是食物，1是可走的路径。要求着到可以走到所有食物一次最短的点。我用bfs做出来，最后的时候他说我有个case没考虑到，就是没有最佳路径的时候怎么办。其他的都没问题。

2. given a infinite stream of real number, 随时找median. 我说用 2 heaps，但是他说infinite的数字要infinite的空间怎么办。然后我就说2heap应该也可以，就是保证一定size把多余的扔掉。我又挣扎说了一些其他方法，都不大行。最后他说你用2heap做做吧，我大概做了出来，然后他就给我看了个case说这个方法什么时候会失败。他最后说其实实际应用中2heap可以用，只要n够大就行。感觉这个面试比较惨。

3. given a probability = [.5 .1 .2 .2], label = [A B C D], write a data structure that generates the label based on the prob. 我说先找cumulative probability［.5, .6, .8 1]，然后弄个0～1之间的random数字比较过去找它的位置就好。他就说有没有更快的方法。其实他想叫我用binary search，但是我一直以为是不是有什么O（1）的解法，浪费了一些时间后才发现原来他想要binary search，最后弄出来了。

4. first is summary missing range problem. ［0 1 2 45 99］ output “3-44，46-98”。做了出来但是做法没有最优，我说可以改，他就说我相信你可以改就下一题了。

second is given a dict of words [aba, cbc], find the letter to letter probability. b->a 50%, b->c 50%. 这个做的还可以，有一个小bug

5. hamming distance between a and b, a, b < 2^64. 这题很快就做了出来。就是把a^b>>i &1 64 次。然后他就说要想办法speed up，说给我64G的ram。我想了很久最后说可以搞个2^8的字典，然后把a^b分8段比就好。他就说为什么用8，然后就问我2^8的字典要用多少空间. 我没记空间大小的那些知识，所以不会做...几经提示后结论是可以用2^32的字典要4G空间，这样比两次就好。他最后又问说如果你用这个方法，但是ram只有2g，那会发生什么情况。我就说那会有error吧。他就说什么error。我说不出来。他就说“you clearly have never used win 95 swap space”. 然后差不多就结束了。我觉的最后这个哥么应该给我差评了。

1. 应该多考虑corner case，总是写完被人问有什么case会有问题

2. 尽量一次算法最优，像什么能用binary search的时候就不要用O(N)的

3. 一些cs基础的东西要懂，什么swap space的。转行不容易啊。。

这题的奇葩点是说有无限的数字，所以heap的size要有上限n。但是当你有上限的时候，一个一直递增的数列就会給你问题，因为会有可能把你的median給扔掉。
第一题历遍每个食物，然后算这个食物到每个点的距离。把每个食物到不同点的距离加起来，最低的就是answer。

第一要考虑食物被隔开的情况，事先要讨论好怎么处理而不是事后被指出。题41最优是o(n).我遍了个o(n2)的

第4题是sorted。 letter of probability的题目是这样，做一个27x27的matrix， 26 个代表字母，最后一个代表开始或者结束，然后你每个字母走过去找它出现的次数，最后除一下row sum求概率就好。比如 [aba, acb]，a之后出现b的机率是50%，出现c的几率是50%。 b之后出现a的机率是50%，b最为结尾的几率是50%。 a作为开头的机率是2/3， a最为结尾的机率是1/3。

补充内容 (2015-7-18 05:50):
说错了， a－b的机率是1/3， a－c的机率是1/3， a－end的机率是1/3.

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

Dynamic programming, maximize vacation days, want list of offices

上来直接问题，一直做了52分钟，挺容易想到DP。但是在实现的时候有很多细节需要考虑。楼主这面面的不好，虽然状态转移方程写出来了，但是实现的时候被指出了很多bug。首先要注意初始化，其次是填二维表的顺序，最后是result存在哪里。面完面试官觉得还过得去，因为毕竟代码写完了。

第二轮，烙印：

上来问了简历，楼主简单地说了下most challenge project，然后开始做题

timestamp, color, find first occurrence of color and reserve the original order

由于上一轮多用了时间，这轮问的这题比较简单。就linear scan，期间用hashmap去重就可以了……不知道他出这题啥用意

overlapping meeting intervals, return the first overlapping interval

这题楼主先说了brute force的解法，O(n^2)。然后提出先sort的解法，O(nlogn)。然后楼主就开始沉思是否有O(n)的解，想着想着被烙印打断。他说nlogn的解法is acceptable，然后叫我实现下。我心里就想着这不是很简单吗……就乖乖地开始实现了。实现完了以后，他就问我你的code是不是有bug？我看了半天说没bug啊，他看没时间了，就给我指出来一个edge case。所以提醒大家遇到简单的题，还是得好好想仔细了再code。

music list, if shuffle is possible or not, test cases

这轮比较扯淡，国男带着自己的电脑过来的。问完题目就自己闷头开始debug，可能在赶deadline……题目不难，但是所有需求没有马上展开，是在我和面试官不停地交流过程中发现的一些隐藏需求。然后被要求code，我就开始写代码，没有一遍bug-free。面试官看了下说有bug，然后又干自己的事去了，我改好给他看，他又说还是有bug，来来回回几次，他才说好。然后他一看还有15分钟，说自己也没next problem了，叫我要不写下test case。写完时间也差不多了，叫我问他问题，问完结束。

第四轮，亚裔 + 白男shadow：

上来先问了下简历，花了大概5-7分钟时间说了most challenge project

wiggle sort

这题我面试前就准备过，听完题目描述，我便成竹在胸。于是小演了一下，先给了sorting的解；然后若做沉思，再给的O(n)解答。面试官很满意，可劲喊good。

longest path length from node to node

这题和leetcode上的max path sum很接近，也算半个原题。我讲了思路，写了code，面试官表示赞同，并拍了照。

楼主准备了surpasser, iterator of iterator, quadtree intersection, threaded binary tree, popular number, maximum submatrix sum等题
你有一个music的播放列表，里面的歌曲unique，但是播放列表的长度未知。
这个音乐播放器APP有两个模式：random模式和shuffle模式。
random模式就是每次随机播放列表里的一首歌；

shuffle模式就是shuffle列表里的歌，然后顺序播放，放完以后重新shuffle，再顺序播放；
现在给你一个播放历史记录，要求你写一个函数来判断用户使用的是random模式，还是shuffle模式。
http://www.1point3acres.com/bbs/thread-138100-1-1.html

算法题（？）一道，给一个

public interface Table {

// Set the cell at (x, y) to value.

public void set(int x, int y, int value);

// Compute the sum of values from (0, 0) to (x, y), inclusive.

public int sum(int x, int y);

}
让我实现set 和sum。
给定了size，但要求dynamic fixed size.
我选了2d array

实现了set， sum

要分析time complexity.

set O(1)

sum O(n^2)

问能不能优化

又建了一个表计算每一行0 到当前位置的值，将sum变成了O(n)又问如果是set不常用sum很常用能否优化

干脆将第二个表换成计算0,0 到当前位置的和，这样sum变成O(1) set变成O(n^2)

然后又问那第一个array还要么？想了一下不用了，可以用data[x][y] + data[x-1][y-1] - data[x-1][y] - data[x][y-1]计算原始值，然后计算差值并叠加即可。

最后又让分析了下时间复杂度，

set O(n^2)

sum O(1)

http://www.1point3acres.com/bbs/thread-144220-1-1.html
1. 老白1号，冲进来寒暄两句就说这是网络设计题（OOD）。。你听说过TCP和UDP？我表示略知一二。。然后说设计个firewall，给一个config表（装满了source 和target的map以及allow and deny），让我写个function，take一个source ip 和 port和 target port and ip，能return 是否allow access。自己设计各种东西from scratch。说白了就是把config表变成一个hashtable，并且不需要写parser（parse config假设已经完成了）。然后follow up，如果config给的是 src ip-> dest ip以及 src ip range->dest ip range （比如126.115.0.*）的混合，你怎么判断一个request是否allow。这还扯到了什么ip mask之类的东西，反正我也不知道在说啥。。。反正我就不停的搞hashtable，各种map，然后各种假设有loop up function，比如给ip和set能知道是否ip在set里，给ip能知道对应set。。最后他居然表示很满意

2. 老白2号，多年刷题终于遇到原题了，上来 welcome to google变成google to welcome。。。果断写完，然后问我inplace咋搞，我偷懒说把input变成string array可好？他居然同意了。。那还做毛，直接换就行了，他表示不错，那如果给你char array呢，比如google变成[g,o,o,g,l,e]，我表示sub出头单词和尾单词，中间recursion return，然后换位子 append就行。他表示满意，问了一下复杂度和test case。然后出现了merge k sorted array（居然不是list？），欣喜若狂的我最终还是没能忍住。。piorityqueue拍脸秒杀。然后居然还有一题，说会不会多线程?然后提到blockingqueue里边的设计，比如如何唤醒blocking线程，我说用轮询flag，他表示能不能不用flag，我说signal。。他表示api是啥，我居然忘了。。wait/notifyall是答案。然后问我如果加一个timeout，你怎么知道是wait timeout继续运行了还是notifyall唤醒之后继续运行？我表示取时间差，如果和timeout一样就是timeout否则就是notifyall提前唤醒（口胡的）。然后他表示很对。。。

3. 中国人坑我。。上来就是题，给list of edge还原成tree(可能多个child，非balance，非bst)，我用hashtable存<int,node>因为他给我的edge里边放的不是node，是unique int id。再建立一个hashtable存node与incoming edge数量。扫一遍edges，唯一一个没incoming edge的就是root。他居然没听懂。。表示我思想很吊，让我先code。然后别人都拍照，这哥们手打我的代码。。让我写formal每行，巨浪费之间。follow up是如果给你的edges不一定能form一个valid tree怎么办？我就说不valid一共三种，多个root，loop，一node多parent。然后我说我那个存incoming edges的table是不是碉堡了？然后我分别check三种情况，这时候出问题了。只看incoming edges还不够，如果1->2 3<->4这种tree，符合只有root没incoming edge但是这里有两颗树，所以应当找出所有node里的可能成为root的，以他做dfs，如果能访问到所有node（one head）且没有visit到已访问node（loop，two parent），那就可以了。。。时间到了，他说再给你5分钟，给爸爸写出DFS。。。你在逗我？

5. 老白3号，给一个没sort的list, sort成 1<2>3<4>5....的形式。绝壁有这么一题，我绝壁没看解法orz。。只能说sort然后swap，还是nlgn。。然后果然要求写linear time，然后就嗝屁了，提示说顺序有毛关系，你写几个例子试试，恍然大悟，只要查看当前位要求然后和后边swap或者continue就行，swap上来也绝不会screw up之前的已经排好序的（要求说为什么，举个例子就行）。然后写代码，bug free。第二题说json的转换，给string转class，给class转string。最近学校作业才做过，写的一点问题没有。然后follow up说我要一个generalize的能用于所有class的这个方法，我说跪求得到class内部结构的API，不然写P？他说默认有了。。然后我说一共8个基本类型，重载8个，然后class一个，用你那个API，给每一个成员变量call对应的重载方法，parse我就不写了你看着办，结果append就行。他表示很好，路子很对，代码就不要你写了。

http://www.1point3acres.com/bbs/thread-107225-1-1.html
果你是manager，如果介绍你的组，来让他加入（当时lz就蒙了，这是behavior？？）扯扯又扯到我intern的项目上了，讲得比较细

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

在g家干过，对这个情况略有了解。这种情况一般是你的packet不够strong，跟别人比起来不够competitive，但是也过了基本的bar所以给你缓冲的机会。你的packet如果有manager看上，会安排你们talk，然后hr会向manager收集对你的feedback。如果feedback是positive的，那么这个positive feedback from hiring manager相当于是你packet的新的有利砝码（和向你要学校老师推荐信一个道理，to strengthen your packet），会被加进你的packet，然后你的packet会被重新提交给hc去review。重新review三种结果：1. hc觉得可以了，给你offer; 2. hc觉得还是缺点什么，但是又没到直接rej的地步，于是打回去继续match manager，重复上述步骤；3. hc被你弄烦了，给了个rej，结束整个process.
其实没有啥好准备的，我所认识的hiring managers都觉得能被安排talk的其实skills都已经过关了，只要你不是口语交流能力太让人心塞，都会给你positive feedback，所以一切都是看hc，看hc其实就是看rp，谁知道那天他们心情好不好，101堵不堵车。。。
我的建议是——找好下家。google的程序实在是太慢，而且hr说话很有技巧，总会给你自己很有希望的错觉，然后拖了你三四个月大半年给你一句sorry。不要太过expect，理性考虑其他的选择。

http://www.1point3acres.com/bbs/thread-73684-1-1.html
0. manager's experience with Google
1. team - what do they do, team chemistry, (more competitive or laid back?)
2. technologies used for work?
3. product development direction?
4. potential project for me? will it be shipped?
5. how is living in XXX, if it's not MTV then: relationship with the headquarters
6. expectation from me? possible course that might help me better prepare for the project?
7. introduce my past project/experience
8. any more questions for me?
http://www.1point3acres.com/bbs/thread-90080-1-1.html
1. 给一个整数(1-3999)，转换为罗马数字
2. *(char *)0=0; 这个语句执行会产生什么结果。follow up virtual memory, page table permission之类的概念，还有hypervisor的shadow paging

第二轮
1. 程序对于相同的input有时会crash有时会正确。可能原因是什么
2.给你一个很大的字典。一对词如果不share 任何字母，比如dog, cat不share字母，而dog, boy就share一个o，则是interesting pair.找出所以interesting pairs中长度乘积最大的pair.输出这个乘积。
能不能证明n^2是upper bound?

第三轮。
1.给两个四分树，求两个图重叠的1的个数
2.怎么continuous deploy
3.run length representation的合并

第四轮
1.将一个数组right rotate k次。要求O(N),in-place
2.shuffle一个数组，使之A[0]<=A[1]>=A[2]<=A[3]

第三轮比较难，是一个computer vision的research面的，我完全没有学过computer vision.不过我跟他谈二维线段树，他表示很满意的样子。说有时候二维线段树确实比四分树好。

第四轮，第二题当时只有10分钟了。不过当时一看到shuffle这个词就想到swap.后来一套，也把O(N)的算法YY出来了。
http://blog.csdn.net/ljffdream/article/details/44765311
2. Given a source word, tart 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.
http://www.1point3acres.com/bbs/thread-141728-1-1.html
还是那个不相同字符个数不超过M的最长子串长度…………我当时就惊了，一分钟写完code，然后小哥拍了照，说follow up，如果这是个字符流，只能遍历一次，怎么办，我当时想的很混乱，写的也很混乱，不知道小哥怎么看，反正这面不是很好。
二轮，中国小哥，人特别nice，让我自我介绍了一下，然后问了我malloc和new的区别，析构函数为什么不能抛异常，异常的机制，c中内存分配方式的情况，然后用怎么分配一个二维数组，。然后写了四行代码…………小哥真的很nice。到后面我专业术语我实在没法用英语说了，全用中文了。
三轮，hk小哥，英文，设计买票系统，有几个requirement，每人只能一次看10个seats，每个人不能同时看相同范围的seats，一个人只能一次book一个seat，两分钟内没有book自动退出。然后就设计了几个api接口，然后设计了底层database，然后小哥一直针对系统问问题，一直给提示，我就顺着他的思路说，加cookie，session，blabla之类的。人也很nice，一直都给hint
四轮，白人小哥，小哥英语讲得太快了，是这四轮里，我听得最费劲的，我听力和口语都只是正常国内学术的水平，所以一直在pardon中……，很简单的两道题……一道是求一个数二进制表示中bit为1的个数，二是设计一个类，实现insert，remove，poprandom一个字符，很简答的，我开始用set和vector，然后小哥一个个让我分析复杂度，其实函数超级简单，所以复杂度也是一眼就能看出来，就跟vector和set本身的操作复杂度一样，后来小哥说popRandom复杂度可不可以降一下，我说想想，然后把vector去掉了，直接用set来做，然后就降到O(logn)了，然后就结束了，随便问了几个问题。

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=137325&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
数字只有 0， 1 ， 2 三个值，设计一个存储结构，实现数组操作，高效的利用内存。
解法：用 2bits 存储一个，这样一个32bits 的 int 可以存储16个字，实现 get(int index) 和 set(int index , int val)

Onsite 1
说有一个视频文件和许多音频文件。有好多数组，数组里的值是一段段的视频或音频文件，其长度为数组值的段。求sync point。
如 [1,5,8,9]
[1,4,14,23]
这两个文件的 sync point 为 [1,14,23]
merge sort
可以理解为数组里的值是一段段的视频或音频文件，其长度为数组值的段。第一个数组 [1,5,8,9] 第二个数组[1,4,9,9] 这样对于第一数组，所有时间轴上新的...
所有时间轴上新的起点为[1,6,14,23] 同理第二个数组[1,5,14,23] 所以所有的sync point为a[1,14,23]

Onsite 2

一个数可以表示成 n = x*x*x + y*y*y = z*z*z + d*d*d，一个数可以表示成 2个数的立方和，至少有两对这样的数。
给定一个n，求所有小于等于这个n 满足条件的数。
我先建的一个表把1到t的立方都求出来，之后类似类似3 sum求解

Onsite 3
设计短网址服务

Onsite 4
给一个图让求图中所有的正方形
怎么存图，数据结构自己说的算。自己想了半天，没说出面试官想要的。最后面试官给了提示。
class point{
double x;
double y;
point west;
point east;
point north;
point south;
}
之后写了个暴力解法。

Onsite 5
面试官想演示贪吃蛇的游戏，之后让你想出几个类，来实现这个游戏。还有简单说下算法。之后实现其中的一个。让我实现吃豆的逻辑。

http://www.1point3acres.com/bbs/thread-147010-1-1.html
2. 这道题说起来比较复杂。假设你有一张表，这个表是每个字母在其他字母后面出现的概率。然后这个概率是根据一些东西算出来的，比如说一本字典。
假设字典是 ["cat", "cap"]
那表格就会是
a c p t.
a 0 0.5 0 0
c 0 0 0 0
p 0.25 0 0 0
t 0.25 0 0 0

ok，不知道格式会不会坏><，总之就是你有这样一个表格，然后他们的概率加起来是1嘛，但你不用担心这个表格是怎么来的。
然后如果你有这本字典，让你返回长度是4的最可能出现的单词（保证只有一个）.
follow up是如果没有这本字典，你如何算长度是4的最可能出现的单词（保证只有一个）
再follow up是，假设你现在根据比如说google search query有一个，2014年最经常搜索的单词list，然后根据这个list算出一个概率表格以及最可能出现的单词，然后现在你知道2015年添加了一些单词，如何更efficient的算出新的概率表格以及最可能出现的单词。

有字典的我就说最简单暴力的方法说把字典遍历一遍所有单词的概率算一遍最后得出最可能的单词.

然后没有字典的，有点像trie tree的感觉，dfs算最可能的单词

维特比算法就是给你一个状态转移概率矩阵，求最大概率的路径

matrix太大那个后来很多思路都是面试官在说，感觉他只是想和你讨论讨论，看看你有没有什么思路。
我当时说的是，把matrix分成四份，在四个machine上分别计算longest subsequence，然后边界要特殊处理，因为边界有可能会连接到另一个小matrix。
在边界处理这边，后来是面试官提供了一个思路，他说可以用类似hashmap的数据结构把边界上在这个小matrix连着的点存起来（一头，一尾），然后一个一个小matrix的边界再连接起来算。

我讲的有点乱><，当时面试官也没有再go to detail，讨论了一下思路，然后问我比如那个大matrix上最长的一条是一个U型啊，或者画个其它形状，问我会怎么实现刚刚讨论的算法。

我当时问他matrix里面有没有重复，他说先不考虑重复。实现code实现的是descending的，然后让我稍微讲了下有重复该怎么办，没让写code

1. longest common prefix 没让写code，就谈了idea
2. longest common substring
follow up是优化空间（因为楼主一开始用了n*n的space，大叔让我用n）

第二题longest common substring. 我会用第一个string 建suffix trees , 然后剩余的string 一个一个用suffix tree检验如果string average length 是n 这样tree 的space 是<= o(n ^2)

建suffix tree 应该是两个string的和吧，s1: 'abcdefg', s2: 'cdemx' 通过 'abcdefg#cdemx$' build. 这样时间复杂度就降低了， O(m+n), 比起DP的m*n 好多了， space也变成了tree的大小。

第四轮是白人小哥，人也挺好的，全程狂写笔记
就一道题，滑雪。跑test case跑得楼主口干舌燥+腰疼
follow up是如果这个matrix特别特别大，一个machine装不下要怎么办。

就是设计一个电梯系统，我写了building，floor， button， elevator几个class。然后用了一个queue装这个elevator接下来要去几层这样。你可以设计的很复杂，也可以很简单。我写了最简单的就是，queue里面是先来后到的。
我记得还有一种比较复杂（但是智能）的设计是用状态机。= =然后我觉得太复杂惹就没有管它直接写了最简单的~
http://www.1point3acres.com/bbs/thread-146028-1-1.html
第一个人问的问题是给一个二维矩阵，里面有一些墙，一个起点，一个终点，每次行走类似于滑冰，如果没有墙，则可以走到底，问最短路径怎么做。我用bfs做的，之后follow up让你返回起始究竟是选择的哪个路径。第一个人面试的时候没面试好，前一天没睡好，头一直疼。。。。
用BFS就可以啦，遍历每个节点的时候用map保存起始节点到当前节点的路径，遍历到终点的时候返回就可以了。
用一个class来定义每个节点
class node{
int x,y; //位置信息
vector<*node> //路径信息
}

补充内容 (2015-11-16 04:27):
用queue来做bfs, 想要优化的话改为用priority_queue做GBFS(greedy best first search) class里面再加一个变量表示当前节点到终点的直线距离，每次queue里弹出当前距终点最进的节点。

第二个人先让我说一个我遇见的bug，然后写题，题目也是一个二维矩阵，里面存着各种符号，如果横着或者竖着连续出现三个及三个以上重复的就返回false。我就brute force做的。。。。。不过小哥很nice，沟通不错，之后先让我说test case，时间复杂度之类的，然后就是如果用多线程来做可以怎么优化，就是每个thread扫不同行。然后就随便聊了聊就完了。

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

（1）Google: 店面Two Sum(hashmap), Telephone number combination(dfs), string 处理，positive feedback, onsite安排在new york office. Onsite 题：dfs, holiday plan (dynamic programming), 设计数据结构使找平面上某个点一定距离内所有点最优，搜索设计（json, restful api)... 结果： Reject

http://www.1point3acres.com/bbs/thread-148857-1-1.html
1. skip Iterator 和zigzag iterator for n collections。做好LC就好了。
2. 就是一个二维数组代表每个点的海拔，然后每天都下一次雨，下雨之后整个水位会长1，从0开始，然后你坐在船上从左上角出发，只有当雨水高度大于周围海拔高度的时候，你可以漂到周围那个点。问最少用几天可以到达右下角
开始地形是
1 2
3 4
然后
第一天过后雨水高度是
1 1
1 1
第二天过后是
2 2
2 2
。。。以此类推。面试官说你先给一个能work的代码就行。楼主就DFS，然后面试官说给复杂度，楼主给了，面试官说优化，楼主说了DP，给了复杂度。面试官很开心。
3. 第三个题真的特别特别长，不过核心就是fisher-yates random那个算法。面试官自己都说这个题真的很长，而且不容易懂，但是他希望能写完代码。楼主就弄懂之后就开始狂写。写完之后说这个题其实你有个地方应该clarify一下，不过没什么大关系。
4. 简单说就是摩斯码。真心记不太清了。刚吃完饭，面试官很好说热身一下，先给个单词，然后给每个字母的摩斯码，然后产生出来这个单词的摩斯码。然后反过来，给个摩斯码，同样给出每个字母所对应的摩斯码，给出所有可能得单词。刷好LC就行了。有个很像的题。然后注意分析复杂度。

http://www.1point3acres.com/bbs/thread-148930-1-1.html
给的题算查找吧。给定一个vector，找一对i, j 使得A[j]=A[i] + 1并且j - i最大。follow up是A[j] > A[i]即可，要nlogn。后面LZ脑卡并没有自己想出来解法。。。小哥给了大致解法让我implement查找，我说那就binary search然后写了写又跑了个test。

我是直接hashmap存同一value最大和最小index做了个O(n)的
我就直接unordered_map<int, pair<int, int> >存每个val的第一次出现和最后一次出现的index，之后遍历这个hashmap找有木有key - 1就好了。。。于是就是O(n)。c++的unordered_map也是非常神奇，我不知道如何做到O(1)取begin和O(1)next的。。。

第一题小哥用另一个vector存了相当于cumulate min，比如{6, 2, 4, 5, 7}那就是{6, 2, 2, 2, 2}，然后从后往前每个element做个查找就好。

第一题是判断两个树是否相似。相似的定义是根节点value一样且两个子树相似（可以左-左 + 右-右，也可以左-右 + 右-左，‘-’表示两棵树子树的对应关系）。recursion解决之后三哥问了时间复杂度，LZ开始脑卡，说是4^n，然后让优化。LZ就在白板上写啊写说感觉用个map搞类似dp并不能优化似的因为木有重复对比（LZ至今没想到怎么拿map合理存树的那个结构，当时是说map套map来存子树的对比结果）。。。三哥说要看你怎么用了，还提示我说array是怎么看相似的。。。总之又想了两分钟未果，三哥说要不我给你换个题吧。题目忘了不过似乎用BIT搞的，三哥表示可以。然后又出了一题说如何求3个8bit数的平均值（尽量准确），CPU是8位的且不支持浮点。LZ脑袋还是晕乎乎的，于是先跟他说了2个数的求法，然后说3个数好像不能只用位移和加法（竟然忘了除法这回事），直到最后忽然想起原来没有浮点除法还有整数除法，最后给的算式似乎也是有问题的。。。.

第二题，三个八位数求平均，先加起来的话会overflow，求算每个数先取7位还是会overflow，该怎么做呢？
第二题我从2个数入手和你想的差不多，相当于是(a >> 1) + (b >> 1) + ((a & 1) & (b & 1))，然后从此莫名给自己加上了个不能用除法只能用移位的限定，最后幡然悔悟。。。所以应该是a / 3 + b / 3 + c / 3 + (a % 3 + b % 3 + c % 3) / 3之类的吧。。。这个结果一定不会overflow因为它是三个不溢出的数的平均值。然而最后还是LZ脑卡，写成和2个数运算差不多的格式了，就是a / 3 + b / 3 + c / 3 + ((a & 1) & (b & 1) & (c & 1))。。。在回家的飞机上LZ想一头撞死。。
三个8位数求平均。你可以把八位数拆成两个四位数就好了啊。分别对高四位和低四位求平均。再合并。 ///???

问了个sort linked list。。。LZ脑卡依旧先拿multimap搞的。。。然后大叔不满意，LZ给了mergesort，然后说了几种情况，跑了两个test

经典的二维矩阵update和query，
然后出了个字符串题，问一个字符串是不是完全由同一个子串多次重复形成的
我的思路是先求字符串长度的factor，然后在每次验证这个长为factor的子串能否符合条件之前先小小地剪枝一下，就是看s[factor]是不是与s[0]一样（虽然感觉用处不大。。。），如果一样再去检验后面的。这样大概是O(sqrt(n))？木有仔细验证过。。。

run-length encoding和decoding。。。encoding时候还让我拿两种方法写while loop
http://www.1point3acres.com/bbs/thread-148698-1-1.html
国人大哥放水，leetcode原题：https://leetcode.com/problems/number-of-islands/ 我用recursive 的 dfs写的，挂电话就发现island判断有个巨大的bug，所有test case都跑不过的－－不过面试官似乎也没发现。设计 test case 时候没有想到big data，如果有大量的1，recursive时C＋＋栈会爆掉。我想这个题正确的做法应该用iterative dfs。

给一个无向图，不是全链接，节点上有数字。求最长连续递增数字串的长度
9-1-2-3-4
| |
2-3
答案是4：1-2-3-4
这个题我用dfs做，不过因为对图的数据结构表示不熟悉，又受到leetcode 题目https://leetcode.com/problems/longest-increasing-subsequence/ 的干扰（leetcode上允许不连续！这个题必须是相邻节点）最后写的简直是correct-free乱七八糟的，面试官都放弃治疗了。follow-up 图改成二叉树。

给一个二叉树，求树的直径。dfs，问了复杂度。

在无限数字流中估计中位数。要求可用内存越多中位数越精确。我说用的两个set，和两个heap一样。只是内存不够的时候从maxheap扔最小数，minheap扔最大数。
面试官说如果1 2 3 。。。。。。 10000000 0 -1 -2 -3 。。。。。 -10000000 怎么办，我说random input，面试官说输入流是串行的，不能random，我说用reservoir sampling.

总体感觉G家面试很拼基本功呀，题目小变化多。面试精神高度紧张时，遇到相似的题高兴死了，很容易忽视小差异掉进坑里。从我个人经历感觉G家不要求bug free，而更看重分析题目的过程。-google 1point3acres

http://www.1point3acres.com/bbs/thread-148682-1-1.html
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/thread-148686-1-1.html
第二题有个x,y坐标系的array A[(1，0),(0，1)] 都在一个圆上圆心会给（0，0）
有第二个点的arrayB[(8,9),(12,-5)] 求问对于每个在B array里的点，找出A里距离最近的点

第二题把A的点换成极坐标sort 然后binary search

换成极坐标就可以通过binary search最接近的角度来直接得到最近的点而不用计算距离再比较。计算距离需要O(a*b),而binary search是O(bloga)+O(aloga) 更快
但是使用极坐标来获得角度最近的点不一定是距离的点啊，还是需要计算距离啊
这里我说的极坐标的中心点是圆心。角度最近的点就是距离最近的点。不需要计算距离
http://www.1point3acres.com/bbs/thread-148690-1-1.html
第一题：给一个network of computers， each computer only see its neighbors and can send package to them. Design a protocol to tell hwo many computer are in the network.
就是实现一个protocol，实现任何一台computer都可以知道网络中有多少computer。
第一题估计是个 BFS， package 里面如下变量一个 global count 计算目前 visited 的计算机总数，一个变量标志本计算机是否已经被访问过，这样一个 BFS就可以计算所有的计算机了。

我刚开始就说bfs 被打枪了最后面试官说是dfs
递归的时候把那个set传参就好了
而实际上这个传参的过程也就对应着数据包的流动

个人观点，DFS的call stack操作正好对应数据包的流动。
多走一层递归就意味着把数据包往未遍历的节点传递。
return则代表把数据包往已遍历的节点返回。
中间操作代表修改数据包的内容。
最后出发点是可以收到一个数据包的。

至于BFS么……你可以记录一个节点的指针，代码可以直接去找那个节点，可是数据包飞不过去

第一题应当是每个节点保存拓扑图每当收到相邻节点的拓扑更新和本地比较如果有新的更新就更新本地然后再把更新后的拓扑图发给相邻节点最终每个节点都有完整的拓扑再count一下vertex

第二题： square a very long number. For an example, the number 12 is represented in array as [2,1], 12^2 = 144, the output should be [4,4,1]

Google Interview Misc

Labels

Popular Posts