Get a free weekly practice problem!

Keep that axe sharp.

× No thanks

You only have free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

You want to be able to access the largest element in a stack.

You've already implemented this Stack class:

class Stack(object): def __init__(self): """Initialize an empty stack""" self.items = [] def push(self, item): """Push a new item onto the stack""" self.items.append(item) def pop(self): """Remove and return the last item""" # If the stack is empty, return None # (it would also be reasonable to throw an exception) if not self.items: return None return self.items.pop() def peek(self): """Return the last item without removing it""" if not self.items: return None return self.items[-1]

Use your Stack class to implement a new class MaxStack with a method get_max that returns the largest element in the stack. get_max should not remove the item.

Your stacks will contain only integers.

What if we push several items in increasing numeric order (like 1, 2, 3, 4...), so that there is a new max after each push? What if we then pop each of these items off, so that there is a new max after each pop? Your algorithm shouldn't pay a steep cost in these edge cases.

You should be able to get a runtime of for push, pop, and get_max.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

time for push, pop, and get_max. additional space, where m is the number of operations performed on the stack.

Our solution requires additional space for the second stack. But do we really need it?

Can you come up with a solution that requires additional space? (It's tricky!)

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Wanna review this one again later? Or do you feel like you got it all?

Mark as done Pin for review later

Reset editor

Powered by qualified.io

. . .