DEV Community: Jeena John

Data Structures and Algorithms in Javascript - Part 3

Jeena John — Wed, 13 Jan 2021 16:07:47 +0000

This is Part 3 of my series of posts on Data Structures and Algorithms in Javascript...to get you started.

In Part 3, we will cover

Most frequently occurring item in an array
Sum of elements of a nested array
Array chunks

1. Find the most frequently occurring item in an array

Here, a hash table is used to store each element of the array and its frequency (count) as key-value pairs.

let array = [2, 4, 1, 6, 1, 40, 1, 2, 4, 10, 1];

function mostFrequent(arr) {
  let hashMap = {};
  let mostFreq = { value: undefined, count: 0 };
  for (let i = 0; i < arr.length; i++) {
    if (!hashMap[arr[i]]) {
      hashMap[arr[i]] = 1; //set count to 1 initially
    } else {
      ++hashMap[arr[i]]; //increment count
    }
    if (mostFreq.count < hashMap[arr[i]]) {
      //make the new element the most frequent one
      mostFreq.value = arr[i];
      mostFreq.count = hashMap[arr[i]];
    }
  }
  return mostFreq.value;
}

console.log(mostFrequent(array));

2. Find the sum of elements of a nested array

Recursion is used to find the sum.

let array = [1, 2, 3, [4, 5], [6, 7, [8, 9]]];

function findSum(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i].length > 1) {
      sum += findSum(arr[i]); //nested array
    } else {
      sum += arr[i];
    }
  }
  return sum;
}

console.log(findSum(array));

3. Split an array into chunks

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

function chunkArray(arr, size) {
  let chunk = [];
  let result = [];
  for (let i = 0; i < arr.length; i++) {
    if (chunk.length < size) {
      chunk.push(arr[i]);
    } else {
      result.push(chunk); //add chunk to result
      chunk = []; // reset chunk
      chunk.push(arr[i]);
    }
  }
  if (chunk.length > 0) {
    result.push(chunk);
  }
  return result;
}

console.log(chunkArray(array, 3));

Data Structures and Algorithms in Javascript - Part 2

Jeena John — Wed, 13 Jan 2021 02:32:30 +0000

This is a continuation of my post on Data Structures and Algorithms in Javascript...to get you started.

In Part 2, we will cover

Merge Sort
Binary Search

Merge Sort

Merge sort is a divide and conquer algorithm. Merge sort works as follows:

Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
Repeatedly merge sublists to produce new sorted sublists (conquer) until there is only one sublist remaining. This will be the sorted list.

let array = [38, 27, 43, 3, 9, 82, 10];

function merge(left, right) {
  let results = [];
  while (left.length && right.length) {
    left[0] < right[0]
      ? results.push(left.shift())
      : results.push(right.shift());
  }
  return [...results, ...left, ...right];
}

function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  }
  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid)); // first half
  let right = mergeSort(arr.slice(mid)); //second half
  return merge(left, right);
}

console.log(mergeSort(array));

Time Complexity: In sorting n objects, Merge sort has an average and worst-case performance of O(n log n).

Binary Search

Binary Search is used to search for an element in sorted arrays. It uses divide and conquer approach. Binary Search works as follows:
To search for target value(num),

Compare the middle element of the array with num.
If num equals middle element, its position in the array is returned.
If num < middle element, the search continues in the lower half of the array.
If num > middle element, the search continues in the upper half of the array. As the array is sorted, in each iteration the algorithm eliminates the half in which the target value doesn't exist.

let array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

function _findNumber(arr, left, right, num) {
  let mid = Math.floor((left + right) / 2);
  if (num === arr[mid]) {
    return mid;
  }
  if (left === right) {
    //only one element to be checked and it is not num
    return -1;
  }
  return num > arr[mid]
    ? _findNumber(arr, mid + 1, right, num)
    : _findNumber(arr, left, mid - 1, num);
}

function findNumber(arr, num) {
  if (arr.length === 0) {
    // no elements in array
    return -1;
  }
  return _findNumber(arr, 0, arr.length - 1, num);
}

console.log(findNumber(array, 4));

Time Complexity: O(log n) where n is the number of elements in the array.

Data Structures and Algorithms in Javascript...to get you started

Jeena John — Fri, 08 Jan 2021 19:15:01 +0000

I thought of compiling together some of the common Data Structures and Algorithms implementations in Javascript and sharing them with the community. This is Part 1 of the series.

This article is intended as a starting point for someone who is prepping for a DS and Algorithms job interview.

In Part 1, we will cover

