NIW送NeBraska 和TX 有不同吗 - 未名空间MITBBS历史存档

NIW送NeBraska 和TX 有不同吗# EB23 - 劳工卡

l*n2012-01-10 08:01

1 楼

昨天的电面，开始还不错，问了很多C++的东西，virtual function, overloading之类
的，然后就是两道算法题，第一道是很常规的链表处理题，很快搞定并写程序，第二道
题题目比较长，他先给我解释说google在搜索完成显示结果的时候会生成快视图（也
就是把含有搜索关键字的部分显示一下）。现在搜索三个词，比如“hello”,"world",
"goodbye", 搜索完成之后会有三个array，每一个array都存放着三个词在一篇文章里
的位置。写一个函数，返回两个值，代表文章中的两个位置，在这两个位置之间，“
hello”,"world", "goodbye"至少各出现一次，而且要求这两个位置之间的距离尽可能
短。那位大哥光阐述这道题就用了5分钟。。。我听的有点晕，不过迅速明白了题的意
思，但是到最后也没能给出他认为的最优答案，看看哪位达人有思路？？？？

a*22012-01-10 08:01

2 楼

请问一下最近在上海签证的同学，需要纸质的照片吗？我的朋友告诉我说北京大使馆
还是需要的，而且要贴在确认页上，但是我在上海领馆没有看到这样的要求，到底怎么
弄是对的呢？
谢谢！！

i*c2012-01-10 08:01

3 楼

我指处理的速度？刁难程度？
新手求指点

b*v2012-01-10 08:01

4 楼

这道题我有个想法，不过有点复杂
假设给hello上红色，world上绿色，goodbye上蓝色
则那两个位置必定是一红一绿中间夹若干蓝，但没有其他红绿，
或是一红一蓝中间夹若干绿，或是一绿一蓝中间夹若干红。
所以我们可以把三个数组合并成一个大数组并排序O(N*logN)
然后依次遍历这个大数组，并维持如下不变量：
上一个红的位置r，
上一个绿的位置g，
上一个蓝的位置b，
当前最小窗口的起始位置start, end
当扫描到大数组中一个新的元素x时，
(1)x.color = red，
如果x-min(g, b) < end-start，则更新start=min(g, b), end=x
同时更新r=x
(2)x.color = green，类似(1)
(3)x.color = blue，类似(1)
当扫描到大数组最后一个元素，就能打印出最小窗口
算法的复杂度是O(N*logN)，其中N是三个数组的元素个数之和
update: 不用合并成大数组，既然是从小到大依次遍历大数组的元素，
可以用merge sort的想法，每次从三个小数组里取最小元素。
这样，算法复杂度是O(N)。

",

【在 l*******n 的大作中提到】

: 昨天的电面，开始还不错，问了很多C++的东西，virtual function, overloading之类
: 的，然后就是两道算法题，第一道是很常规的链表处理题，很快搞定并写程序，第二道
: 题题目比较长，他先给我解释说google在搜索完成显示结果的时候会生成快视图（也
: 就是把含有搜索关键字的部分显示一下）。现在搜索三个词，比如“hello”,"world",
: "goodbye", 搜索完成之后会有三个array，每一个array都存放着三个词在一篇文章里
: 的位置。写一个函数，返回两个值，代表文章中的两个位置，在这两个位置之间，“
: hello”,"world", "goodbye"至少各出现一次，而且要求这两个位置之间的距离尽可能
: 短。那位大哥光阐述这道题就用了5分钟。。。我听的有点晕，不过迅速明白了题的意
: 思，但是到最后也没能给出他认为的最优答案，看看哪位达人有思路？？？？

t*b2012-01-10 08:01

5 楼

如果电子照片合格的话，任何地方都不需要纸质的。

B*g2012-01-10 08:01

6 楼

TX慢死

【在 i****c 的大作中提到】

: 我指处理的速度？刁难程度？
: 新手求指点

B*t2012-01-10 08:01

7 楼

