Javascript

JavaScript Data Structures

String reversal

const str = 'test';

const reverseOne = str => {
  let reversed = '';
  for (let i = str.length - 1; i >= 0; i--) {
    reversed = reversed + str[i];
  }

  return reversed;
};

const reverseTwo = str => {
  return str
    .split('')
    .reverse()
    .join('');
};

const reverseThree = str => {
  let reversed = '';
  for (let char of str) {
    reversed = char + reversed;
  }

  return reversed;
};

const reverseFour = str => {
  let arr = str.split('').reduce((reversed, char) => {
    return char + reversed;
  }, '');

  return reversed;
};

Basic debugger statements

Sometimes that we to pause during execution to do some debugging.

const reverse = str => {
  debugger;
  let reversed = '';
  for (let char of str) {
    reversed = char + reversed;
  }

  return reversed;
};

reverse(str);

From within the terminal, we can then inspect by running:

node inspect path/to/file.js
cont # to continue execution (can also use c)
repl # kicks you into a js repl

Palindromes

const palindrome = str => {
  if (typeof str === String) {
    return str === reverse(str);
  } else {
    return false;
  }
};

palindrome('noon'); // true
palindrome('asdf'); // false

const palindromeTwo = str => {
  str.split('').every((char, index) => {
    if (i <= Math.ceil(str.length / 2)) {
      return char === str[str.length - 1 - index];
    }
  });
};

Reverse Integer

const reverseInt = n => {
  // Check if negative
  const isPos = Math.sign(n);
  // 1. cast to string
  const str = n.toString();
  // 2. reverse
  str
    .split('')
    .reverse()
    .join('');
  // 3. cast to int
  const revInt = parseInt(str);
  return isPos > 0 ? revInt : revInt * -1;
  // return isPos * Math.sign(n);
};

Max Chars

// 1
// maxChar('abccccccd'); // 'c'
const maxChar = (str) => {
    let obj = {};
    for (let char of str) {
        if (typeof obj[char] !== 'undefined') {
            obj[char] = obj[char] + 1l
        } else {
            obj[char] = 1;
        }
    }

    let maxChar = '';
    let max = 0;
    for (let key of obj) {
        if (obj[key] > max) {
            max = obj[key];
            maxChar = key;
        }
    }

    return maxChar;
};

// 2
const chars = {};
const maxCharTwo = str => {
    for (let char of str) {
        if (!chars[char]) {
            chars[char] = 1;
        } else {
            chars[char]++;
        }
    }

    let maxChar = '';
    let max = 0;

    for (let key of obj) {
        if (obj[key] > max) {
            max = obj[key];
            maxChar = key;
        }
    }
    return maxChar;
}

// 3
const maxCharThree = str => {
    for (let char of str) {
        chars[char] === !chars[char] ? 1 : chars[char]++;
    }
}

Fizz Buzz

let fizzBuzz = i => {
  switch (true) {
    case i % 3 === 0 && i % 5 === 0:
      return 'fizzbuzz';
    case i % 3 === 0:
      return 'fizz';
    case i % 5 === 0:
      return 'buzz';
    default:
      return i;
  }
};

Array Chunk Problem

One solution:

/**
 * Given an 1D array, chunk into 2D based on int
 *
 * @param {*} arr Init array
 * @param {*} i Chunk size
 * @returns {Object} Chunked array object
 */
let arrayChunk = (arr, i) => {
  let tmp = [];
  let chunkedArr = [];
  arr.map((d, index) => {
    tmp.push(d);
    if (index % i === i - 1) {
      chunkedArr.push(tmp);
      tmp = [];
    }
  });

  return chunkedArr;
};

Second solution:

/**
 * Given an 1D array, chunk into 2D based on int
 *
 * @param {*} arr Init array
 * @param {*} i Chunk size
 * @returns {Object} Chunked array object
 */
let arrayChunk = (arr, i) => {
  const chunkedArr = [];
  for (let el of arr) {
    const last = chunkedArr[chunkedArr.length - 1];

    if (!last || last.length === size) {
      chunkedArr.push([el]);
    } else [
      last.push([el]);
    ]
  }
  return chunkedArr;
};

