## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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];

}
}``````

Comment hidden because of low score. Click to expand.
0

it takes O(k + c) where c may be even larger if there are too many duplicates, we can try handling the duplicates by tweaking the code. But can there be an O(logk) solution.

Comment hidden because of low score. Click to expand.
0

would this work for k=10?
also the input you have taken is too simple...
how about array_1 having 1 3 5 7 9 11 13
and array_2 having 2 4 6 8 10 12

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use Quick Select Algorithm.

Comment hidden because of low score. Click to expand.
0

That would not be optimal. You are not taking advantage of the two arrays already being sorted.

Comment hidden because of low score. Click to expand.
0

ohh did not noticed the 2 arrays are sorted... then i would suggest to go for merge sort.
if 1st array has a elements and 2nd array has b elements
then do merge sort till we reach (a+b-k)th element.
We can do it inplace based on the length on a & b.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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) )

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int arr1={1,4,6,9,10};
int arr2={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++;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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()

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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
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)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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>s1:
return s1
elif s2<s1:
return s1
return s2
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()``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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>s1:
return s1
elif s2<s1:
return s1
return s2
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)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.