I participated in an Amazon coding problem yesterday, and one of the questions was a really simple one. To paraphrase: “Develop a method to handle Amazon shopping carts that takes two inputs, items being the current shopping cart which is an array of product IDs, and queue being the operation IDs to apply to the shopping cart. If the ID is positive, append the product ID to the end of the cart, if the ID is negative, remove the first instance of the module of the ID from the shopping cart. Return the processed shopping cart.”

I implemented a simple solution, and it passed all the simple test cases, however it failed all the test cases with large inputs. I ended up not having time to come up with a performatic solution, my best being O(n^2) I think, which I will attach below. How would you have done it? I thought about using either a collections.deque or collections.defaultdict.

def problem_solution(items: list[int], query: list[int]) -> list[int]:
    for item in query:
        if item > 0:
            items.append(item)
            
        else:
            items.remove(abs(item))
            
    return items