JavaScript is a fantastic language for writing leetcode-style solutions. But unlike Python, C++, etc, it's missing a few critical data structures.

During a recent interview, I found myself scrambling to find a JS implementation of a min-heap online. As I was explaining to the interviewer the correct solution, I had to explain my interview language of choice did not have the native data structure I needed.

I never wanted to find myself in the same situation in the future.

And I didn't love any of the existing implementations online. I felt like they were either too complex to quickly drop into an interview or too simple and missing basic features.

Requirements:

• Every class needed to execute in Node v10, but should use ES6+ practices
  • This means no private functions, no nullish coalescing etc.
• Each class should be easy to read and understand by an interviewer
• Include the minimum viable function set but otherwise keep it short

Building a heap class

The heap was the most critical since it's a fairly common occurrence in problems and has some complexity.

We will use a zero-indexed array as the heap.

Constructor:

All arguments should be optional.

• A comparator should be an input to decide heap type and heapify custom objects (like .sort()).
• An input array which can be O(n) heapified should also be optional.

constructor(comparator = (a, b) => a - b, input = [])

We heapify down each node from the parent node to the root of the heap.

class Heap {
    constructor(comparator = (a, b) => a - b, input = []) {
        this.arr = input;
        this.comparator = comparator;
        if (this.size() > 1) {
            for (let i = Heap.parent(this.size() - 1); i >= 0; i--)
                this.heapifyDown(i);
        }
    }
}

Push, peek, size, pop

The easiest functions to implement:

size(): returns the length of the internal array.

peek(): returns 0th element if it exists, otherwise it returns null

push(): pushes like usual to the end of the array, and then calls heapifyUp on the last element to maintain the heap invariant.

pop(): swaps the first and last elements of the heap, pops() from the array (previously the highest priority element). And then heapifyDown() from index 0 to maintain the heap invariant.

push(elem) {
    this.arr.push(elem);
    this.heapifyUp(this.size() - 1);
}

peek() {
    return this.size() > 0 ? this.arr[0] : null;
}

pop() {
    if (this.size() === 0)
        return null;
    Heap.swap(this.arr, 0, this.size() - 1);
    const result = this.arr.pop();
    this.heapifyDown(0);
    return result;
}

size() {
    return this.arr.length;
}

heapifyUp and heapifyDown

These are recursive internal functions that are used to swap heap elements to keep the heap valid.

heapifyUp(): Base case = heapifying up from the root (0).
Otherwise, we grab the parent of element we're heapifying, and if the parent is lower priority then the current element, we swap them and recurse on the parent index.

heapifyUp(idx) {
    if (idx === 0)
        return;
    const parentIdx = Heap.parent(idx);
    if (this.comparator(this.arr[idx], this.arr[parentIdx]) < 0) {
        Heap.swap(this.arr, parentIdx, idx);
        this.heapifyUp(parentIdx);
    }
}

heapifyDown(): Base case there are no children nodes for our index (no where to heapifyDown into).
We grab the child with the maxmimum priority from our current location, and swap with our current index if that child is of higher priority. And then we recurse on the child index.

heapifyDown(idx) {
    if (Heap.leftChild(idx) >= this.size())
        return;
    const childIdx = this.maxPriorityChild(idx);
    if (this.comparator(this.arr[childIdx], this.arr[idx]) < 0) {
        Heap.swap(this.arr, childIdx, idx);
        this.heapifyDown(childIdx);
    }
}

This is the gist of our heap class, with a few static functions to move indices from parent to child and vice-versa!

The full class can be found here.

Building a dead-simple Trie class

A Trie is a super awesome data structure that I find myself using all the time in coding challenges.

The idea is that it's a tree of characters for various words, in our case, we'll be using standard JS objects to allow O(1) access to check characters at each level in the Trie.

We need three functions:

• The ability to insert into the Trie
• The ability to check if a full word exists in the Trie
• The ability to check if a prefix of a given word exists in the Trie

These last two can be combined with an optional argument in the function.

Insert

Given a base object, we want to walk the tree with each character, creating an empty object, walking into it and then inserting the next character. But we also don't want to override existing data at the same level in the tree, ex: help, hello.

{"h":{"e":{"l":{"l":{"o":{"end":true}}}}}}

We can use the spread operator to make a shallow copy of existing object data, otherwise it's undefined and will create the empty object we want.

insert(word) {
    let temp = this.o;
    word.split('').forEach(e => {
        temp[e] = { ...temp[e] };
        temp = temp[e];
    });
    temp.end = true;
}

Find

The find function is very similar, we just walk down the object, and if at any point, the character we're looking at next doesn't exist, we return false.

If the user wants the full word match only, we will return the status of the .end property on the final node. Otherwise, once we've exhausted the character walk, the prefix find is true.

find(word, full = true) {
    let temp = this.o;
    let arr = word.split('');
    for (let i = 0; i < word.length; i++) {
        if (!temp[arr[i]])
            return false;
        temp = temp[arr[i]];
    }
    return full ? !!temp.end : true;
}

The full class can be found here.

I won't delve into the details, but I also included a disjoint set class that also comes in handy!

Hopefully this helps anyone else in the process of interviewing that needs some quick JS classes!