# 5 Stack and Queue Interview Questions (Amazon, Facebook, Apple and Microsoft)

Here, we will explore different types of data structure questions asked by tech companies during their interview process. These are some difficult questions, so feel free to skip them and come back after you have finished reading all the blogs.

*Question 1: Three in One*

*Describe how you could use a single Python list to implant three stacks.*

Visualization:

We will divide the list in three equal parts.

This will allow the stacks placement in a limited space.

The stacks has their specific indexes over here.

Sq bracket means the element is included and simple bracket means the element is excluded

Let's move on to the code now.

```
class MultiStack:
def __init__(self, stackSize):
self.stackNumber = 3
self.custList = [0] * (stackSize * self.stackNumber)
self.sizes = [0] * self.stackNumber
self.stackSize = stackSize
def isFull(self, stacknum) :
if self.sizes[stacknum] == self.stacksize:
return True
else:
return False
def isEmpty(self, stacknum):
if self.sizes[stacknum] == 0:
return True
else:
return False
def indexOfTop(self, stacknum):
offset = stacknum * self.stackSize
return offset + self.sizes[stacknum] - 1
def push(self, item, stacknum):
if self.isFull(stacknum):
return "This stack s empty"
else:
self.sized[stacknum] += 1
self.custList[self.indexOfTop(stacknum)] = item
def pop(self, stacnum):
if self.isEmpty(stacknum):
return "This stack is empty"
else:
value = self.custList[self.indexOfTop(stacknum)]
self.custList[self.indexOfTop(stacknum)] = 0
self.sizes[stacknum] -= 1
return value
def peek(self,stacknum):
if self.isEmpty(stacknum):
return "This stack is empty"
else:
value = self.custList[self.indexOfTop(stacknum)]
return value
customStack = MultiStack(6)
print(customStack.isFull(0))
print(customStack.isEmpty(1))
customStack.push(1,0)
customStack.push(2,0)
customStack.push(3,2)
print(customStack.peek(0))
print(customStack.pop(0))
```

Explanation:

Our stack will be with capacity so we need to set stack size in the parameter. Then we will set the number of stacks (as per question, we will set it to 3). Then, in the next property, we need to create fixed size list. `custList`

will take number of stacks multiply with number of stack size. If it's empty, the elements will be zero. Then, we'll create another list in which we will keep the size of stacks.

First method will be `isFull`

method. It will take two params - self, stack number. By using this method, we will be able to find which stack is full. In this function, `if`

- self sizes of this stack number equals to self stack size, then it means its full.

Next method will be `isEmpty`

method. We know that, in sizes list we are keeping the stack sizes.

Next, the method takes two parameters and returns the top element's index. I created an offset variable that multiplies `stacknum`

by `self.stackSize`

. We return the offset plus the stack size from sizes minus one. This gives us the top element of the stack.

Push method : In case of stack, push method is used to insert an element to the stack. This element is places at the top of the other elements. Our method will have three params - self, item and `stacknum`

(in which we want to insert the element). Inside the size list, we will increase the size of the stack. Then we will add the item at the end of the list.

Pop method: This method returns and removes the top element from the stack. It takes two parameters - self and `stacknum`

to specify which stack to remove from. I will create a value to take the top element from the given stack.

Peek method : Peek method is similar to pop method.

*Question 2: Stack Minimum*

*How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in O(1)*

Note : Minimum does not change very often. The only change when a smaller element is added.

One solution is to add a single integer minimum value. Then, when the minimum value is popped up from the stack, we search through the stack to find new minimum. To implement O(1), we have to implement linked list here.

```
class Node:
def __init__(self,value = None, next = None):
self.value = value
self.next = next
def __str__(self):
string = str(self.value)
if self.next:
string += "," + str(self.next)
else:
return string
class Stack:
def __init__(self):
self.top = top
self.minNode = None
def min(self):
if not self.minNode:
return None
return self.minNode.value
def push(self, item):
if self.minNode and (self.minNode.value <= item):
self.minNode = Node(value = self.minNode.value, next = self.minNode)
else:
self.minNode = Node(value = item, next = self.minNode)
self.top = Node(value = item, next = self.top)
def pop(self):
if not self.top:
return None
self.minNode = self.minNode.next
item = self.top.value
self.top = self.top.next
return item
customStack = stack()
customStack.push(5)
print(customStack.min())
customStack.push(6)
print(customStack.min())
customStack.push(3)
print(customStack.min())
customStack.pop()
print(customStack.min())
```

*Question 3: Stack of Plates*

Imagine a stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when a previous stack exceeds some threshold. Implement a data structure `SetOfStacks`

that mimics this. `SetOfStacks`

should be composed of several stacks and should create a new stack once the previous exceeds capacity, `SetOfStacks.push()`

and `SetOfStacks.pop()`

should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).

Follow up: Implement a function `popAt`

(int index) which performs a pop operation on a specific sub - stack.

Explanation:

```
class PlateStack:
def __init__(self, capacity):
self.capacity = capacity
self.stacks = []
def __str__(self):
return self.stacks
def push(self,item):
if len(self.stacks) > 0 and (len(self.stacks[-1])) < self.capacity:
self.stacks[-1].append(item)
else:
self.stacks.append([item]) #2D
def pop(self):
while len(self.stacks) and len(self.stacks[-1]) == 0:
self.stacks.pop()
if len(self.stacks) == 0:
return None
else:
return self.stacks[-1].pop()
def pop_at(self, stackNumber):
if len(self.stacks[stackNumber]) > 0:
return self.stacks[stackNumber].pop()
else:
return None
customStack = PlateStack(2)
customStack.push(1)
customStack.push(2)
customStack.push(3)
print(customStack.pop())
```

*Question 4: Queue via Stacks*

Implement Queue class which implements a queue using two stacks.

Explanation:

Code:

```
class Stack:
def __init__(self):
self.list = []
def __len__(self):
return len(self.list)
def push(self,item):
self.list.append(item)
def pop(self):
if len(self.list) == 0:
return None
return self.list.pop()
class QueueviaStack:
def __init__(self):
self.inStack = Stack()
self.outStack = Stack()
def enqueue(self, item):
self.inStack.push(item)
def dequeue(self):
while len(self.inStack) :
self.outStack.push(self.inStack.pop())
result = self.outStack.pop()
while len(self.outStack):
self.inStack.push(self.outStack.pop())
return result
customQueue = QueueviaStack()
customQueue.enqueue(1)
customQueue.enqueue(2)
customQueue.enqueue(3)
print(customQueue.dequeue())
customQueue.enqueue(4)
print(customQueue.dequeue())
```

*Question 5: Animal Shelter*

An animal shelter, which holds only dogs and cats, operates on a strictly "first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like.

Create a data structures to maintain this system and implement operations such as `enqueue`

, `dequeueAny`

, `dequeueDog`

, and `dequeueCat`

Visualization :

Code:

```
class AnimalShelter:
def __init__(self):
self.cats = []
self.dogs = []
def enqueue (self, animal, type):
if type == "Cat" :
self.cats.append(animal)
else:
self.dogs.append(animal)
def dequeueCat(self):
if len(self.cats) == 0 :
return None
else:
cat = self.cats.pop(0)
return cat
def dequeueDog(self):
if len(self.dogs) == 0:
return None
else:
dog = self.dogs.pop(0)
return dog
def dequeueAny(self):
if len(self.cats) == 0:
result = self.dogs.pop(0)
else:
result = self.cats.pop(0)
return result
customQueue = AnimalShelter()
customQueue.enqueue("Cat1", "Cat")
customQueue.enqueue("Cat2", "Cat")
customQueue.enqueue("Dog1", "Dog")
customQueue.enqueue("Cat3", "Cat")
customQueue.enqueue("Dog2", "Dog")
```

End.