d*******n
发帖数: 141 | 1 攒rp，5555，第一个人的问题完全没答好……
interviewer 1:
1. input: a1,...,an
output: a2*a3..*an, a1*a3..*an, ..., a1*..*a(n-1)
2. input: a1,...,an
output: ai + aj = ak
3. input: a big string, a small string
output: smallest window in the big string which contains all chars of the
small string
interviewer 2:
1. target sum problem;
2. how to make copy big file to many machines faster
ps，第一个interviewer是search部的，好像很tough的样子，后来我一查是个东欧滴人
儿，sigh，估计要挂了。第二个是个老美，超级nice，题也不难，是测试部的。
结论：面试官来自哪儿hien重要…… |
k***e
发帖数: 556 | 2 真是个人有个人都偏好
第一人的三道题目本版全部出现过
第二人的第二题很open 不好弄 你怎么回答的？
the
【在 d*******n 的大作中提到】
: 攒rp，5555，第一个人的问题完全没答好……
: interviewer 1:
: 1. input: a1,...,an
: output: a2*a3..*an, a1*a3..*an, ..., a1*..*a(n-1)
: 2. input: a1,...,an
: output: ai + aj = ak
: 3. input: a big string, a small string
: output: smallest window in the big string which contains all chars of the
: small string
: interviewer 2:
|
d*******n
发帖数: 141 | 3 第一个我也觉得可惜了，第二题和第三题的优化一点的算法我都没太说清楚，到最后关
头才搞明白，叽里咕噜的瞎说了……一紧张就给忘了，平时多练练还是挺必要的，
55555555
第二个的scenario是这样，文件在一台机器上，然后剩下1000个机器嗷嗷待哺。
就先搞清楚网络带宽是多少，传输率是多少；
然后我就说可以一个机器先copy，然后俩机器就能copy俩了，就是一个二分的问题……
面试官竟然觉得挺新鲜的……
【在 k***e 的大作中提到】
: 真是个人有个人都偏好
: 第一人的三道题目本版全部出现过
: 第二人的第二题很open 不好弄 你怎么回答的？
:
: the
|
k***e
发帖数: 556 | 4 你可以看看google的file system 分布式的 比较适合cluster
此外 如果switch支持broadcast可以一次到位
反正这题很难
【在 d*******n 的大作中提到】
: 第一个我也觉得可惜了，第二题和第三题的优化一点的算法我都没太说清楚，到最后关
: 头才搞明白，叽里咕噜的瞎说了……一紧张就给忘了，平时多练练还是挺必要的，
: 55555555
: 第二个的scenario是这样，文件在一台机器上，然后剩下1000个机器嗷嗷待哺。
: 就先搞清楚网络带宽是多少，传输率是多少；
: 然后我就说可以一个机器先copy，然后俩机器就能copy俩了，就是一个二分的问题……
: 面试官竟然觉得挺新鲜的……
|
d*******n
发帖数: 141 | 5 看面试官吧，我这个面试官挺好的，会引导去想，不会问到cluster之类的，恩
这个人好像看我背景不是分布式计算的，就会更focus在问题上了~~
还有就是不让一次到位，一台机器在一时间只能被一个机器读~~~~
【在 k***e 的大作中提到】
: 你可以看看google的file system 分布式的 比较适合cluster
: 此外 如果switch支持broadcast可以一次到位
: 反正这题很难
|
m*****f
发帖数: 1243 | 6 第二题和第三题的优化一点的算法是什么?
是不是O(n^2) and O(n)
最后一个问题不就是BT download....
【在 d*******n 的大作中提到】
: 第一个我也觉得可惜了，第二题和第三题的优化一点的算法我都没太说清楚，到最后关
: 头才搞明白，叽里咕噜的瞎说了……一紧张就给忘了，平时多练练还是挺必要的，
: 55555555
: 第二个的scenario是这样，文件在一台机器上，然后剩下1000个机器嗷嗷待哺。
: 就先搞清楚网络带宽是多少，传输率是多少；
: 然后我就说可以一个机器先copy，然后俩机器就能copy俩了，就是一个二分的问题……
: 面试官竟然觉得挺新鲜的……
|
r**m
发帖数: 163 | 7 他是让你描述idea和分析复杂度，还是直接就要coding
我那就是直接要coding，写在google docs上，然后他一直问问题
我老改，哎，没做好。
兄弟知道多久给消息吗 |
d*******n
发帖数: 141 | 8 恩，我觉着是吧……这俩具体的算法我都没说清楚……我就蒙了一个complexity
后悔死我了，一紧张就真的会脑子糊住了，第一次技术面试:(
【在 m*****f 的大作中提到】
: 第二题和第三题的优化一点的算法是什么?
: 是不是O(n^2) and O(n)
: 最后一个问题不就是BT download....
|
d*******n
发帖数: 141 | 9 第一个直接要coding，第二个先coding再问问题，也都是在google docs上，嗯
btw，我不是兄弟-__-，不知道多久呢，估计得一阵吧
【在 r**m 的大作中提到】
: 他是让你描述idea和分析复杂度，还是直接就要coding
: 我那就是直接要coding，写在google docs上，然后他一直问问题
: 我老改，哎，没做好。
: 兄弟知道多久给消息吗
|
r**m
发帖数: 163 | 10 噢，不好意思哈
面你的是哪个office的？ 我咋只有一个人面，第一次面试，我也是紧张得要命
【在 d*******n 的大作中提到】
: 第一个直接要coding，第二个先coding再问问题，也都是在google docs上，嗯
: btw，我不是兄弟-__-，不知道多久呢，估计得一阵吧
|
|
|
d*******n
发帖数: 141 | 11 都是Mountview的，嗯
【在 r**m 的大作中提到】
: 噢，不好意思哈
: 面你的是哪个office的？ 我咋只有一个人面，第一次面试，我也是紧张得要命
|
S******A
发帖数: 1002 | 12 谁给说一下这题咋个优化
2. input: a1,...,an
output: ai + aj = ak |
k***e
发帖数: 556 | 13 难道你不是用hash 做第一个都二三？
其实第二题你的idea可以再扩展一下，server传n/1000给每一台机器
接下来就是偶们的最爱了 哈哈
【在 d*******n 的大作中提到】
: 第一个我也觉得可惜了，第二题和第三题的优化一点的算法我都没太说清楚，到最后关
: 头才搞明白，叽里咕噜的瞎说了……一紧张就给忘了，平时多练练还是挺必要的，
: 55555555
: 第二个的scenario是这样，文件在一台机器上，然后剩下1000个机器嗷嗷待哺。
: 就先搞清楚网络带宽是多少，传输率是多少；
: 然后我就说可以一个机器先copy，然后俩机器就能copy俩了，就是一个二分的问题……
: 面试官竟然觉得挺新鲜的……
|
d*******n
发帖数: 141 | 14 第一个的第二道，我想到了hash，但由于我脑子糊成一坨导致我没说清楚……
第三个，我就琢磨keep一个occurrence array，扫描大的字符串，记下里头出现的小字
符串中char的位置，然后不断update窗口的size，这个我只说了idea，没写下来……
【在 k***e 的大作中提到】
: 难道你不是用hash 做第一个都二三？
: 其实第二题你的idea可以再扩展一下，server传n/1000给每一台机器
: 接下来就是偶们的最爱了 哈哈
|
v*****t
发帖数: 127 | 15 semi-brute_force can do it in O(n^2), but much harder(even impossible?) to
do better.
maybe lz means optimize the constant factor in O(n^2)
【在 S******A 的大作中提到】
: 谁给说一下这题咋个优化
: 2. input: a1,...,an
: output: ai + aj = ak
|
d*******n
发帖数: 141 | 16 re..我其实没太捋顺这个，可以先排个序，然后再blabla的...
【在 v*****t 的大作中提到】
: semi-brute_force can do it in O(n^2), but much harder(even impossible?) to
: do better.
: maybe lz means optimize the constant factor in O(n^2)
|
k***e
发帖数: 556 | 17 idea差不多对 应该有戏
【在 d*******n 的大作中提到】
: 第一个的第二道，我想到了hash，但由于我脑子糊成一坨导致我没说清楚……
: 第三个，我就琢磨keep一个occurrence array，扫描大的字符串，记下里头出现的小字
: 符串中char的位置，然后不断update窗口的size，这个我只说了idea，没写下来……
|
d*******n
发帖数: 141 | 18 不管了...人生完整了...
【在 k***e 的大作中提到】
: idea差不多对 应该有戏
|
s***t
发帖数: 49 | 19 第一个的 2，
ak 是 给定常数吗？
the
【在 d*******n 的大作中提到】
: 攒rp，5555，第一个人的问题完全没答好……
: interviewer 1:
: 1. input: a1,...,an
: output: a2*a3..*an, a1*a3..*an, ..., a1*..*a(n-1)
: 2. input: a1,...,an
: output: ai + aj = ak
: 3. input: a big string, a small string
: output: smallest window in the big string which contains all chars of the
: small string
: interviewer 2:
|
v*****t
发帖数: 127 | 20 an interesting case of Interviewer1 - Prob3:
what if small string contains duplicate chars and the window must contain at
least same number of dup chars
【在 d*******n 的大作中提到】
: 第一个的第二道，我想到了hash，但由于我脑子糊成一坨导致我没说清楚……
: 第三个，我就琢磨keep一个occurrence array，扫描大的字符串，记下里头出现的小字
: 符串中char的位置，然后不断update窗口的size，这个我只说了idea，没写下来……
|
|
|
m*****f
发帖数: 1243 | 21 just treat dup chars as "different chars" that has the same location vector,
and apply
the same algorithm.
at
【在 v*****t 的大作中提到】
: an interesting case of Interviewer1 - Prob3:
: what if small string contains duplicate chars and the window must contain at
: least same number of dup chars
|
k***e
发帖数: 556 | 22 just count the # of appearances of each char in the hash map
scan src string form left to right
each char will be put in the hash map once and poped out once
vector,
【在 m*****f 的大作中提到】
: just treat dup chars as "different chars" that has the same location vector,
: and apply
: the same algorithm.
:
: at
|
v*****t
发帖数: 127 | 23 think more~
我觉得我有当面试官的潜质，哈哈
vector,
【在 m*****f 的大作中提到】
: just treat dup chars as "different chars" that has the same location vector,
: and apply
: the same algorithm.
:
: at
|
m*****f
发帖数: 1243 | 24 I am not sure, how to record the small window, that I have every char covered?
【在 k***e 的大作中提到】
: just count the # of appearances of each char in the hash map
: scan src string form left to right
: each char will be put in the hash map once and poped out once
:
: vector,
|
c*****o
发帖数: 178 | 25 请问第一个interviewer的q2是不是要先sort，然后分成<0,=0,>0三个区间？
q3的话，找到small string中的所有character在big string的位置，如果有重复，只
记录第一次出现的位置，放在一个hashtable中。然后找到最大和最小的下标，相减就
是smallerst window。可以先对small string做处理，去掉所有重复的character。请
问这样回答可以吗？ |
k***e
发帖数: 556 | 26 a solution that can cope with the situtation where the pattern in the src
is required to be continuous
use a totalcounter to see how many match happens
suppose unordered_map h; is set up first
the char frequency counter
src, pat, ssize = src.size( ), psize = pat.size( );
start from src[m]
1) src[m] is in the h, then h[src[m]]--,
if h[src[m]] == -1 too many of src[m]. failure. push into h those
src[m]
else totalcount--;
if totalcount == 0
【在 m*****f 的大作中提到】
: I am not sure, how to record the small window, that I have every char covered?
|
c*********n
发帖数: 1057 | 27 可以给个伪代码么？
vector,
【在 m*****f 的大作中提到】
: just treat dup chars as "different chars" that has the same location vector,
: and apply
: the same algorithm.
:
: at
|
v*****t
发帖数: 127 | 28 an issue is
small string = "aab"
inverted index:
'a': 1 4 5 6 7...
'a': 1 4 5 6 7
'b': 2 3 6 9 10...
run the min window coverage algorithm will return an answer of
window[6,6] which is wrong
covered?
【在 m*****f 的大作中提到】
: I am not sure, how to record the small window, that I have every char covered?
|
m*****f
发帖数: 1243 | 29 how to do you get 6 6...,
b怎么可能也有6
【在 v*****t 的大作中提到】
: an issue is
: small string = "aab"
: inverted index:
: 'a': 1 4 5 6 7...
: 'a': 1 4 5 6 7
: 'b': 2 3 6 9 10...
: run the min window coverage algorithm will return an answer of
: window[6,6] which is wrong
:
: covered?
|
d*******n
发帖数: 141 | 30 mark
into
【在 k***e 的大作中提到】
: a solution that can cope with the situtation where the pattern in the src
: is required to be continuous
: use a totalcounter to see how many match happens
: suppose unordered_map h; is set up first
: the char frequency counter
: src, pat, ssize = src.size( ), psize = pat.size( );
: start from src[m]
: 1) src[m] is in the h, then h[src[m]]--,
: if h[src[m]] == -1 too many of src[m]. failure. push into h those
: src[m]
|
|
|
v*****t
发帖数: 127 | 31 呵呵，大概就是那个意思你能理解吧
我稍微改改
'a': 1 4 5 6 7...
'a': 1 4 5 6 7
'b': 2 8...
the result wound be window[1,2] which is wrong,
correct answer should be [6,8]
【在 m*****f 的大作中提到】
: how to do you get 6 6...,
: b怎么可能也有6
|
m*****f
发帖数: 1243 | 32 预先载入hash count, 并且用totalcount计算总数?
如果我们要在 "3331223"
找最小window cover "1233"
是不是会在第三个3 and 第二个 2 这里 reset?
是不是就找不到 3312 这个 cover le?
【在 k***e 的大作中提到】
: a solution that can cope with the situtation where the pattern in the src
: is required to be continuous
: use a totalcounter to see how many match happens
: suppose unordered_map h; is set up first
: the char frequency counter
: src, pat, ssize = src.size( ), psize = pat.size( );
: start from src[m]
: 1) src[m] is in the h, then h[src[m]]--,
: if h[src[m]] == -1 too many of src[m]. failure. push into h those
: src[m]
|
k***e
发帖数: 556 | 33 hi i just put back one char at a time. not all of them
【在 m*****f 的大作中提到】
: 预先载入hash count, 并且用totalcount计算总数?
: 如果我们要在 "3331223"
: 找最小window cover "1233"
: 是不是会在第三个3 and 第二个 2 这里 reset?
: 是不是就找不到 3312 这个 cover le?
|
m*****f
发帖数: 1243 | 34 两个char(even they are the same)不能一样index的话呢, 原来题目里面就有这个assumption...
【在 v*****t 的大作中提到】
: 呵呵，大概就是那个意思你能理解吧
: 我稍微改改
: 'a': 1 4 5 6 7...
: 'a': 1 4 5 6 7
: 'b': 2 8...
: the result wound be window[1,2] which is wrong,
: correct answer should be [6,8]
|
m*****f
发帖数: 1243 | 35 这样的话还有一个问题, 最小window如何记录?
谢谢回答
【在 k***e 的大作中提到】
: hi i just put back one char at a time. not all of them
|
m*****f
发帖数: 1243 | 36 For example,
'a': 1 4 5 6 7...
'a': 1 4 5 6 7
'b': 2 8...
start as (1, 4, 2,), always choose to update the smallest index, and make
sure no two indexes equal.
(1, 4, 2) => (5, 4, 2) => (5, 4, 8) => (5, 6, 8) => (7, 6, 8)...
Answer is (7, 6, 8).
【在 c*********n 的大作中提到】
: 可以给个伪代码么？
:
: vector,
|
d*******n
发帖数: 141 | 37 恩，我也这么觉着来着，或者在记录的时候判断一下，位置不能重复
assumption...
【在 m*****f 的大作中提到】
: 两个char(even they are the same)不能一样index的话呢, 原来题目里面就有这个assumption...
|
x******r
发帖数: 249 | 38 不知这样行吗？
假设small string是s，big string是b. window首尾index是start和end
判断当前window是否包含s只要O(1)时间。（只有256种字符）
1.start=0,找到最小的end，使得window包含s。
2.end不变。找到最大start，使得windows包含s。此为当前最小window
3.++end. 如果b[start]==b[end],则执行第二步，更新当前最小window。重复第3步直
到end==strlen(b) |
c*****y
发帖数: 90 | |
P**********0
发帖数: 412 | |
|
|
g*****u
发帖数: 298 | 41 第1题lz能不能说的详细些？
第三题O(n)?? 不考虑短string的元素个数啦？ |
