Coding Interview Preparation - Stack Implementation

For a recent preparation, I wanted to revisit the creation of a stack in Javascript and how we can do this, taking into consideration changing design aspects as well as efficiency.

Definition

A stack is a data structure in computer science that works according to the Last-in, First-out (LIFO) principle. The example of a waiter is often given, who is taking plates and stacking them on top of each other. There is only one possibility to take them of, which is to start at the top again, the first plate is thus the last one to go.

Use Cases

• You want items to go out in the reverse order that you put them in
• "undo" functionality

Methods

We require a few basic methods to use this data structure:

• push: Adding Items to the top
• pop: Removing items from the top
• isEmpty: See if there are items on the stack
• isFull: see if the stack is full
• peek: Check the item on the top without removing it

Attention Points

Before even starting to code, we always have to remember some attention points. Some things I always try to think about:

• Check input parameters: Ensure you check to see if the input parameters are correct.
• I remember a quote here from Facebook stating that if your code has a chance of failing 0.001% of the time, it will fail at scale!
• Check Performance for your Use Case: Performance is crucial, but sometimes not needed. When building something, do you need performance (typically takes a bit longer due to thinking process and sometimes implementation)? Or do you need speed of delivery? Don't waste spending hourse on over-optimizing, but design for your use case
• Think before you do: before even starting with writing a letter of code, think what you want to do, achieve and what possible ways are. If you can't come up with enough ideas, brainstorm it around.
• Tests: Write tests for everything you do, covering the following cases:
• Main Case: The case your test is designed for
• Edge Case: Edge boundaries (e.g. if you expect a number between 0 an 100, check 0 and 100 specifically)
• Stretch Case: What do you think might get hit but is very unlikely?

Implementation

class Stack {
    constructor(size) {
        this.size = size;
        this.items = [];
    }

    push(item) {
        if (!item) {
            throw new Error("INVALID_ITEM");
        }

        if (this.isFull()) {
            throw new Error("STACK_IS_FULL");
        }

        this.items.push(item);
    }

    pop() {
        if (isEmpty()) {
            return null;
        }

        return this.items.pop();
    }

    peek() {
        if (isEmpty()) {
            return null;
        }

        return this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length > 0;
    }

    isFull() {
        return this.items.length >= this.size;
    }
}

Evolution #1: Remove from bottom

We now are adding the evolution of our class and want to be able to remove items from the bottom, how would we do this? How can we do this performantly?

Implementing this can be done quite easily in Javascript. We can utilize either the shift() or the splice() method for our convenience. Using this shift() method, our method named popFromBottom() could look like this:

shift() {
    if (this.isEmpty()) {
        return null;
    }

    this.items.shift();
}

Assessing the performance is tricky now as it includes the shift() method which is created by Javascript for our convenience. We thus would need to know the performance of the underlying implementation for this. In any case, we know we have 1 check and 1 method call.

If we would use the splice() method in Javascript, we would cut up our array in 2 pieces and "glue" them together afterwards, forming a new array.

Evolution #2: Remove from the bottom without using shift() or splice()

Another evolution we can do on this is to forbid certain methods. Languages such as Javascript add a convenience method to underlying data structures which help us. So we should as well know how we can do this ourselves.

E.g. when we forbid the usage of shift() and splice(), thus we need to think how we can implement the method in an efficient way without any of these methods.

Since we can neither use the splice or shift methods, we could think of the following naively:

1. Create a new empty array (the size of the existing one - 1 element)
2. Loop over the existing array and add each item, skipping the one at the given index (in our case 0 as it's the beginning)

Can we do better at this point in time with what we know? Can we think of other data structure and algorithms that come to mind?

• Data Structures: Queue, Deque (Double Ended Queue), Linked List, …
• Algorithms:
• If size 1, we can push at the end and swap the items in memory (O(1))
• If size n, we can push at the end and swap towards the front (O(n))
• If size n, we can copy to a new array and append the items there

Which would result in code looking like this:

let newArr = [];
let idxToRemove = 0; // Remove the first item

for (let i = 0; i < this.items.length; i++) {
    if (i == idxToRemove) {
        continue;
    }

    newArr.push(this.items[i]);
}

this.items = newArr;

O Table for Common Data Structures - Average Cases

As a reminder, I also include the typical data structures used to remind myself.

|Data Structure|Access|Search|Inseration|Deletion| |-|:-:|:-:|:-:|:-:| |Array|O(1)|O(n)|O(n)|O(n)| |Stack|O(n)|O(n)|O(1)|O(1)| |Queue|O(n)|O(n)|O(1)|O(1)| |Sigly-Linked List|O(n)|O(n)|O(1)|O(1)| |Doubly-Linked List|O(n)|O(n)|O(1)|O(1)| |Hash Table|N/A|O(1)|O(1)|O(1)| |Binary Search Tree|O(log(n))|O(log(n))|O(log(n))|O(log(n))| |B-Tree|O(log(n))|O(log(n))|O(log(n))|O(log(n))| |Red-Black Tree|O(log(n))|O(log(n))|O(log(n))|O(log(n))| |Splay Tree|O(log(n))|O(log(n))|O(log(n))|O(log(n))|