facebook电面题目 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

facebook电面题目

facebook电面题目# JobHunting - 待字闺中

c*e2010-12-02 08:12

1 楼

给一个数组A[]，写一个程序判断是否能够找到3个不同的index i,j & k 使得A[i]+A[j
]+A[k]==0.
要求：time complexity in O(n^2),space complexity in O(1).
我只写出了time complexity in O(n^2),space complexity in O(n)；另外程序有几个
小问题。

c*22010-12-02 08:12

2 楼

modification from finding a pair whose sum is equal to a given num

c*e2010-12-02 08:12

3 楼

没仔细想过这道题，后面短路了没有把space complexity 降下来。

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

: modification from finding a pair whose sum is equal to a given num

h*d2010-12-02 08:12

4 楼

3－sum problem, ihas1337code大侠的blog上有这题

d*t2010-12-02 08:12

5 楼

先排序 O(n*logn)，再先取一个数m，再从剩下的数里找和为-m的两个数，于是时间复
杂度是O(n^2)

c*e2010-12-02 08:12

6 楼

我最怕见过又没有认真做过的题，好像有心理障碍，一片麻木。

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

: 3－sum problem, ihas1337code大侠的blog上有这题

c*e2010-12-02 08:12

7 楼

当时没有想到在一个排好序的数组里找一个指定和的pair是线性的。后来面试官告诉了
我方法，想了半天才明白过来。（心服口服。）

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

: 先排序 O(n*logn)，再先取一个数m，再从剩下的数里找和为-m的两个数，于是时间复
: 杂度是O(n^2)

D*i2010-12-02 08:12

8 楼

排序不会改变原来数值的index么？
结果要求是返回i,j,k使得a[i]+a[j]+a[k]=0吧?
如果空间复杂度为O(1)的话，怎么保存原来的i,j和k啊？
是我没有理解题意么。。。。

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

: 当时没有想到在一个排好序的数组里找一个指定和的pair是线性的。后来面试官告诉了
: 我方法，想了半天才明白过来。（心服口服。）

c*e2010-12-02 08:12

9 楼

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

: 排序不会改变原来数值的index么？
: 结果要求是返回i,j,k使得a[i]+a[j]+a[k]=0吧?
: 如果空间复杂度为O(1)的话，怎么保存原来的i,j和k啊？
: 是我没有理解题意么。。。。

c*e2010-12-02 08:12

10 楼

Only require to return true or false

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

c*e2010-12-02 08:12

11 楼

c*22010-12-02 08:12

12 楼

modification from finding a pair whose sum is equal to a given num

c*e2010-12-02 08:12

13 楼

没仔细想过这道题，后面短路了没有把space complexity 降下来。

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

: modification from finding a pair whose sum is equal to a given num

h*d2010-12-02 08:12

14 楼

3－sum problem, ihas1337code大侠的blog上有这题

d*t2010-12-02 08:12

15 楼

先排序 O(n*logn)，再先取一个数m，再从剩下的数里找和为-m的两个数，于是时间复
杂度是O(n^2)

c*e2010-12-02 08:12

16 楼

我最怕见过又没有认真做过的题，好像有心理障碍，一片麻木。

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

: 3－sum problem, ihas1337code大侠的blog上有这题

c*e2010-12-02 08:12

17 楼

: 先排序 O(n*logn)，再先取一个数m，再从剩下的数里找和为-m的两个数，于是时间复
: 杂度是O(n^2)

D*i2010-12-02 08:12

18 楼

: 当时没有想到在一个排好序的数组里找一个指定和的pair是线性的。后来面试官告诉了
: 我方法，想了半天才明白过来。（心服口服。）

c*e2010-12-02 08:12

19 楼

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

c*e2010-12-02 08:12

20 楼

Only require to return true or false

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

s*f2010-12-02 08:12

21 楼

