Design a stack data structure with the following operations:
maxSize
. The stack should not be able to hold more than maxSize
elements.x
onto the top of the stack. If the stack is full (i.e., already contains maxSize
elements), do nothing.k
elements of the stack by val
. If there are fewer than k
elements in the stack, increment all the elements in the stack.Example:
CustomStack stk = new CustomStack(3); // Stack is Empty []
stk.push(1); // stack becomes [1]
stk.push(2); // stack becomes [1, 2]
stk.pop(); // return 2, stack becomes [1]
stk.push(2); // stack becomes [1, 2]
stk.push(3); // stack becomes [1, 2, 3]
stk.push(4); // stack remains [1, 2, 3] (maxSize reached)
stk.increment(5, 100); // stack becomes [101, 102, 103]
stk.increment(2, 100); // stack becomes [201, 202, 103]
stk.pop(); // return 103, stack becomes [201, 202]
stk.pop(); // return 202, stack becomes [201]
stk.pop(); // return 201, stack becomes []
stk.pop(); // return -1, stack is empty
Explain how you would implement this CustomStack
class with efficient time complexity for all operations. Consider edge cases and constraints while designing your solution.
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
We need to create a special stack that can also increase the values of existing items. A brute force method would directly implement each operation as simply as possible, without any clever tricks or optimizations.
Here's how the algorithm would work step-by-step:
class CustomStack:
def __init__(self, max_size):
self.stack = []
self.max_size = max_size
def push(self, value):
if len(self.stack) < self.max_size:
self.stack.append(value)
def pop(self):
if self.stack:
return self.stack.pop()
else:
return -1
def increment(self, number_of_elements, value):
# Determine how many elements to increment
increment_range = min(number_of_elements, len(self.stack))
# Iterate through the bottom elements of the stack
for index in range(increment_range):
# Increment each element within the range.
self.stack[index] += value
We need to design a special stack that can not only push and pop values, but also increment several of its bottom elements. The clever idea is to avoid changing many stack values individually when incrementing; instead, we store increment amounts separately for efficiency.
Here's how the algorithm would work step-by-step:
class CustomStack:
def __init__(self, max_size: int):
self.max_size = max_size
self.stack_values = []
self.increment_values = []
def push(self, value: int) -> None:
if len(self.stack_values) < self.max_size:
self.stack_values.append(value)
# Initialize increment value to 0 for new element
self.increment_values.append(0)
def pop(self) -> int:
if not self.stack_values:
return -1
stack_index = len(self.stack_values) - 1
value_to_pop = self.stack_values.pop()
increment_to_pop = self.increment_values.pop()
value_to_return = value_to_pop + increment_to_pop
# Propagate increment to the element below.
if self.increment_values:
self.increment_values[-1] += increment_to_pop
return value_to_return
def increment(self, number_of_elements: int, value: int) -> None:
# Increment only the bottom 'number_of_elements' elements
number_of_elements_to_inc = min(number_of_elements, len(self.stack_values))
if number_of_elements_to_inc > 0:
# Apply increment to the appropriate element.
self.increment_values[number_of_elements_to_inc - 1] += value
Case | How to Handle |
---|---|
maxSize is zero | The CustomStack should be initialized but `push` operations will have no effect. |
Pushing more elements than maxSize allows | Only the first maxSize elements should be stored; subsequent `push` calls should be ignored. |
Popping from an empty stack | `pop` should return -1 if the stack is empty. |
Incrementing with k = 0 | The increment operation should have no effect as no elements are incremented. |
Incrementing with k larger than the stack size | All elements in the stack should be incremented by val. |
Large val during increment causing integer overflow | Use a data type (e.g., long) that can accommodate larger numbers or perform overflow checks and handle appropriately (e.g. throwing exception or clamping). |
A sequence of pushes, pops, and increments that leave the stack empty then followed by an increment | Increment should have no effect if the stack is empty after the pop sequence. |
maxSize is a very large number (close to the integer limit) | Ensure memory allocation doesn't exceed available resources, potentially leading to program crashes due to OOM or other issues; it might be necessary to consider alternative data structures or approaches if scalability is crucial. |