Register

CMI2013-B-04

1,335 views
7 7 votes
You are given two sorted lists of integers of size $m$ and $n$. Describe a divide and conquer algorithm for computing the $k$-th smallest element in the union of the two lists in time $O(\log m + \log n)$.

1 Answer

Voting & Accepting an answer helps improve the community
← Previous · CMI2013-B-03Next → · CMI2013-B-05
← Previous in category · CMI2013-A-10Next in category → · CMI2013-B-05
Position:
Show:

Related questions

33 33 votes
5 answers 5 answers
10.6k
10.6k views
go_editor asked May 23, 2016
10,565 views
CMI2013-A-05
You have $n$ lists, each consisting of $m$ integers sorted in ascending order. Merging these lists into a single sorted list will take time:$O(nm \log m)$$O(mn \log n)$...
2 2 votes
3 3 answers
2.8k
2.8k views
Arjun asked Jun 8, 2016
2,799 views
CMI2013-B-06b
Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. ...
1 1 vote
2 2 answers
1.4k
1.4k views
go_editor asked May 23, 2016
1,441 views
CMI2013-B-06a
Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. ...
3 3 votes
1 1 answer
731
731 views
go_editor asked May 23, 2016
731 views
CMI2013-B-05
You are going abroad and you have to complete a number of formalities before you leave. Each task takes a full day to complete. Fortunately, you have an army of friends t...