Giter Site home page Giter Site logo

trekhleb / javascript-algorithms Goto Github PK

View Code? Open in Web Editor NEW
181.2K 181.2K 29.3K 12.94 MB

📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings

License: MIT License

JavaScript 99.99% Shell 0.01%
algorithm algorithms computer-science data-structures interview interview-preparation javascript javascript-algorithms

javascript-algorithms's Introduction

JavaScript Algorithms and Data Structures

🇺🇦 UKRAINE IS BEING ATTACKED BY RUSSIAN ARMY. CIVILIANS ARE GETTING KILLED. RESIDENTIAL AREAS ARE GETTING BOMBED.


CI codecov repo size

This repository contains JavaScript based examples of many popular algorithms and data structures.

Each algorithm and data structure has its own separate README with related explanations and links for further reading (including ones to YouTube videos).

Read this in other languages: 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português, Русский, Türkçe, Italiana, Bahasa Indonesia, Українська, Arabic, Tiếng Việt, Deutsch

☝ Note that this project is meant to be used for learning and researching purposes only, and it is not meant to be used for production.

Data Structures

A data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

B - Beginner, A - Advanced

Algorithms

An algorithm is an unambiguous specification of how to solve a class of problems. It is a set of rules that precisely define a sequence of operations.

B - Beginner, A - Advanced

Algorithms by Topic

Algorithms by Paradigm

An algorithmic paradigm is a generic method or approach which underlies the design of a class of algorithms. It is an abstraction higher than the notion of an algorithm, just as an algorithm is an abstraction higher than a computer program.

How to use this repository

Install all dependencies

npm install

Run ESLint

You may want to run it to check code quality.

npm run lint

Run all tests

npm test

Run tests by name

npm test -- 'LinkedList'

Troubleshooting

If linting or testing is failing, try to delete the node_modules folder and re-install npm packages:

rm -rf ./node_modules
npm i

Also make sure that you're using a correct Node version (>=16). If you're using nvm for Node version management you may run nvm use from the root folder of the project and the correct version will be picked up.

Playground

You may play with data-structures and algorithms in ./src/playground/playground.js file and write tests for it in ./src/playground/__test__/playground.test.js.

Then just simply run the following command to test if your playground code works as expected:

npm test -- 'playground'

Useful Information

References

Big O Notation

Big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows. On the chart below you may find most common orders of growth of algorithms specified in Big O notation.

Big O graphs

Source: Big O Cheat Sheet.

Below is the list of some of the most used Big O notations and their performance comparisons against different sizes of the input data.

Big O Notation Type Computations for 10 elements Computations for 100 elements Computations for 1000 elements
O(1) Constant 1 1 1
O(log N) Logarithmic 3 6 9
O(N) Linear 10 100 1000
O(N log N) n log(n) 30 600 9000
O(N^2) Quadratic 100 10000 1000000
O(2^N) Exponential 1024 1.26e+29 1.07e+301
O(N!) Factorial 3628800 9.3e+157 4.02e+2567

Data Structure Operations Complexity

Data Structure Access Search Insertion Deletion Comments
Array 1 n n n
Stack n n 1 1
Queue n n 1 1
Linked List n n 1 n
Hash Table - n n n In case of perfect hash function costs would be O(1)
Binary Search Tree n n n n In case of balanced tree costs would be O(log(n))
B-Tree log(n) log(n) log(n) log(n)
Red-Black Tree log(n) log(n) log(n) log(n)
AVL Tree log(n) log(n) log(n) log(n)
Bloom Filter - 1 1 - False positives are possible while searching

Array Sorting Algorithms Complexity

Name Best Average Worst Memory Stable Comments
Bubble sort n n2 n2 1 Yes
Insertion sort n n2 n2 1 Yes
Selection sort n2 n2 n2 1 No
Heap sort n log(n) n log(n) n log(n) 1 No
Merge sort n log(n) n log(n) n log(n) n Yes
Quick sort n log(n) n log(n) n2 log(n) No Quicksort is usually done in-place with O(log(n)) stack space
Shell sort n log(n) depends on gap sequence n (log(n))2 1 No
Counting sort n + r n + r n + r n + r Yes r - biggest number in array
Radix sort n * k n * k n * k n + k Yes k - length of longest key

Project Backers

You may support this project via ❤️️ GitHub or ❤️️ Patreon.

Folks who are backing this project ∑ = 1

Author

@trekhleb

A few more projects and articles about JavaScript and algorithms on trekhleb.dev

javascript-algorithms's People

Contributors

adityahiran avatar agusnavce avatar albertstill avatar alexanderkhivrych avatar applejax avatar austintheriot avatar avi09 avatar bruce-feldman avatar childrentime avatar davidkadaria avatar fveronezipeters avatar iwaskorean avatar jpvg10 avatar kersov avatar m-maksyutin avatar moshejs avatar niltonslf avatar oscarrg avatar petershershov avatar requiresun avatar robtaussig avatar seincorp avatar tapaswenipathak avatar tiendq avatar trekhleb avatar tusba avatar ujjwalaryal avatar vivitruong avatar vladimirschneider avatar yeonjuan avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

javascript-algorithms's Issues

Translate to korean

Hello!!
I want to translate README into Korean.
Can I?
And, are there any restriction?

Translate to russian

Hello.

I want to translate all README into Russian, are there any rules for translation?

Wrong description

Please add correct description for javascript-algorithms/src/data-structures/linked-list/LinkedList.js, because comment in Delete function is misleading:
// If the head must be deleted then make 2nd node to be a head.

