Stytch: Create a system that matches buy and sell offers

question.txt

You are going to create an API for a simple order book.
The API should have four methods:
1. make_buy_offer
        a. input: int offer
        b. output: boolean matched
2. make_sell_offer
        a. input: int offer
        b. output: boolean matched
3. get_buy_list
        a. output: list[int] offers
4. get_sell_list
        a. output: list[int] offers


make_buy_offer:
Requests to buy will try to match with existing sell orders. A match is made when a 
buy is greater than or equal to a sell order. If multiple matches can be made, match 
with the lowest sell offer. If no matches are made, add the offer to the buy list.


make_sell_offer:
Requests to sell will try to match with existing buy orders. A match is made when a 
sell is less than or equal to a buy order. If multiple matches can be made, match with 
the highest buy offer. If no matches are made, add the offer to the sell list.


get_buy_list:
Return all offers in the buy list.


get_sell_list:
Return all offers in the sell list.


Example:
// This won't match – there are no sell orders yet
make_buy_offer(95)
// output: false


// This won't match – no buy offers high enough
make_sell_offer(105)
// output: false


// This won't match – no sell offers low enough
make_buy_offer(101)
// output: false


// This will match – there are buy offers high enough
make_sell_offer(90)
// output: true


// This won't match – no buy offers high enough
make_sell_offer(97)
// output: false


get_buy_list
// output: [95]


get_sell_list
// output: [105, 97]

WallStreet.py

import heapq

class MaxHeapObj(object):
  def __init__(self, val): self.val = val
  def __lt__(self, other): return self.val > other.val
  def __eq__(self, other): return self.val == other.val
  def __str__(self): return str(self.val)

class MinHeap(object):
  def __init__(self): self.h = []
  def heappush(self, x): heapq.heappush(self.h, x)
  def heappop(self): return heapq.heappop(self.h)
  def peek(self): return self.h[0]
  def is_empty(self): return len(self.h) == 0
  def __getitem__(self, i): return self.h[i]
  def __len__(self): return len(self.h)
  def __repr__(self): return self.h

class MaxHeap(MinHeap):
  def heappush(self, x): heapq.heappush(self.h, MaxHeapObj(x))
  def heappop(self): return heapq.heappop(self.h).val
  def peek(self): return self.h[0].val
  def is_empty(self): return len(self.h) == 0
  def __getitem__(self, i): return self.h[i].val
  def __repr__(self): return [x.val for x in self.h]



class WallStreet():
  def __init__(self):
    self.sell_list = MinHeap()
    self.buy_list = MaxHeap()
  
  def make_buy_offer(self, offer):
    # If there are no sell offers or all sell offers are higher than the buy offer
    if self.sell_list.is_empty() or self.sell_list.peek() > offer:
        # Put it on the buy list
        self.buy_list.heappush(offer)
        return False
    
    # We have a match for the top sell offer
    self.sell_list.heappop()
    return True
  
  def make_sell_offer(self, offer):
    # If there are no buy offers or all buy offers are lower than the sell offer
    if self.buy_list.is_empty() or self.buy_list.peek() < offer:
        # Put it on the sell list
        self.sell_list.heappush(offer)
        return False
    
    # We have a match for the top buy offer
    self.buy_list.heappop()
    return True
  
  def get_buy_list(self):
    return self.buy_list.__repr__()
  
  def get_sell_list(self):
    return self.sell_list.__repr__()

ws = WallStreet()
print(ws.get_buy_list())
print(ws.get_sell_list())
print(ws.make_buy_offer(95))
print(ws.make_sell_offer(105))
print(ws.make_buy_offer(101))
print(ws.make_sell_offer(90))
print(ws.make_sell_offer(97))
print(ws.get_buy_list())
print(ws.get_sell_list())


# // This won't match – there are no sell orders yet
# make_buy_offer(95)
# // output: false


# // This won't match – no buy offers high enough
# make_sell_offer(105)
# // output: false


# // This won't match – no sell offers low enough
# make_buy_offer(101)
# // output: false


# // This will match – there are buy offers high enough
# make_sell_offer(90)
# // output: true


# // This won't match – no buy offers high enough
# make_sell_offer(97)
# // output: false


# get_buy_list
# // output: [95]


# get_sell_list
# // output: [105, 97]