Interview Cake

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 ICKStack class:

@interface ICKStack : NSObject { NSMutableArray<NSNumber *> *_items; } @property (readonly, nonatomic) NSUInteger count; @property (readonly, nonatomic) BOOL isEmpty; @property (readonly, nonatomic) NSNumber *top; - (void)push:(NSNumber *)item; - (NSNumber *)pop; @end @implementation ICKStack // initialize an empty stack - (instancetype)init { if (self = [super init]) { _items = [NSMutableArray new]; } return self; } // push a new item onto the stack - (void)push:(NSNumber *)item { [_items addObject:item]; } // remove and return the last item - (NSNumber *)pop { // if the stack is empty, return nil if (_items.count == 0) { return nil; } NSNumber *lastItem = _items.lastObject; [_items removeLastObject]; return lastItem; } // count the number of items in the stack - (NSUInteger)count { return _items.count; } // check if the stack is empty - (BOOL)isEmpty { return _items.count == 0; } // return the last item without removing it - (NSNumber *)top { return _items.lastObject; } @end

Use your ICKStack class to implement a new class ICKMaxStack with a method -getMax that returns the largest element in the stack. -getMax 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 -getMax.

A just-in-time approach is to have -getMax simply walk through the stack (popping all the elements off and then pushing them back on) to find the max element. This takes time for each call to -getMax. But we can do better.

To get time for -getMax, we could store the max integer as a member variable (call it max). But how would we keep it up to date?

For every -push:, we can check to see if the item being pushed is larger than the current max, assigning it as our new max if so. But what happens when we -pop the current max? We could re-compute the current max by walking through our stack in time. So our worst-case runtime for -pop would be . We can do better.

What if when we find a new current max (newMax), instead of overwriting the old one (oldMax) we held onto it, so that once newMax was popped off our stack we would know that our max was back to oldMax?

What data structure should we store our set of maxes in? We want something where the last item we put in is the first item we get out ("last in, first out").

We can store our maxes in another stack!

We define two new stacks within our ICKMaxStack class—_stack holds all of our integers, and _maxesStack holds our "maxima." We use _maxesStack to keep our max up to date in constant time as we -push: and -pop:

  1. Whenever we -push: a new item, we check to see if it's greater than or equal to the current max, which is at the top of _maxesStack. If it is, we also -push: it onto _maxesStack.
  2. Whenever we -pop, we also -pop from the top of maxesStack if the item equals the top item in _maxesStack.
@interface ICKMaxStack : NSObject { ICKStack *_stack; ICKStack *_maxesStack; } - (void)push:(NSNumber *)item; - (NSNumber *)pop; - (NSNumber *)getMax; @end @implementation ICKMaxStack - (instancetype)init { if (self = [super init]) { _stack = [ICKStack new]; _maxesStack = [ICKStack new]; } return self; } // Add a new item to the top of our stack. If the item is greater // than or equal to the last item in maxesStack, it's // the new max! So we'll add it to maxesStack. - (void)push:(NSNumber *)item { [_stack push:item]; if (_maxesStack.isEmpty || [_maxesStack.top compare:item] <= NSOrderedSame) { [_maxesStack push:item]; } } // Remove and return the top item from our stack. If it equals // the top item in maxesStack, they must have been pushed in together. // So we'll pop it out of maxesStack too. - (NSNumber *)pop { NSNumber *item = [_stack pop]; if ([item isEqualToNumber:_maxesStack.top]) { [_maxesStack pop]; } return item; } // The last item in maxesStack is the max item in our stack. - (NSNumber *)getMax { return _maxesStack.top; } @end

time for -push:, -pop, and -getMax. 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!)

Notice how in the solution we're spending time on -push: and -pop so we can save time on -getMax. That's because we chose to optimize for the time cost of calls to -getMax.

But we could've chosen to optimize for something else. For example, if we expected we'd be running -push: and -pop frequently and running -getMax rarely, we could have optimized for faster -push: and -pop methods.

Sometimes the first step in algorithm design is deciding what we're optimizing for. Start by considering the expected characteristics of the input.

Reset editor

Powered by qualified.io

. . .