It would be better to add:
'while' will delete all nodes with the same value, starting with the this.head.

Collision resolution in hash-table

In the HashTable implementation currently there is no collision resolution mechanism. The following insertion method updates the existing node. There can be chaining or open addressing methods implemented.

  insert(key, value) {
    const bucketLinkedList = this.buckets[this.hash(key)];
    const node = bucketLinkedList.find({ callback: nodeValue => nodeValue.key === key });

    if (!node) {
      // Insert new node.
      bucketLinkedList.append({ key, value });
    } else {
      // Update value of existing node.
      node.value.value = value;
    }
  }  

Rename `QuickSortInPlace` to `TrueQuickSort` or something similar.

It should be mentioned that QuickSortInPlace is the actual quick sort. Other implementation that allows using extra space is like quick sort but not the strictly the actual algorithm.

I've seen this at several places. For example the following implementation of quicksort in Haskell

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]  
    in  smallerSorted ++ [x] ++ biggerSorted  

It is shown as a quicksort implementation but in reality it is not.
A lot of newbies will get a wrong idea about the quicksort this way who are only learning algos this way.
It should at least be mentioned in the ReadMe that the one with the in-place is the real one.

Add Liu Hui's π algorithm

https://en.wikipedia.org/wiki/Liu_Hui's_%CF%80_algorithm

e.g:

const getSideLength = (sideLength, count) => {
  if (count <= 0) return sideLength;
  const m = sideLength / 2;
  const g = Math.sqrt((0.5 ** 2) - (m ** 2));
  const j = 0.5 - g;
  return getSideLength(Math.sqrt((j ** 2) + (m ** 2)), count - 1);
};


const pi = (splitCount = 0) => {
  const sideLength = getSideLength(0.5, splitCount);
  const sideCount = 6 * (splitCount ? 2 ** splitCount : 1);
  return sideLength * sideCount;
};

// for (let i = 0; i < 100; i += 1) {
//   const p = pi(i);
//   console.log(i, p, p === Math.PI);
// }

export default pi;

My concern about no classification by Procedural/Imperative and Functional programming Paradigm

Hi, this is a great project. Thanks.
I have a concern that I would like to share.

For instance, looking at /algorithms/math/factorial which is one of the most basic math topic:
https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/factorial

I found 2 implementations:

factorial.js

export default function factorial(number) {
  let result = 1;

  for (let i = 2; i <= number; i += 1) {
    result *= i;
  }

  return result;
}

factorialRecursive.js

export default function factorialRecursive(number) {
  return number > 1 ? number * factorialRecursive(number - 1) : 1;
}

factorial.js is a code of Procedural/Imperative programming style, and uses mutable variables.

factorialRecursive.js is recursive, and can be said functional programming style, immutable. Alghouth this is a typical implementation which I can see everywhere, in terms of "Big O notations". this is rather anti-pattern.

A better or I would say, a proper way is,

factorialFunctional.js

//[...Array(5).keys()]
//-> [ 0, 1, 2, 3 ,4 ]

const natural = n => {
    const arr0 = [...Array(n + 1).keys()];
    const [first, ...arr] = arr0;
    return arr;
};

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

function factorialFunctional(number) {
    const list = number < 1
        ? [1]
        : natural(number)
    const multiply = (a, b) => a * b;
    return list.reduce(multiply);
}

console.log(
    factorialFunctional(5)//120
);

This is as efficient as the factorial.js in terms of "Big O notations", and immutable.

I think when algorithms are presented, it's significantly important to clarify what kind of programming paradigm the algorithms are based on.

Currently, it seems the contributions are updated randomly without formal classification for them, and I think it's a good idea to show a guideline in the README that to clarify which paradigm every algorithm belongs to. In this manner, a contributors notice "oh, here, there is no Functional or Imperative pattern yet, so I will add.."

Thanks.

Z -algorithm

I'm new to open source,I wanted to implement z-algorithm for strings

Translate to Spanish

I believe it would be nice to translate the README.md to Spanish and would love to help!

Workshopper

How about creating a workshopper? I would love to create one.

Test suite failed to run on Ubuntu

Test suite failed to run

SecurityError: localStorage is not available for opaque origins

  at Window.get localStorage [as localStorage] (node_modules/jsdom/lib/jsdom/browser/Window.js:257:15)
      at Array.forEach (<anonymous>)

I'm not sure what this is called or if it belongs here

Hey, I apologize in advance if this is misplaced. I don't have any maths education or know anything of algorithms.

I've been working on something that I believe I misconstrued from a problem I saw asked that dealt with binary trees. I don't know if this is a valid algorithm or not:

// Find all subtrees of n-ary tree. For example:
//
//          1
//        /   \
//       /     \
//      2       3
//     / \     /|\
//    4   6   5 7 8
//       / \
//      9  10
       
// I want to show all subtrees:

// 1    1   1       1       1        1         1
//     /     \     / \     / \      / \         \
//    2       3   2   3   2   3    2   3         3
//                        |        |  /         /
//                        4        4 5         5

I think essentially what I'm trying to communicate here is any valid branching path/"state" from the tree starting at the root node. I first tried order-specific (all permutations of each "level" were valid) but this was far too difficult and I've since retreated to trying to figure out order-inspecific. I could be way off, but this appears to work:

https://repl.it/@GavinRay97/VivaciousWarmheartedComputers-1

Console Output of Trees - CLICK TO EXPAND

