Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col...
by dogruck on Friday October 20, 2017 @04:15AM
(#15514275)
Confusing because the problem statement says you cannot assume anything about the data structure storing each set. To me, that implies it must be treated as a stream -- not an array with indexing.
But yeah, if they are arrays, you use binary search. Not obvious, but also straightforward if you are looking to beat O(k).
Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col...
by szemet on Friday October 20, 2017 @05:07AM
(#15514451)
If the data structures can be split (as it seems), then the first step should be to get the head k element of both collections, so we only have to work with a maximum of 2k elements. Then the solution is not O(2 * log(N)) but O(2 * log(min(N,2k))).
Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col...
by Asooka on Friday October 20, 2017 @02:16AM
(#15513830)
The article keeps mentioning sorted sets, which is slightly confusing, because I am familiar with sets being defined, both in math and every programming language I know, as unordered. Is set in OCaml an ordered collection usually?
Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col...
by a-nikolaev on Friday October 20, 2017 @03:06AM
(#15514012)
The article mentions word "set" only in the statement of the problem. And even in that statement it's made clear that the choice of words is intentional, because the underlying data structure is not specified, so it doesn't have to be an array immediately.
Ordered collection != sorted collection, btw. Sorted collections are actually more like sets than like arrays. A data structure that stores the elements in a sorted fashion is actually able to store an unordered collection with naturally defined insertion / deletion operations. (In OCaml, Set data structure is represented as a balanced binary tree, for instance, and it requires an order relation defined for its elements.)
Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col...
by pronoiac on Friday October 20, 2017 @05:15PM
(#15519146)
Could you add "disjoint" to the title? It's so close to containing the gist of the problem. If anyone else goes from the title to the solution, it'll save some confusion.
Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col...
by pronoiac on Thursday October 19, 2017 @04:57PM
(#15511493)
If you're like me, and have forgotten union vs intersection, I'll restate the question:
Sets A and B are each sorted, and they have no elements in common. If you combine A and B, what would be the kth smallest element?
Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col...
by OJFord on Friday October 20, 2017 @03:49AM
(#15514171)
The sets do not necessarily have no elements in common - their union is the set of all the elements in either of them. (Being a set, it does not have 'duplicates' even if an element appears in both of your A and B.)
Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col...
by pronoiac on Friday October 20, 2017 @05:10PM
(#15519133)
The lack of overlap is mentioned in the body, but not in the title.
The title is so close to presenting the problem on a way that people could fully consider how they'd handle the problem before following the link. Just add "disjoint" to the title.
I am very keen to OCaml and so using OCaml to solve various algorithm problems to have some fun.
But yeah, if they are arrays, you use binary search. Not obvious, but also straightforward if you are looking to beat O(k).
https://leetcode.com/problems/median-of-two-sorted-arrays/de...
Ordered collection != sorted collection, btw. Sorted collections are actually more like sets than like arrays. A data structure that stores the elements in a sorted fashion is actually able to store an unordered collection with naturally defined insertion / deletion operations. (In OCaml, Set data structure is represented as a balanced binary tree, for instance, and it requires an order relation defined for its elements.)
Will change
The title is so close to presenting the problem on a way that people could fully consider how they'd handle the problem before following the link. Just add "disjoint" to the title.