sorry bt i dint get the approach. can u please explain a bit more by taking
examples...thanks a lot in advance
On 14 May 2010 10:12, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
This was also asked in my Yahoo! Interview this year. :)
--
You have to take some i nodes from array A and the rest k-i-1 from array B.
You do not know i. = Problem is to Find i
So we do a binary search for that.
The value i is acceptable if the (k-i) th element in B is greater than ith
element in A.
So, i guess you would have got it now.
You are given two sorted lists of size m and n. Give an O(log m+log n)
time algorithm for computing the kth smallest element in the union of
the two lists
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
This is for kth largest. Change it for kth smallest
In fact, this problem is amenable to something very similar to binary
search. Suppose my arrays are A and B. The idea is to keep track of two
indices, a (for A) and b (for B), such that a + b = k - 1 (it's very
important to maintain this
exactly ..
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Fri, May 14, 2010 at 10:07 AM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:
This is for
This was also asked in my Yahoo! Interview this year. :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Fri, May 14, 2010 at 10:10 AM, Rohit Saraf
