[請益] CS Interview Question 1

[Skuld (Sherry)]

I came across this question while practicing for interviews.
This is said to be an interview question from Google.

Given two sorted arrays A and B of n number each
(can assume to be integers, but it does not matter).
Consider the set C = { a+b | a \in A, b \in B }
The set C contains n^2 numbers.
Want to output the largest n numbers in the set C.

Do people have solutions in O(n log n) time?
A more challenging question is to do it in linear time.

Thank you for any input or advices.

--
※ 發信站: 批踢踢參(ptt3.cc)
◆ From: 68.55.53.166

> -------------------------------------------------------------------------- <

作者: Ptt (杜奕瑾) 看板: Job
標題: Re: [請益] CS Interview Question 1
時間: Thu Jan 26 14:42:43 2006

這問題是個有名的paper..
正在研究可以download的地方

http://citeseer.ist.psu.edu/context/127394/0



※ 引述《Skuld (Sherry)》之銘言：
: I came across this question while practicing for interviews.
: This is said to be an interview question from Google.
: Given two sorted arrays A and B of n number each
: (can assume to be integers, but it does not matter).
: Consider the set C = { a+b | a \in A, b \in B }
: The set C contains n^2 numbers.
: Want to output the largest n numbers in the set C.
: Do people have solutions in O(n log n) time?
: A more challenging question is to do it in linear time.
: Thank you for any input or advices.

--
※ 發信站: 批踢踢參(ptt3.cc)
◆ From: 165.112.191.116

> -------------------------------------------------------------------------- <

作者: Ptt (杜奕瑾) 看板: Job
標題: Re: [請益] CS Interview Question 1
時間: Thu Jan 26 18:45:24 2006

剛寫了一個程式...
只要改push pop那段改為logn就是nlogn (ex 用 heap..)
push pop若可以改為constant time的就可以有n (linear)..
(linear 可能要多加條件 如已知資料範圍)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 30

typedef
struct DATA
{
  int value;
  int a;
  int b;
} DATA;

DATA Candidate[SIZE], empty;
int  count =0;

void push(DATA d)      // maintain sorted candidate  min...max
{
  int i, j;
  for(i=0; i<count && Candidate[i].value < d.value; i++);
  for(j=count; j>i; j--)
     memcpy(&Candidate[j], &Candidate[j-1], sizeof(DATA));
  Candidate[i]=d;
  count++;
}
DATA pop()            // return the max one
{
  if(count>0)
     return Candidate[--count];
  return empty;
}

void printFristNinC(int A[], int B[], int n)
{
  int i=0;
  DATA d, t;
  if(!A || !B || n<=0) return;

  d.a=0;
  d.b=0;
  d.value = A[0] + B[0];
  push(d);
  for(i=0; i<SIZE; i++)
  {
      d = pop();
      printf("%5d", d.value);
      if(d.a==0)
      {
        t.a=0;
        t.b=d.b+1;
        t.value = A[t.a]+B[t.b];
        push(t);
      }
      t.a = d.a+1;
      t.b = d.b;
      t.value = A[t.a]+B[t.b];
      push(t);
  }
}

int cmp(void const *a, void const *b)
  const int *pa=(int const *)a;
  const int *pb=(int const *)b;
  return (*pb)-(*pa);
}

main()
{
  int A[SIZE], B[SIZE], all[SIZE*SIZE], i, j;

  for(i=0; i<SIZE; i++)
   {
     A[i]=rand()%(SIZE*10);
     B[i]=rand()%(SIZE*10);
   }
  for(i=0; i<SIZE; i++)
    for(j=0; j<SIZE; j++)
    {
      all[i*SIZE+j] = A[i]+B[j];
    }

  qsort(A, SIZE, sizeof(int), cmp);
  qsort(B, SIZE, sizeof(int), cmp);
  qsort(all, SIZE*SIZE, sizeof(int), cmp); // 對照組 驗證用

  for(i=0; i<SIZE; i++)       //print out A[] B[]
      printf("%4d", A[i]);
  printf("\n");

  for(i=0; i<SIZE; i++)
      printf("%4d", B[i]);
  printf("\n");

  printFristNinC(A, B, SIZE); //core function
  printf("\n");

  for(i=0; i<SIZE; i++)       //used to compare the result from core funtion
      printf("%5d", all[i]);
  printf("\n");
}


※ 引述《Skuld (Sherry)》之銘言：
: I came across this question while practicing for interviews.
: This is said to be an interview question from Google.
: Given two sorted arrays A and B of n number each
: (can assume to be integers, but it does not matter).
: Consider the set C = { a+b | a \in A, b \in B }
: The set C contains n^2 numbers.
: Want to output the largest n numbers in the set C.
: Do people have solutions in O(n log n) time?
: A more challenging question is to do it in linear time.
: Thank you for any input or advices.

--
※ 發信站: 批踢踢參(ptt3.cc)
◆ From: 216.15.33.137

> -------------------------------------------------------------------------- <

作者: Skuld (Sherry) 看板: Job
標題: Re: [請益] CS Interview Question 1
時間: Thu Jan 26 20:25:50 2006


printFirstNinC function is very cool.  It gets all the pairs from A and B.
I have a questions

We loop n times to get all the pairs for index 0 and 1 in A, and we
can loop n*n-2 times more to get the rest of the pairs?

經過解釋 已了解了 =)

Thank you.  The program is amazing.

--
※ 發信站: 批踢踢參(ptt3.cc)
◆ From: 68.55.53.166