Implement Stack with in-place

Question

Implement a stack data structure that supports push, pop, and top operations using only in-place operations. The stack should allow for constant time complexity for push and pop operations, and you should ensure that the space complexity remains O(1). Your implementation should also handle edge cases, such as popping from an empty stack.

Codemia · Accepted Answer

To implement a stack with in-place operations, the key constraint is that we need to develop a structure that allows for constant time complexity for both `push` and `pop` operations while utilizing O(1) space complexity. A stack operates on a Last In First Out (LIFO) principle, which means the most recently added element is the first to be removed. The challenge here is to maintain this structure without using any auxiliary data structures like arrays or linked lists, which would increase space complexity.

We can achieve this by using a linked list-like approach where we manage our stack using a single variable to represent the top of the stack. Each node will contain the value and a reference to the next node. For example:

1. **Push Operation**: Create a new node pointing to the current top and then update the top to this new node. This can be done in O(1) time.
2. **Pop Operation**: Store the value of the current top, update the top to the next node, and return the stored value. This remains O(1) as well.
3. **Top Operation**: Simply return the value of the top node. This is also O(1).

If we encounter a pop operation on an empty stack, we need to handle it gracefully by either raising an exception or returning a sentinel value.

Here is the implementation in Python:

```python
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

def push(self, value):
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node

def pop(self):
        if self.is_empty():
            raise IndexError('Pop from empty stack')
        popped_value = self.top.value
        self.top = self.top.next
        return popped_value

def top_value(self):
        if self.is_empty():
            raise IndexError('Top from empty stack')
        return self.top.value

def is_empty(self):
        return self.top is None
```

The time complexity for all operations (push, pop, top) is O(1) since each operation only involves a constant number of steps. The space complexity is also O(1) because we are only using a fixed amount of space for the node references and not utilizing any additional data structures that grow with the number of elements in the stack.

1. **Popping from an empty stack**: This should raise an exception or return a specific error message to indicate that the operation cannot be performed.
2. **Top operation on an empty stack**: Similar to pop, this should also raise an exception.
3. **Pushing after multiple pops**: Ensure that the stack correctly maintains order and integrity after various operations. Each operation should be tested to ensure that the stack behaves correctly under all circumstances.

Implement Stack with in-place

MongoDB

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

MongoDB Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string