Third solution:

/**
 * Given an 1D array, chunk into 2D based on int
 *
 * @param {*} arr Init array
 * @param {*} i Chunk size
 * @returns {Object} Chunked array object
 */
let arrayChunk = (arr, i) => {
  const chunkedArr = [];
  let start = 0;
  let index = 1;
  while (start < arr.length) {
    chunkedArr.push(arr.slice(start, index * i));

    start = start + i;
    index++;
  }
  return chunkedArr;
};

Fourth solution:

/**
 * Given an 1D array, chunk into 2D based on int
 *
 * @param {*} arr Init array
 * @param {*} i Chunk size
 * @returns {Object} Chunked array object
 */
let arrayChunk = (arr, i) => {
  const chunkedArr = [];
  let start = 0;
  while (start < arr.length) {
    chunkedArr.push(arr.slice(start, start + i));
    start += i;
  }
  return chunkedArr;
};

Anagrams

Solution one:

const anagram = (strA, strB) => {
  // use regexp to remove spaces and grammar
  const cmpA = strA.replace(/[^\w]/g, '').toLowerCase();
  const cmpB = strB.replace(/[^\w]/g, '').toLowerCase();

  if (cmpA.length !== cmpB.length) {
    return false;
  }

  let charMapA = {};
  let charMapB = {};
  for (let i in cmpA) {
    if (!charMapA[cmpA[i]]) {
      charMapA[cmpA[i]] = 1;
    } else {
      charMapA[cmpA[i]] = charMapA[cmpA[i]]++;
    }

    if (!charMapB[cmpB[i]]) {
      charMapB[cmpB[i]] = 1;
    } else {
      charMapB[cmpB[i]] = charMapB[cmpB[i]]++;
    }
  }

  const keysA = Object.keys(charMapA);
  const keysB = Object.keys(charMapB);

  if (keysA.length !== keysB.length) {
    return false;
  }

  for (let k in keysA) {
    if (typeof keysB[k] === 'undefined') {
      return false;
    }

    if (keysA[k] !== keysB[k]) {
      return false;
    }
  }

  return true;
};

Solution two (basic refactor):

const anagram = (strA, strB) => {
  const filterStr = str => str.replace(/[^\w]/g, '').toLowerCase();

  // use regexp to remove spaces and grammar
  const cmpA = filterStr(str);
  const cmpB = filterStr(str);

  if (cmpA.length !== cmpB.length) {
    return false;
  }

  let charMapA = {};
  let charMapB = {};
  const mapHelper = (i, str, map) => {
    if (!map[str[i]]) {
      map[str[i]] = 1;
    } else {
      map[str[i]] = map[str[i]]++;
    }
  };

  for (let i in cmpA) {
    mapHelper(i, cmpA, charMapA);
    mapHelper(i, cmpB, charMapB);
  }

  const keysA = Object.keys(charMapA);
  const keysB = Object.keys(charMapB);

  if (keysA.length !== keysB.length) {
    return false;
  }

  for (let k in keysA) {
    if (typeof keysB[k] === 'undefined') {
      return false;
    }

    if (keysA[k] !== keysB[k]) {
      return false;
    }
  }

  return true;
};

Solution three:

const anagrams = (strA, strB) => {
  const charMapA = buildCharMap(strA);
  const charMapB = buildCharMap(strB);

  if (Object.keys(charMapA).length !== Object.keys(charMapB).length) {
    return false;
  }

  for (let char in charMapA) {
    if (aCharMap[char] !== bCharMap[char]) {
      return false;
    }
  }

  return true;
};

const buildCharMap = str => {
  const charMap = {};
  for (let char of str.replace(/[^\w]/g, '').toLowerCase()) {
    charMap[char] = charMap[char] + 1 || 1;
  }

  return charMap;
};

Solution four:

const anagrams = (strA, strB) => cleanStr(strA) === cleanStr(strB);