var exampleTree = {
  a: {
    b: {
      d: null,
      e: {
        f: null,
        g: {
          i: {
            l: null,
            m: null,
            n: null,
          },
          k: null,
        },
        h: null
      }
    },
    c: null,
    o: null
  },
}

"a -> b"
"a -> b-c"
"a -> b-c -> d"
"a -> b-c -> d-e"
"a -> b-c -> d-e -> f"
"a -> b-c -> d-e -> f-g"
"a -> b-c -> d-e -> f-g-h"
"a -> b-c -> d-e -> f-g-h -> i"
"a -> b-c -> d-e -> f-g-h -> i-k"
"a -> b-c -> d-e -> f-g-h -> i-k -> l"
"a -> b-c -> d-e -> f-g-h -> i-k -> l-m"
"a -> b-c -> d-e -> f-g-h -> i-k -> l-m-n"
"a -> b-c -> d-e -> f-g-h -> i-k -> m"
"a -> b-c -> d-e -> f-g-h -> i-k -> m-n"
"a -> b-c -> d-e -> f-g-h -> i-k -> n"
"a -> b-c -> d-e -> f-g-h -> i -> l"
"a -> b-c -> d-e -> f-g-h -> i -> l-m"
"a -> b-c -> d-e -> f-g-h -> i -> l-m-n"
"a -> b-c -> d-e -> f-g-h -> i -> m"
"a -> b-c -> d-e -> f-g-h -> i -> m-n"
"a -> b-c -> d-e -> f-g-h -> i -> n"
"a -> b-c -> d-e -> f-g-h -> k"
"a -> b-c -> d-e -> f-g -> i"
"a -> b-c -> d-e -> f-g -> i-k"
"a -> b-c -> d-e -> f-g -> i-k -> l"
"a -> b-c -> d-e -> f-g -> i-k -> l-m"
"a -> b-c -> d-e -> f-g -> i-k -> l-m-n"
"a -> b-c -> d-e -> f-g -> i-k -> m"
"a -> b-c -> d-e -> f-g -> i-k -> m-n"
"a -> b-c -> d-e -> f-g -> i-k -> n"
"a -> b-c -> d-e -> f-g -> i -> l"
"a -> b-c -> d-e -> f-g -> i -> l-m"
"a -> b-c -> d-e -> f-g -> i -> l-m-n"
"a -> b-c -> d-e -> f-g -> i -> m"
"a -> b-c -> d-e -> f-g -> i -> m-n"
"a -> b-c -> d-e -> f-g -> i -> n"
"a -> b-c -> d-e -> f-g -> k"
"a -> b-c -> d-e -> g"
"a -> b-c -> d-e -> g-h"
"a -> b-c -> d-e -> g-h -> i"
"a -> b-c -> d-e -> g-h -> i-k"
"a -> b-c -> d-e -> g-h -> i-k -> l"
"a -> b-c -> d-e -> g-h -> i-k -> l-m"
"a -> b-c -> d-e -> g-h -> i-k -> l-m-n"
"a -> b-c -> d-e -> g-h -> i-k -> m"
"a -> b-c -> d-e -> g-h -> i-k -> m-n"
"a -> b-c -> d-e -> g-h -> i-k -> n"
"a -> b-c -> d-e -> g-h -> i -> l"
"a -> b-c -> d-e -> g-h -> i -> l-m"
"a -> b-c -> d-e -> g-h -> i -> l-m-n"
"a -> b-c -> d-e -> g-h -> i -> m"
"a -> b-c -> d-e -> g-h -> i -> m-n"
"a -> b-c -> d-e -> g-h -> i -> n"
"a -> b-c -> d-e -> g-h -> k"
"a -> b-c -> d-e -> g -> i"
"a -> b-c -> d-e -> g -> i-k"
"a -> b-c -> d-e -> g -> i-k -> l"
"a -> b-c -> d-e -> g -> i-k -> l-m"
"a -> b-c -> d-e -> g -> i-k -> l-m-n"
"a -> b-c -> d-e -> g -> i-k -> m"
"a -> b-c -> d-e -> g -> i-k -> m-n"
"a -> b-c -> d-e -> g -> i-k -> n"
"a -> b-c -> d-e -> g -> i -> l"
"a -> b-c -> d-e -> g -> i -> l-m"
"a -> b-c -> d-e -> g -> i -> l-m-n"
"a -> b-c -> d-e -> g -> i -> m"
"a -> b-c -> d-e -> g -> i -> m-n"
"a -> b-c -> d-e -> g -> i -> n"
"a -> b-c -> d-e -> g -> k"
"a -> b-c -> d-e -> h"
"a -> b-c -> e"
"a -> b-c -> e -> f"
"a -> b-c -> e -> f-g"
"a -> b-c -> e -> f-g-h"
"a -> b-c -> e -> f-g-h -> i"
"a -> b-c -> e -> f-g-h -> i-k"
"a -> b-c -> e -> f-g-h -> i-k -> l"
"a -> b-c -> e -> f-g-h -> i-k -> l-m"
"a -> b-c -> e -> f-g-h -> i-k -> l-m-n"
"a -> b-c -> e -> f-g-h -> i-k -> m"
"a -> b-c -> e -> f-g-h -> i-k -> m-n"
"a -> b-c -> e -> f-g-h -> i-k -> n"
"a -> b-c -> e -> f-g-h -> i -> l"
"a -> b-c -> e -> f-g-h -> i -> l-m"
"a -> b-c -> e -> f-g-h -> i -> l-m-n"
"a -> b-c -> e -> f-g-h -> i -> m"
"a -> b-c -> e -> f-g-h -> i -> m-n"
"a -> b-c -> e -> f-g-h -> i -> n"
"a -> b-c -> e -> f-g-h -> k"
"a -> b-c -> e -> f-g -> i"
"a -> b-c -> e -> f-g -> i-k"
"a -> b-c -> e -> f-g -> i-k -> l"
"a -> b-c -> e -> f-g -> i-k -> l-m"
"a -> b-c -> e -> f-g -> i-k -> l-m-n"
"a -> b-c -> e -> f-g -> i-k -> m"
"a -> b-c -> e -> f-g -> i-k -> m-n"
"a -> b-c -> e -> f-g -> i-k -> n"
"a -> b-c -> e -> f-g -> i -> l"
"a -> b-c -> e -> f-g -> i -> l-m"
"a -> b-c -> e -> f-g -> i -> l-m-n"
"a -> b-c -> e -> f-g -> i -> m"
"a -> b-c -> e -> f-g -> i -> m-n"
"a -> b-c -> e -> f-g -> i -> n"
"a -> b-c -> e -> f-g -> k"
"a -> b-c -> e -> g"
"a -> b-c -> e -> g-h"
"a -> b-c -> e -> g-h -> i"
"a -> b-c -> e -> g-h -> i-k"
"a -> b-c -> e -> g-h -> i-k -> l"
"a -> b-c -> e -> g-h -> i-k -> l-m"
"a -> b-c -> e -> g-h -> i-k -> l-m-n"
"a -> b-c -> e -> g-h -> i-k -> m"
"a -> b-c -> e -> g-h -> i-k -> m-n"
"a -> b-c -> e -> g-h -> i-k -> n"
"a -> b-c -> e -> g-h -> i -> l"
"a -> b-c -> e -> g-h -> i -> l-m"
"a -> b-c -> e -> g-h -> i -> l-m-n"
"a -> b-c -> e -> g-h -> i -> m"
"a -> b-c -> e -> g-h -> i -> m-n"
"a -> b-c -> e -> g-h -> i -> n"
"a -> b-c -> e -> g-h -> k"
"a -> b-c -> e -> g -> i"
"a -> b-c -> e -> g -> i-k"
"a -> b-c -> e -> g -> i-k -> l"
"a -> b-c -> e -> g -> i-k -> l-m"
"a -> b-c -> e -> g -> i-k -> l-m-n"
"a -> b-c -> e -> g -> i-k -> m"
"a -> b-c -> e -> g -> i-k -> m-n"
"a -> b-c -> e -> g -> i-k -> n"
"a -> b-c -> e -> g -> i -> l"
"a -> b-c -> e -> g -> i -> l-m"
"a -> b-c -> e -> g -> i -> l-m-n"
"a -> b-c -> e -> g -> i -> m"
"a -> b-c -> e -> g -> i -> m-n"
"a -> b-c -> e -> g -> i -> n"
"a -> b-c -> e -> g -> k"
"a -> b-c -> e -> h"
"a -> b-c-o"
"a -> b-c-o -> d"
"a -> b-c-o -> d-e"
"a -> b-c-o -> d-e -> f"
"a -> b-c-o -> d-e -> f-g"
"a -> b-c-o -> d-e -> f-g-h"
"a -> b-c-o -> d-e -> f-g-h -> i"
"a -> b-c-o -> d-e -> f-g-h -> i-k"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> l"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> l-m"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> m"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> m-n"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> n"
"a -> b-c-o -> d-e -> f-g-h -> i -> l"
"a -> b-c-o -> d-e -> f-g-h -> i -> l-m"
"a -> b-c-o -> d-e -> f-g-h -> i -> l-m-n"
"a -> b-c-o -> d-e -> f-g-h -> i -> m"
"a -> b-c-o -> d-e -> f-g-h -> i -> m-n"
"a -> b-c-o -> d-e -> f-g-h -> i -> n"
"a -> b-c-o -> d-e -> f-g-h -> k"
"a -> b-c-o -> d-e -> f-g -> i"
"a -> b-c-o -> d-e -> f-g -> i-k"
"a -> b-c-o -> d-e -> f-g -> i-k -> l"
"a -> b-c-o -> d-e -> f-g -> i-k -> l-m"
"a -> b-c-o -> d-e -> f-g -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> f-g -> i-k -> m"
"a -> b-c-o -> d-e -> f-g -> i-k -> m-n"
"a -> b-c-o -> d-e -> f-g -> i-k -> n"
"a -> b-c-o -> d-e -> f-g -> i -> l"
"a -> b-c-o -> d-e -> f-g -> i -> l-m"
"a -> b-c-o -> d-e -> f-g -> i -> l-m-n"
"a -> b-c-o -> d-e -> f-g -> i -> m"
"a -> b-c-o -> d-e -> f-g -> i -> m-n"
"a -> b-c-o -> d-e -> f-g -> i -> n"
"a -> b-c-o -> d-e -> f-g -> k"
"a -> b-c-o -> d-e -> g"
"a -> b-c-o -> d-e -> g-h"
"a -> b-c-o -> d-e -> g-h -> i"
"a -> b-c-o -> d-e -> g-h -> i-k"
"a -> b-c-o -> d-e -> g-h -> i-k -> l"
"a -> b-c-o -> d-e -> g-h -> i-k -> l-m"
"a -> b-c-o -> d-e -> g-h -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> g-h -> i-k -> m"
"a -> b-c-o -> d-e -> g-h -> i-k -> m-n"
"a -> b-c-o -> d-e -> g-h -> i-k -> n"
"a -> b-c-o -> d-e -> g-h -> i -> l"
"a -> b-c-o -> d-e -> g-h -> i -> l-m"
"a -> b-c-o -> d-e -> g-h -> i -> l-m-n"
"a -> b-c-o -> d-e -> g-h -> i -> m"
"a -> b-c-o -> d-e -> g-h -> i -> m-n"
"a -> b-c-o -> d-e -> g-h -> i -> n"
"a -> b-c-o -> d-e -> g-h -> k"
"a -> b-c-o -> d-e -> g -> i"
"a -> b-c-o -> d-e -> g -> i-k"
"a -> b-c-o -> d-e -> g -> i-k -> l"
"a -> b-c-o -> d-e -> g -> i-k -> l-m"
"a -> b-c-o -> d-e -> g -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> g -> i-k -> m"
"a -> b-c-o -> d-e -> g -> i-k -> m-n"
"a -> b-c-o -> d-e -> g -> i-k -> n"
"a -> b-c-o -> d-e -> g -> i -> l"
"a -> b-c-o -> d-e -> g -> i -> l-m"
"a -> b-c-o -> d-e -> g -> i -> l-m-n"
"a -> b-c-o -> d-e -> g -> i -> m"
"a -> b-c-o -> d-e -> g -> i -> m-n"
"a -> b-c-o -> d-e -> g -> i -> n"
"a -> b-c-o -> d-e -> g -> k"
"a -> b-c-o -> d-e -> h"
"a -> b-c-o -> e"
"a -> b-c-o -> e -> f"
"a -> b-c-o -> e -> f-g"
"a -> b-c-o -> e -> f-g-h"
"a -> b-c-o -> e -> f-g-h -> i"
"a -> b-c-o -> e -> f-g-h -> i-k"
"a -> b-c-o -> e -> f-g-h -> i-k -> l"
"a -> b-c-o -> e -> f-g-h -> i-k -> l-m"
"a -> b-c-o -> e -> f-g-h -> i-k -> l-m-n"
"a -> b-c-o -> e -> f-g-h -> i-k -> m"
"a -> b-c-o -> e -> f-g-h -> i-k -> m-n"
"a -> b-c-o -> e -> f-g-h -> i-k -> n"
"a -> b-c-o -> e -> f-g-h -> i -> l"
"a -> b-c-o -> e -> f-g-h -> i -> l-m"
"a -> b-c-o -> e -> f-g-h -> i -> l-m-n"
"a -> b-c-o -> e -> f-g-h -> i -> m"
"a -> b-c-o -> e -> f-g-h -> i -> m-n"
"a -> b-c-o -> e -> f-g-h -> i -> n"
"a -> b-c-o -> e -> f-g-h -> k"
"a -> b-c-o -> e -> f-g -> i"
"a -> b-c-o -> e -> f-g -> i-k"
"a -> b-c-o -> e -> f-g -> i-k -> l"
"a -> b-c-o -> e -> f-g -> i-k -> l-m"
"a -> b-c-o -> e -> f-g -> i-k -> l-m-n"
"a -> b-c-o -> e -> f-g -> i-k -> m"
"a -> b-c-o -> e -> f-g -> i-k -> m-n"
"a -> b-c-o -> e -> f-g -> i-k -> n"
"a -> b-c-o -> e -> f-g -> i -> l"
"a -> b-c-o -> e -> f-g -> i -> l-m"
"a -> b-c-o -> e -> f-g -> i -> l-m-n"
"a -> b-c-o -> e -> f-g -> i -> m"
"a -> b-c-o -> e -> f-g -> i -> m-n"
"a -> b-c-o -> e -> f-g -> i -> n"
"a -> b-c-o -> e -> f-g -> k"
"a -> b-c-o -> e -> g"
"a -> b-c-o -> e -> g-h"
"a -> b-c-o -> e -> g-h -> i"
"a -> b-c-o -> e -> g-h -> i-k"
"a -> b-c-o -> e -> g-h -> i-k -> l"
"a -> b-c-o -> e -> g-h -> i-k -> l-m"
"a -> b-c-o -> e -> g-h -> i-k -> l-m-n"
"a -> b-c-o -> e -> g-h -> i-k -> m"
"a -> b-c-o -> e -> g-h -> i-k -> m-n"
"a -> b-c-o -> e -> g-h -> i-k -> n"
"a -> b-c-o -> e -> g-h -> i -> l"
"a -> b-c-o -> e -> g-h -> i -> l-m"
"a -> b-c-o -> e -> g-h -> i -> l-m-n"
"a -> b-c-o -> e -> g-h -> i -> m"
"a -> b-c-o -> e -> g-h -> i -> m-n"
"a -> b-c-o -> e -> g-h -> i -> n"
"a -> b-c-o -> e -> g-h -> k"
"a -> b-c-o -> e -> g -> i"
"a -> b-c-o -> e -> g -> i-k"
"a -> b-c-o -> e -> g -> i-k -> l"
"a -> b-c-o -> e -> g -> i-k -> l-m"
"a -> b-c-o -> e -> g -> i-k -> l-m-n"
"a -> b-c-o -> e -> g -> i-k -> m"
"a -> b-c-o -> e -> g -> i-k -> m-n"
"a -> b-c-o -> e -> g -> i-k -> n"
"a -> b-c-o -> e -> g -> i -> l"
"a -> b-c-o -> e -> g -> i -> l-m"
"a -> b-c-o -> e -> g -> i -> l-m-n"
"a -> b-c-o -> e -> g -> i -> m"
"a -> b-c-o -> e -> g -> i -> m-n"
"a -> b-c-o -> e -> g -> i -> n"
"a -> b-c-o -> e -> g -> k"
"a -> b-c-o -> e -> h"
"a -> b -> d"
"a -> b -> d-e"
"a -> b -> d-e -> f"
"a -> b -> d-e -> f-g"
"a -> b -> d-e -> f-g-h"
"a -> b -> d-e -> f-g-h -> i"
"a -> b -> d-e -> f-g-h -> i-k"
"a -> b -> d-e -> f-g-h -> i-k -> l"
"a -> b -> d-e -> f-g-h -> i-k -> l-m"
"a -> b -> d-e -> f-g-h -> i-k -> l-m-n"
"a -> b -> d-e -> f-g-h -> i-k -> m"
"a -> b -> d-e -> f-g-h -> i-k -> m-n"
"a -> b -> d-e -> f-g-h -> i-k -> n"
"a -> b -> d-e -> f-g-h -> i -> l"
"a -> b -> d-e -> f-g-h -> i -> l-m"
"a -> b -> d-e -> f-g-h -> i -> l-m-n"
"a -> b -> d-e -> f-g-h -> i -> m"
"a -> b -> d-e -> f-g-h -> i -> m-n"
"a -> b -> d-e -> f-g-h -> i -> n"
"a -> b -> d-e -> f-g-h -> k"
"a -> b -> d-e -> f-g -> i"
"a -> b -> d-e -> f-g -> i-k"
"a -> b -> d-e -> f-g -> i-k -> l"
"a -> b -> d-e -> f-g -> i-k -> l-m"
"a -> b -> d-e -> f-g -> i-k -> l-m-n"
"a -> b -> d-e -> f-g -> i-k -> m"
"a -> b -> d-e -> f-g -> i-k -> m-n"
"a -> b -> d-e -> f-g -> i-k -> n"
"a -> b -> d-e -> f-g -> i -> l"
"a -> b -> d-e -> f-g -> i -> l-m"
"a -> b -> d-e -> f-g -> i -> l-m-n"
"a -> b -> d-e -> f-g -> i -> m"
"a -> b -> d-e -> f-g -> i -> m-n"
"a -> b -> d-e -> f-g -> i -> n"
"a -> b -> d-e -> f-g -> k"
"a -> b -> d-e -> g"
"a -> b -> d-e -> g-h"
"a -> b -> d-e -> g-h -> i"
"a -> b -> d-e -> g-h -> i-k"
"a -> b -> d-e -> g-h -> i-k -> l"
"a -> b -> d-e -> g-h -> i-k -> l-m"
"a -> b -> d-e -> g-h -> i-k -> l-m-n"
"a -> b -> d-e -> g-h -> i-k -> m"
"a -> b -> d-e -> g-h -> i-k -> m-n"
"a -> b -> d-e -> g-h -> i-k -> n"
"a -> b -> d-e -> g-h -> i -> l"
"a -> b -> d-e -> g-h -> i -> l-m"
"a -> b -> d-e -> g-h -> i -> l-m-n"
"a -> b -> d-e -> g-h -> i -> m"
"a -> b -> d-e -> g-h -> i -> m-n"
"a -> b -> d-e -> g-h -> i -> n"
"a -> b -> d-e -> g-h -> k"
"a -> b -> d-e -> g -> i"
"a -> b -> d-e -> g -> i-k"
"a -> b -> d-e -> g -> i-k -> l"
"a -> b -> d-e -> g -> i-k -> l-m"
"a -> b -> d-e -> g -> i-k -> l-m-n"
"a -> b -> d-e -> g -> i-k -> m"
"a -> b -> d-e -> g -> i-k -> m-n"
"a -> b -> d-e -> g -> i-k -> n"
"a -> b -> d-e -> g -> i -> l"
"a -> b -> d-e -> g -> i -> l-m"
"a -> b -> d-e -> g -> i -> l-m-n"
"a -> b -> d-e -> g -> i -> m"
"a -> b -> d-e -> g -> i -> m-n"
"a -> b -> d-e -> g -> i -> n"
"a -> b -> d-e -> g -> k"
"a -> b -> d-e -> h"
"a -> b -> e"
"a -> b -> e -> f"
"a -> b -> e -> f-g"
"a -> b -> e -> f-g-h"
"a -> b -> e -> f-g-h -> i"
"a -> b -> e -> f-g-h -> i-k"
"a -> b -> e -> f-g-h -> i-k -> l"
"a -> b -> e -> f-g-h -> i-k -> l-m"
"a -> b -> e -> f-g-h -> i-k -> l-m-n"
"a -> b -> e -> f-g-h -> i-k -> m"
"a -> b -> e -> f-g-h -> i-k -> m-n"
"a -> b -> e -> f-g-h -> i-k -> n"
"a -> b -> e -> f-g-h -> i -> l"
"a -> b -> e -> f-g-h -> i -> l-m"
"a -> b -> e -> f-g-h -> i -> l-m-n"
"a -> b -> e -> f-g-h -> i -> m"
"a -> b -> e -> f-g-h -> i -> m-n"
"a -> b -> e -> f-g-h -> i -> n"
"a -> b -> e -> f-g-h -> k"
"a -> b -> e -> f-g -> i"
"a -> b -> e -> f-g -> i-k"
"a -> b -> e -> f-g -> i-k -> l"
"a -> b -> e -> f-g -> i-k -> l-m"
"a -> b -> e -> f-g -> i-k -> l-m-n"
"a -> b -> e -> f-g -> i-k -> m"
"a -> b -> e -> f-g -> i-k -> m-n"
"a -> b -> e -> f-g -> i-k -> n"
"a -> b -> e -> f-g -> i -> l"
"a -> b -> e -> f-g -> i -> l-m"
"a -> b -> e -> f-g -> i -> l-m-n"
"a -> b -> e -> f-g -> i -> m"
"a -> b -> e -> f-g -> i -> m-n"
"a -> b -> e -> f-g -> i -> n"
"a -> b -> e -> f-g -> k"
"a -> b -> e -> g"
"a -> b -> e -> g-h"
"a -> b -> e -> g-h -> i"
"a -> b -> e -> g-h -> i-k"
"a -> b -> e -> g-h -> i-k -> l"
"a -> b -> e -> g-h -> i-k -> l-m"
"a -> b -> e -> g-h -> i-k -> l-m-n"
"a -> b -> e -> g-h -> i-k -> m"
"a -> b -> e -> g-h -> i-k -> m-n"
"a -> b -> e -> g-h -> i-k -> n"
"a -> b -> e -> g-h -> i -> l"
"a -> b -> e -> g-h -> i -> l-m"
"a -> b -> e -> g-h -> i -> l-m-n"
"a -> b -> e -> g-h -> i -> m"
"a -> b -> e -> g-h -> i -> m-n"
"a -> b -> e -> g-h -> i -> n"
"a -> b -> e -> g-h -> k"
"a -> b -> e -> g -> i"
"a -> b -> e -> g -> i-k"
"a -> b -> e -> g -> i-k -> l"
"a -> b -> e -> g -> i-k -> l-m"
"a -> b -> e -> g -> i-k -> l-m-n"
"a -> b -> e -> g -> i-k -> m"
"a -> b -> e -> g -> i-k -> m-n"
"a -> b -> e -> g -> i-k -> n"
"a -> b -> e -> g -> i -> l"
"a -> b -> e -> g -> i -> l-m"
"a -> b -> e -> g -> i -> l-m-n"
"a -> b -> e -> g -> i -> m"
"a -> b -> e -> g -> i -> m-n"
"a -> b -> e -> g -> i -> n"
"a -> b -> e -> g -> k"
"a -> b -> e -> h"
"a -> c"
"a -> c-o"
"a -> o"
Results (plus head node):  412