Stack
Queue
Binary Search Tree

Part 2 covers Merge Sort and Binary Search.
Part 3 covers the solutions for finding the most frequently occurring item in an array, Sum of elements of a nested array and Array chunks.

1. Stack

Stack is a linear data structure that follows LIFO (Last In First Out) or FILO (First In Last Out). There are two main operations on a Stack.

Push - adds an element to the top of the Stack.
Pop - removes the most recently added element (from the top of the Stack).

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
  }
}
class Stack {
  constructor() {
    this.top = null; // no nodes
  }
  push(value) {
    let node = new Node(value);
    node.prev = this.top;
    this.top = node;
  }
  pop() {
    if (this.top) {
      let value = this.top.value;
      this.top = this.top.prev;
      return value;
    } else {
      return 'Stack is empty';
    }
  }
}

let stack1 = new Stack(); // stack to store integers
stack1.push(1);
stack1.push(2);
stack1.push(3);

console.log(stack1.pop()); // 3
console.log(stack1.pop()); // 2
console.log(stack1.pop()); // 1
console.log(stack1.pop()); // stack is empty

2. Queue

Queue is also a linear data structure. Queue follows FIFO (First In First Out). The two main operations on Queue are:

Enqueue - adds an element to the tail of the Queue.
Dequeue - removes an element from the head of the Queue.

class Node {
  constructor(val) {
    this.value = val;
    this.next = null;
  }
}
class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  enqueue(val) {
    // to tail
    let node = new Node(val);
    if (!this.head) {
      //if queue is empty, point head and tail to this new node
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node; // make new node as tail
    }
  }
  dequeue() {
    //  from head
    if (this.head) {
      let val = this.head.value;
      this.head = this.head.next;
      return val;
    } else {
      return 'Queue is empty';
    }
  }
}

let q1 = new Queue();

q1.enqueue(1);
q1.enqueue(2);
q1.enqueue(3);

console.log(q1.dequeue()); // 1
console.log(q1.dequeue()); // 2
console.log(q1.dequeue()); // 3
console.log(q1.dequeue()); // Queue is empty

3. Binary Search Tree

A Binary Search Tree is an ordered or sorted binary tree.

There is a root node
Each node (including the root node) has a key greater than all the keys in the node's left subtree and less than those in its right subtree

Insertion

The key of the new node is first compared with that of the root.
If the key of the new node is less than the root's, then the new node is compared with the key of the root's left child.
If the key of the new node is greater than the root's, then the new node is compared with the root's right child.
This process continues until the new node is compared with a leaf node, and then it is added as this node's right or left child, depending on its key. If the key is less than the leaf's key, then it is inserted as the leaf's left child, otherwise as the leaf's right child.

Traversal

There are 3 common binary tree traversals.

Pre-order (Node->Left->Right)
In-order (Left->Node->Right)
Post-order (Left->Right->Node)

An in-order traversal of a binary search tree will always result in an ascending sorted list of node items. Here, I have implemented in-order traversal.

Traverse the left subtree by recursively calling the printNode function.
Print the key of the current node.
Traverse the right subtree by recursively calling the printNode function.

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

class BinarySearchTree {
  constructor() {
    this.root = null; // root node
  }
  insertNode(parentNode, newNode) {
    if (newNode.value < parentNode.value) {
      //check the left child
      parentNode.left !== null
        ? this.insertNode(parentNode.left, newNode)
        : (parentNode.left = newNode);
    } else {
      // check the right child
      parentNode.right !== null
        ? this.insertNode(parentNode.right, newNode)
        : (parentNode.right = newNode);
    }
  }
  insert(val) {
    let newNode = new Node(val);
    this.root !== null
      ? this.insertNode(this.root, newNode)
      : (this.root = newNode);
  }
  printNode(node) {
    if (node.left !== null) {
      this.printNode(node.left); // traverse left subtree
    }
    console.log(node.value);
    if (node.right !== null) {
      this.printNode(node.right); // traverse right subtree
    }
  }
  print() {
    this.root !== null
      ? this.printNode(this.root)
      : console.log('No nodes in the tree');
  }
}

let bst1 = new BinarySearchTree();

bst1.insert(50); 
bst1.insert(30);
bst1.insert(10);
bst1.insert(40);
bst1.insert(20);
bst1.insert(80);
bst1.insert(70);
bst1.insert(60);
bst1.insert(100);
bst1.insert(90);

bst1.print();

Hope this helps!

Don't forget to checkout Part 2 and Part 3 of this series.
More coming soon!!