const cleanStr = str =>
  str
    .replace(/[^\w]/g, '')
    .toLowerCase()
    .split('')
    .sort()
    .join('');

Capitalising a sentece

Easy solution for first of sentence:

const capitaliseStr = str => str[0].toUpperCase() + str.slice(1);

If you actually need to capitalise all sentences...

First solution:

const capitaliseStr = str => {
  const arr = str.split(' ');

  return arr
    .map(str => {
      return str[0].toUpperCase() + str.slice(1);
    })
    .join(' ');
};

Second solution:

const capitaliseStr = str => {
  let res = str[0].toUpperCase();
  for (let i = 1; i < str.length; i++) {
    if (str[i - 1] === ' ') {
      res = res + str[i].toUpperCase();
    } else {
      res = res + str[i];
    }
  }
  return res;
};

Stepper

Without a space:

const step = stepper => {
  let res = '';
  for (let i = 0; i < stepper; i++) {
    let count = 0;
    while (count <= i) {
      res = res + '#';
      count++;
    }

    if (i !== stepper - 1) {
      res = res + '\n';
    }
  }

  console.log(res);
  return res;
};

module.exports = {
  step,
};

With a space:

const step = stepper => {
  let res = '';
  for (let i = 0; i < stepper; i++) {
    let count = 0;
    while (count <= i) {
      res = res + '#';
      count++;
    }

    while (count <= stepper) {
      res = res + ' ';
      count++;
    }

    if (i !== stepper - 1) {
      res = res + '\n';
    }
  }

  console.log(res);
  return res;
};

module.exports = {
  step,
};

Using recursion (doesn't return the string):

const step = (n, row = 0, stair = '') => {
  // Complete
  if (n === row) {
    return;
  }

  // Handling a row
  if (n === stair.length) {
    console.log(stair);
    return step(n, row + 1);
  }

  // Handling str on row
  if (stair.length <= row) {
    stair += '#';
  } else {
    stair += ' ';
  }

  return step(n, row, stair);
};

Pyramids

Solution One:

const pyramid = n => {
  const midpoint = Math.floor((2 * n - 1) / 2);
  let level = '';
  for (let row = 0; row < n; row++) {
    for (let column = 0; column < 2 * n - 1; column++) {
      if (midpoint - row <= column && midpoint + row >= column) {
        level += '#';
      } else {
        level += ' ';
      }

      if (column === 2 * n - 2) {
        level += '\n';
      }
    }
  }

  return level;
};

Solution with recursion:

const pyramid = (n, row = 0, level = '') => {
  // Complete
  if (n === row) {
    console.log(level);
    return;
  }

  // Handling a row
  if (2 * n - 1 === level.length) {
    console.log(level);
    return pyramid(n, row + 1);
  }

  const midpoint = Math.floor((2 * n - 1) / 2);
  let add = '';
  if (midpoint - row <= level.length && midpoint + row >= level.length) {
    add += '#';
  } else {
    add += ' ';
  }

  return pyramid(n, row, level + add);
};

Vowel Counting

Solution One:

let vowels = str => {
  let count = 0;
  // could also just use vowels = 'aeiou'
  const vowels = ['a', 'e', 'i', 'o', 'u'];
  for (let char of str) {
    if (vowels.includes(char)) {
      count++;
    }
  }

  return count;
};

Solution Two:

let vowels = str => {
  const matches = str.match(/[aeiou]/gi);
  return matches ? matches.length : 0;
};

General Matrix

Solution One:

let matrix = n => {
  let mat = [];
  let count = 1;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (j === 0) {
        mat[i] = [];
      }

      mat[i][j] = count;
      count++;
    }
  }

  return mat;
};

Matrix Spiral

Solution One:

