Iteration

Kitchen Rush

You own a restaurant and are getting non-stop orders from customers. You can't cook the food fast enough! You tell your head chef to only cook the lowest-numbered orders at all times.

Design a class to keep track of the orders called KitchenOrders. You should write a method for adding a new order, a method for looking at the lowest numbered order, and a method for removing the lowest order number.

Example:

orders = KitchenOrders()

orders.add(3)
orders.add(1)
orders.add(1)
orders.add(2)
orders.getLowest()  # 1, smallest of [3,1,1,2]

orders.removeLowest()
orders.getLowest()  # 1, smallest of [3,1,2]

orders.removeLowest()
orders.getLowest()  # 2, smallest of [3,2]

Hint: Remember, you add/remove from the Heap like this:

h = []                # store heap as an array
heapq.heappush(h, 3)  # adds 3 to heap
heapq.heappop(h)      # removes and returns minimum number
h[0]                  # minimum number in heap

First Test Case:

c = KitchenOrders()
c.add(3)
c.getLowest()
c.add(1)
c.getLowest()
c.removeLowest()
c.getLowest()
# We compare the result of every function when judging.

One solution is to keep track of the smallest number you've seen so far. The problem with this is if you remove the lowest number, you need to re-iterate through all the numbers to find the new lowest number, which is $O(n)$ .

It's much smarter to use a Heap instead, because a Heap totally avoids any $O(n)$ time operations. A Heap lets you find the smallest element in $O(1)$ time, and it lets you add/remove an element in $O(\log n)$ time. Here's how you use a Heap to solve this problem:

import heapq

class KitchenOrders:    
    def __init__(self):
        self.heap = [] # start with an empty heap
    
    def add(self, number):
        heapq.heappush(self.heap, number) # add number to heap

    def getLowest(self):
        return self.heap[0] # get smallest number in heap

    def removeLowest(self):
        heapq.heappop(self.heap) # remove smallest number in heap

Get Time Complexity $O(1)$

Remove Time Complexity $O(\log n)$

Add Time Complexity $O(\log n)$

Space Complexity $O(n)$ , where $n$ is the number of items in the Heap.

Mark as Completed:

Submits:

KitchenOrders

Test your code to get an output here!