A couple of weeks ago one of my colleagues at college asked me if I could find the solution to this problem that was in a Microsoft interview. I thought about it and later that night I had a couple of solutions including the O(NlgN) O(lgN) one (reading the sequences is counted out ) that was required for it. Next morning I also had an implementation in C++ of the solution which worked fine. Now if you want to take a shot at it, the problem statement goes like this:
P.S.: Regarding round #17 and #18, I was very busy with the exams and I didn't have the time to participate at them. But I took my shot at round #20 and came out 9th and hopefully I will be free to take my shot at round #19.
UPD1. Thanks to fcdkbear for pointing out that I requested an O(NlgN) algorithm.
UPD2. The two sequences are stored in arrays, so you have random acces to the elements.
You are given two sorted sequences of 32-bit integer numbers. Find the median of the sequence obtained by concatening the two sequences.I will later post the solutions I found, because I like the sort of trade-off that appears whilst you improve your solution's execution time. But I don't want to spoil all the fun. So, for now, I will leave you the time to solve it. If you want to step up, you can e-mail me the solutions at [email protected] and I will post the names of the best 10 solvers in the solution post.
P.S.: Regarding round #17 and #18, I was very busy with the exams and I didn't have the time to participate at them. But I took my shot at round #20 and came out 9th and hopefully I will be free to take my shot at round #19.
UPD1. Thanks to fcdkbear for pointing out that I requested an O(NlgN) algorithm.
UPD2. The two sequences are stored in arrays, so you have random acces to the elements.
so you have 2 array of integers and they are sorted.
#define size= total size of array 1 and array 2
let's assume tot=sorted array after you combine array 1 and array 2
function Occ(x) = total occurrence x in array 1 and array 2( you can do binary search or use STL lower_bound)
1. if median is odd, the index of median in tot is (size+1)/2, so you do binary search.
you get the smallest "answer" for Occ(answer)>=(size+1)/2 ->index of median. answer=median itself
2. if median is even, the index of median in tot are size/2 and size/2+1; where median=(tot[size/2]+tot[size/2+1])/2
you do binary search two times,
you get the smallest "answer1" for Occ(answer1)>=size/2
you get the smallest "answer2" for Occ(answer2)>=size/2+1
thus median=(answer1+answer2)/2
Correct me if I'm wrong thx :D
Where wiil you store the values of Occ(x)? X may be as large as 2^32-1.
And, as i understand, Occ(x)=total ototal occurrence of numbers less than or equal to x in array 1 and array 2. Am i right?
Occ(x)=lower_bound(array1,array1+size1,number x)+
lower_bound(array2,array2+size2,number x)
thus you get total occurence of x in both array.
That's why you need lg N again and total complexity become O(lg^2(N))
I think, your algo will be incorrect if there will be some equal numbers. For example, array1[]={4,4,4} and array2[]={4,4}.
But I think, we can modify your algo and get the right answer. We can find the number of elemets, that are strictly less than x and number of elements, that are strictly bigger than x(in both arrays). So, we could know the positions of X in the final sorted sequence. We can find the number, which position is size/2(and, maybe, size/2+1), so we will know the answer.
Occ(4)=5( 3 in array 1 and 2 in array 2), which is bigger than 3(index of median) So median is 4.
you are doing binary search, so when 4 is valid, you try to find smaller value so that Occ(x)>=index of median, let's say you try 3,Occ(3) is 0, thus 4 is the smallest number for median.
but yeah basically it's the same
1) get current element
2) move to the next element
3) ask is the sequence has more elements
You solution uses random access to is't elements, so it operates with another meaning of the "sequence" word.
I believe you can take in this problem the sequence as an array of numbers. Like:
int a[65536];
in C or C++. So you can have random acces to the elements. Sorry for the misunderstanding. :(