Google Interview problem solution

#javascript #interview #google #datastructure

Explanation of Daily coding problem #365

A quack is a data structure combining properties of both stacks and queues. It can be viewed as a list of elements written left to right such that three operations are possible:

push(x): add a new item x to the left end of the list
pop(): remove and return the item on the left end of the list
pull(): remove the item on the right end of the list.

Implement a quack using three stacks and O(1) additional memory, so that the amortized time for any push, pop, or pull operation is O(1).

Solution in JavaScript

Push and Pop Is already supported in JavaScript as list operation which will actually remove items from the right and both of the operation is O(1).

Pull will be tricky as removing first item will require us to move every other item in the list Which will be O(n) operation.

We can utilize deque ( double ended queue) which is a type of queue which allows as to remove and items from front as well as back . so we can use deque as stack and queue both. You can read more about deque here. Deque generally is created using two data structure i.e. circular array , doubly linked list.

But for our solution we need to create deque with stacks.
One way is to have three stacks.

left ( will be used for push and pop )
right ( will be used for pull)
buffer ( will be used for reversing a stack )![Untitled

Push

we can add items from left directly and As we're using JavaScript Arrays which are dynamic we don't have to worry about the upper limit of quack or we can say our left stack.

Pop

If we have item in the left array we can simply pop like this

but in our case we need to check whether we have item in our right list , if yes then we need to balance our quack.
Example:

For this we need to move half of our items in the right stack to left stack

Move half of the items in the buffer.
Move remaining items to left.
Move all items in the buffer to the right back.

Same Goes for the pull operation , if we don't have have item in the right array we need to balance our quack (move half items from left to right)

Here's the full code

class Quack {
  constructor(left = [], right = []) {
    this.left = left;
    this.right = right;
    this.buffer = [];
  }

  print() {
    console.log(this.left, this.right);
  }

  push(newItem) {
    this.left.push(newItem);
  }

  pop() {
    if (this.left.length <= 0 && this.right.length <= 0) {
      console.log("Quack is already Empty");
      return;
    }
    if (this.left.length === 0) this.balance(this.right, this.left);
    this.left.pop();
  }

  pull() {
    if (this.left.length <= 0 && this.right.length <= 0) {
      console.log("Quack is already Empty");
      return;
    }
    if (this.right.length === 0) this.balance(this.left, this.right);
    this.right.pop();
  }

  balance(from, to) {
    const length = from.length;
    const halfPoint = Math.floor(length / 2);
    for (let i = 0; i < halfPoint; i++) {
      this.buffer.push(from.pop());
    }

    while (from.length > 0) {
      to.push(from.pop());
    }

    while (this.buffer.length > 0) {
      from.push(this.buffer.pop());
    }
  }
}

const quack = new Quack();

quack.push(1);
quack.push(2);
quack.push(3);

quack.print();
quack.balance(quack.right, quack.left);

quack.print();
quack.pull();
quack.pop();
quack.pop();
quack.pull();

quack.print();