Could anyone tell me whether the problem I'm describing is a real/existing algorithm, and how bad/far off my solution is so far? It's probably O(n^10) or something ridiculous too.

Thank you!

Translation

Hello, Can I try to translate the repo to Chinese?

Add Red Black Tree

Hello,

I have once write Red Black Tree in Java and interesting to write another version in Javascript. Anyone have already working on it? If no one, maybe I will pull the Red Black Tree tonight.

Regard,
Hafidz

automated test suite

a suggestion for improve quality, readability and robustness of the algorithms is to have test cases.

without tests it is hard to know if the algorithms / data structure works as intended.

Longest common substring does not handle unicode properly

It seems that the algorithm longestCommonSubstring does not handle unicode characters properly:

longestCommonSubstr('𐌵𐌵**ABC', '𐌵𐌵--ABC') === '𐌵𐌵'
// whereas the longest one should be ABC (in terms of number of code points)

// Number of code points:
[...'𐌵𐌵'].length === 2
[...'ABC'].length === 3

// Number of "characters":
'𐌵𐌵'.length === 4
'ABC'.length === 3

You should maybe add a note on the algorithm regarding this. Basically the problem can occur whenever the strings contain characters outside the BMP range (ie code points greater than 0xffff).

Feel free to close the issue whenever you want. The aim was just to signal the problem is case you want to patch it in a way.