let matrix = n => {
  let results = [];

  // init all 2d arrays
  for (let i = 0; i < n; i++) {
    results.push([]);
  }

  let count = 1;
  let startRow = 0;
  let endRow = n - 1;
  let startCol = 0;
  let endCol = n - 1;

  while (startCol <= endCol && endRow >= startRow) {
    // Top row
    for (let i = startCol; i <= endCol; i++) {
      results[startRow][i] = count;
      count++;
    }
    startRow++;

    // Right col
    for (let i = startRow; i <= endRow; i++) {
      results[i][endCol] = count;
      count++;
    }
    endCol--;

    // Bottom row
    for (let i = endCol; i >= startCol; i--) {
      results[endRow][i] = count;
      count++;
    }
    endRow--;

    // Start col
    for (let i = endRow; i >= startRow; i--) {
      results[i][startCol] = count;
      count++;
    }
    startCol++;
  }
  console.log('results', results);
  // find midpoint to start at (base on even/odd) console.log(results);
  return results;
};

Runtime Complexity

Linear runtime (N):

const capitaliseStr = str => {
  let res = str[0].toUpperCase();
  for (let i = 1; i < str.length; i++) {
    if (str[i - 1] === ' ') {
      res = res + str[i].toUpperCase();
    } else {
      res = res + str[i];
    }
  }
  return res;
};

For an example of quadratic runtime (N^2):

const step = (n, row = 0, stair = '') => {
  // Complete
  if (n === row) {
    return;
  }

  // Handling a row
  if (n === stair.length) {
    console.log(stair);
    return step(n, row + 1);
  }

  // Handling str on row
  if (stair.length <= row) {
    stair += '#';
  } else {
    stair += ' ';
  }

  return step(n, row, stair);
};

Determining complexity

How can we determine complexity?

Time	Value	Definition
Constant	1	No mantter how many elements we're working with, the algorithm/operation/whatever will always take the same amount of time
Logarithmic	log(n)	You have this if doubling the number of elements you are iterating over doesn't double the amount of work. Always assume search algorithms to be log(n)
Linear	n	Iterating through all elements in a colection of data (think arrays)
Quasilinear	n * log(n)	You have this if doubling the number of elements you are iterating over doesn't double the amount of work. Always assume sort algorithms to be n*log(n)
Quadratic	n^2	Every el in a collection has to be compared to every other elements (handshake problem)
Exponential	2^n	If you add a "single" element to a collection, the processing power required doubles

Big 'O' Notation

Complexity	Name
O(n)	Linear
O(1)	Constant
O(n^2)	Quadratic

Common Complexities (Runtime)

Example	Likely complexity
Iterating through simple loop on single collection	Probably O(n)
Iterating through half a collection?	Still O(n). There are no constants in runtime.
Iterating through 2 different collections with separate for loops	O(n + m)
Two nested for loops iterating over the same collection?	O(n^2)
Two nested for loops iterating over different collections?	O(n*m)
Sorting	O(n*log(n))
Two nested for loops	O(n^2)
Two nested for loops on different collections	O(n*m)
Sorting?	O(n*log(n))
Searching a sorted array?	O(log(n))

Space Complexity

Extremely similar to performance but related to memory.

Fibonacci

First solution:

const fib = n => {
  const result = [0, 1];

  for (let i = 2; i <= n; i++) {
    const a = result[result.length - 1];
    const b = result[result.length - 2];

    result.push(a + b);
  }

  return result[n];
};

Recursive solution one:

const fibonacci = (n, iter = 0, value = 1, prev = 0) => {
  // 0, 1, 1, 2, 3, 5 ... handle base cases
  if (n === 0) {
    return 1;
  } else if (n === 1) {
    return 2;
  }

  if (iter < n - 1) {
    const newValue = value + prev;
    return fibonacci(n, iter + 1, newValue, value);
  }

  return value;
};

Recursive solution two:

const fibonacci = n => {
  if (n < 2) {
    return n;
  }

  return fib(n - 1) + fib(n - 2);
};

To get the complexity of the Fibonacci sequence, we need to think about how all the totals come together for the return calls.

Fibonacci tree

We don't care of fib(0) since it comes back with zero.

Remove fib(0)

Therefore for us, we can total calls of fib(1) and that is how we see that we get 5 for fib(4).

The time complexity is O(2^n).

Memoization

Here are some of the performance characteristics of recursion vs quadratic.

