Interview Question

Software Development Engineer Intern Interview

Implement a data structure like a stack but with a way to

  find a max at O(1) time.

Interview Answer

2 Answers


Later found out this was in Cracking the Coding Interviews.

Interview Candidate on Mar 8, 2013

There are several ways to do this. You push two numbers onto the stack whenever you add, first pushing the new number and then the max of the new number and whatever was below it. If you are allowed to store the max value in a field in the stack implementation you can write a normal stack implementation, except when a new value is equal to or greater than the old max, first push the old max onto the stack. then when you call get max you get pop until the value = the max you stored, and the next value you pop is the new maximum.

Malcolm on Mar 12, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.