Pearl No. 4 – Kth Smallest in the Union of Two Sorted Collections | Hacker News Reader

Pearl No. 4 – Kth Smallest in the Union of Two Sorted Collections

typeocaml.com

61 pointsjacksontale16 comments

This blog post is about using OCaml to solve the Pearl No. 4 in the book of "Pearls of Functional Algorithm Design, by Richard Bird".

I am very keen to OCaml and so using OCaml to solve various algorithm problems to have some fun.

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

Is there a good reason for this article forcing me to scroll back to the top of the page half way through?

This page is difficult to read on mobile. Feels like pulling taffy.

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

Good thought, and also if k < N / 2

Edited the post and added your comment

There is a related problem on leetcode (Find the median of two sorted arrays):

https://leetcode.com/problems/median-of-two-sorted-arrays/de...

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?

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

Sorry for the confusion. You are absolutely right. I just copy/paste the original problem statement in the book.

Will change

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.

Probably means that there ARD no duplicates among the elements.

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?

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

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.

Reply on news.ycombinator.com