Instantly share code, notes, and snippets.

# iscott/ds_and_algos.md

Last active October 30, 2023 12:41
Show Gist options
• 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).
• 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(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);```

Visualize it here

```// Singly Linked List:

constructor(value) {
value: value,
next: null
};
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
}
this.length++;
return this;
}

printList() {
const array = [];
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
}
newNode.next = holdingPointer;
this.length++;
return this.printList();
}

traverseToIndex(index) {
//Check parameters
let counter = 0;
while(counter !== index){
currentNode = currentNode.next;
counter++;
}
return currentNode;
}

remove(index) {
// Check Parameters
this.length--;
return this.printList();
}
}

Visualize it here

```class DoublyLinkedList {

constructor(value) {
value: value,
next: null,
prev: null
};
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
}
this.length++;
return this;
}

printList() {
const array = [];
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
}

newNode.next = follower;
follower.prev = newNode;
this.length++;
console.log(this)
return this.printList();
}

traverseToIndex(index) {
//Check parameters
let counter = 0;
while(counter !== index){
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
}

# Fibonacci Iterative vs Recursive

```// 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

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

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```