For the recusive function, if we saw the tree that represents all the calls, you will see quickly that each iteration requires two more calls until we reach fib(1) and fib(0).

Given the number of operations increases exponentially, we then know that it becomes O(2^n). This is a massive no no.

With the first iterative solutin, we will get linear runtime.

What the interviewer wants to hear for the recursive answer is that we are wasting resources by recalling the same functions over and over (think of how often fib(3) might be called lower in the recursion tree when running fib(6)).

What they want to here is memoization - store the arguments of each function call along with the result. If the function is called again with the same arguments, return the precomputed results, rather than running the function again.

Using this will dramatically improve runtime.

Implementing memoization

Recursive solution with memoization:

const memoize(fn) {
  const cache = {};
  return function(...args) {
    if (cache[args]) {
      return cache[args];
    }

    // NOTE: apply is integral - check MDN if you don't know how it works
    // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Function/apply
    const result = fn.apply(this, args);
    cache[args] = result;

    return result;
  };
}

const slowFib = n => {
  if (n < 2) {
    return n;
  }

  return fib(n - 1) + fib(n - 2);
}

const fibonacci = memoize(slowFib);
// fib = memoize(fib); // could also do this if we rename slowFib => fib

What's a data structure?

Data structures are all about runtime complexity:

Ways of organizing information with optimal 'runtime complexity' for adding or removing records.
Javascript natively implements several data structures. You will still be asked about 'inferior' data structures.

Queueing

Enqueing: push to back, dequeueing: pop from top.

Implementing a queue in JS:

Queue	Array equivalent
Add to queue	array.unshift();
Remove from queue	array.pop();

So we could handicap an array. Why would we do that? Just to basically help hide some of the array functionality to lock it down.

export default class Queue {
  constructor() {
    this.data = [];
  }

  add(record) {
    this.data.unshift(record);
  }

  remove() {
    return this.data.pop();
  }
}

// another file
import Queue from 'path/to/file';
const q = new Queue();

q.add({ foo: 'bar' });
const nextInQ = q.remove();

Weave

Weave receives two queues as arguments and combines the contents of each into a new, third queue. The third queue should contain the alterating content of the two queues. The function should handle queues of different lengths without inserting undefined into the new one.

Image you have queue one [1,2,3] and queue two 'hello', 'world', '! then we want to have [1, 'hello', 2, 'world', 3, '!'].

// first, update queue
export default class Queue {
  constructor() {
    this.data = [];
  }

  add(record) {
    this.data.unshift(record);
  }

  remove() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }
}

import Queue from 'path/to/file';
// using weave
function weave(srcOne, srcTwo) {
  const q = new Queue();
}

module.exports = weave;

Assuming we have that queue class, one implementation is:

const runWeave = (qOne, qTwo) => {
  const weave = new Queue();

  while (qOne.peek() || qTwo.peek()) {
    if (qOne.peek()) {
      weave.add(qOne.remove());
    }

    if (qTwo.peek()) {
      weave.add(qTwo.remove());
    }
  }

  return weave;
};

Stacks

Stack is like a push pop implementation of records. It is First in, Last out.

Stack implemntation

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

  push(record) {
    this.data.push(record);
  }

  pop() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }
}

Queue from Stacks

Using two stacks, can we emulate a queue?

const Stack = require('stack');
const Queue = require('queue');

const s1 = new Stack();
const s2 = new Stack();

const q = new Queue();

const base = ['green', 'blue', 'red'];
// start with ['green', 'blue', 'red']
// act as if we were queueing to get green out first
while (base.length > 0) {
  s1.push(base.unshift());
}

while (s1.peek()) {
  s2.push(s1.pop());
}

// now to act as if it is FIFO
s2.pop(); // gets out green

Instead of just emulating, if we create a new queue:

class Queue {
  constructor() {
    this.first = new Stack();
    this.second = new Stack();

    add(record) {
      this.first.push(record);
    }

    remove() {
      while (this.first.peek()) {
        this.second.push(this.first.pop());
      }
      const record = this.second.pop();

      while (this.second.peek()) {
        this.first.push(this.second.pop());
      }

      return record;
    }

    peek() {
      while (this.first.peek()) {
        this.second.push(this.first.pop());
      }

      const record = this.second.peek();

      while (this.second.peek()) {
        this.first.push(this.second.pop());
      }

      return record;
    }
  }
}

