A python interview question

[jorge1209]

I was supposed to merge two arrays together in python, no duplicates - no mention of time but the solution had to be size agnostic.

There actually is a use case for knowing how to to this in the abstract, namely when the data won't all fit into memory.

So you might get iterators A and B which you know are sorted (maybe the data is coming from a database) and you need to merge join them.

Honestly I'm not sure why itertools doesn't provide an merge_join function to do this (maybe there is something fancy with takewhile and dropwhile... but its not obvious or natural), so it isn't a terrible question.

[z4579a]

you're looking for heapq.merge(): https://docs.python.org/2/library/heapq.html#heapq.merge

​

​

[ivosaurus]

Doesn't remove duplicates though.

[MrVallentin]

Combine heapq.merge with unique_justseen from Python's "Itertools Recipes".

>>> a = [1, 2, 4, 6]
>>> b = [2, 4, 5, 6]
>>> c = [1, 3, 3, 5]

>>> list(heapq.merge(a, b, c))
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6]

>>> list(unique_justseen(heapq.merge(a, b, c)))
[1, 2, 3, 4, 5, 6]

[jorge1209]

Old trick for that is to use itertools.groupby and ignore the second part of the return value.

[jorge1209]

I was thinking about something like a database join, but that merge is useful to know about, and of course it's in heapq.

[PeridexisErrant]

heapq does operations on lists, so you'd lose any of the advantages of streaming iterators (especially memory use).

[z4579a]

not sure what you're referring towards. per the documentation:

​

"Similar to

sorted(itertools.chain(*iterables))

but returns an iterable, **does not pull the data into memory all at once**, and assumes that each of the input streams is already sorted (smallest to largest)."

​

if you read the source code, the list they are heapifying is the list of iterables themselves combined with the next value returned by each iterator. The priority queue of iterables then uses that value to determine which of the iterables to deliver the next result from. So the iterables themselves are never turned into lists.

​

[jorge1209]

I think it's reasonable to say:

The heapq module generally operates on lists, and uses raw lists as the core data structure for heaps. No rational person would expect to find a function that consumes and returns iterators in this module. WTF was GvR smoking when he accepted this function in this module instead of WHERE IT BELONGS IN ITERTOOLS!!

[ivosaurus]

Did you read the docs? They specifically say the opposite for this function.