Interview Questions

1. Accenture – Min Stack

   coding

   Title:

   Min Stack

   Problem:

   Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class with methods: push(val) which pushes the element onto the stack, pop() which removes the element on the top of the stack, top() which gets the top element, and getMin() which retrieves the minimum element in the stack.

   Input:

   class MinStack: def init(self): """Initialize your data structure here.""" pass

   def push(self, val: int) -> None:
       pass
   
   def pop(self) -> None:
       pass
   
   def top(self) -> int:
       pass
   
   def getMin(self) -> int:
       pass
   

   Output:

   A list of return values for each operation: return None for 'push' and 'pop', and return the integer value for 'top' and 'getMin'.

   Sample Input:

   operations = ['MinStack','push','push','push','getMin','pop','top','getMin'], values = [[],[-2],[0],[-3],[],[],[],[]]

   Sample Output:

   [None, None, None, None, -3, None, 0, -2]

   Example:

   1 <= number of calls <= 10^4; -2^31 <= val <= 2^31 - 1

   Constraints:

   Use two stacks: one stack holds all values and the second stack keeps track of the current minimum after each push. When pushing, also push min(value, current_min) to the min stack. When popping, pop from both stacks.

   Hints:

   Could you implement this with a single stack by storing both the value and the current minimum at each stack level or using a space-optimized approach?

   Follow-up:

   Can you implement this with a single stack by storing both the value and the current minimum at each stack level or using a space-optimized approach?