🥞Data Structures and Algorithms explained and implemented in JavaScript + eBook

Home Page: https://books.adrianmejia.com

License: MIT License

JavaScript 99.93% Dockerfile 0.07%

algorithms javascript computer-science javascript-algorithms data-structures coding-interviews book algorithm graph search tree heap

dsa.js-data-structures-algorithms-javascript's Introduction

Data Structures and Algorithms in JavaScript

This is the coding implementations of the DSA.js book and the repo for the NPM package.

In this repository, you can find the implementation of algorithms and data structures in JavaScript. This material can be used as a reference manual for developers, or you can refresh specific topics before an interview. Also, you can find ideas to solve problems more efficiently.

Installation
Features
What's Inside
Book
FAQ
Support
License

Installation

You can clone the repo or install the code from NPM:

npm install dsa.js

and then you can import it into your programs or CLI

const { LinkedList, Queue, Stack } = require('dsa.js');

For a list of all available data structures and algorithms, see index.js.

Features

Algorithms are an essential toolbox for every programmer.

You will need to mind algorithms runtime when you have to sort data, search for a value in a big dataset, transform data, scale your code to many users, to name a few. Algorithms are just the step you follow to solve a problem, while data structures are where you store the data for later manipulation. Both combined create programs.

Algorithms + Data Structures = Programs.

Most programming languages and libraries indeed provide implementations for basic data structures and algorithms. However, to make use of data structures properly, you have to know the tradeoffs to choose the best tool for the job.

This material is going to teach you to:

🛠 Apply strategies to tackle algorithm questions. Never to get stuck again. Ace those interviews!
✂️ Construct efficient algorithms. Learn how to break down problems into manageable pieces.
🧠 Improve your problem-solving skills and become a well-rounded developer by understanding fundamental computer science concepts.
🤓 Cover essential topics, such as big O time, data structures, and must-know algorithms. Implement 10+ data structures from scratch.

What's Inside

