Big O Notation
Definition: |
Way of estimating the complexity of an algorithm by measuring how it's operations scale as the input size grows |
Worst Case: |
Big O is only concerned with the worst case scenario |
Simplification: |
Constants do not matter. Smaller terms do not matter. Always know what n is |
Hints: |
Arithmetic is constant as is variable assignment and accessing elements in an array or object by index or key; |
Common Runtimes: |
Constant: O(1) Logarithmic O(log n) Linear O(n) Logarithmic O(n log n) Quadratic O(n2) Exponential O(2n) |
Stacks and Queues
Queues: |
First in first out. Items only added to the back and only removed from the front. Use linked lists for implementation because removing from the front of an array is O(n) |
Stacks: |
Last in first out. Items only added and removed from the back (or top like a stack of pancakes). Arrays are fine for stacks because push and pop are both O(1) |
Trees
Trees: |
A data structure that organizes and stores data in a hierarchical tree like fashion. |
Tree Terminology: |
Node: basic unit, children: nodes directly below a node, descendants: nodes below a node, parent: node directly above a node, ancestor: node above a node, root: node at the top of the tree, leaf node: node without any children |
Tree examples: |
Filesystems, HTML DOM, Taxonomy |
Types: |
n-ary tree's can have any number of children. Binary trees: trees where each node has 0,1 or 2 children |
Graphs
Definition: |
Like trees except the can contain loops (cycles) also relationships can be directed or undirected. |
Terminology: |
Node (Vertex) basic unit, Edge: connects two nodes, Adjacent: two nodes that share an edge, Weight: optional parameter for edges (like price) |
Node Class: |
just needs this.name and this.adjacent |
Graph Class: |
this.nodes = new Set( ) |
Bubble and Merge Sort Example
function bubbleSort(arr){
for(let i = 0; i < arr.length; i++){
for(let j = 0; j < arr.length-i; j++){
console.log(arr);
if(arr[j] > arr[j + 1]){
let newVal = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = newVal;
}
}
}
}
const merge = (arr1, arr2) => {
let output = [];
let arrOneIdx = 0;
let arrTwoIdx = 0;
while (arrOneIdx < arr1.length && arrTwoIdx < arr2.length) {
if (arr1[arrOneIdx] < arr2[arrTwoIdx]) {
output.push(arr1[arrOneIdx]);
arrOneIdx++;
} else {
output.push(arr2[arrTwoIdx]);
arrTwoIdx++;
}
}
while(arrOneIdx < arr1.length){
output.push(arr1[arrOneIdx]);
arrOneIdx ++
}
while(arrTwoIdx < arr2.length){
output.push(arr2[arrTwoIdx]);
arrTwoIdx ++
}
return output;
};
function mergeSort(arr) {
if (arr.length <= 1) return arr;
let mid = Math.floor(arr.length / 2);
let left = mergeSort(arr.slice(0, mid));
let right = mergeSort(arr.slice(mid));
return merge(left, right);
}
|
JavaScript Tricky Parts
Closures: |
A closure occurs when a function remembers it's scope even after that function has finished executing. |
Scope: |
In JavaScript, scope refers to the context in which variables and functions are declared and can be accessed. There are two main types of scope: global scope (accessible from anywhere in your code) and local scope (limited to a specific function or block of code). |
Nested Functions: |
When you have a function defined inside another function, the inner function has access to the variables and parameters of the outer function. This is where closures come into play. |
Closers revisited: |
A closure is created when an inner function references variables from its containing (outer) function, and that inner function is returned or passed around. This allows the inner function to maintain access to the outer function's variables even after the outer function has completed its execution. |
Closure use cases: |
1) Data encapsulation, ie create private variables. 2) Function Factories: use closers create and return functions 3) Callback functions 4) Event Handling |
Prototype: |
The prototype is an object on every JS object that contains properties and methods that aren't on the object itself, this allows for the sharing and inheritance of functionality, JS classes use the prototype under the hood. |
The 'new' keyword: |
The new keyword does four things 1) Creates an empty object 2) Set this to be that object 3) Returns the object 4) Creates a link to that objects prototype |
|
|
Divide and Conquer
Definition: |
Given a data set divide and conquer removes a large fraction of the data set at each step |
Binary Search: |
data must be structured, for example a sorted array |
Tips: |
make sure data is structured, if you can solve it quickly with linear search try binary search. Watch out for one of errors. |
Runtime: |
O(log n) because it cuts the data set in 1/2 each step |
Recursion
Definition: |
A powerful programing technique that involves a function calling itself |
Loops: |
All loops can be written with recursion and visa versa |
Base Case: |
The base case is required, every recursive function needs one it's what tells the function when it's done. Without a base case you'll get a stack overflow. |
Use Cases: |
Filesystems, Fractals, Parsing, Nested Data |
Binary Search Trees
Definition: |
A binary tree for efficient searching and sorting. |
Rules: |
1) Each node must only have at max two children. 2) The nodes are organized where all nodes in the left subtree are < than the nodes value and all the nodes in the right subtree have values greater than the nodes value. |
Traversal: |
Typically uses recursion for traversal with either In Order, Pre Order or Post Order Traversal methods. |
In order example: traverse(node) {
if (node.left) traverse(node.left);
console.log(node.val);
if (node.right) traverse(node.right);
}
BFS and DFS
class treeNode {
constructor(val, children = []) {
this.val = val;
this.children = children;
}
depthFirstFind(val) {
let toVisitStack = [this];
while (toVisitStack.length) {
let current = toVisitStack.pop();
console.log("Visiting", current.val);
if (current === val) {
return current.val;
}
for (let child of current.children) {
toVisitStack.push(child);
}
}
}
breathFirstFind(val) {
let toVisitQueue = [this];
while (toVisitQueue.length) {
let current = toVisitQueue.shift();
console.log('visiting', current.val);
if (current === val) {
return current;
}
for (let child of current.children) {
toVisitQueue.push(child);
}
}
}
}
|
Whiteboarding Process
Step 1: |
Listen carefully |
Step 2: |
Repeat the question back in your own words |
Step 3: |
Ask clarifying statements like edge cases. |
Step 4: |
Write test cases |
Step 5: |
Write down requirements; like arguments, what it returns etc... |
Step 6: |
Write pseudo code |
Step 7: |
Code |
Step 8: |
Test your code, be the computer |
Step 9: |
Try to optimize, clean up code, be prepared to talk about runtime/ Big O |
Tips: |
Use good variable names, don't brush past tricky parts, limit use of built in methods, take your time they want you to think deeply and approach it methodically it's not a race |
Problem Solving Process
1) Understand the problem |
restate it in your own words, understand the inputs and outputs |
2) Explore Examples |
start with simple examples, move to more complex examples |
3) Break it down |
write out the steps, write pseudocode |
4) Solve a simpler problem |
if your stuck solve the parts of the problem that you can and come back to the hard part |
5) Use tools |
debug, console.log etc.... |
6) Look back and refactor |
clean up code, can you improve performance? |
|
|
Binary Search Example:
function binarySearch(arr, val) {
let leftIdx = 0;
let rightIdx = arr.length - 1;
while (leftIdx <= rightIdx) {
// find the middle value
let middleIdx = Math.floor((leftIdx + rightIdx) / 2);
let middleVal = arr[middleIdx];
if (middleVal < val) {
// middleVal is too small, look at the right half
leftIdx = middleIdx + 1;
} else if (middleVal > val) {
// middleVal is too large, look at the left half
rightIdx = middleIdx - 1;
} else {
// we found our value!
return middleIdx;
}
}
// left and right pointers crossed, val isn't in arr
return -1;
}
|
Recursive Examples
/* product: calculate the product of an array of numbers. /
function product(nums) {
// base case
if(nums.length === 0) return 1;
// normal case
return nums[0] * product(nums.slice(1))
}
/* longest: return the length of the longest word in an array of words. /
function longest(words) {
// base case
if (words.length === 0) return 0;
// normal case
const currentLength = words[0].length;
const remainingWords = words.slice(1);
const maxLength = longest(remainingWords);
return Math.max(currentLength, maxLength);
}
/* everyOther: return a string with every other letter. /
function everyOther(str) {
// base case
if (str.length === 0) return "";
// normal case
const currentLetter = str[0];
const remainingLetters = str.slice(2);
return ${currentLetter}${everyOther(remainingLetters)}
;
}
/* isPalindrome: checks whether a string is a palindrome or not. /
function isPalindrome(str) {
// base case
if (str.length === 0 || str.length === 1) return true;
// normal case
if (str[0].toLowerCase() === str[str.length - 1].toLowerCase()) {
return isPalindrome(str.slice(1, str.length - 1));
} else return false;
}
|
Frequency Counter and Multiple Pointers Example
function findFreq(string){
let stringFreq = {};
for(let char of string){
stringFreq[char] = stringFreq[char] + 1 || 1
}
return stringFreq
}
function constructNote(messaage, letters) {
const messFreq = findFreq(messaage);
const lettFreq = findFreq(letters);
for(let char in messFreq){
if(!lettFreq[char]) return false;
if(messFreq[char] > lettFreq[char]) return false;
}
return true;
}
function averagePair(array, target) {
let left = 0;
let right = array.length - 1;
while (left < right) {
const average = right + left / 2;
if (average === target) return true;
else if (average > target) right -= 1;
else left += 1;
}
return false;
}
|
Frequency Counter and Multiple Pointers Example
function findFreq(string){
let stringFreq = {};
for(let char of string){
stringFreq[char] = stringFreq[char] + 1 || 1
}
return stringFreq
}
function constructNote(messaage, letters) {
const messFreq = findFreq(messaage);
const lettFreq = findFreq(letters);
for(let char in messFreq){
if(!lettFreq[char]) return false;
if(messFreq[char] > lettFreq[char]) return false;
}
return true;
}
function averagePair(array, target) {
let left = 0;
let right = array.length - 1;
while (left < right) {
const average = right + left / 2;
if (average === target) return true;
else if (average > target) right -= 1;
else left += 1;
}
return false;
}
|
|
Created By
Metadata
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets