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:

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

First Test Case:

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)O(n).

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

Get Time Complexity O(1)O(1)

Remove Time Complexity O(logn)O(\log n)

Add Time Complexity O(logn)O(\log n)

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

Mark as Completed:
Submits:
KitchenOrders
Test your code to get an output here!
Test your code to get an output here!