#!/usr/bin/python3

"""
I was asked this in an interview and am feeling right now as though I pretty
much choked. Doing it after-the-fact to make myself feel better.

Given sorted lists of numbers A, B, merge them together into a new sorted list,
omitting repeats.
"""

def get_merged_list(A, B):

    seen = set()
    results = []

    while True:

        # if we've exahausted both, we're done:
        if not A and not B:
            return results

        # we might have just _one_ list empty:
        if A:
            a = A[0]
        else:
            a = None
        if B:
            b = B[0]
        else:
            b = None

        # three "outer cases":
        if a is None:
            c = B.pop(0)
        elif b is None:
            c = A.pop(0)
        else:
            # third case has three cases
            if a > b:
                c = B.pop(0)
            elif b > a:
                c = A.pop(0)
            else:
                # they are the same. pop both.
                B.pop(0)
                c = A.pop(0)

        # we definitely have a 'c' at this point

        # have we seen it already?
        if c in seen or (results and c == results[-1]):
            continue

        results.append(c)
        seen.add(c)


cases = [
    {
        'A': [1, 3, 3, 4, 5, 6, 8, 8, 8, 10],
        'B': [1, 10, 11],
        'expected': [1, 3, 4, 5, 6, 8, 10, 11],
    },

    {
        'A': [-3, -2, 0, 9, 10, 100],
        'B': [87, 88],
        'expected': [-3, -2, 0, 9, 10, 87, 88, 100],
    },

    {
        'A': [],
        'B': [],
        'expected': [],
    },

    {
        'A': [0, 3],
        'B': [2],
        'expected': [0, 2, 3],
    },
    {
        'A': [2],
        'B': [0, 3],
        'expected': [0, 2, 3],
    },
]

for case in cases:
    A = case['A']
    B = case['B']
    expected = case['expected']
    assert get_merged_list(A, B) == expected, 'wrong:' + expected