Skip to content

Instantly share code, notes, and snippets.

@iscott
Last active October 30, 2023 12:41
Show Gist options
  • Save iscott/efe76bdd5f8004c290e768bd0dafc052 to your computer and use it in GitHub Desktop.
Save iscott/efe76bdd5f8004c290e768bd0dafc052 to your computer and use it in GitHub Desktop.
Intro to Datastructures and Algorithms Cheat Sheet

Cheat Sheet: Datastructures and Algorithms

By Ira Herman


Live Video Walkthrough (bonus lesson) recording

================

Big O Notation:

  • Time/Space Complexity review: Big O Notation

Data Structures:

  • Arrays - how they work with memory/addressing
  • Hash Maps/Hash Tables
  • Linked Lists (Singly and Doubly)
  • Stacks LIFO and Queues FIFO
  • Trees
  • Graphs

Algorithms:

================

Big O Notation:

Key words: analyzing the "complexity" of an algorithm. We'll look at time complexity (how long it takes to do something), but this can also be applied to space complexity - how much space/memory it will take up.

Big O analysis is a way to measure the time it takes (speed/efficiency) of an algorithm regardless of processor or hardware speed. So it is timeless -- even as computers get faster and faster, we can apply the same Big O analysis to an algorithm.

How to figure it out:

  • Is the amount of work the same, regardless of the size of the data set?
    • You might have O(1).
  • Does the function have to go through an entire list (use a loop)?
    • If so, there’s an N in that Big O class somewhere.
  • Are there nested loops?
    • That might give you O(N^2) (or worse).
  • Does the function break the list into smaller chunks?
    • You could have O(log(N)).

What's it called?

  • Constant complexity: O(1).
  • Linear complexity: O(N).
  • Quadratic complexity: O(N^2).
  • Logarithmic complexity: O(log(N)).
  • Factorial complexity: O(N!).

The main ones you'll usually be asked about are the first 4:

  • O(1)
  • O(N)
  • O(N^2)
  • O(log(N))

O(1) Constant Time Complexity

O(N) Linear Time Complexity

O(N^2) Quadratic Time Complexity

O(log(N)) Logarithmic Time Complexity

A good example: Binary search.

What's an example of Factorial O(N!) complexity?

The traveling salesman problem.

More details here

Challenge yourself

Take a look at the code samples here and analyze the time complexity using Big O notation:

Ira's Big O Code Samples repl.it

const groceries = ["eggs", "bread", "cheese", "milk", "chocolate"];
const stores = ["Whole Foods", "Sprouts", "Ralphs", "Safeway"];


////////////////////////////////////////////////////
// 1:
// What is the time complexity of this algorithm?

function getGrocery(arr, index){
  return arr[index];
}

getGrocery(groceries, 4);



////////////////////////////////////////////////////
// 2:
// What is the time complexity of this algorithm?

function listGroceries(arr){
  for (let i=0; i < arr.length; i++){
    console.log(arr[i]);
  }
}

listGroceries(groceries);



////////////////////////////////////////////////////
// 3:
// What is the time complexity of this algorithm?

function listGroceriesAtEachStore(storesArr, groceriesArr){
  for (let i=0; i < storesArr.length; i++){
    console.log(storesArr[i]);

    for (let j=0; j < groceriesArr.length; j++){
      console.log(groceriesArr[j]); 
    }
  }
}

listGroceriesAtEachStore(stores, groceries);

Linked List

Visualize it here

The code: Linked list example implementation repl.it

// Singly Linked List:

class LinkedList {

  constructor(value) {
    this.head = {
      value: value,
      next: null
    };
    this.tail = this.head;
    this.length = 1;
  }

  append(value) {
    const newNode = {
      value: value,
      next: null
    }
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }
  
  prepend(value) {
    const newNode = {
      value: value,
      next: null
    }
    newNode.next = this.head;
    this.head = newNode;
    this.length++;
    return this;
  }
  
  printList() {
    const array = [];
    let currentNode = this.head;
    while(currentNode !== null){
        array.push(currentNode.value)
        currentNode = currentNode.next
    }
    return array;
  }
  
