Tsc 能在9月底前把140缩短到4个月么 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Immigration - 落地生根

Tsc 能在9月底前把140缩短到4个月么

Tsc 能在9月底前把140缩短到4个月么# Immigration - 落地生根

H*e2011-08-20 07:08

1 楼

1。一个array,找两个数字使得和为0，简单，只要用一个hashtable就可以了，只需
要走一遍， O(n) time O(n) space
2。三个数字和为0， a+b+c = 0, 那么a+b＋c = 0,那么 array当中必须有负数才行，
把正数和负数分开，分别放到两个hashtable中：正hashtable和负hashtable.
a+b+c = 0, 组合只有可能 ++- or --+, 所以对每个正hashtable的元素a，看有没有
两元素加起来为'-a'；对每个负hashtable的元素b，看有没有两元素加起来为'-b',如
果有，则为解。 O(n^2) time, O(n) space
3。四个元素为0。这个是怎么有time O(n^2)的解的？space是多少的？
4。五个元素为0就更没头绪了。
－－－－－－
引用前面的帖子。
发信人: fengzhongdi (fzd), 信区: JobHunting
标题: LinkedIn面试被老印郁闷到了.....
发信站: BBS 未名空间站 (Wed May 18 20:57:55 2011, 美东)
问了三个问题,第一个题目还算靠谱,就是在arraylist里面有乱序的数字,如何找出两个
数字使得和为0, O(n), 然后如何找出三个数字和为0, O(n^2), 四个数字和为0,这里我
卡了一下,在提示后给出了O(n^2)的解,然后如何找出五个数字和为0,我给出了O(n^3)的
解.

f*D2011-08-20 07:08

2 楼

前一段有律师还发文章说有这个消息
十分怀疑

m*n2011-08-20 07:08

3 楼

2个的话，直接hashtable O(N)，先排序，然后再left--> , NlgN)
3个的话，直接先排序NlgN, 然后求a+b=-c 对每一个元素做a+b=x操作 N^2
4个的话，也是排序，然后a+b+c=-d ,用前一步算法 N^3
....

f*s2011-08-20 07:08

4 楼

移民局的官老爷，谁也猜不准

H*e2011-08-20 07:08

5 楼

没看出来排序在这里有什么用
你已经有hashtable了，寻找一个元素已经是O(1)

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

: 2个的话，直接hashtable O(N)，先排序，然后再left--> , : NlgN)
: 3个的话，直接先排序NlgN, 然后求a+b=-c 对每一个元素做a+b=x操作 N^2
: 4个的话，也是排序，然后a+b+c=-d ,用前一步算法 N^3
: ....

f*D2011-08-20 07:08

6 楼

可是律师声称是派人参加个什么会，人家官老爷的主任自己说的

L*Q2011-08-20 07:08

7 楼

一种延伸是不让你使用额外的storage，所以没法用hashtable。
三个数和为0，不用分正数负数，一个hashtable装全部数就行了。使用hashtable有一
个容易产生bug的地方：把一个数多次计算。比如-2 -1 4，不留神就会得到-2， -2，
4的组合。hashtable只告诉你某个数存在否，但没告诉你存在多少次。
不用hashtable的解法，sort然后头尾往中间扫描两端。最初是第一个array[0]，然后
test array[1..n]中是否有2个数加起来等于-array[0]。接下来是array[1]，test
array[2..n]中是否有2个数加起来等于-array[1]。时间复杂度仍然为O(N^2)，空间复
杂度O(1)

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

: 1。一个array,找两个数字使得和为0，简单，只要用一个hashtable就可以了，只需
: 要走一遍， O(n) time O(n) space
: 2。三个数字和为0， a+b+c = 0, 那么a+b＋c = 0,那么 array当中必须有负数才行，
: 把正数和负数分开，分别放到两个hashtable中：正hashtable和负hashtable.
: a+b+c = 0, 组合只有可能 ++- or --+, 所以对每个正hashtable的元素a，看有没有
: 两元素加起来为'-a'；对每个负hashtable的元素b，看有没有两元素加起来为'-b',如
: 果有，则为解。 O(n^2) time, O(n) space
: 3。四个元素为0。这个是怎么有time O(n^2)的解的？space是多少的？
: 4。五个元素为0就更没头绪了。
: －－－－－－

l*b2011-08-20 07:08

8 楼

是说努力把时间缩短到4个月吧
o8也说要努力把美国带出经济衰退，把失业率降到多少。愿望总是美好的。

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

: 可是律师声称是派人参加个什么会，人家官老爷的主任自己说的

m*n2011-08-20 07:08

9 楼

对第一个没用，对后来的有用。
这个题目是两个元素和是n的简版。
a+b=0, 如果是sorted, 你左右操作指针，就可以找到那两个元素in O(n)
a+b+c=0,实际是要找a+b=-c, 针对每个元素，用前面的办法操作就是n*o(n)
a+b+c+d =0 实际不就是a+b+c=-d, 同样用前一步的函数调用n回，用n*o(n^2)
应该这样可以吧。

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

: 没看出来排序在这里有什么用
: 你已经有hashtable了，寻找一个元素已经是O(1)

y*y2011-08-20 07:08

10 楼

不可能。这几个月140拖的时间越来越长了。

L*Q2011-08-20 07:08

11 楼

原帖说4个数的算法是O(N^2)

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

: 对第一个没用，对后来的有用。
: 这个题目是两个元素和是n的简版。
: a+b=0, 如果是sorted, 你左右操作指针，就可以找到那两个元素in O(n)
: a+b+c=0,实际是要找a+b=-c, 针对每个元素，用前面的办法操作就是n*o(n)
: a+b+c+d =0 实际不就是a+b+c=-d, 同样用前一步的函数调用n回，用n*o(n^2)
: 应该这样可以吧。

n*g2011-08-20 07:08

12 楼

他们的话要能信，母猪会上树

m*n2011-08-20 07:08

13 楼

我能想到的办法还是先sort一下，
然后两个一组，一组从左，一组从右。
如果要为0，必然左是负数，右是正数。
一次只移动一个指针，相当一个左窗口，一个右窗口，滑动距离是1

【在 L***Q 的大作中提到】

: 原帖说4个数的算法是O(N^2)

m*72011-08-20 07:08

14 楼

pp 15 days

L*Q2011-08-20 07:08

15 楼

如果一个数可以被计算多次，O(n^2)的算法还是可以的。计算每一对数的和，然后放入
hashtable。然后再对每一对数的和，在hashtable中查找是否有其负。时间复杂度O(n^
2)，空间复杂度O(n^2)。
如果每个数只能算一次，那俺再想想

【在 L***Q 的大作中提到】

: 原帖说4个数的算法是O(N^2)

g*e2011-08-20 07:08

16 楼

可能是还没到9月底,现在是最忙的时候,忙着处理完EB2.

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

: 不可能。这几个月140拖的时间越来越长了。

m*n2011-08-20 07:08

17 楼

这应该符合O(n^2)的要求， n个数，对数只有n*(n-1)/2 对，扫描两次，应该可以的。

n^

【在 L***Q 的大作中提到】

: 如果一个数可以被计算多次，O(n^2)的算法还是可以的。计算每一对数的和，然后放入
: hashtable。然后再对每一对数的和，在hashtable中查找是否有其负。时间复杂度O(n^
: 2)，空间复杂度O(n^2)。
: 如果每个数只能算一次，那俺再想想

H*e2011-08-20 07:08

18 楼

不管你们信不信，反正我是不信

L*Q2011-08-20 07:08

19 楼

这个有可能不对，例如-100 1 ... 99。一个答案是-100,1,2,97，但是右侧的两个数字
没在滑动距离为1 的窗口内

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

: 我能想到的办法还是先sort一下，
: 然后两个一组，一组从左，一组从右。
: 如果要为0，必然左是负数，右是正数。
: 一次只移动一个指针，相当一个左窗口，一个右窗口，滑动距离是1

s*n2011-08-20 07:08

20 楼

真实的谎言。我不信。

H*e2011-08-20 07:08

21 楼

每个数肯定只能算一次
然后用hashtable找数，很可能找到自己
这个就是code不clean的地方

n^

【在 L***Q 的大作中提到】

f*D2011-08-20 07:08

22 楼

我那廉价又充沛的感情
又被欺骗了

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

: 他们的话要能信，母猪会上树

i*e2011-08-20 07:08

23 楼

To find an answer where sum of four numbers equal to X, you can do it in O(n
^2) using some extra space. Basic idea is like what LeoZQ said, put all pair
sums in a hash table and search in the hash table. See below for a nice
idea:
http://stackoverflow.com/questions/3569504/find-four-elements-i
However, if you think carefully, if you wish to find all possible
quadruplets that sum to X, the worst case is O(n^3). This is because the
number of combinations grow in the order of O(n^3). (Credits to adjlist who figure this out.)
I have the problems two sum, 3sum, and 4sum here, and created test cases for
you to see if your program is correct. (you can submit Java or C++).
http://www.leetcode.com/onlinejudge

I*62011-08-20 07:08

24 楼

不要过分悲观。如果他们说努力,肯定会有改善

L*Q2011-08-20 07:08

25 楼

大牛出现了，膜拜一下，保佑俺接下来interview人挡杀人佛挡杀佛

(n
pair
who figure this out.)
for

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

: To find an answer where sum of four numbers equal to X, you can do it in O(n
: ^2) using some extra space. Basic idea is like what LeoZQ said, put all pair
: sums in a hash table and search in the hash table. See below for a nice
: idea:
: http://stackoverflow.com/questions/3569504/find-four-elements-i
: However, if you think carefully, if you wish to find all possible
: quadruplets that sum to X, the worst case is O(n^3). This is because the
: number of combinations grow in the order of O(n^3). (Credits to adjlist who figure this out.)
: I have the problems two sum, 3sum, and 4sum here, and created test cases for
: you to see if your program is correct. (you can submit Java or C++).

l*w2011-08-20 07:08

26 楼

They concentrate on 140 currently at least.
http://dashboard.uscis.gov/

m*n2011-08-20 07:08

27 楼

这个会对啊， -100，1是在左窗口， 2,97是右窗口。
如果左+右=0 ，就找到了。
否则左+右>0, 右=右-1
否则左=左+1

【在 L***Q 的大作中提到】

: 这个有可能不对，例如-100 1 ... 99。一个答案是-100,1,2,97，但是右侧的两个数字
: 没在滑动距离为1 的窗口内

f*D2011-08-20 07:08

28 楼

I can't see the fact from your link.

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

: They concentrate on 140 currently at least.
: http://dashboard.uscis.gov/

H*e2011-08-20 07:08

29 楼

，
我把正数和负数分开，就是为了避免你说的bug
~~~~~~~~~~~
为什么这里不包括array[0] ?

【在 L***Q 的大作中提到】

: 一种延伸是不让你使用额外的storage，所以没法用hashtable。
: 三个数和为0，不用分正数负数，一个hashtable装全部数就行了。使用hashtable有一
: 个容易产生bug的地方：把一个数多次计算。比如-2 -1 4，不留神就会得到-2， -2，
: 4的组合。hashtable只告诉你某个数存在否，但没告诉你存在多少次。
: 不用hashtable的解法，sort然后头尾往中间扫描两端。最初是第一个array[0]，然后
: test array[1..n]中是否有2个数加起来等于-array[0]。接下来是array[1]，test
: array[2..n]中是否有2个数加起来等于-array[1]。时间复杂度仍然为O(N^2)，空间复
: 杂度O(1)

f*D2011-08-20 07:08

30 楼

I can't see the fact from you link.

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

: They concentrate on 140 currently at least.
: http://dashboard.uscis.gov/

z*u2011-08-20 07:08

31 楼

假设我们想找数列里有没有m个数的和为0
l = ceil(m / 2);
k = m - l;
首先，找到数列里每一个可能的l个数的组合，把他们的sum以及用到的数一起存到
hashtable，这个过程是O(n^l) time, O(n^l) space
重复以上过程，用k代替l，O(n^k) time, O(n^k) space
然后，遍历第一个hashtable，对里面的每一个元素
1, 查看第二个hashtable里有没有元素，它们的sum互为正负（O(1) time)
2, 如果有互为正负的数，看他们用到的数有没有重复(O(m))
对于给定的题目，m是常数，所以遍历部分的时间复杂度是O(n^l)
因为 l >= k，所以最终的时间复杂度是 O(n^l), l = ceil(m/2)
m = 2, O(n)
m = 3, O(n^2)
m = 4, O(n^2)
m = 5, O(n^3)
etc...

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

L*Q2011-08-20 07:08

32 楼

你的solution是看每个正数a，是否有2个负数之和等于这个-a；也看每个负数b，是否
有2个正数之和等于-b。
分开也会有bug的。比如-2 0 4。正数为4，然后在负数的hashtable里面查是否有2个负
数之和等于-4。那咋查hashtable才能避免把-2算2次呢？
一个办法：hashmap，保存数和它出现的次数。

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

:
: ，
: 我把正数和负数分开，就是为了避免你说的bug
: ~~~~~~~~~~~
: 为什么这里不包括array[0] ?

m*n2011-08-20 07:08

33 楼

这个解法靠谱。。。

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

: 假设我们想找数列里有没有m个数的和为0
: l = ceil(m / 2);
: k = m - l;
: 首先，找到数列里每一个可能的l个数的组合，把他们的sum以及用到的数一起存到
: hashtable，这个过程是O(n^l) time, O(n^l) space
: 重复以上过程，用k代替l，O(n^k) time, O(n^k) space
: 然后，遍历第一个hashtable，对里面的每一个元素
: 1, 查看第二个hashtable里有没有元素，它们的sum互为正负（O(1) time)
: 2, 如果有互为正负的数，看他们用到的数有没有重复(O(m))
: 对于给定的题目，m是常数，所以遍历部分的时间复杂度是O(n^l)

L*Q2011-08-20 07:08

34 楼

Good idea
一个hashtable保存每两个数的和。另外要一个hashmap保存每个数在array里面出现的
次数。从hashtable里面找到2对之后，在hashmap里面check这4个数字出现的次数是否
valid。

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

H*e2011-08-20 07:08

35 楼

“那咋查hashtable才能避免把-2算2次呢？”
这个就是那个two sum ＝ 0问题啊
只走一次。
比如在放入元素之前，检查sum-itself在不在，之后再放itself进hashtable

【在 L***Q 的大作中提到】

: 你的solution是看每个正数a，是否有2个负数之和等于这个-a；也看每个负数b，是否
: 有2个正数之和等于-b。
: 分开也会有bug的。比如-2 0 4。正数为4，然后在负数的hashtable里面查是否有2个负
: 数之和等于-4。那咋查hashtable才能避免把-2算2次呢？
: 一个办法：hashmap，保存数和它出现的次数。

L*Q2011-08-20 07:08

36 楼

俺还是没看出有什么区别。两个test case：
case 1： -2 -2 4 5
case 2： -2 4 5
分正负hashtable，两个test case你的hashtable放的东西一样
负hashtable只有-2，正hashtable有4和5

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

: “那咋查hashtable才能避免把-2算2次呢？”
: 这个就是那个two sum ＝ 0问题啊
: 只走一次。
: 比如在放入元素之前，检查sum-itself在不在，之后再放itself进hashtable

H*12011-08-20 07:08

37 楼

为什么不是l = 2^ceil(log m)
then k = l/2

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

z*u2011-08-20 07:08

38 楼

minimize max(l,k), subject to l + k = m; l belongs to N; k belongs to N

【在 H*****1 的大作中提到】

: 为什么不是l = 2^ceil(log m)
: then k = l/2

m*n2011-08-20 07:08

39 楼

public class CheckZeroSum {

public static void main(String args[]) {
int elem[]={-4,-3,-2,-1,2,3};
int elem2[] = {-5,-1,0,1,2,4,5};
checkZero(elem,4);
checkZero(elem2,2);
}

public static void checkZero(int[] elem, int n) {
//left, right
//left window size, right window size
int left = 0 ;
int right = elem.length-1;
int left_windowsize= n/2;
int right_windowsize= n-n/2;
while(leftint leftsum=0;
int rightsum=0;
for(int i=0;ileftsum+=elem[left+i];
}
for(int j=0;jrightsum+=elem[right-j];
}
if(leftsum+rightsum==0) {
for(int i=0;iSystem.out.println(elem[left+i]+" ");
}
for(int j=0;jSystem.out.println(elem[right-j]+" ");
}
left++;
right--;
}
else if(leftsum+rightsum>0) {
right--;
}
else
left++;

}

}

}
简单的实现，至少对4和2都是对的

m*n2011-08-20 07:08

40 楼

没人探讨下我的解法是否正确？