Question

You are interested in analyzing some hard-to-obtain data from two separate databases. Each database contains n numerical values -so there are 2n values total - and you may assume that no two values are the same.

You’d like to determine the median of this set of 2n values, which we will define here to be the nth smallest value. However, the only way you can access these values is through queries to the databases. In a single query, you can specify a value k to one of the two databases, and the chosen database will return the kth smallest value that it contains. Since queries are expensive (you pay $10 for each), you would like to compute the median using as few queries as possible.

Write a java method named findMedian(Database a, Database b), that returns the median value using at most O(log n) queries.

/*
Notes for your code:

Database a, and Database b here are special objects that you can query for the kth smallest item.

• If you call a.query(1), Database a will return the smallest item in it (and charge you $10)
• If you call a.query(5), Database a will return the 5th smallest item in it (and charge you another $10) and so on.
• Also, you can get the size of Database a by calling a.size(); (this will cost you nothing)
• And if you call a.query(a.size()) this will give you the largest element in Database a (and you will pay $10 of course)
• AND Note the important fact that no two values are the same (among both Databases)

Please give me a clear Java code with explanation !

public static int findMedian(Database a, Database b){} The head of the method should look like this !

Answer 1

Here is the solution to the question above. I have inserted comments wherever necessary for better understanding.

CODE:

//We can consider the two database tables as sorted arrays

//Assumption- we have 0-based indexing in database queries just like arrays. so a.query(0) will yield smallest element of database a

//O(n) approach will brute force - that is access all the elements and store it in 3 array and then find nth smallest element

//We are using here O(log n) approach - Divide and Conquer Approach



public class median{

public static float findMedian(Database a,Database b){

int m=a.size();int n=b.size(); // 0 cost

int k=n;//to find nth smallest element

int aa=a.query(1);int bb=b.query(1);

if(n==1) return (a<b)?a:b; // compare if only single element is present

else return func(a,b,m,n,k,0,0);

}

static int func(Database a,Database b, int m,int n, int k,int s1,int s2){

if(s1==m)return b.query(s2+k-1); // If we have reached end of Database(array) a

if(s2==n) return a.query(s1+k-1); // If we have reached end of Database(array) b

if(k==0 || k>(m-s1)+(n-s2)) return -1;  // k should reach 0 or exceed size of databases a,b

int current = k/2;

if(current-1 >= m-s1){

if(a.query(m-1) < b.query(s2+current-1)) return b.query(s2+(k-(m-s1)-1)); 

else return func(a,b,m,n,k-current,s1,s2+current);

}

if(current-1 >= n-s2){

if(b.query(n-1) < a.query(s1+current-1)) return a.query(s1+(k-(n-s2)-1));

else return func(a,b,m,n,k-current,s1+current,s2);

}else{

if(a.query(current+s1-1) < b.query(current+s2-1)) return func(a,b,m,n,k-current,s1+current,s2);

else return func(a,b,m,n,k-current,s1,s2+current);

}

}

}

If you find this helpful please do UPVOTE the answer.

!!!!!!!!!!!!!!!!!!!!!!!!!!!! H A P P Y C H E G G I N G !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!