All the code and explanations are available on this repo. You can dig through the links and code examples from the (src folder). However, the inline code examples are not expanded (because of Github's asciidoc limitations), but you can follow the path and see the implementation.

Note: If you prefer to consume the information more linearly, then the book format would be more appropriate for you.

The topics are divided into four main categories, as you can see below:

📈 Algorithms Analysis

Computer Science nuggets without all the mumbo-jumbo. (Click to expand)

Computer Science nuggets without all the mumbo-jumbo

Learn to calculate run time from code examples

Learn how to compare algorithms using Big O notation. (Click to expand)

Learn how to compare algorithms using Big O notation.

Comparing algorithms using Big O notation

Let's say you want to find the duplicates on an array. Using Big O notation, we can compare different solutions that solve the same problem but has a massive difference in how long it takes to do it.

Optimal solution using a map

Finding duplicates in an array (naïve approach)

8 examples to explain with code how to calculate time complexity. (Click to expand)

8 examples to explain with code how to calculate time complexity

Most common time complexities

Time complexity graph

🥞 Linear Data Structures

Understand the ins and outs of the most common data structures. (Click to expand)

Understand the ins and outs of the most common data structures

Arrays: Built-in in most languages so not implemented here. Array Time complexity

Linked List: each data node has a link to the next (and previous). Code | Linked List Time Complexity

Queue: data flows in a "first-in, first-out" (FIFO) manner. Code | Queue Time Complexity

Stack: data flows in a "last-in, first-out" (LIFO) manner. Code | Stack Time Complexity

When to use an Array or Linked List. Know the tradeoffs. (Click to expand)

When to use an Array or Linked List. Know the tradeoffs

Use Arrays when…

You need to access data in random order fast (using an index).

Your data is multi-dimensional (e.g., matrix, tensor).

Use Linked Lists when:

You will access your data sequentially.

You want to save memory and only allocate memory as you need it.

You want constant time to remove/add from extremes of the list.

when size requirement is unknown - dynamic size advantage

Build a List, Stack, and a Queue. (Click to expand)

Build a List, Stack and a Queue from scratch

Build any of these data structures from scratch:

Linked List

Stack

Queue

🌲 Non-Linear Data Structures

Understand one of the most versatile data structure of all: Hash Maps. (Click to expand)

HashMaps

Learn how to implement different types of Maps such as:

HashMap

TreeMap

Also, learn the difference between the different Maps implementations:

HashMap is more time-efficient. A TreeMap is more space-efficient.

TreeMap search complexity is O(log n), while an optimized HashMap is O(1) on average.

HashMap’s keys are in insertion order (or random depending on the implementation). TreeMap’s keys are always sorted.

TreeMap offers some statistical data for free such as: get minimum, get maximum, median, find ranges of keys. HashMap doesn’t.

TreeMap has a guarantee always an O(log n), while HashMaps has an amortized time of O(1) but in the rare case of a rehash, it would take an O(n).

Know the properties of Graphs and Trees. (Click to expand)

Know the properties of Graphs and Trees

Graphs

Know all the graphs properties with many images and illustrations.

Graphs: data nodes that can have a connection or edge to zero or more adjacent nodes. Unlike trees, nodes can have multiple parents, loops. Code | Graph Time Complexity

Trees

Learn all the different kinds of trees and their properties.

Trees: data nodes has zero or more adjacent nodes a.k.a. children. Each node can only have one parent node otherwise is a graph, not a tree. Code | Docs

Binary Trees: same as a tree but only can have two children at most. Code | Docs

Binary Search Trees (BST): same as a binary tree, but the nodes value keep this order left < parent < right. Code | BST Time complexity

AVL Trees: Self-balanced BST to maximize lookup time. Code | AVL Tree docs | Self-balancing & tree rotations docs

Red-Black Trees: Self-balanced BST looser than AVL to maximize insertion speed. Code
Implement a binary search tree for fast lookups.

Implement a binary search tree for fast lookups

Learn how to add/remove/update values in a tree:

How to make a tree balanced?

From unbalanced BST to balanced BST
1                           2
  \                       /   \
   2        =>           1     3
    \
     3

⚒ Algorithmic Toolbox

Never get stuck solving a problem with 7 simple steps. (Click to expand)

Never get stuck solving a problem with 8 simple steps

Understand the problem

Build a simple example (no edge cases yet)

Brainstorm solutions (greedy algorithm, Divide and Conquer, Backtracking, brute force)

Test your answer on the simple example (mentally)

Optimize the solution

Write code. Yes, now you can code.

Test your written code

Analyse the complexity, both space and time, and make sure to optimize further.

Full details here

Master the most popular sorting algorithms (merge sort, quicksort, etc.) (Click to expand)

Master the most popular sorting algorithms

We are going to explore three essential sorting algorithms O(n^2), which have low overhead:

Bubble Sort. Code | Docs

Insertion Sort. Code | Docs

Selection Sort. Code | Docs

and then discuss efficient sorting algorithms O(n log n) such as:

Merge Sort. Code | Docs

Quicksort. Code | Docs

Learn different approaches to solve problems such as divide and conquer, dynamic programming, greedy algorithms, and backtracking. (Click to expand)

Learn different approaches to solve algorithmic problems

We are going to discuss the following techniques for solving algorithms problems:

Greedy Algorithms: makes greedy choices using heuristics to find the best solution without looking back.

Dynamic Programming: a technique for speeding up recursive algorithms when there are many overlapping subproblems. It uses memoization to avoid duplicating work.

Divide and Conquer: divide problems into smaller pieces, conquer each subproblem, and then join the results.

Backtracking: search all (or some) possible paths. However, it stops, and go back as soon as notice the current solution is not working.

Brute Force: generate all possible solutions and tries all of them. (Use it as a last resort or as the starting point).

FAQ

How would I apply these to my day-to-day work? (Click to expand)

As a programmer, we have to solve problems every day. If you want to solve problems well, it's good to know about a broad range of solutions. Often, it's more efficient to learn existing resources than stumble upon the answer yourself. The more tools and practice you have, the better. This book helps you understand the tradeoffs among data structures and reason about algorithms performance.

Why you created this repo/book?

There are not many books about Algorithms in JavaScript. This material fills the gap. Also, it's good practice :)

Is there anyone I can contact if I have questions about something in particular?

Yes, open an issue or ask questions on the [slack channel](https://dsajs-slackin.herokuapp.com).

Book

This project is also available in a book. You will get a nicely formatted PDF with 180+ pages + ePub and Mobi version.

Support

Reach out to me at one of the following places!

Twitter at @iAmAdrianMejia
Chat on dsajs.slack.com

License

dsa.js-data-structures-algorithms-javascript's People

Contributors

Stargazers

Watchers

Forkers

niilante axtiwari mwingfly alblandino boopathi4291 edin93 jajibhee hitunes ivanji ghanima keenanamigos nditah rubenbase tarsbase risyasin kgrvamsi hunglethanh9 bulgypanda fasibaag oscollection viniciusvinna cmmdev layzhi dinophile kevin-crawford bssrdf hacksparrow ilphil dreduard mbeaudru wakecold plasmagoat renishb10 pingjunweb shaunstanislauslau hunterxdong czosa my-interview-prep iamsingularity brandturner 17605094230 nyhxiaoning phandd mistyyyy m-bekheet beesitech hong4rc christophervistal25 r17x toddmath parwatcodes vukan71 496545016 ilijian cccfork matthewlilley karanorsingh rahulsoibam hhy5277 dblankin grpetr189853 topspinppy obedampah didakmc sjl421 iamdileepkumar learning-javascript elenag518 yemaungmaung donozone crisjc6 sviatoslav-lebediev codesofra umarabdullahi shadkhan 1ncounter diwakersurya gourav-singhal benfluleck saim-akhtar nehrakln07 sachinjain007 yaseen-nadaf taranggodhari vagoel quinsulon marioiheanacho ajdinmasic-code cmeese549 dasarianudeep zacharyad rishabh2712 rawris ravi1122 ajitsinghkamal pabline deepaksalve vhish agozie jslegers

dsa.js-data-structures-algorithms-javascript's Issues

Linked List Code Typo But Not Sure 😄

Here on Line 11 and 12 Both Comment says about moving slow pointer (on Line 11 - slow moves by 1, on Line 12 slow moves by 2 ).

Isn't should be fast pointer on line 12 or I am getting something wrong.

add() function in linked-list.js

In the add() function in linked-list.js I see the following line of code:
if (current.next) { current.next.previous = newNode; } // <7>
What is the reason behind this line of code? If we are inserting behind current, I don't know why would you set the current.next.previous to the node we wanna insert.

https://github.com/amejiarosario/dsa.js/blob/cc1ccc0183ea5d4675815413b7d1d4cc14da348c/src/data-structures/linked-lists/linked-list.js#L83-L105

Minor code documentation fix

Hi, I was reviewing the graph component's source code and looking at the bfs* iterator definition in graph.js. I noticed that its documentation incorrectly said it performed a "depth-first search"

In the spirit of "no contribution is too small..." 😆

removeByPosition () function in linked-list.js

https://github.com/amejiarosario/dsa.js/blob/d4a5037740b6efbd634e222fc645190e4244e40f/src/data-structures/linked-lists/linked-list.js#L225-L236

The following code is correct.

  removeByPosition(position = 0) {
    const current = this.get(position);
    if (position === 0) {
      this.removeFirst();
    } else if (position === this.size) {
      this.removeLast();
    }else if(current) {
      current.previous.next = current.next;
      current.next.previous = current.previous;
      this.size -=1;
    }
    return current && current.value;
  }

Should return the same node when we add a duplicated node

As the title of this issue mention you need to add one line of code, otherwise all the nodes we be removed

if (found) { // duplicated: value already exist on the tree
        found.meta.multiplicity = (found.meta.multiplicity || 1) + 1; // <2>
        newNode = found; // new line to add
      }

Lorem ipsum in book

See page 30 in ePub. Also, how can I get the updates? Is there any link?

book/asciidoc/pdf: Fix link to appending

book/content/part03/map.asc:

* *TreeMap*: it’s a map implementation that uses a self-balanced Binary Search Tree (like <<c-avl-tree#>>). The BST nodes store the key, and the value and nodes are sorted by key guaranteeing an *O(log n)* look up.

book/C-AVL-tree.asc

[appendix]
[[c-avl-tree]]
== AVL Tree
(((AVL Tree)))
(((Tree, AVL)))
AVL Tree is named after their inventors (**A**delson-**V**elsky and **L**andis).

Search for .pdf for more instances.

Radix sort

I have created a pull request to add radix sort algorithm. Please approve it and merge. #108 @amejiarosario

What if value in array is '-1'?

I mean, what if array is something like:

const arr = [3, 4, -1, 3]

then this:

searchByIndex(arr, 2) will return -1

https://github.com/amejiarosario/dsa.js/blob/bb003f18651670dfd223452f8693b7b67f0f3b4d/src/data-structures/arrays/array.js#L48

Missing word in algorithms analysis part one

see image. Could be care or something else but word is missing.

also a little further down

but it should be changed to 1M because the final table is 1M

different page, small error

worst to wors

e

LL Rotation, lose the newParent previous right node; RR Rotation too.

If the newParent.left previous is exist, we will lose it;

function leftRotation(node) {
    const newParent = node.right; // E.g., node 3
    const grandparent = node.parent; // E.g., node 1

    // swap node 1 left child from 2 to 3.
    swapParentChild(node, newParent, grandparent);

    // Update node 3 left child to be 2, and
    // updates node 2 parent to be node 3 (instead of 1).
    newParent.setLeftAndUpdateParent(node);
    // remove node 2 left child (previouly was node 3)
    node.setRightAndUpdateParent(null);

    return newParent;
}
function setLeftAndUpdateParent(node) {
    this.left = node;
    if (node) {
      node.parent = this;
      node.parentSide = LEFT;
    }
  }

If we do this: newParent.setLeftAndUpdateParent(node); in leftRotation, and
this.left = node; in setLeftAndUpdateParent,
we will lose the left of newParent.

I think the above should write as follow.

function leftRotation(node) {
    const newParent = node.right; // E.g., node 3
    const grandparent = node.parent; // E.g., node 1
    const previousLeft = newParent.left;
  
    // swap node 1 left child from 2 to 3.
    swapParentChild(node, newParent, grandparent);
  
    // Update node 3 left child to be 2, and
    // updates node 2 parent to be node 3 (instead of 1).
    newParent.setLeftAndUpdateParent(node);
    // remove node 2 left child (previouly was node 3)
    node.setRightAndUpdateParent(previousLeft);
  
    return newParent;
  }

Add this: const previousLeft = newParent.left; and node.setRightAndUpdateParent(previousLeft);
right? Maybe I am wrong.

Better hash function ?

// TextEncoder
const encoder = new TextEncoder();

/**
 * @description Polynomial hash codes are used to hash String typed keys.
 * It uses FVN-1a hashing algorithm for 32 bits
 * @see http://bit.ly/fvn-1a
 * @param {any} key
 * @return {integer} bucket index
 */
hashFunction(key) {
  const bytes = encoder.encode(key);

  // FNV_offset_basis (32 bit)
  let hash = 2166136261;

  const { length } = bytes;

  for (let i = 0; i < length; ) {
    // XOR
    hash ^= bytes[i++];
    // 32 bit FNV_prime
    hash *= 16777619;
  }

  return (hash >>> 0) % this.buckets.length;
}

New function support key out of ASCII.

A question about balance function in AVL

function balance(node) {
  if (node.balanceFactor > 1) {
    // left subtree is higher than right subtree
    if (node.left.balanceFactor > 0) {
      return rightRotation(node);
    } if (node.left.balanceFactor < 0) {
      return leftRightRotation(node);
    }
  } else if (node.balanceFactor < -1) {
    // right subtree is higher than left subtree
    if (node.right.balanceFactor < 0) {
      return leftRotation(node);
    } if (node.right.balanceFactor > 0) {
      return rightLeftRotation(node);
    }
  }
  return node;
}

When the node.balanceFactor > 1 and node.left.balanceFactor = 0, we do nothing with balance function.
As follows:

         32                                            32        
      /     \                                          / 
     8       64*                                      8    
   /  \      / \                                     /  \  
  4   16   48  128    --- remove the node-64 --->   4   16
 / \  / \                                          / \  / \ 
2  6 10 20                                        2  6 10 20

If we use the balance as follows, (when node.left.balanceFactor = 0, we do RR rotation.):

function balance(node) {
  if (node.balanceFactor > 1) {
    // left subtree is higher than right subtree
   if (node.left.balanceFactor < 0) {
      return leftRightRotation(node);
    }
    return rightRotation(node);
  } else if (node.balanceFactor < -1) {
    // right subtree is higher than left subtree
    if (node.right.balanceFactor > 0) {
      return rightLeftRotation(node);
    }
    return leftRotation(node);
  }
  return node;
}

We can get this:

         32                                            32        
      /     \                                          / 
     8       64*                                      8    
   /  \      / \                                     /  \  
  4   16   48  128    --- remove the node-64 --->   4   16
 / \  / \                                          / \  / \ 
2  6 10 20                                        2  6 10 20

                                 8
                              /     \
--- balance the node-32 -->  4       32
                            / \     /
                           2  6   16
                                  / \
                                10  20

Do you think so?

I'd like to make a quest if I may. I want to translate your articles into Chinese. I wish more people could make a look of these wonderful articles! May I?
Thank you very much.

Humble disagreement on straightforward recursive fibonacci implementation being "divide and conquer"

I think that binary search is a better representative of "divide and conquer" approach.

Even more, I suggest removing straightforward recursive fibonacci implementation from that group — it seems to belong to group "never do like this" (unless you have some cool recursion optimisation in your language).

The reason is, instead of "dividing and conquering", the problem is actually multiplied to two problems on each step (and one problem is equivalent to another one from previous step).

Maybe code like this would be closer to demo "divide and conquer", using fibonacci and recursion.

Typos in book content: makePizza parameter, array.pop() mutation, and BST node values

Hi, I found a few errors in the book! I'll put up an accompanying PR with fixes.

broken links/routes on big-o-examples

Difficulty figuring out how to use BFS on the graph structure

Hi
I find it not easy to understand how to use the bfs generator in practice.
Let say i have built a huge graph using the Graph class you have provided.
For a given node, I'd like to find out which are its immediate neighbors.
How would I use the BFS for that ?
Or should I just get the node entry and check its adjacents hashmap and export it to an array?
Thanks in advance

Graph nodes store adjacents in HashSet object which does not exist

Hi
Great content.
I am experimenting with it.
In : dsa.js-data-structures-algorithms-javascript/src/data-structures/graphs/node.js
the constructor uses HashSet where it should be HashMapSet if I am not mistaken.

pull-issue

You need any changes and anything then mentioned this pulls request

avl-tree.js: deleting root value deletes the tree by setting root to undefined

The remove function of the AVL tree appears to delete the entire tree by setting the root property of the tree to undefined if the root value is removed.

This is because the function's call this.root = balanceUpstream( node.parent ); has parameter node.parent = null if node is the root (see commented out function call below). Function balanceUpstream will then immediately return undefined which remove assigns to this.root deleting the tree.

I have fixed this in my implementation of avl-tree.js using a ternary operator:

remove( value ) {
        const node = super.find( value );
        if ( node ) {
            const found = super.remove( value );
            const parent = node.parent ? node.parent : this.root;
            this.root = balanceUpstream( parent );
            //this.root = balanceUpstream( node.parent );
            return found;
        }
        return false;
    }

Posted as a (potential) issue as I am not sure whether this is an issue only in my implementation which differs somewhat from the one in this repository.

Cheers!

Book in ePub format?

Hello, sorry if I’m asking in wrong place, but I was not able to find any contact form on your e-commerce site where you sell this book.

I would like to purchase it, but I’m curious whether ePub format will be available soon? How long approximately it will take? And if I purchase it right now, will I get ePub update for free once it release?

Also, little suggestion, please create some contact form on your website or leave contacts so people can ask questions directly.

Thanks for your great job.

[bug] [docs] Images not rendering

Hey, I just noticed that the paths are misconfigured in the docs, example:

removeFirst() function in linked-list.js

When there is only one Node , this linkedlist is wrong.

  removeFirst() {
    const head = this.first;
    if (head) {
      this.first = head.next;
      if (this.first) {
        this.first.previous = null;
      }
      this.size -= 1;
    } else {
      this.last = null;
    }
    return head && head.value;
  }

The following code is correct.

  removeFirst() {
    const head = this.first;
    if (head) {
      this.first = head.next;
      if (this.first) {
        this.first.previous = null;
      }
      else {
        this.last = null;
      }
      this.size -= 1;
    }
    return head && head.value;
  }

amejiarosario / dsa.js-data-structures-algorithms-javascript Goto Github PK

dsa.js-data-structures-algorithms-javascript's Introduction

Data Structures and Algorithms in JavaScript

Table of Contents

Installation

Features

What's Inside

📈 Algorithms Analysis

Learn to calculate run time from code examples

Comparing algorithms using Big O notation

Most common time complexities

Time complexity graph