Algorithms Flashcards
Fizzbuzz
Print Numbers 1 to N. If a Number is divisible by 3 print fizz, if a number is divisible by 5 print buzz, if a number is divisible by 15 print fizz buzz
Pascals Triangle
Triangle of rows of arrays where each cell is the sum of the two cells above it
Needle in Haystack
Return the index where needle starts in haystack if it is a substring
Pivot Index of Array
Return the index where the sum of the left is equal to the sum of the right
Fibonacci w Memoization
Return the nth fib digit in linear time
Reverse a LL
single or double
SLL
push, pop, get(index), insert(index, val), delete(index)
DLL
push, pop, get(index), insert(index, val), delete(index)
Binary Search Tree
Insert(val), find(val)
Merge Sort
Merge function O(n+m), sort O(logn)
Quick Sort
O(nlogn)
Stack
LIFO
Binary Heap
Min or Max, compact as possible, all left children are filled, then all right children are filled
Priority Queue
Min Binary Heap w Priority for nodes
BFS Graph Traversal
use a queue, shift()
DFS Graph Traversal
Recursive. Explore as far down one path before visiting neighbors
Dijktra’s Algorithm
shortest path between two vertices
Capitalize Words Recursively
Given an array of words, return the same array with the words capitalized
Hash Table
hash function, Map(), separate chaining
Queue
FIFO
Graph
add/remove vertex, add/remove edge
Binary Search Iterative/Recursive
Iterative/Recursive
Trie
Trie
Validate BST
recursively
Staircase Problem
recursively
Search a 2D Matrix
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
Merge 2 sorted linked lists
similar to merging two sorted arrays
Deserialize BST
construct BST from a string or array
Is BST Balanced?
abs value of difference in height between subtrees <=1
Lowest common ancestor for a BST
given root, x node, y node
Serialize BST
given BST, construct a string
Find Min area of rectangle given array of points
use a hashmap, find diagonals, calculate area
Unique BST given n
Cartesean Numbers F(i,n) = G(i-1) * G(n-i)
Level Order Traversal of BST
use BFS