  insert(index, value){
    //Check for proper parameters;
    if(index >= this.length) {
      console.log('yes')
      return this.append(value);
    }
    
    const newNode = {
      value: value,
      next: null
    }
    const leader = this.traverseToIndex(index-1);
    const holdingPointer = leader.next;
    leader.next = newNode;
    newNode.next = holdingPointer;
    this.length++;
    return this.printList();
  }
  
  traverseToIndex(index) {
    //Check parameters
    let counter = 0;
    let currentNode = this.head;
    while(counter !== index){
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }
  
  remove(index) {
    // Check Parameters      
    const leader = this.traverseToIndex(index-1);
    const unwantedNode = leader.next;
    leader.next = unwantedNode.next;
    this.length--;
    return this.printList();
  }
}

let myLinkedList = new LinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);myLinkedList.prepend(1);
myLinkedList.insert(2, 99);
myLinkedList.insert(20, 88);
myLinkedList.remove(2);

Doubly Linked List

Visualize it here

The code: Doubly Linked list example implementation repl.it

class DoublyLinkedList {
  
  constructor(value) {
    this.head = {
      value: value,
      next: null,
      prev: null
    };
    this.tail = this.head;
    this.length = 1;
  }
  
  append(value) {
    const newNode = {
      value: value,
      next: null,
      prev: null
    }
    console.log(newNode)
    newNode.prev = this.tail
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }
  
  prepend(value) {
    const newNode = {
      value: value,
      next: null,
      prev: null
    }
    newNode.next = this.head;
    this.head.prev = newNode
    this.head = newNode;
    this.length++;
    return this;
  }
  
  printList() {
    const array = [];
    let currentNode = this.head;
    while(currentNode !== null){
      array.push(currentNode.value)
      currentNode = currentNode.next
    }
    return array;
  }
  
  insert(index, value){
    //Check for proper parameters;
    if(index >= this.length) {
      return this.append(value);
    }
    
    const newNode = {
      value: value,
      next: null,
      prev: null
    }

    const leader = this.traverseToIndex(index-1);
    const follower = leader.next;
    leader.next = newNode;
    newNode.prev = leader;
    newNode.next = follower;
    follower.prev = newNode;
    this.length++;
    console.log(this)
    return this.printList();
  }
  
  traverseToIndex(index) {
    //Check parameters
    let counter = 0;
    let currentNode = this.head;
    while(counter !== index){
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }
}

let myLinkedList = new DoublyLinkedList(10);
myLinkedList.append(5)
myLinkedList.append(16)
myLinkedList.prepend(1)
myLinkedList.insert(2, 99)
// myLinkedList.insert(20, 88)
// myLinkedList.printList()
// myLinkedList.remove(2)
// myLinkedList.reverse()

Fibonacci Iterative vs Recursive

The code: Fibonacci loop and recursive solution implementations repl.it

// Given a number N return the index value of the Fibonacci sequence, where the sequence is:

// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...
// the pattern of the sequence is that each value is the sum of the 2 previous values, that means that for N=5 → 2+3

//For example: fibonacciRecursive(6) should return 8


function fibonacciIterative(n){
  let arr = [0, 1];
  for (let i = 2; i < n + 1; i++){
    arr.push(arr[i - 2] + arr[i -1]);
  }
 return arr[n];
}
fibonacciIterative(3);

function fibonacciRecursive(n) {
  if (n < 2){
    return n;
  }
  return fibonacciRecursive(n - 1) + fibonacciRecursive (n - 2)
}

fibonacciRecursive(6)

Factorial Iterative vs Recursive

The code: Factorial loop and recursive solution implementations repl.it

function findFactorialIterative(number) {
  let answer = 1;
  // you actually no longer need the if statement because of the for loop
  // if (number === 2) {
  //   answer = 2;
  // }
  for (let i = 2; i <= number; i++) {
    answer = answer * i;
  }
  return answer;
}

function findFactorialRecursive(number) {
  if(number === 2) {
    return 2;
  }
  return number * findFactorialRecursive(number - 1)
}

findFactorialIterative(5);
findFactorialRecursive(5);

//If you want, try to add a base case condition for the recursive solution if the parameter given is less than 2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment