[Python3] OOD | Interview Friendly Solution
Complexity\nTime: O(nlogn)\nSpace: O(n)\n\n\n# Code\n\nimport abc\nimport heapq\nfrom enum import Enum\nfrom abc import ABC, abstractmethod\nfrom typing import 
# Complexity\nTime: $$O(nlogn)$$\nSpace: $$O(n)$$\n\n\n# Code\n```\nimport abc\nimport heapq\nfrom enum import Enum\nfrom abc import ABC, abstractmethod\nfrom typing import Optional, List\n\nMOD = int(1e9+7)\nclass OrderType(Enum):\n    BUY = 0\n    SELL = 1\n\n    @classmethod\n    def get(cls, order_type_id: int):\n        order_type_map = {k.value: k for k in cls}\n        return order_type_map[order_type_id]\n\nclass Backlog(ABC):\n    def __init__(self):\n        self.__heap = []\n        self.__price_amount_map = dict()\n        self.__total_amount = 0\n\n    def get_total_amount(self) -> int:\n        return self.__total_amount%MOD\n\n    def add_to_total_amount(self, amount: int):\n        self.__total_amount += amount\n\n    def remove_from_total_amount(self, amount: int):\n        self.__total_amount -= amount\n\n    def peek(self) -> Optional[int]:\n        if len(self.__heap) == 0:\n            return None\n        return self.__heap[0]\n\n    def push(self, price: int):\n        heapq.heappush(self.__heap, price)\n\n    def pop(self) -> Optional[int]:\n        if self.peek() is None:\n            return\n        return heapq.heappop(self.__heap)\n\n    def get_orders_for_price(self, price: int) -> int:\n        return self.__price_amount_map.get(price, 0)\n\n    def update_orders_for_price(self, price: int, amount: int):\n        self.__price_amount_map[price] = amount\n\n    @abstractmethod\n    def add(self, price: int, amount: int): ...\n\n    @abstractmethod\n    def remove(self, amount: int): ...\n\nclass BuyBacklog(Backlog):\n    def peek(self) -> Optional[int]:\n        top = super().peek()\n        if top is None:\n            return\n        return -top\n\n    def push(self, price: int):\n        price *= -1\n        super().push(price=price)\n\n    def pop(self) -> Optional[int]:\n        val = super().pop()\n        if val is None:\n            return\n        return -val\n\n    def add(self, price: int, amount: int):\n        existing_orders_for_price = self.get_orders_for_price(price=price)\n        if existing_orders_for_price == 0:\n            self.push(price=price)\n        new_orders_for_price = existing_orders_for_price + amount\n        self.add_to_total_amount(amount=amount)\n        self.update_orders_for_price(price=price, amount=new_orders_for_price)\n\n    def remove(self, amount: int) -> Optional[int]:\n        max_buy_price = self.peek()\n        if max_buy_price is None:\n            return\n        max_price_amount = self.get_orders_for_price(price=max_buy_price)\n        amount = min(amount, max_price_amount)\n        self.remove_from_total_amount(amount=amount)\n        max_price_amount -= amount\n\n        self.update_orders_for_price(price=max_buy_price, amount=max_price_amount)\n        if max_price_amount == 0:\n            self.pop()\n        return max_buy_price\n\nclass SellBacklog(Backlog):\n    def add(self, price: int, amount: int):\n        existing_orders_for_price = self.get_orders_for_price(price=price)\n        if existing_orders_for_price == 0:\n            self.push(price=price)\n        new_orders_for_price = existing_orders_for_price + amount\n        self.add_to_total_amount(amount=amount)\n        self.update_orders_for_price(price=price, amount=new_orders_for_price)\n\n    def remove(self, amount: int) -> Optional[int]:\n        min_buy_price = self.peek()\n        if min_buy_price is None:\n            return\n        min_price_amount = self.get_orders_for_price(price=min_buy_price)\n        amount = min(amount, min_price_amount)\n        self.remove_from_total_amount(amount=amount)\n        min_price_amount -= amount\n        self.update_orders_for_price(price=min_buy_price, amount=min_price_amount)\n        if min_price_amount == 0:\n            self.pop()\n        return min_buy_price\n\n\nclass Solution:\n    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n        buy_backlog = BuyBacklog()\n        sell_backlog = SellBacklog()\n\n        for price, amount, order_type_id in orders:\n            order_type = OrderType.get(order_type_id=order_type_id)\n            if order_type == OrderType.BUY:\n                min_sell_price = sell_backlog.peek()\n                while amount > 0 and min_sell_price is not None and min_sell_price <= price:\n                    sell_amount = sell_backlog.get_orders_for_price(price=min_sell_price)\n                    sell_backlog.remove(amount=amount)\n                    amount -= sell_amount\n                    min_sell_price = sell_backlog.peek()\n                if amount > 0:\n                    buy_backlog.add(price=price, amount=amount)\n            elif order_type == OrderType.SELL:\n                max_buy_price = buy_backlog.peek()\n                while amount > 0 and max_buy_price is not None and max_buy_price >= price:\n                    buy_amount = buy_backlog.get_orders_for_price(price=max_buy_price)\n                    buy_backlog.remove(amount=amount)\n                    amount -= buy_amount\n                    max_buy_price = buy_backlog.peek()\n                if amount > 0:\n                    sell_backlog.add(price=price, amount=amount)\n            else:\n                raise KeyError(f\'invalid order type\')\n\n        total_remaining_amount = (sell_backlog.get_total_amount() + buy_backlog.get_total_amount())%MOD\n        return total_remaining_amount\n\n```
['Python3']