To clarify with the above challenge, it's to go A => StackA => StackB and back treating both the stacks as a queue.

Linked List

Basic singularly linked list

A node generally contains data and a reference to the next node and the linked list is the collections of nodes linked to each other.

const nodeOne = {
  data: 123,
};

const nodeTwo = {
  data: 456,
};

nodeOne.next = nodeTwo;

We can build a Node and LinkedList class to help us out here:

class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor(head = null) {
    this.head = head;
  }

  insertFirst(data) {
    const node = new Node(data, this.head);
    this.head = node;
  }

  /**
   * Return size of LinkedList
   *
   * @returns {Number} Size of list
   * @memberof LinkedList
   */
  size() {
    if (this.head) {
      // traverse the head
      let node = this.head;
      let size = 1;
      while (node.next) {
        node = node.next;
        size++;
      }

      return size;
    }

    return 0;
  }

  getFirst() {
    return this.head;
  }

  getLast() {
    let node = this.head;
    while (node.next) {
      node = node.next;
    }

    return node;
  }

  /**
   * Note, we might not have to iterate through all the null values.
   *
   * @memberof LinkedList
   */
  clear() {
    if (this.head.next) {
      let node = this.head.next;
      while (node.next) {
        let temp = node.next;
        node = null;
        node = temp;
      }
    }

    this.head = null;
  }

  removeFirst() {
    if (!this.head) {
      return;
    }

    this.head = this.head.next;
  }

  removeLast() {
    if (!this.head) {
      return;
    }

    if (!this.head.next) {
      this.head = null;
      return;
    }

    let node = this.head.next;
    let prev = this.head;

    while (node.next) {
      prev = node;
      node = node.next;
    }

    prev.next = null;
  }

  insertLast(data) {
    // this could also be done using this.getLast()
    const n = new Node(data);

    if (!this.head) {
      this.head = n;
      return;
    }

    if (!this.head.next) {
      this.head.next = n;
      return;
    }

    let node = this.head.next;

    while (node.next) {
      node = node.next;
    }

    node.next = n;
  }

  /**
   * Get node at a particular index with head equating to 0.
   *
   * @param {*} index Index to fetch at.
   * @memberof LinkedList
   */
  getAt(index) {
    if (!this.head) {
      return null;
    }

    let count = 0;
    let node = this.head;
    while (count < index) {
      if (!node.next) {
        return null;
      }

      count++;
      node = node.next;
    }

    return node;
  }

  /**
   * Remove at a particular index.
   *
   * @param {*} index index to remove.
   * @memberof LinkedList
   */
  removeAt(index) {
    if (!this.head) {
      return;
    } else if (index === 0 && this.head.next) {
      let node = this.head.next;
      this.head = node;
    }

    let prev = this.head;
    let node = this.head.next;
    let counter = 0;

    while (counter < index) {
      if (!node.next) {
        return;
      }

      prev = node;
      node = node.next;
    }

    prev.next = node.next;
  }

  /**
   * Insert node at a particular index. Ensure it can handle cases where there is a next or no next.
   * Insert at end if index is out of bounds.
   *
   * @param {*} index Index to insert the object at.
   * @memberof LinkedList
   */
  insertAt(data, index) {
    if (!this.head) {
      this.head = new Node(data);
    }

    if (index === 0) {
      this.head = new Node(data, this.head);
    }

    let counter = 0;
    let prev = this.head;
    let node = this.head.next;
    while (counter < index) {
      if (!node.next) {
        node.next = new Node(data);
      }

      prev = node;
      node = node.next;
    }

    prev.next = new Node(data, node);
  }
}

Basic notes on generators

function* numbers() {
  yield 1;
  yield 2;
  yield* moreNumbers(); // I will pass another generator, next should continue to receive yields from this function
  yield 6;
  yield 7;
}

