amejiarosario/dsa.js-data-structures-algorithms-javascript

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

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

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

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;
  }

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!

[bug] [docs] Images not rendering

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

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;
  }

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.

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.

Radix sort

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

pull-issue

You need any changes and anything then mentioned this pulls request

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

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

Lorem ipsum in book

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

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.

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
      }

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.

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.

broken links/routes on big-o-examples

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.

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.

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.

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.

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..." 😆