wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Maximum Sums
        
(Message started by: mad on Mar 8^th, 2008, 5:59am)

Title: Maximum Sums
Post by mad on Mar 8^th, 2008, 5:59am

Given two sorted postive integer arrays A(n) and B(n) sorted in decreasing order , we define a set S = {(a,b) | a in A and b in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
from S with largest values using an O(n) algorithm.

Title: Re: Maximum Sums
Post by Aryabhatta on Mar 8^th, 2008, 11:06am

I believe this is already there on this forum somewhere.

Perhaps under a title similar to "The hardest interview question ever"

Title: Re: Maximum Sums
Post by mad on Mar 8^th, 2008, 4:36pm

I am unable to locate a link. Tried searching, but it is showing this post only again.

Could you please provide a link?

Title: Re: Maximum Sums
Post by towr on Mar 9^th, 2008, 3:22am

Perhaps you didn't set the default age back far enough.
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1132204952;