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:

1. We will divide the list in three equal parts.

   This will allow the stacks placement in a limited space.

2. The stacks has their specific indexes over here.

3. 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.