1. sort each array according to the appearance in the paper.
2. create a queue with 3 size_t var(ct1, ct2, ct3), which count
the number of each word(all init to 0's), and 2 pointers to rear
and front.
3. enqueue the element with smallest value in the 3 arrays, and
move the array pointer accordingly, and increment cti
accordingly. Suppose ct1 is just increased by 1:
3.1 if one of cti is 0, go back 3.
3.2 Check the front pointer. If it points to the same word
as just enqueued, pop the fron

【在 l*******n 的大作中提到】

: 昨天的电面，开始还不错，问了很多C++的东西，virtual function, overloading之类
: 的，然后就是两道算法题，第一道是很常规的链表处理题，很快搞定并写程序，第二道
: 题题目比较长，他先给我解释说google在搜索完成显示结果的时候会生成快视图（也
: 就是把含有搜索关键字的部分显示一下）。现在搜索三个词，比如“hello”,"world",
: "goodbye", 搜索完成之后会有三个array，每一个array都存放着三个词在一篇文章里
: 的位置。写一个函数，返回两个值，代表文章中的两个位置，在这两个位置之间，“
: hello”,"world", "goodbye"至少各出现一次，而且要求这两个位置之间的距离尽可能
: 短。那位大哥光阐述这道题就用了5分钟。。。我听的有点晕，不过迅速明白了题的意
: 思，但是到最后也没能给出他认为的最优答案，看看哪位达人有思路？？？？

i*c2012-01-10 08:01

8 楼

谢谢

【在 B*****g 的大作中提到】

: TX慢死

l*a2012-01-10 08:01

9 楼

why so complicate?
since u already have 3 sorted arrays
a[0..n-1] a[i] means the location of (i+1)th appearance of the word a in the file
b[0..m-1]
c[0..k-1]
i,j,l start from 0
eachtime compare a[i] b[j] c[l].
the distance=max {a[i] b[j] c[l]} - min{a[i] b[j] c[l]}
if distanceincrease the index of min
go back to compare a[i] b[j] c[l].
###eactime u should have location of 3 words...and compare them
until there is no one word ...till a[n-1] or b[m-1] or c[k-1]
【在 BlueAnt (

s*e2012-01-10 08:01

10 楼

Are you serious?

【在 B*****g 的大作中提到】

: TX慢死

r*o2012-01-10 08:01

11 楼

我的想法是
1. sort each array, a[], b[], c[], and create three indexes: index_a, index_
b, index_c, all initialized as 0.
2. begin:
start=min{index_a, index_b, index_c};
end=max{index_a, index_b, index_c}.
record max_distance, max_start, max_end;
while(1)
find index of min(a[index_a+1], b[index_b+1], c[index_c+1]), if index=a, then index_a++, and so on;
recalculate start and end;
calculate current distance and record max_distance, max_start, max_end
if necessary.

【在 B*****t 的大作中提到】

: 1. sort each array according to the appearance in the paper.
: 2. create a queue with 3 size_t var(ct1, ct2, ct3), which count
: the number of each word(all init to 0's), and 2 pointers to rear
: and front.
: 3. enqueue the element with smallest value in the 3 arrays, and
: move the array pointer accordingly, and increment cti
: accordingly. Suppose ct1 is just increased by 1:
: 3.1 if one of cti is 0, go back 3.
: 3.2 Check the front pointer. If it points to the same word
: as just enqueued, pop the fron

B*g2012-01-10 08:01

12 楼

个人经验

【在 s*******e 的大作中提到】

: Are you serious?

b*v2012-01-10 08:01

13 楼

也可以把三个数组分别排序，然后按照merge sort的方式
每次从三个数组取最小的元素来考虑，并更新r,g,b,start,end

【在 b******v 的大作中提到】

: 这道题我有个想法，不过有点复杂
: 假设给hello上红色，world上绿色，goodbye上蓝色
: 则那两个位置必定是一红一绿中间夹若干蓝，但没有其他红绿，
: 或是一红一蓝中间夹若干绿，或是一绿一蓝中间夹若干红。
: 所以我们可以把三个数组合并成一个大数组并排序O(N*logN)
: 然后依次遍历这个大数组，并维持如下不变量：
: 上一个红的位置r，
: 上一个绿的位置g，
: 上一个蓝的位置b，
: 当前最小窗口的起始位置start, end

i*l2012-01-10 08:01

14 楼

TX 4 MONTHS VS NST 18 MONTH

【在 i****c 的大作中提到】

: 谢谢

b*v2012-01-10 08:01

15 楼

你的算法中如何移动i,j,l?

the file

【在 l*****a 的大作中提到】

: why so complicate?
: since u already have 3 sorted arrays
: a[0..n-1] a[i] means the location of (i+1)th appearance of the word a in the file
: b[0..m-1]
: c[0..k-1]
: i,j,l start from 0
: eachtime compare a[i] b[j] c[l].
: the distance=max {a[i] b[j] c[l]} - min{a[i] b[j] c[l]}
: if distance: increase the index of min

B*g2012-01-10 08:01

16 楼

TX现在这么快了？nnd，俺是10个多月

【在 i***l 的大作中提到】

: TX 4 MONTHS VS NST 18 MONTH

f*62012-01-10 08:01

17 楼

Hmm...assume the min index is from array a and the max is from array c, what
is the point of considering b[j+1]-b[j] here?

【在 r****o 的大作中提到】

: 我的想法是
: 1. sort each array, a[], b[], c[], and create three indexes: index_a, index_
: b, index_c, all initialized as 0.
: 2. begin:
: start=min{index_a, index_b, index_c};
: end=max{index_a, index_b, index_c}.
: record max_distance, max_start, max_end;
: while(1)
: find index of min(a[index_a+1], b[index_b+1], c[index_c+1]), if index=a, then index_a++, and so on;
: recalculate start and end;

r*o2012-01-10 08:01

18 楼

Hmm...I changed my algorithm,
each time find the index of min{a[i+1], b[j+1], c[l+1]}, and increases the
index.

what

【在 f******6 的大作中提到】

:
: Hmm...assume the min index is from array a and the max is from array c, what
: is the point of considering b[j+1]-b[j] here?

l*a2012-01-10 08:01

19 楼

increase the index of min

【在 b******v 的大作中提到】

: 你的算法中如何移动i,j,l?
:
: the file

s*s2012-01-10 08:01

20 楼

找minispan.三个pointer,从最小值开始移动.

x*32012-01-10 08:01

21 楼

赞，我觉得这方法能行

【在 s*********s 的大作中提到】

: 找minispan.三个pointer,从最小值开始移动.

d*22012-01-10 08:01

22 楼

it doesn't work, it never says b[j+1] is between a[i+1] and c[l+1]

the

【在 r****o 的大作中提到】

: Hmm...I changed my algorithm,
: each time find the index of min{a[i+1], b[j+1], c[l+1]}, and increases the
: index.
:
: what

r*o2012-01-10 08:01

23 楼

why?
start from a[0], b[0], c[0], index_a=0, index_b=0, index_c=0.
Each time, compare a[index_a+1], b[index_b+1] and c[index_c+1], change the
index of the min.

【在 d********2 的大作中提到】

: it doesn't work, it never says b[j+1] is between a[i+1] and c[l+1]
:
: the

x*r2012-01-10 08:01

24 楼

不确定完全看懂了你的解，不过我觉得这样会被local maximum卡住
例如大数组是 1r 2g 3b 100r 100g 100b
这样就不会找到100， 100
如果没看清你的解那不好意思:P

【在 b******v 的大作中提到】

: 这道题我有个想法，不过有点复杂
: 假设给hello上红色，world上绿色，goodbye上蓝色
: 则那两个位置必定是一红一绿中间夹若干蓝，但没有其他红绿，
: 或是一红一蓝中间夹若干绿，或是一绿一蓝中间夹若干红。
: 所以我们可以把三个数组合并成一个大数组并排序O(N*logN)
: 然后依次遍历这个大数组，并维持如下不变量：
: 上一个红的位置r，
: 上一个绿的位置g，
: 上一个蓝的位置b，
: 当前最小窗口的起始位置start, end

a*u2012-01-10 08:01

25 楼

this algorithm should work, except min{a[i+1], ...} could just be replaced
by min{a[i], ...} :)

【在 r****o 的大作中提到】

: Hmm...I changed my algorithm,
: each time find the index of min{a[i+1], b[j+1], c[l+1]}, and increases the
: index.
:
: what

b*v2012-01-10 08:01

26 楼

不会被卡住的
例如
x=100r时，start=min{2,3}=2, end=100, rx=100g时，start=min{3,100}=3, end=100, gx=100b时，start=min{100,100}=100, end=100, b
【在 x****r 的大作中提到】

: 不确定完全看懂了你的解，不过我觉得这样会被local maximum卡住
: 例如大数组是 1r 2g 3b 100r 100g 100b
: 这样就不会找到100， 100
: 如果没看清你的解那不好意思:P

g*u2012-01-10 08:01

27 楼

这不就是min cover window么，经典题啊

",

【在 l*******n 的大作中提到】

: 昨天的电面，开始还不错，问了很多C++的东西，virtual function, overloading之类
: 的，然后就是两道算法题，第一道是很常规的链表处理题，很快搞定并写程序，第二道
: 题题目比较长，他先给我解释说google在搜索完成显示结果的时候会生成快视图（也
: 就是把含有搜索关键字的部分显示一下）。现在搜索三个词，比如“hello”,"world",
: "goodbye", 搜索完成之后会有三个array，每一个array都存放着三个词在一篇文章里
: 的位置。写一个函数，返回两个值，代表文章中的两个位置，在这两个位置之间，“
: hello”,"world", "goodbye"至少各出现一次，而且要求这两个位置之间的距离尽可能
: 短。那位大哥光阐述这道题就用了5分钟。。。我听的有点晕，不过迅速明白了题的意
: 思，但是到最后也没能给出他认为的最优答案，看看哪位达人有思路？？？？

B*t2012-01-10 08:01

28 楼

好办法！确实想复杂了。

word a in the file

【在 l*****a 的大作中提到】

: why so complicate?
: since u already have 3 sorted arrays
: a[0..n-1] a[i] means the location of (i+1)th appearance of the word a in the file
: b[0..m-1]
: c[0..k-1]
: i,j,l start from 0
: eachtime compare a[i] b[j] c[l].
: the distance=max {a[i] b[j] c[l]} - min{a[i] b[j] c[l]}
: if distance: increase the index of min

x*32012-01-10 08:01

29 楼

没听过min cover window，能给个连接啥的吗，多谢了

【在 g*****u 的大作中提到】

: 这不就是min cover window么，经典题啊
:
: ",

v*w2012-01-10 08:01

30 楼

agree

the file

【在 l*****a 的大作中提到】

: why so complicate?
: since u already have 3 sorted arrays
: a[0..n-1] a[i] means the location of (i+1)th appearance of the word a in the file
: b[0..m-1]
: c[0..k-1]
: i,j,l start from 0
: eachtime compare a[i] b[j] c[l].
: the distance=max {a[i] b[j] c[l]} - min{a[i] b[j] c[l]}
: if distance: increase the index of min

w*g2012-01-10 08:01

31 楼

http://www.careercup.com/page?pid=google-interview-questions&n=3

w*g2012-01-10 08:01

32 楼

http://www.careercup.com/page?pid=google-interview-questions&n=3

w*g2012-01-10 08:01

33 楼

http://www.careercup.com/page?pid=google-interview-questions&n=3

w*g2012-01-10 08:01

34 楼

这样不是assume a,b,c三个array的index一起increase, 但是有时候minspan并不一定
是在同一个位置的啊？

the file

【在 l*****a 的大作中提到】

: why so complicate?
: since u already have 3 sorted arrays
: a[0..n-1] a[i] means the location of (i+1)th appearance of the word a in the file
: b[0..m-1]
: c[0..k-1]
: i,j,l start from 0
: eachtime compare a[i] b[j] c[l].
: the distance=max {a[i] b[j] c[l]} - min{a[i] b[j] c[l]}
: if distance: increase the index of min

z*g2012-01-10 08:01

35 楼

我有同样的问题。请教i, j, l 的移动方法。

【在 w****g 的大作中提到】

: 这样不是assume a,b,c三个array的index一起increase, 但是有时候minspan并不一定
: 是在同一个位置的啊？
:
: the file

l*a2012-01-10 08:01

36 楼

移动a[i],b[j],c[l]中最小的。
你找几个实例试试就知道了

【在 w****g 的大作中提到】

: 这样不是assume a,b,c三个array的index一起increase, 但是有时候minspan并不一定
: 是在同一个位置的啊？
:
: the file

r*12012-01-10 08:01

37 楼

好。

in the file

【在 l*****a 的大作中提到】

: why so complicate?
: since u already have 3 sorted arrays
: a[0..n-1] a[i] means the location of (i+1)th appearance of the word a in the file
: b[0..m-1]
: c[0..k-1]
: i,j,l start from 0
: eachtime compare a[i] b[j] c[l].
: the distance=max {a[i] b[j] c[l]} - min{a[i] b[j] c[l]}
: if distance: increase the index of min