l****o
发帖数: 315 | 1 Onsite完，应该是挂了。
第一轮，越南人，黑脸
问google search的时候auto complete怎么弄的，答trie, 然后要求实现建树，和给出
所有auto complete的结果。然后follow up了结果有序，如果是非英文情况和在多台机
器上如何优化。都答出来了，写了80多行code累死我了。
第二轮，亚裔，很友好。
leetcode俩题，加一个design，关于音乐app的。都不难，应该没什么问题。
第三轮，中年老美+shadow，正常
read4k，我应该是可以写出来的，不过面试官尝试给hint然后要我按照他的套路写，结
果就写的略混乱。
第四轮，年轻老美，黑脸
有一个无序数组， 和一个数 x，要你找这个数组里triplet, a + b + c <= x 的个数
。这个题只给了基本解之上的优化，回来之后查了好像用什么binary indexed tree.
非常不好想。。。
第五轮，欧洲人？很友好
给你一些string，比如
A: BCD
B:E
F:G
表示A和B, C, D有关联，B和E有关联，F和G有关联，
然后再给你两个字符问这两个是不是有关联，建图， DFS搞定。
第二题问了anagram substring match的问题。 sliding window + rotate hashing 搞
定。
----------------------------------------------------------------------------
--------------
感觉有些题，和我之前看到的一些entry level的面经貌似有点难，不知道是不是把简
历写的比较好看。而且还有4个朋友帮忙强推依然是挂了。希望以后有更多的国人朋友
进Google当面试官。
在美帝呆了6年左右，下一步计划回国了，现在国内热钱也很多，很可能自己会找人一
起合作做项目，如果有人近期也有这个打算请联系我，也许回去后可以一起想想做点什
么。 |
m******s
发帖数: 1469 | 2 Zan
【在 l****o 的大作中提到】
: Onsite完，应该是挂了。
: 第一轮，越南人，黑脸
: 问google search的时候auto complete怎么弄的，答trie, 然后要求实现建树，和给出
: 所有auto complete的结果。然后follow up了结果有序，如果是非英文情况和在多台机
: 器上如何优化。都答出来了，写了80多行code累死我了。
: 第二轮，亚裔，很友好。
: leetcode俩题，加一个design，关于音乐app的。都不难，应该没什么问题。
: 第三轮，中年老美+shadow，正常
: read4k，我应该是可以写出来的，不过面试官尝试给hint然后要我按照他的套路写，结
: 果就写的略混乱。
|
z******g
发帖数: 271 | |
n*****n
发帖数: 5277 | |
m****t
发帖数: 555 | |
h****g
发帖数: 105 | 6 lz是fresh么，你的题目偏难啊，尤其是triplet那道
【在 l****o 的大作中提到】
: Onsite完，应该是挂了。
: 第一轮，越南人，黑脸
: 问google search的时候auto complete怎么弄的，答trie, 然后要求实现建树，和给出
: 所有auto complete的结果。然后follow up了结果有序，如果是非英文情况和在多台机
: 器上如何优化。都答出来了，写了80多行code累死我了。
: 第二轮，亚裔，很友好。
: leetcode俩题，加一个design，关于音乐app的。都不难，应该没什么问题。
: 第三轮，中年老美+shadow，正常
: read4k，我应该是可以写出来的，不过面试官尝试给hint然后要我按照他的套路写，结
: 果就写的略混乱。
|
p********g
发帖数: 7 | 7 楼主面得好难啊。。。看了这么多google面经没见到要实现auto complete的。。。 |
s*****r
发帖数: 43070 | 8 这都什么题啊，颇有一些吃饱没事面人玩的
【在 l****o 的大作中提到】
: Onsite完，应该是挂了。
: 第一轮，越南人，黑脸
: 问google search的时候auto complete怎么弄的，答trie, 然后要求实现建树，和给出
: 所有auto complete的结果。然后follow up了结果有序，如果是非英文情况和在多台机
: 器上如何优化。都答出来了，写了80多行code累死我了。
: 第二轮，亚裔，很友好。
: leetcode俩题，加一个design，关于音乐app的。都不难，应该没什么问题。
: 第三轮，中年老美+shadow，正常
: read4k，我应该是可以写出来的，不过面试官尝试给hint然后要我按照他的套路写，结
: 果就写的略混乱。
|
l*********b
发帖数: 65 | 9 A+B+C<=X 那道题我电面的时候面到了！！！！！答得一般 但是已经是第二题的follow
up了 （原题是 a + b <= x）所以勉勉强强答出来 就到时间了 以为挂了后来还是给
了onsite。。 |
x**********a
发帖数: 1372 | |
|
|
l****o
发帖数: 315 | 11 google 一下 interview read4k 就有。
【在 z******g 的大作中提到】
: 多谢分享
: 请问ｒｅａｄ４ｋ是什麽？
|
s********k
发帖数: 2352 | 12 LZ很强啊！祝一切顺利
【在 l****o 的大作中提到】
: Onsite完，应该是挂了。
: 第一轮，越南人，黑脸
: 问google search的时候auto complete怎么弄的，答trie, 然后要求实现建树，和给出
: 所有auto complete的结果。然后follow up了结果有序，如果是非英文情况和在多台机
: 器上如何优化。都答出来了，写了80多行code累死我了。
: 第二轮，亚裔，很友好。
: leetcode俩题，加一个design，关于音乐app的。都不难，应该没什么问题。
: 第三轮，中年老美+shadow，正常
: read4k，我应该是可以写出来的，不过面试官尝试给hint然后要我按照他的套路写，结
: 果就写的略混乱。
|
d******v
发帖数: 801 | |
l*********s
发帖数: 11 | |
r****n
发帖数: 63 | 15 Bless
btw: 希望lz可以进去G家，以后当面试官~
【在 l****o 的大作中提到】
: Onsite完，应该是挂了。
: 第一轮，越南人，黑脸
: 问google search的时候auto complete怎么弄的，答trie, 然后要求实现建树，和给出
: 所有auto complete的结果。然后follow up了结果有序，如果是非英文情况和在多台机
: 器上如何优化。都答出来了，写了80多行code累死我了。
: 第二轮，亚裔，很友好。
: leetcode俩题，加一个design，关于音乐app的。都不难，应该没什么问题。
: 第三轮，中年老美+shadow，正常
: read4k，我应该是可以写出来的，不过面试官尝试给hint然后要我按照他的套路写，结
: 果就写的略混乱。
|
f******4
发帖数: 51 | 16 投的什么职位啊？software engineer？ |
m******a
发帖数: 84 | |
r****r
发帖数: 159 | |
m****t
发帖数: 555 | 19 triplet那道题，简单的做法和3sum差不多。先排序，转化为2sum问题。对于每个a[i],
计算a[j], a[k] 的 2sum。 头尾 j,k 两二个指针往中间走，if a[j]+a[k]<=X-a[i]
，则count += k-j;最后输出count.
这样的时间复杂度是O(n^2). |
L******n
发帖数: 13 | 20 正解
string 关联那题可以并查集啊
【在 l*********s 的大作中提到】
: string 关联那题可以并查集啊
|
|
|
s**x
发帖数: 7506 | |
v***t
发帖数: 13 | 22 请教Autocomplete那题，用trie的话，怎么处理非ASCII和多机并行？ |
c*****m
发帖数: 271 | 23 2sum问题只能处理等于某数的情况吧，如1,2,7,8, 要求2sum<=9的，这里只有两个，而
不是3个
],
【在 m****t 的大作中提到】
: triplet那道题，简单的做法和3sum差不多。先排序，转化为2sum问题。对于每个a[i],
: 计算a[j], a[k] 的 2sum。 头尾 j,k 两二个指针往中间走，if a[j]+a[k]<=X-a[i]
: ，则count += k-j;最后输出count.
: 这样的时间复杂度是O(n^2).
|
Q**F
发帖数: 995 | 24 int countTriplet(vector &v, int target){
int size= (int)v.size();
if(size<=2) {
return 0;
}
if(size == 3){
return (v[0]+v[1]+v[2] == target) ? 1:0;
}
sort(v.begin(), v.end());
int result = 0;
for(int i=0; i
if(i>0 && v[i] == v[i-1]){
continue;
}
int leftover = target-v[i];
for(int j=i+1; j
int k= size-1;
while(v[j]+v[k]>leftover && k>j){
k--;
}
result += (k-j);
}
}
return result;
}
这个解法应该没有问题吧。
【在 c*****m 的大作中提到】
: 2sum问题只能处理等于某数的情况吧，如1,2,7,8, 要求2sum<=9的，这里只有两个，而
: 不是3个
:
: ],
|
q*****n
发帖数: 22 | 25 你这是立方，等于没优化，最后一步可以二分，就是n^2log n
：int countTriplet(vector<int> &v, int target){
： int size= (int)v.size(); |
m****t
发帖数: 555 | 26 1,2,7,8, 要求2sum<=9
有(1,2), (1,7), (1,8),(2,7), 不是2个，是4个
贴个简单的解法吧。
int le3Sum(int[] a, int X) {
int count=0;
Arrays.sort(a);
for (int i = 0 ; i <= a.length - 3; i++) {
int j = i+1;
int k = a.length - 1;
while (j < k) {
if (a[j] + a[k] <= X-a[i]) {
count += k-j;
j++;
} else {
k--;
}
}
}
return count;
}
【在 c*****m 的大作中提到】
: 2sum问题只能处理等于某数的情况吧，如1,2,7,8, 要求2sum<=9的，这里只有两个，而
: 不是3个
:
: ],
|
k*********g
发帖数: 40 | 27 anagram substring match
请问这个问题的细节？谢谢
【在 l****o 的大作中提到】
: Onsite完，应该是挂了。
: 第一轮，越南人，黑脸
: 问google search的时候auto complete怎么弄的，答trie, 然后要求实现建树，和给出
: 所有auto complete的结果。然后follow up了结果有序，如果是非英文情况和在多台机
: 器上如何优化。都答出来了，写了80多行code累死我了。
: 第二轮，亚裔，很友好。
: leetcode俩题，加一个design，关于音乐app的。都不难，应该没什么问题。
: 第三轮，中年老美+shadow，正常
: read4k，我应该是可以写出来的，不过面试官尝试给hint然后要我按照他的套路写，结
: 果就写的略混乱。
|
l****o
发帖数: 315 | 28 不是，有两年左右的experience，不过还是面的entry
【在 h****g 的大作中提到】
: lz是fresh么，你的题目偏难啊，尤其是triplet那道
|
l****o
发帖数: 315 | 29 是的
【在 f******4 的大作中提到】
: 投的什么职位啊？software engineer？
|
l****o
发帖数: 315 | 30 嗯，是可以并查集。
【在 l*********s 的大作中提到】
: string 关联那题可以并查集啊
|
|
|
l****o
发帖数: 315 | 31 就比如 S: afaghhsa
T: gaf
找T在S里的anagram
【在 k*********g 的大作中提到】
: anagram substring match
: 请问这个问题的细节？谢谢
|
f*******w
发帖数: 1243 | 32 triple那道题应该不用BIT吧……
按3SUM的做法应该没问题啊
如果A[s] + A[e] <= target, 那么所有的 A[s] + A[s+1] 到 A[s] + A[e]都满足条件
，counter直接加e - s，然后移动s
如果A[s] + A[e] > target, 那么 A[s] + A[e] 到 A[e-1] + A[e]都肯定比target大
，可以放心的排除e |
f*******w
发帖数: 1243 | 33
Substring with Concatenation of All Words的简装版，words长度为1
【在 l****o 的大作中提到】
: 就比如 S: afaghhsa
: T: gaf
: 找T在S里的anagram
|
