CareerCup

public class KthLargest {

		public static void main(String []args)
		{
			int []array1 = {1,3,5,7,9,11};
			int []array2 = {12,13,14,15,16}; 
			int k = 4;
			System.out.println(new KthLargest().kthLargestElement(array1,array2,k));
			
		}
		
		public int kthLargestElement(int []input1,int []input2,int k)
		{
			
			
			int i1,i2;
			boolean flag = false;
for(i1 = input1.length - 1,i2 = input2.length - 1;input1.length - i1 + input2.length - i2  <= k + 1;)
			{
				
					if(i2 < 0)
					{
						i1--;
						flag = true;
						continue;
					}
					
					if(i1 < 0)
					{
						i2--;
						flag = false;
						continue;
					}
				
					if(input1[i1] > input2[i2])
					{
						i1--;
						flag = true;
					}
					else
					{
						i2--;
						flag = false;
					}
				
				
			}
			
			
			
			if(flag)
				return input1[i1+1];
			else
				return input2[i2+1];
			
		}
}

Since the arrays are sorted we can merge them in O(n+m).
To be more optimum.. merge till we reach kth element in the resultant array.

We can use Quick Select Algorithm.

Let s be 1 and take two pointers, one for each array, initially pointing to the last (greatest) element of its array.

1. If both arrays are exhausted, error: there are not k elements in the arrays.
2. If one array is exhausted, the element pointed to in the other array is the s-th largest.
3. Otherwise the maximum of the elements pointed to in both arrays is the s-th largest.
4. If s=k, return this element.
5. Otherwise move each pointer that pointed to the s-th largest element (this could be both pointers) backwards in its array until it reaches a different element or, if there are no more, call its array "exhausted".
6. Increment s and repeat.

In my stament, A[], B[] is the given two sorted arrays, and |A|=n,|B|=m

1) two pointers Algorithm must works (such as one sub-program in MERGE_SORT)
however, you may have to scan all the element in worst case (k=n+m). And the time complexity is O(n+m)

2) we could find that the result element will either in A[] or in B[] (or both cause the duplicates)
Now suppose the result element is in A[], we can binary search it.
for one element you are searching now (suppose it's X), we can calculate how many element in total is less or equal to X. (do another binary search in B[])
Then we can get the result if it's indeed in the A[].

For the result in B[], we could process in the same way.
so the Time Complexity is O( log(n)*log(m) )

Can you define "the union of two sorted arrays (with duplicates)"? I'm interested in what that means for duplicates.

int arr1[5]={1,4,6,9,10};
	int arr2[4]={2,3,5,8};
	int k=3; // 3rd should be 8
	int value=-1;
	int index=0;
	int a1=(sizeof(arr1)/sizeof(int))-1;
	int a2=(sizeof(arr2)/sizeof(int))-1;
	while(index<k)
	{
		if(arr1[a1]>arr2[a2])
		{
			value=arr1[a1--];
		}
		else
		{
			value=arr2[a2--];
		}
		index++;
	}

Solution in C:

#!/usr/bin/python

from sys import stdin,stdout,argv

class SubArr:
def __init__(self, arr):
self.arr=arr
self.first=0
self.last=len(arr)
def get(self, pos):
res=9999
pos+=self.first
if pos<len(self.arr) and pos<self.last:
res=self.arr[pos]
return res
def size(self):
return self.last-self.first
def median(self):
sz=self.size()
pos=sz/2
if sz%2==1:
res=self.get(pos)
else:
res=(self.get(pos)+self.get(pos-1))/2.0
return res

def median2(s1, s2):
if s1.get(s1.size()-1)<=s2.get(0):
return s1.get(s1.size()-1)
elif s2.get(s2.size()-1)<=s1.get(0):
return s1.get(0)
elif s2.size()==1:
return s2.get(0)
t=s2.size()/2
med1=s1.median()
med2=s2.median()
if med1==med2:
return int(med1)
elif med1<med2:
s1.first+=t
s2.last-=t
else:
s1.last-=t
s2.first+=t
return median2(s1,s2)

def kth_elem(l1, l2, k):
if k>=len(l1)+len(l2):
return "error"
s1=SubArr(l1)
s2=SubArr(l2)
if s1.get(k)>s2.get(k):
tmp_s=s1
s1=s2
s2=tmp_s
if k==0:
return s1.get(0)
s1.last=k+1
s2.last=k
return median2(s1,s2)

def main():
l1=[1,3,4,10,15,20,22,27,35,50]
l2=[1,3,4,5,6,7,12,33]
print l1
print l2
for k in range(0, 20):
print str(k)+"th element is "+str(kth_elem(l1, l2, k))

if __name__ == "__main__":
main()

def median(s):
l=len(s)
if l%2==0:
return (s[l/2-1]+s[l/2])/2.0
else:
return s[(l-1)/2]

def median2(s1,s2):
if len(s2)==1:
return s2[0]
t=len(s2)/2
if median(s1)<median(s2):
s1=s1[-t:]
s2=s2[:t]
else:
s1=s1[:t]
s2=s2[-t:]
return median2(s1,s2)

def k_elem(s1, s2, k):
if s1[k-1]<s2[k-1]:
swap(s1,s2)

s1=s1[:k]
s2=s2[:k-1]
return median2(s1,s2)

def median(s):
  l=len(s)
  if l%2==0:
    return (s[l/2-1]+s[l/2])/2.0
  return s[(l-1)/2]

def median2(s1, s2):
  print s1
  print s2
  if len(s2)==1:
    if s2[0]>s1[1]:
      return s1[1]
    elif s2[0]<s1[0]:
      return s1[0]
    return s2[0]
  t=len(s2)/2
  print t
  if median(s1)<median(s2):
    s1=s1[t:]
    s2=s2[:-t]
  else:
    s1=s1[:-t]
    s2=s2[t:]
  return median2(s1,s2)

def k_elem(s1, s2, k):
  print s1
  print s2
  print k
  if s1[k-1]>s2[k-1]:
    tmp_s=s1
    s1=s2
    s2=tmp_s
  s1=s1[:k]
  s2=s2[:k-1]
  return median2(s1,s2)

def main():
  print "hello"
  l1=[1,2,3,4]
  l2=[5,6,7]
  print k_elem(l1, l2, 3)

if __name__ == "__main__":
  main()

Here's the clean solution in python - try it !
Explanation: take the first K elements of both sorted arrays and then find the median !!
Finding the median of two sorted arrays is done in O(log(K)) time by each time removing half of the elements of each array - the bottom half of the array with the lower median, and the upper half of the array with the higher median !!!

def median(s):
  l=len(s)
  if l%2==0:
    return (s[l/2-1]+s[l/2])/2.0
  return s[(l-1)/2]

def median2(s1, s2):
  if len(s2)==1:
    if s2[0]>s1[1]:
      return s1[1]
    elif s2[0]<s1[0]:
      return s1[0]
    return s2[0]
  t=len(s2)/2
  if median(s1)<median(s2):
    s1=s1[t:]
    s2=s2[:-t]
  else:
    s1=s1[:-t]
    s2=s2[t:]
  return median2(s1,s2)

def k_elem(s1, s2, k):
  if s1[k-1]>s2[k-1]:
    tmp_s=s1
    s1=s2
    s2=tmp_s
  s1=s1[:k]
  s2=s2[:k-1]
  return median2(s1,s2)

def main():
  l1=[1,3,15,14]
  l2=[5,6,7]
  print k_elem(l1, l2, 3)