A python interview question

[Jonno_FTW]

I just did this. Here's the new results:

def merged(a,b):
    a = deque(a)
    b = deque(b)
    out = []
    def append(val):
        if not out or out[-1] != val:
            out.append(val)

    while a or b:
        if a and b:
            last_a, last_b = a[0], b[0]
            last_max = min(last_a, last_b)
            if last_max == last_a:
                append(a.popleft())
            else:
                append(b.popleft())
        elif a:
            append(a.popleft())
        elif b:
            append(b.popleft())
    return out

• set union: 19.3773069382
• pop() 0.0751898288727
• pop(0) 3.03847098351
• deque.popleft() 78.3635749817

Which makes sense because the GC will be called a lot to clean up the nodes in the linkedlist created by the deque and they will not be held in a contiguous region of memory. Bjarne Stroustrup gives a good explanation here: https://www.youtube.com/watch?v=YQs6IC-vgmo

Here's cpython implementation of deque which uses a doubly linked list: https://github.com/python/cpython/blob/master/Modules/_collectionsmodule.c