jeffzh4ng / iruka

data structures and algorithms

iruka

Mirror

A collection of classical data structures and algorithms implemented in Typescript. Click the 📹 emoji for tutorials.

The repository's primary goal is educational. Hence, all implementations include a prolific number of comments which guide the reader. The name of the project, iruka, is an ode to Iruka sensei from Naruto. He became a teacher to pass on the Will of Fire, and teach the future ninja of the leaf village. Likewise, this project is here to teach the future software engineers of earth.

You can use this package in your projects if you so wish. Test coverage will be kept at 100%. To install the package, use npm or yarn:

yarn add dsa-ts

Data Structures

• Sequences
  • 📹 Linked List
  • 📹 Stack
  • 📹 Queue
  • Double-ended Queue
  • 📹 Circular Buffer
• Priority Queues
  • 📹 Binary Heap
  • D-Heap
  • 📹 Indexed Binary Heap
  • Mergeable Heaps
    • 📹 Binomial Heap
    • 📹 Lazy Binomial Heap
    • 📹 Fibonnaci Heap
• Search Trees
  • 📹 Binary Search Tree
  • 📹 AVL Tree
  • Red-black Tree
  • B-Tree
• Hash Tables
  • 📹 Hash Table (Separate Chaining)
  • Hash Table (Open Addressing)
    • Hash Table (Linear Probing)
    • Hash Table (Quadratic Probing)
    • Hash Table (Double Hashing)

Algorithms

• Search
  • Binary Search
  • Breadth-first Search
  • Depth-first Search
• Sorting
  • Merge Sort
  • Quick Sort
  • Heap Sort
  • Topological Sort (DFS)
  • Topological Sort (Kahns)
  • Counting Sort
  • Bucket Sort
• [] Graph Theory
  • [] Graphs
    • Shortest Paths
      • Dijkstra's SSSP
      • Bellman-Ford SSSP
      • Floyd-Warshall APSP
    • Minimum Spanning Tree
  • Network Flow

References

• Fundamental Data Structures
• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
• Algorithm Design by Jon Kleinberg and Éva Tardos
• Algorithms by William Fiset
• Algorithms by Jeff Erickson
• Stanford CS 166
• Harvard CS 224

Contributing

When contributing to this repository, please first discuss the change you wish to make via issue, email, or any other method with the owners of this repository before making a change.

Commiting Process

The commit process does not directly use git. dsa-ts uses commitizen to ensure we are comitting semantic commits. To commit, use the command yarn commit, and follow the citizen cli which prompts you for various metainfo regarding the commit. After the pre-commit tests are run successfully, you are able to push to your development branch with git push.

License

This repository is released under the MIT license. In short, this means you are free to use this software in any personal, open-source or commercial projects.

iruka's Issues

Add testing to CI

Fix release workflow

Duplicate in Array problem set.

Simplify releases

With semantic-release and commitizen

Missed = sign on linkedlist implementation

In LinkedList implementation:

link
in line 116 I think this should be (i > list.size()) no equal needed as we already checked it in the previous if condition and we only want to make sure it's not bigger than list bound.

in line 120: I think we should loop until
j < i
not
j < i -1,

 for (let j = 0; j < i; j++) {
      cur = cur.next
    }

we need current pointer to hold the node before the ith node, so if i = 3 we want it to be the third node in the list so cur should point to i -1 that is 2

OR you missed = sign

 for (let j = 0; j <= i -1; j++) {
      cur = cur.next
    }

and If you approve I can make PR with these changes
PS: thank you so much I really enjoyed your videos :)

Add code coverage

question: hash-table-open-addressing-base no.125 line

values(): Array<V> {
    const values: Array<V> = []

    for (let i = 0; i < this.keyList.length; i++) {
      if (this.keyList[i] && this.keyList[i] !== this.TOMBSTONE) values.push(values[i]) // values.push(this.valueList[i]) ? 
    }

    return values
  }

HelloWorld Data Structure

Create the HelloWorld data structure

doesn't have to be peekFront??

iruka/src/data-structures/sequences/queue/queue.ts

Line 62 in 02acaa0

return this.list.peekBack()

MinBinaryHeap heapify calls compare function when unnecessary

I'm talking about this call:

iruka/src/data-structures/priority-queues/min-binary-heap.ts

Line 161 in 02acaa0

const elementIsLessThanChild = this.less(k, smallestIndex)

This call should not always happen here, as it can cause the compare function to be called with undefined values while the compare function should only receive whatever the generic heap value type is.

This is causing an issue for me when constructing a MinHeap with heapify as I'm storing key-value pairs in a length-2 array. My compare function ((a, b) => a[0] - b[0]) is being called even though indexOutOfBounds is true, which causes undefined to be passed as b, causing TypeError: Cannot read property '0' of undefined.

Inlining the function call fixes it:

const indexOutOfBounds = leftChildIndex >= this.size()
if (indexOutOfBounds || this.less(k, smallestIndex)) break

Alternatively the bound check can be put in the while condition