Add Max Heap?

A Max Heap DS would be terrific in this repo. Should I work on it and submit a PR? I'm also open to other DS or algorithm contributions.

TSP or TPP Algorithm

I'm looking for any implementation of Multiple Travelers Purchase Problem, any idea ?

Combination without repetition algorithm difficult to understand

##I found the algorithm is so hard to understand that I almost pulled my hairs off. I tried to analyze it in Python tutor but It didn't get easier. After struggling for a few hours, I figured a solution that is more expressive and easier to understand.

function comboWithoutRepeat(chooseFrom, numChosen) {
  const combinations = []
  function recursive(chooseFrom, numChosen, path = []) {
    if (numChosen === 0) {
      combinations.push(path)
      return
    }
    for (let i = 0; i <= chooseFrom.length - numChosen; i++) {
      const letter = chooseFrom[i]
      const rest = chooseFrom.slice(i + 1)
      recursive(rest, numChosen - 1, [letter].concat(path))
    }
  }
  recursive(chooseFrom, numChosen)
  return combinations
}

console.log(comboWithoutRepeat([1, 2, 3, 4], 3, ''))

Grouping algorithms for studying

Thank you for creating this repo, it's awesome.
I just have one small question, can you divide all algorithms into group of level like: Beginner, Intermediate, Advance , etc so someone like students or newbies know where to start?