//给一个数组A[]，写一个程序判断是否能够找到3个不同的index i,j & k 使得A[i]+A
[j
//]+A[k]==0.
//要求：time complexity in O(n^2),space complexity in O(1).
//but here the returned index related to the after-sort-array.
//through O(n^2), it still can be improved by using binary search.
//also, if (in[0] + in[1] + in[2] >= sum),
//(in[len-1] + in[len-2] + in[len-3] <= sum) the program need stop.
bool FindThreeNum(int in[], int len, int sum, int out[]){
if (!in || len < 3 || !out)
return false;
std::sort(in, in + len);
for (int i = 0; i < len - 2; ++i){
int j = i + 1;
int k = len - 1;
int two_sum = sum - in[i];
while(j < k){
if (in[j] + in[k] == two_sum){
out[0] = i;
out[1] = j;
out[2] = k;
return true;
}else if(in[j] + in[k] < two_sum){
++j;
}else{
--k;
}
}
}
return false;
}

z*n2010-12-02 08:12

22 楼

时间复杂度 O(n*log(n))的排序算法，空间复杂度都不是O(1)

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

: 先排序 O(n*logn)，再先取一个数m，再从剩下的数里找和为-m的两个数，于是时间复
: 杂度是O(n^2)

s*f2010-12-02 08:12

23 楼

bool FindThreeNum1(int in[], int len, int sum, int out[]){
if (!in || len < 3 || !out)
return false;
std::sort(in, in + len);
int prej = 1;
int prek = len - 1;
for (int i = 0; i < prek - 2; ++i){
bool nobig = true;
bool nosmall = true;
int j = prej;
int k = prek;
int two_sum = sum - in[i];
while(j < k){
if (in[j] + in[k] == two_sum){
out[0] = in[i];
out[1] = in[j];
out[2] = in[k];
return true;
}else if(in[j] + in[k] < two_sum){
nosmall = false;
++j;
if (nobig){
prej = j;
}
}else{
nobig = false;
--k;
if (nosmall){
prek = k;
}
}
}
}
return false;
}

[j

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

: 给一个数组A[]，写一个程序判断是否能够找到3个不同的index i,j & k 使得A[i]+A[j
: ]+A[k]==0.
: 要求：time complexity in O(n^2),space complexity in O(1).
: 我只写出了time complexity in O(n^2),space complexity in O(n)；另外程序有几个
: 小问题。

b*g2010-12-02 08:12

24 楼

太有同感了。
而且是觉得是看过了，心里就默认会了，其实自己知道并没有在血液里理解。:-)

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

: 我最怕见过又没有认真做过的题，好像有心理障碍，一片麻木。

s*n2010-12-02 08:12

25 楼

bool findZeroSum (int set[], int size){
int i,jk, left, right;
int vi, vj, vk;
bool found=false;
if (size<3) return false;
sort (set,set+size);
for (i=size-1;i>1;i--){
left = 0; right = i-1;
while (right>left){
if (set[left]+set[right]==-set[i]) {found=true; j=left; k=right; break
;}
else if (set[left]+set[right]>-set[i]) left++;
else right--;
}
if (found) break;
}
if (found){
return true;
}return false;
}

+A

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

: //给一个数组A[]，写一个程序判断是否能够找到3个不同的index i,j & k 使得A[i]+A
: [j
: //]+A[k]==0.
: //要求：time complexity in O(n^2),space complexity in O(1).
: //but here the returned index related to the after-sort-array.
: //through O(n^2), it still can be improved by using binary search.
: //also, if (in[0] + in[1] + in[2] >= sum),
: //(in[len-1] + in[len-2] + in[len-3] <= sum) the program need stop.
: bool FindThreeNum(int in[], int len, int sum, int out[]){
: if (!in || len < 3 || !out)

a*m2010-12-02 08:12

26 楼

用o(n^2)的排序就好了。

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

: 时间复杂度 O(n*log(n))的排序算法，空间复杂度都不是O(1)

y*g2010-12-02 08:12

27 楼

heapsort就是inplace nlogn

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

: 时间复杂度 O(n*log(n))的排序算法，空间复杂度都不是O(1)

e*s2010-12-02 08:12

28 楼

同问，sort了之后index不是改变了吗？

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

e*s2010-12-02 08:12

29 楼

对不起，我又没认真看回复。。。。
public static bool FindSum(int[] arr)
{
bool found = false;
Array.Sort(arr);
int lenght = arr.Length;
int left, right;
for(int i = lenght - 1; i >= 2; i--)
{
left = 0;
right = i - 1;
while (left < right)
{
if (arr[left] + arr[right] == -arr[i])
return true;
else if (arr[left] + arr[right] < -arr[i])
left++;
else
right--;
}
}
return found;
}

j*x2010-12-02 08:12

30 楼

反正这里考虑的重点不是这个部分

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

: 时间复杂度 O(n*log(n))的排序算法，空间复杂度都不是O(1)

z*t2010-12-02 08:12

31 楼

There is a detailed solution for this problem on the website:
http://codercareer.blogspot.com/2011/10/no-09-numbers-with-give

[j

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

h*n2010-12-02 08:12

32 楼

nice
可以和hash的做法互为补充啊~

+A
几个

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

: There is a detailed solution for this problem on the website:
: http://codercareer.blogspot.com/2011/10/no-09-numbers-with-give
:
: [j

z*t2010-12-02 08:12

33 楼

不然吧。
http://codercareer.blogspot.com/2011/10/no-09-numbers-with-give
中的做法比用hash的算法要好吧。
hash需要O(n)的辅助空间，但链接中的算法不需要

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

: nice
: 可以和hash的做法互为补充啊~
:
: +A
: 几个