-
String reverseal
- Array.from(str).reduce((acc, ch) => ch + acc)
-
Palindrome
- Reverse string
- return input === reverse
- str.split('') is faster than Array.from
-
Reverse Int
- Coerce to string then reverse.
- parseInt(n) creates integer up until the non-int '-' Coerce back into number and multiply by Math.sign(n)
-
Max char (String map)
- Generate a character map with frequencies.
str.split("").forEach(ch => { charMap[ch] = charMap[ch] + 1 || 1; });
- Use for (let char in charMap) to loop over the object keys
- update maxCount and maxChar to reflect the frequency and return value/answer respectively.
-
Recursion notes
- Figure out bare minimum param necessary to represent problem
- Give reasonable defaults to the bare minimum
- Check the base case, any work left? if not, return.
- Do some work, call your func again, make sure arguments have changed.
-
Vowels
- Create check array. Array lets you have substrings in the future. Better than just one long string.
-
Matrix
- Ensure the incrementor is the comparator
- Standard for loop while pushing empty arrays to start
- use i for looping to prevent misusing variables
-
Runtime complexity
- How much more processing power is required to run an algo if we double the inputs?
- Examples:
- Reverse string: time cost is directly proportional to n (str length)
- Steps (#): n = 2, 2x2 levels. n=3, 3x3 levels. n^2 complexity
- Constant (1) => No matter the input, algo/operation always takes same time. Ex. Capitalizing first letter of a word.
- Logarithmic (log(n)) => Doubling the number of elements you are iterating doesn't double the amount of work. Searching is log(n).
- Linear (n) => Iterating through all elements. If you see a for loop going from 0 to array.length its probably n.
- Quasilinear (n*log(n)) Doubling the number of elements doesn't double the work. Sorting
- Quadratic (n^2) => Every element in a collection has to be compared to every other element. Handshake problem (new person has to shake everyones hand. Each additional person adds to the length)
- Exponential time (2^n) => Adding a single element doubles the amount of work.
-
Run time oddities
- Even if you only go through half the string, its still linear.
- If you do a linear algo with two seperate inputs that would be O(n + m) to account for the complexity of both.
- Nested for loops = n^2 or (n*n).
- Nested for loops on different quantities would be n*m because m could be much larger or much smaller than n.
- Sorting => O(n*log(n));
- Searching after sorted => O(log(n));
- Space complexity refers to the amount of space/memore an algorithim needs. Sameish rules ex. reverse string needs one extra element per ch.
-
Fib/Memoization
- Programatic solution = linear increases by 1 permutation per additional increase in params.
- Recursive solution is way worse (exponential time), however you can take advantage of memoization to make it dramatically better.
- Higher order fn
function memoize(fn) { const cache = {}; return (...args) => { if (cache[args]) { return cache[args]; } else { const result = fn.apply(this, arsg); cache[args] = result; return result; } }; }
- You need to use the memoized version and close over the internal cache.
const fib = (n) => { if (n<2) { return n; } return fib(n-1) + fib(n-2); } fib = memoize(fib);