AVL tree does not rebalance after removal

Hi! Thanks for your project. I can't seem to find the removal algorithm in AVL tree: if it simply borrows the binary tree removal, it's incomplete. I was particularly interested in that, cause I have been looking for a removal procedure that doesn't mutate the nodes.

Cheers.

the picture about Red-Black Tree is not match

see javascript-algorithms/src/data-structures/tree/red-black-tree/readme.md
There are four pictures describe the red-black tree's four cases(LL /LR /RR /RL).But the Right Right Case and the Right Left Case 's picture are the same.

Trie - remove words

Removing words in a Trie seems equally important as adding words. It would be nice to have that.

removeChild in BinaryTreeNode does not remove parent from child

Apologies if this is the expected behavior. In BinaryTreeNode.js, the function removeChild sets either this.left or this.right to null, but does not set nodeToRemove.parent to null. So for example the following test fails:

const rootNode = new BinarySearchTreeNode('foo');
rootNode.insert('bar');
const childNode = rootNode.find('bar');
rootNode.remove('bar');
expect(childNode.parent).toBeNull();

removal from linkedlist

"This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration." - Not correct for removal. Deleting a node from a linked list is not efficient as you have to traverse the list (in case it is very large list then it will not be optimal) The option is to use Vector.

What about rope?

