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:
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(logn) time. Here's how you use a Heap to solve this problem:
Get Time Complexity O(1)
Remove Time Complexity O(logn)
Add Time Complexity O(logn)
Space Complexity O(n), where n is the number of items in the Heap.
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()