问个fb onsite题目 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个fb onsite题目

问个fb onsite题目# JobHunting - 待字闺中

j*j2015-05-13 07:05

1 楼

http://mitbbs.com/article_t/shopping/31833755.html
没有limit的人，可以take the risk

S*w2015-05-13 07:05

2 楼

Leetcode原题，three sum的变种, 容许数字重用

d*u2015-05-13 07:05

3 楼

不是100% 肯定

r*g2015-05-13 07:05

4 楼

?

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

: Leetcode原题，three sum的变种, 容许数字重用

b*52015-05-13 07:05

5 楼

我靠，我估计就挂在了这题。。
就是比如【-2， -1， 0， 0 ， 1， 1， 2】
this is corresponding to [ a, b, c, d, e, f, g]
比如说你要的target是0
要的答案是：【b， c， e] ( first 0, first 1)
[b, c, f] (first 0, second 1)
[b, d, e] (second 0, first 1)
[b, d, f] (second 0, second 1)
along with others...

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

: Leetcode原题，three sum的变种, 容许数字重用

y*e2015-05-13 07:05

6 楼

我问过这题
http://www.mitbbs.com/article_t/JobHunting/32899939.html

b*52015-05-13 07:05

7 楼

反正我被问的，就是我楼上写的那个意思。。我结果写的吭哧吭哧的。。。

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

: 我问过这题
: http://www.mitbbs.com/article_t/JobHunting/32899939.html

y*e2015-05-13 07:05

8 楼

那可不一定。。。没有拒信就有希望！

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

: 我靠，我估计就挂在了这题。。
: 就是比如【-2， -1， 0， 0 ， 1， 1， 2】
: this is corresponding to [ a, b, c, d, e, f, g]
: 比如说你要的target是0
: 要的答案是：【b， c， e] ( first 0, first 1)
: [b, c, f] (first 0, second 1)
: [b, d, e] (second 0, first 1)
: [b, d, f] (second 0, second 1)
: along with others...
:

S*w2015-05-13 07:05

9 楼

谢谢大家回复
这题目就是看着简单其实不简单

S*w2015-05-13 07:05

10 楼

是不是考虑用 combinational sum 方法

g*c2015-05-13 07:05

11 楼

这题是不是用backtracking？

b*52015-05-13 07:05

12 楼

我被问的题，是只能取3个element

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

: 是不是考虑用 combinational sum 方法

S*w2015-05-13 07:05

13 楼

请斧正感觉有点over kill
public List> findSum(int[] candidates, int k, int target) {
List> ret = new ArrayList>();
if (candidates.length == 0) return ret;
Arrays.sort(candidates);
List path = new ArrayList();
dfs(candidates, 0, k, target, path, ret);
return ret;
}
private void dfs(int[] candidates, int depth, int k, int target, List<
Integer> path, List> ret) {
if (k == path.size()) {
if (target == 0) ret.add(new ArrayList(path));
}
else {
if (target < 0 || depth == candidates.length || target <
candidates[depth]) {
return;
}
else {
for(int i = depth; i < candidates.length; ++i) {
path.add(i);
dfs(candidates, i, k, target - candidates[i], path, ret);
path.remove(path.size() - 1);
}
}
}
}
{-2, -1, 0, 0, 1, 1, 1, 2}
0 1 2 3 4 5 6 7
[0, 2, 7]
[0, 3, 7]
[0, 4, 4]
[0, 4, 5]
[0, 4, 6]
[0, 5, 5]
[0, 5, 6]
[0, 6, 6]
[1, 1, 7]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]
[2, 2, 2]
[2, 2, 3]
[2, 3, 3]
[3, 3, 3]
-2, 0, 1, 2, 4, 6
0 1 2 3 4 5
是说比如-2,4,6,1,2,0取三数和为0的话，那么
-2,-2,4
-2,2,0
-2,1,1
0，0，0
[0, 0, 4] -2, -2, 4
[0, 1, 3] -2, 0, 2
[0, 2, 2] -2, 1, 1
[1, 1, 1] 0, 0, 0

