GitHub - dsa.js: Data Structures and Algorithms explained in JavaScript

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.

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 implementations that do exactly the same but they take different time to complete.

• Optimal solution using a map
• Finding duplicates in an array (naïve approach)

8 examples to explain with code how to calculate time complexity

Most common time complexities

Time complexity graph

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

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.

Build a List, Stack and a Queue from scratch

Build any of these data structures from scratch:

• Linked List
• Stack
• Queue

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 in 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 HashMap s 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

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 its 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 tree but only can have two children at most. Code | Docs

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

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

  • Red-Black Trees: Self-balanced BST more loose than AVL to maximize insertion speed. Code

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

Never get stuck solving a problem with 7 simple steps

1. Understand the problem
2. Build a simple example (no edge cases yet)
3. Brainstorm solutions (greedy algorithm, Divide and Conquer, Backtracking, brute force)
4. Test your solution on the simple example (mentally)
5. Optimize the solution
6. Write Code, yes, now you can code.
7. Test your written code

Full details here

Master the most popular sorting algorithms

We are going to explore three basic sorting algorithms O(n2) 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

• Quick sort. Code | Docs

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 to optimize it with other techniques).