from typing import Iterable
from typing import List
from typing import Counter


def compute_union(x: Iterable, y: Iterable) -> List:
    """Returns union of items in `x` and `y`, where `x` and `y` allow for
    duplicates.  Items must be hashable.  For example:

    x = ['a', 'a', 'b', 'c']
    y = ['a', 'c', 'c', 'd']

    then their union is ['a', 'a', 'b', 'c', 'c', 'd'].

    **DOES NOT GUARANTEE ORDER OF THE OUTPUT LIST**
    """

    # 1) count everything in `x` and `y`
    counter_x = Counter(x)
    counter_y = Counter(y)

    # 2) fill in `union` with values
    union = []
    keys = set.union(set(x), set(y))
    for key in keys:
        count_x = counter_x.get(key, 0)
        count_y = counter_y.get(key, 0)
        union.extend([key for _ in range(max(count_x, count_y))])

    return union