S*w2015-05-13 07:05

14 楼

是的，可以只检查选择3个情况

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

: 我被问的题，是只能取3个element

p*g2015-05-13 07:05

15 楼

这个复杂度是O(n^k)

) {

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

: 请斧正感觉有点over kill
: public List> findSum(int[] candidates, int k, int target) {
: List> ret = new ArrayList>();
: if (candidates.length == 0) return ret;
: Arrays.sort(candidates);
: List path = new ArrayList();
: dfs(candidates, 0, k, target, path, ret);
: return ret;
: }
: private void dfs(int[] candidates, int depth, int k, int target, List<

b*52015-05-13 07:05

16 楼

我用的是3sum的两个index的变形，就是等于target的时候，我写的乱七八糟的。。
其实还没combination sum清楚。。。

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

: 是的，可以只检查选择3个情况

S*w2015-05-13 07:05

17 楼

也不算吧
C(N,3) N^3

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

: 这个复杂度是O(n^k)
:
: ) {

S*w2015-05-13 07:05

18 楼

所以感觉有点overkill
来这里问问

。

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

: 我用的是3sum的两个index的变形，就是等于target的时候，我写的乱七八糟的。。
: 其实还没combination sum清楚。。。

b*52015-05-13 07:05

19 楼

对。我后来写的3sum的变形，也变为N^3了，所以我觉得他虽然说3sum，其实就是
考combination sum

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

: 也不算吧
: C(N,3) N^3

S*w2015-05-13 07:05

20 楼

用3sum的话
固定i,
如果 Ai + Aj + Ak == target,
j, k 怎么移动？
++j, --k 肯定会漏掉
++j, 可能漏调 1, xxxx, -1, -1 的情况
---k 类似
总之不太好写

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

: 对。我后来写的3sum的变形，也变为N^3了，所以我觉得他虽然说3sum，其实就是
: 考combination sum

b*52015-05-13 07:05

21 楼

我用了两个while loop， outer loop移动j， inner loop移动k。。。
所以写的磕磕碰碰的。。所以我说combination sum写清楚。。。

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

: 用3sum的话
: 固定i,
: 如果 Ai + Aj + Ak == target,
: j, k 怎么移动？
: ++j, --k 肯定会漏掉
: ++j, 可能漏调 1, xxxx, -1, -1 的情况
: ---k 类似
: 总之不太好写

r*72015-05-13 07:05

22 楼

这个不如排个序然后用2sum得两种解法相结合，N^2

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

: 也不算吧
: C(N,3) N^3

b*52015-05-13 07:05

23 楼

你写个code出来看看。。。

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

: 这个不如排个序然后用2sum得两种解法相结合，N^2

t*r2015-05-13 07:05

24 楼

说个题外话，这种题用FP写容易很多
用IP写实属蛋疼

S*w2015-05-13 07:05

25 楼

求算法

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

: 这个不如排个序然后用2sum得两种解法相结合，N^2

r*72015-05-13 07:05

26 楼

如果我没理解错，就是一组数中有3个数x[i0], x[i1], x[i2]加起来等于target，然后
这个数组中的数有重复？
那你就对x每个元素都做target - x[i]然后再在数组里求x[i0] + x[i1]等于target -
x[i]不就行了吗？

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

: 求算法

S*w2015-05-13 07:05

27 楼

任何一个数，都可以重用
如果数组是【0， 0】
你的算法是怎么弄？

-

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

: 如果我没理解错，就是一组数中有3个数x[i0], x[i1], x[i2]加起来等于target，然后
: 这个数组中的数有重复？
: 那你就对x每个元素都做target - x[i]然后再在数组里求x[i0] + x[i1]等于target -
: x[i]不就行了吗？

p*g2015-05-13 07:05

28 楼

我贴一个吧，不过是输出数字值，不是下标的。不知道fb要求什么。
import java.util.*;
public class Fb3Sum {

public static List> threeSum(int[] nums, int target) {
Arrays.sort(nums);
List> res = new ArrayList>();
for (int i=0; i<=nums.length-3; i++){
List> lists = twoSum(nums, i+1, target-nums[i]);
for (List list: lists) {
list.add(0, nums[i]);
}
res.addAll(lists);
}
return res;
}

private static void addToLists(List> lists, int i, int j,
int count ){
for (int k=0; kList list = new ArrayList();
list.add(i);
list.add(j);
lists.add(list);
}
}

private static List> twoSum(int[] nums, int s, int target){
List> lists = new ArrayList>();
int i=s, j=nums.length-1;
while ( iint sum = nums[i]+nums[j];
if ( sum>target ){
j--;
} else if (sum < target ){
i++;
} else {
int count ;
if ( nums[i] != nums[j] ) {
int left = 1;
int right =1;
while ( nums[i] == nums[i+left] )
left++;
while ( nums[j] == nums[j-right] )
right++;
count = left *right;
addToLists(lists, nums[i], nums[j], count);
i+=left;
j=j-right+1;
} else {
int len = j-i+1;
count = len*(len-1)/2;
addToLists(lists, nums[i], nums[j], count);
break;
}
}
}

return lists;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// int[] nums={-2, -1, 0, 1 ,1 , 2, 3, 4};
// int[] nums={-2, -1, 0, 0 , 1, 1, 2};
int[] nums={-2, -1, 0, 0, 1, 1, 1, 2};

int target = 0;
List> res = Fb3Sum.threeSum(nums, target);
for (List list : res) {
for ( int i : list )
System.out.print(i+", ");
System.out.println();
}
}
}

r*72015-05-13 07:05

29 楼

已经贴上了

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

: 我贴一个吧，不过是输出数字值，不是下标的。不知道fb要求什么。
: import java.util.*;
: public class Fb3Sum {
:
: public static List> threeSum(int[] nums, int target) {
: Arrays.sort(nums);
: List> res = new ArrayList>();
: for (int i=0; i<=nums.length-3; i++){
: List> lists = twoSum(nums, i+1, target-nums[i]);
: for (List list: lists) {

r*72015-05-13 07:05

30 楼

我开始理解错了，以为是元素有重复
不过可以重用有啥影响呢？2sum那种两头夹的方法可以改成重用的吧，允许start ==
end即可，再不济把数组给double一下啊。。。

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

: 任何一个数，都可以重用
: 如果数组是【0， 0】
: 你的算法是怎么弄？
:
: -

c*n2015-05-13 07:05

31 楼

这个在leetcode 上discussion forum 那么多答案，为什么还问？
Arrays.sort(A);
for(int i=0;iint newTarget = target - A[i];
// now use the O(N) 2-sum on a sorted array
int l = i+1; int h = size-1;
while(l < h) {
if (A[l] + A[h] == newTarget) print_out_result;
else
if (A[l]+ A[h] < newTarget) l++;
else h--;
}
}

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

: 求算法

S*w2015-05-13 07:05

32 楼

我贴一个吧，不过是输出数字值，不是下标的。不知道fb要求什么。
import java.util.*;
public class Fb3Sum {

public static List> threeSum(int[] nums, int target) {
Arrays.sort(nums);
List> res = new ArrayList>();
for (int i=0; i<=nums.length-3; i++){
List> lists = twoSum(nums, i+1, target-nums[i]);
// i 可以重用
for (List list: lists) {
list.add(0, nums[i]);
}
res.addAll(lists);
}
return res;
}

private static void addToLists(List> lists, int i, int j,
int count ){
for (int k=0; kList list = new ArrayList();
list.add(i);
list.add(j);
lists.add(list);
}
}

private static List> twoSum(int[] nums, int s, int target){
List> lists = new ArrayList>();
int i=s, j=nums.length-1;
while ( iint sum = nums[i]+nums[j];
if ( sum>target ){
j--;
} else if (sum < target ){
i++;
} else {
int count ;
if ( nums[i] != nums[j] ) {
int left = 1;
int right =1;
while ( nums[i] == nums[i+left] )
left++;
while ( nums[j] == nums[j-right] )
right++;
count = left *right;
addToLists(lists, nums[i], nums[j], count);
这错了？
i+=left;
j=j-right+1;
} else {
int len = j-i+1;
count = len*(len-1)/2;
不一定吧
addToLists(lists, nums[i], nums[j], count);
break;
}
}
}

return lists;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// int[] nums={-2, -1, 0, 1 ,1 , 2, 3, 4};
// int[] nums={-2, -1, 0, 0 , 1, 1, 2};
int[] nums={-2, -1, 0, 0, 1, 1, 1, 2};

int target = 0;
List> res = Fb3Sum.threeSum(nums, target);
for (List list : res) {
for ( int i : list )
System.out.print(i+", ");
System.out.println();
}
}
}

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

b*52015-05-13 07:05

33 楼

差不多那个意思。所以说，还是combination sum 清楚。。。

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

S*w2015-05-13 07:05

34 楼

这不对吧
题目要求数可以重用

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

: 这个在leetcode 上discussion forum 那么多答案，为什么还问？
: Arrays.sort(A);
: for(int i=0;i: int newTarget = target - A[i];
: // now use the O(N) 2-sum on a sorted array
: int l = i+1; int h = size-1;
: while(l < h) {
: if (A[l] + A[h] == newTarget) print_out_result;
: else
: if (A[l]+ A[h] < newTarget) l++;

b*52015-05-13 07:05

35 楼

其实，还不大能用count，因为其实不是int【】，而是一个custom class
class S{
int num；
string name；
}
要输出的是name的组合。

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

c*n2015-05-13 07:05

36 楼

哦，sorry, 我理解成“有重复数” 。。。
how about simply replicating the array 3 times?

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

: 这不对吧
: 题目要求数可以重用

s*h2015-05-13 07:05

37 楼

可是事先算算每个元素重复的个数吗？
上面的例子只需要看【-2， -1， 0 ， 1， 2】，用普通的3sum 得到[-1,0,1] 因
为 -1重复一遍，0重复两遍，1重复遍，所以要输出 [-1,0,1] 1*2*2=4次就可以了。

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

b*52015-05-13 07:05

38 楼

好像不大对
就是给你一个array
[{0, "a"}, {0, "b"} ,{1, "c"}, {1, "d"}]
target是1
你要输出 “ac”， "ad", "bc", "bd"

b*52015-05-13 07:05

39 楼

好人做到底吧。还被问了POI，那个fbrefer给的link里的POI的presentation，好
像面试官听都没听说过。。。反正最后也答的不大好

b*52015-05-13 07:05

40 楼

可以，但你看我前面说的，其实不是一个integer array，是个custom class array
， class里有一个string 和integer，用integer来算3sum，输出的要是那些
corresponding name
比如-1有“a", "b" "c", 你就要输出“axx", "bxx”， “cxx“

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

: 可是事先算算每个元素重复的个数吗？
: 上面的例子只需要看【-2， -1， 0 ， 1， 2】，用普通的3sum 得到[-1,0,1] 因
: 为 -1重复一遍，0重复两遍，1重复遍，所以要输出 [-1,0,1] 1*2*2=4次就可以了。

s*h2015-05-13 07:05

41 楼

那这样的话最坏的情况会有 O(N^3) 的可能性，所以就只能combination了。

b*52015-05-13 07:05

42 楼

我说了半天了，觉得还是combination简单清楚。。。

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

: 那这样的话最坏的情况会有 O(N^3) 的可能性，所以就只能combination了。