Facebook onsite 个人认为巨难的一道题，请大牛们来评估下 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Facebook onsite 个人认为巨难的一道题，请大牛们来评估下

Facebook onsite 个人认为巨难的一道题，请大牛们来评估下# JobHunting - 待字闺中

C*n2013-12-10 08:12

1 楼

题目看起来很简单，但是就是很纠结
看起来各种有思路，但是往深想是很纠结的。在面试官的各种提示下，做了出来，但是
结果不好。。。。
题目是：
给A，B 2个array，里面都是integer，已经排好序了，由大到小，他们的长度都是N
现在从A和B里各选出一个数，总成一个sum，请返回前N个最大的sum
最好不要简单表达下思路的，我开始也是这样，但是不通。。。
希望能彻底想到如何返回N个sum
谢谢大家。。。
我本人来说的话，真的目前没有见过这样的题。。。我是小弱，所以希望见多识广的大
牛们帮我看看这种题

f*n2013-12-10 08:12

2 楼

建立一个max_heap, 每次取最大的，假设为这次取出的是(a[i]+b[j]),取出该值存入结
果后，把a[i-1]+b[j] 和 a[i]+b[j-1]加入堆中，以此类推，有点类似order level
traverse.

g*e2013-12-10 08:12

3 楼

感觉可以用个maxHeap, 存每一个pair, 用pair的和来排序
另外用一个set 来记录已经存入heap的pair
每次从heap里拿出pair sum最大的，比如A(i), B(j)，然后把和 ), B(j+1)> 放入heap. (如果它们不在set里面的话）
初始化就是把放入heap.
然后抽取N次max，每次把新的candidate(s)放入heap

P*r2013-12-10 08:12

4 楼

这样做都不用max heap. 是巨简单的解法。

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

: 建立一个max_heap, 每次取最大的，假设为这次取出的是(a[i]+b[j]),取出该值存入结
: 果后，把a[i-1]+b[j] 和 a[i]+b[j-1]加入堆中，以此类推，有点类似order level
: traverse.

c*r2013-12-10 08:12

5 楼

http://stackoverflow.com/questions/5212037/find-the-pair-across

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

: 题目看起来很简单，但是就是很纠结
: 看起来各种有思路，但是往深想是很纠结的。在面试官的各种提示下，做了出来，但是
: 结果不好。。。。
: 题目是：
: 给A，B 2个array，里面都是integer，已经排好序了，由大到小，他们的长度都是N
: 现在从A和B里各选出一个数，总成一个sum，请返回前N个最大的sum
: 最好不要简单表达下思路的，我开始也是这样，但是不通。。。
: 希望能彻底想到如何返回N个sum
: 谢谢大家。。。
: 我本人来说的话，真的目前没有见过这样的题。。。我是小弱，所以希望见多识广的大

l*o2013-12-10 08:12

6 楼

一开始想歪了。。。
这个题跟merge k sorted list @leetcode 类似。我用了那个方法。
https://www.dropbox.com/s/6bvp9alxzn21z8v/findN.java

b*c2013-12-10 08:12

7 楼

x*log(x)誰都想的到，問題是有更快的嗎

l*o2013-12-10 08:12

8 楼

不能了吧

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

: x*log(x)誰都想的到，問題是有更快的嗎

b*c2013-12-10 08:12

9 楼

map> two_sum(N);
int pos[N];
for(int i=0;ipos[i]=0;
if (two_sum.find(A[i]+b[0]) != two_sum.end()){
list lst(1,i);
two_sum[A[i]+b[0]] = lst;
}
else two_sum[A[i]+b[0]].push_back(i);
}
//pop sum
B[n]= -INT_MAX;
for(int i=0;iif (two_sum.empty()) break;
list &lst= *two_sum.rbegin();
cout<for (list::iterator it = lst.begin(); it!=lst.end(); it++){
int pos_A = *it;
while ( pos[pos_A]if (pos[pos_A]if (two_sum.find(A[pos_A]+b[pos[pos_A]]) != two_sum.end()){
list lst(1,pos_A);
two_sum[A[pos_A]+b[pos[pos_A]]] = lst;
}
else two_sum[A[pos_A]+b[pos[pos_A]]].push_back(pos_A);
}
}
two_sum.erase(two_sum.rbegin());
}

h*62013-12-10 08:12

10 楼

可以当作杨氏矩阵取最大的N个数来解吧。

m*n2013-12-10 08:12

11 楼

来个C++的吧：
vector findN(vector v1, vector v2, int N) {
int i=v1.size()-1;
int j=v1.size()-1;
vector result;
while(i>=0&&j>=0&&result.size()result.push_back(v1[i]+v2[j]);
if(i==0) {
j--;
continue;
}
if(j==0) {
i--;
continue;
}
if (v1[i]-v1[i-1]i--;
} else {
j--;
}
}
}

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

m*n2013-12-10 08:12

12 楼

忘了return了
vector findN(vector v1, vector v2, int N) {
int i=v1.size()-1;
int j=v1.size()-1;
vector result;
while(i>=0&&j>=0&&result.size()result.push_back(v1[i]+v2[j]);
if(i==0) {
j--;
continue;
}
if(j==0) {
i--;
continue;
}
if (v1[i]-v1[i-1]i--;
} else {
j--;
}
}
return result;
}

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

: 来个C++的吧：
: vector findN(vector v1, vector v2, int N) {
: int i=v1.size()-1;
: int j=v1.size()-1;
: vector result;
: while(i>=0&&j>=0&&result.size(): result.push_back(v1[i]+v2[j]);
: if(i==0) {
: j--;
: continue;

m*n2013-12-10 08:12

13 楼

我假设数组的由小到大，并且不足N个结果的时候直接return实际结果

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

: 忘了return了
: vector findN(vector v1, vector v2, int N) {
: int i=v1.size()-1;
: int j=v1.size()-1;
: vector result;
: while(i>=0&&j>=0&&result.size(): result.push_back(v1[i]+v2[j]);
: if(i==0) {
: j--;
: continue;

c*u2013-12-10 08:12

14 楼

您这个好像是错的。
例如：
v1={2,4,6,8,10}
v2={1,2,3,4,5}
N =5
应该返回
result={15,14,13,13,12}
而您的程序返回的是
result={15,14,13,12,11}

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

: 我假设数组的由小到大，并且不足N个结果的时候直接return实际结果

c*y2013-12-10 08:12

15 楼

抛砖引玉哈！
下面是一个O(N)的解法，是不是最快了？
Input: two sorted arrays in descending order
A[N]
B[N]
Solution:
Step1: construct two arrays
A'[N] = A[N] + B[0];
B'[N] = B[N] + A[0];
Step2: Use merge sort to take the first N largest out of A' and B'
int C[N];
memset(C, 0, N * sizeof(int));
int i = 0, j = 0, k = 0;
while (i < N && j < N) {
if (A'[i] > B'[j]) {
C[k] = A'[i];
k++;
i++;
} else {
C[k] = B'[j];
k++;
j++;
}
if (k == N) {
break;
}
}
return C;

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

T*32013-12-10 08:12

16 楼

边界没检查，可以假设在两个数组A和B最左侧pad一个Integer.MIN_VALUE
for (int i = N-1; i >= 0; --i) {
for (int j = N-1; j >= 0; --j) {
if (B[j] > A[i-1]) list.add(A[i]+B[j]);
else continue;
}
}

i*e2013-12-10 08:12

17 楼

How about this:
Step 1: sort A & B together and return the indices of A's elements, p_1, ...
, p_n (does not need really sort since each is already sorted);
Step 2: find first p_i such that there is more than N pairs before:
(p_1-1) + (p_2-2)*2 + ... + (p_i-i)*i >= N
etc etc

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

y*g2013-12-10 08:12

18 楼

抛砖引玉，难道我理解错了吗？
------------------------------------------------------
int left = N, ai = N - 1, bi = N - 1;
vector res(N, 0);
while(true){
res.push_back(A[ai] + B[bi]);
if(--left == 0) break;
(A[ai] + B[bi - 1] > A[ai - 1] + B[bi]) ? bi -- : ai --;
}
------------------------------------------------------
果然理解错了，还以为每个数只能用一次。

C*N2013-12-10 08:12

19 楼

#include
#include
#include
using namespace std;
struct currentListStruct
{
double A;
double B;
std::vector values;
};
void getMaxNSum (std::vector & array1, std::vector & array2,
currentListStruct & cur, int N)
{
if (array1.empty () || array2.empty ()) {
return;
}
cur.A = array1.back();
cur.B = array2.back();
cur.values.push_back (cur.A + cur.B);

double a=array1.front()-1, b=array2.front()-1;
// a, b initilized to a small value

array1.pop_back();
array2.pop_back();
while (cur.values.size() < N)
{
if (array1.empty () && array2.empty ())
break;
if (!array1.empty()) {
a = array1.back();
}
if (!array2.empty()) {
b = array2.back();
}

if (a>=b || array2.empty()) {
array1.pop_back();
if (a <= cur.A)
continue;
else {
cur.A = a;
}
}
if (b>a || array1.empty() ) {
array2.pop_back();
if (b <= cur.B)
continue;
else {
cur.B = b;
}
}
cur.values.push_back (cur.A + cur.B);
}
}

P*r2013-12-10 08:12

20 楼

很棒的解法。

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

: 一开始想歪了。。。
: 这个题跟merge k sorted list @leetcode 类似。我用了那个方法。
: https://www.dropbox.com/s/6bvp9alxzn21z8v/findN.java

b*62013-12-10 08:12

21 楼

啊我被面过这道！做不出来就要hint啊

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

x*02013-12-10 08:12

22 楼

B*D2013-12-10 08:12

23 楼

Assuming that K is O(N), the best solution is O(N). It uses a modified
special binary search to find the Kth largest sum. After that you can
iterate all pairs.
If K is O(N^2), the best solution would be O(N^2) since you must iterate
through all K solutions.