I found this repo while looking for a good example of rope. But I can't find one :(

bug in AVL tree rotateLeftRight and rotateRightLeft

in rotateLeftRight, while leftRightNode has left child, it will be lost.
also as well rotateRightLeft.

the following code is my correction.

 rotateLeftRight(rootNode) {
    // Detach left node from rootNode since it is going to be replaced.
    const leftNode = rootNode.left;
    rootNode.setLeft(null);

    // Detach right node from leftNode.
    const leftRightNode = leftNode.right;
    leftNode.setRight(null);

    if (leftRightNode.left) {
      leftNode.setRight(leftRightNode.left);
      leftRightNode.setLeft(null);
    }

    // Attach leftRightNode to the rootNode.
    rootNode.setLeft(leftRightNode);

    // Attach leftNode as left node for leftRight node.
    leftRightNode.setLeft(leftNode);

    // Do left-left rotation.
    this.rotateLeftLeft(rootNode);
  }
  rotateRightLeft(rootNode) {
    // Detach right node from rootNode since it is going to be replaced.
    const rightNode = rootNode.right;
    rootNode.setRight(null);

    // Detach left node from rightNode.
    const rightLeftNode = rightNode.left;
    rightNode.setLeft(null);

    if (rightLeftNode.right) {
      rightNode.setLeft(rightLeftNode.right);
      rightLeftNode.setRight(null);
    }

    // Attach rightLeftNode to the rootNode.
    rootNode.setRight(rightLeftNode);

    // Attach rightNode as right node for rightLeft node.
    rightLeftNode.setRight(rightNode);

    // Do right-right rotation.
    this.rotateRightRight(rootNode);
  }

