wu :: forums
« wu :: forums - Maximum Sums »
Welcome, Guest. Please Login or Register.
Nov 24th, 2024, 8:29am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs (Moderators: towr, Eigenray, Icarus, ThudnBlunder, Grimbal, william wu, SMQ)
   Maximum Sums		 « Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Maximum Sums  (Read 772 times)
mad
Junior Member
**





   


Posts: 118
Maximum Sums  
« on: Mar 8th, 2008, 5:59am »		 Quote Quote Modify Modify
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.
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
 Posts: 1321
Re: Maximum Sums  
« Reply #1 on: Mar 8th, 2008, 11:06am »		 Quote Quote Modify Modify
I believe this is already there on this forum somewhere.
 
Perhaps under a title similar to "The hardest interview question ever"
IP Logged
mad
Junior Member
**





   


Posts: 118
Re: Maximum Sums  
« Reply #2 on: Mar 8th, 2008, 4:36pm »		 Quote Quote Modify Modify
I am unable to locate a link. Tried searching, but it is showing this post only again.
 
Could you please provide a link?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Maximum Sums  
« Reply #3 on: Mar 9th, 2008, 3:22am »		 Quote Quote Modify Modify
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;
« Last Edit: Mar 9th, 2008, 3:23am by towr » IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board