function* moreNumbers() {
  yield 3;
  yield 4;
  yield 5;
}

const generator = numbers();

const values = [];
for (let value of generator) {
  values.push(value);
}

console.log(values); // [1,2,3,4,5,6,7]

A practical example:

class Tree {
  constructor(value = null, children = []) {
    this.value = value;
    this.children = children;
  }

  *printValues() {
    yield this.value;
    for (let child of this.children) {
      yield* child.printValues();
    }
  }
}

const tree = new Tree(1, [new Tree(2, [new Tree(4)]), new Tree(3)]);

// Go in a Depth First Search way to print out the tree
const values = [];
for (let value of tree.printValues()) {
  values.push(value);
}

console.log(values); // [1,2,4,3]

In practise with linked lists:

class LinkedList {
  constructor(head = null) {
    this.head = head;
  }

  // ... other methods

  /**
   * This will allow us to use a for/of loop with our linked list.
   *
   * @memberof LinkedList
   */

  *[Symbol.iterator]() {
    let node = this.head;
    while (node) {
      yield node;
      node = node.next;
    }
  }
}

// in use assuming we have a LinkedList object list
for (let node of list) {
  console.log(node.data);
}

Midpoint of a Linked List

Get list length / 2 but fetch the roof.

const midpoint = list => {
  let slow = list.getFirst();
  let fast = list.getFirst();

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
};

Detecting Linked List Loops

How can you detect if a linked list has a circular reference?

const circular = list => {
  let slow = list.getFirst();
  let fast = list.getFirst();

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
};

Linked List distance n from last

Given linked list and int n, return el n spaces from the last node in the list. Do not call the size method. Always assume that nwill be less than the length of the list.

const fromLast = (list, n) => {
  let slow = list.getFirst();
  let fast = list.getFirst();

  while (n > 0) {
    fast = fast.next;
    n--;
  }

  while (fast.next && fast.next) {
    slow = slow.next;
    fast = fast.next;
  }
};

Trees Overview

Two basics ways we will go through the trees. Depth First Search and Breadth First Search.

A node class should have a data property, add method and remove method.

class Node {
  constructor(data) {
    this.data = data;
    this.children = [];
  }

  /**
   * Given some data, create a new node and add it to the current node's 'children' array
   */
  add(data) {
    this.children.push(new Node(data));
  }

  /**
   * Given some data, look at each child of the current node and remove any node with data === data
   */
  remove(data) {
    this.children = this.children.filter(node => node.data !== data);
  }
}

For the tree class, we want a constructor with root set to null.

We then want a traverseBFS and traverseDFS method.

Note: Practical reasoning for BFS vs DFS.

BFS example includes a tree of the position hierarchy of a company and wanting to print a tree of positions given importance.

DFS example.

class Tree {
  constructor() {
    this.root = null;
  }

  /**
   * (node) => // do something with node
   */
  traverseBFS(fn) {
    // start at root
    // check if children
    // if children, iterate through and recall function
    const arr = [this.root];
    while (arr.length) {
      const node = arr.shift();
      arr.push(...node.children);
      fn(node);
    }
  }

  traverseDFS(fn) {
    // start with root
    // check if children
    // if children, iterate through in depth fashion
    const arr = [this.root];
    while (arr.length) {
      const node = arr.shift();
      arr.unshift(...node.children);
      fn(node);
    }
  }
}

Level width

Given the root node of a tree, return an array where each element is the width of the tree at each level.

What we need to do is use a "stopper" variable to help us define when we hit the end of level.

Approach to level width

// given a node
let node = new Node(); // assume initiated with a bunch of children

const levelWidth = node => {
  const counters = [0];
  const arr = [node, 's'];
  while (arr.length > 1) {
    const node = arr.shift();
    if (node === 's') {
      arr.push('s');
      counters.push(0);
    } else if (arr.length) {
      counters[counters.length - 1]++;
      arr.push(...node.children);
    }
  }

  return counters;
};

levelWidth(node.root);

Binary Search Trees

Binary trees can only have at most 2 children.