A suggestion about Factorial

Not an issue - more of a suggestion. Is it better to start the loop from 2?

export default function factorial(number) {
  let result = 1;

  for (let i = 2; i <= number; i += 1) {
    result *= i;
  }

  return result;
}

A* algorithm?

Hey! This repo is awesome! Nice job!

While I was reading through the algorithms, I found weird that the A* algorithm was missing, which is one of the few I know.

I'm just gonna leave this as a suggestion, sorry if I can't do a pull request!

Fibonacci sequences

Not an issue - more of a suggestion. Would be good to return an array for the fibonacci sequence, as well as the sequence at nth position (and maybe rename the nth-position fibonacciNth() or something). For example:

export default function fibonacci(steps) {
  const fibSequence = [];

  let currentValue = 1;
  let previousValue = 0;

  if(steps === 1) {
    return [1];
  }

  while(steps--) {
    currentValue += previousValue;
    previousValue = (currentValue - previousValue);

    fibSequence.push(currentValue);
  }

  return fibSequence;
}

And:

export default function fibonacciNth(steps) {
  let currentValue = 1;
  let previousValue = 0;

  if(steps === 1) {
    return 1;
  }

  while(steps--) {
    currentValue += previousValue;
    previousValue = (currentValue - previousValue);
  }

  return currentValue;
}

Also, where before there was a:

while(iterationsCounter) {
  // Do code
  
  iterationsCounter -= 1;
}

This is mildly verbose, and can be more succinctly written without detriment to legibility as:

while(iterationsCounter--) {
  // Do code
}

Personally I think that's more readable. Happy to do a PR?

Edit: camel cased variable names to match existing code

Add B-Tree

I would like to contriblute to adding the B-Tree data structure.
It is a rather common data structure that is great for large data, I'll be glad to implement it.

rabinKarp seems to miss some matches

Hello,

I recently tried to run some property based tests on the algorithms provided in javascript-algorithms.
I discovered the following failing case with rabinKarp algorithm:

expect(rabinKarp("^ !/'#'pp", " !/'#'pp")).toBe(2); // output: -1

In order to find it, I used fast-check framework with the property:

// for any strings a, b and c
// rabinKarp(a + b + c, b) should be different from -1 (indeed b is a substring of a+b+c)
fc.assert(
  fc.property(
    fc.string(), fc.string(), fc.string(),
    (a, b, c) => rabinKarp(a + b + c, b) !== -1
  )
);

I was not able to have a smaller example for this precise case :/

Add another section

You've created a wonderful repository!
It's really interesting, especially for learning purposes, like in my case.

What do you think about adding a new section that explains how to calculate 3D geometry functions?

Implementing Segment tree

I'm planning to get started on a segment tree implementation. The first step would be to implement Range Min Query, then possibly a generalized implementation.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.