Intersection of two list in N time
Question: I have two lists `(['a', 's', 'f', 'f', 's'], ['f', 'f', 'a', 's'])`. The
required output is `['a','s','f','f']`. The output should give the
intersection of two lists. The arrangement of characters in the output list is
according to the order of occurrence in the first list `['a', 's', 'f', 'f',
's']`.

How can I implement this in python? I have already done this in N**2 time. Is
it possible to do this in N time?  
My current solution:

    
    
    def com(string1, string2):
        string2_list=list(string2)
        store=""
        for check in string1:
            for i,v in enumerate(string2_list):
                if v==check:
                    store=store+check
                    del(string2_list[i])
        return store
    


Answer: Use `collections.Counter`'s built-in intersection operation.

    
    
    >>> l1, l2 = (['a', 's', 'f', 'f', 's'], ['f', 'f', 'a', 's'])
    >>> import collections
    >>> collections.Counter(l1) & collections.Counter(l2)
    Counter({'f': 2, 'a': 1, 's': 1})
    

From here it is not hard to build a suitable list:

    
    
    >>> counter = collections.Counter(l1) & collections.Counter(l2)
    >>> out = list(counter.elements())
    >>> print out
    ['a', 's', 'f', 'f']
    

Or, to order according to one of the lists:

    
    
    >>> out = []
    >>> for k in l1:
    ...     if counter[k] > 0:
    ...         counter[k] -= 1
    ...         out.append(k)
    ...
    >>> print out
    ['a', 's', 'f', 'f']
    

This is expected-time O(N): Counter creation is expected O(N) time, and
counter intersection is expected O(N) time as well. ​