Because of the restrictions of binary search trees, we generally set them up so that the node has properties left and right with a value property that is greater than left.value but smaller than right.value.

Creating a BST:

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  insert(data) {
    if (data < this.data && this.left) {
      this.left.insert(data);
    } else if (data < this.data && !this.left) {
      this.left = new Node(data);
    } else if (data > this.data && this.right) {
      this.right.insert(data);
    } else if (data > this.data && !this.right) {
      this.right = new Node(data);
    }
  }

  // Find node with data value
  contains(data) {
    if (this.data === data) {
      return this;
    } else if (data < this.data) {
      return this.left.contains(data);
    } else if (data > this.data && this.right) {
      return this.right.contains(data);
    }
  }
}

Validating a BST

To handle this, we basically want to keep a min and max value to ensure that the thresholds are kept correctly.

const validation = (node, min = null, max = null) => {
  if (max !== null && node.data > max) {
    return false;
  } else if (min !== null && node.data < min) {
    return false;
  }

  if (node.left && !validate(node.left, min, node.data)) {
    return false;
  }

  if (node.right && !validate(node.right, node.data, max)) {
    return false;
  }

  return true;
};

validation(rootNode);

Eventing system

class Events {
  constructor() {
    this.events = {};
  }

  on(eventName, callback) {
    if (this.events[eventName]) {
      this.events[eventName].push(callback);
    } else {
      this.events[eventName] = [callback];
    }
  }

  trigger(eventName) {
    if (this.events[eventName]) {
      for (let fn of this.events[eventName]) {
        fn();
      }
    }
  }

  off(eventName) {
    delete this.events[eventName];
  }
}

Sort Algos and Complexities

Name	Worst case runtime	Difficulty
BubbleSort	n^2	easiest
SelectionSort	n^2	easier
MergeSort	n*log(n)	medium

Bubble sort

Take example [10,-30,97,0,5].

const arr = [10, -30, 97, 0, 5];

const bubbleSort = arr => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
};
const bubbleSorted = bubbleSort(arr);

Selection Sort

const selectionSort = arr => {
  for (let i = 0; i < arr.length; i++) {
    let indexOfMin = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] > arr[indexOfMin]) {
        indexOfMin = j;
      }
    }

    if (indexOfMin !== i) {
      let temp = arr[j];
      arr[j] = arr[indexOfMin];
      arr[indexOfMin] = temp;
    }
  }
  return arr;
};

const selectionSorted = selectionSort(arr);

Merge Sort

// Used to break down array recursively
const mergeSort = arr => {
  if (arr.length === 1) {
    return arr;
  }

  const center = Math.floor(arr.length / 2);
  const left = arr.slice(0, center);
  const right = arr.slice(center);

  return merge (
    mergeSort(left);
    mergeSort(right);
  );
}

// Used to build the array back together
const merge = (left, right) => {
  // create results array
  let results = [];
  // while elements in BOTH arrays
  while (left.length && right.length) {
    // compare first left < first right
    if (left[0] < right[0]) {
      // shift el into res arr
      results.push(left.shift());
    } else {
      results.push(right.shift());
    }
  }

  // take everything from the arr that has stuff in it and put it in results
  return [...results, ...left, ...right];
}

JavaScript Data Structures

String reversal

Basic debugger statements

Palindromes

Reverse Integer

Max Chars

Fizz Buzz

Array Chunk Problem

Anagrams

Capitalising a sentece

Stepper

Pyramids

Vowel Counting

General Matrix

Matrix Spiral

Runtime Complexity

Determining complexity

Big 'O' Notation

Common Complexities (Runtime)

Space Complexity

Fibonacci

Memoization

Implementing memoization

What's a data structure?

Queueing

Weave

Stacks

Queue from Stacks

Linked List

Basic notes on generators

Midpoint of a Linked List

Detecting Linked List Loops

Linked List distance n from last

Trees Overview

Level width

Binary Search Trees

Validating a BST

Eventing system

Sort Algos and Complexities

Bubble sort

Selection Sort

Merge Sort

Repository

Sections

Related