Algorithms

Bit Manipulation

List of problems with solutions

Question: Common bit tasks

Solution:

Tasks: getBit(n,i), setBit(n,i), clearBit(n,i)

function S(e,t){return 0!==(e&1<<t)}

function w(e,t){return e|1<<t}

function O(e,t){return e&~(1<<t)}

Question: Complement of Base 10 Integer

Solution:

The complement strategy is to flip the bits of its binary representation

Time is O(1)

Space is O(1)

function(e){if(1===e)return 0;if(0===e)return 1;for(var t=1,n=e;n;)e^=t,t<<=1,n>>=1;return e}

function E(e){if(0===e)return 1;if(1===e)return 0;for(var t,n=[],a="";e>0;)t=Math.floor(e%2),n.push(t),e=Math.floor(e/2);for(;n.length;)a+=n.pop().toString();for(var r="",i=0;i<a.length;i++)0===Number(a[i])?r+="1":r+="0";return parseInt(r,2)}

Question: Power of two: Given an integer, write a function to determine if it is a power of two
Solution:
approach iterative, bit manipulation, math and use toString
for bit manipulation approach, time and space is O(1)
Time is O(log n)
Space is is O(1)
```
function(e){if(e<=0)return!1;for(;e%2===0;)e/=2;return 1===e}
```
```
function(e){return e>0&&0===(e&e-1)}
```
```
function(e){if(e<0)return!1;e=e.toString(2);for(var t=0,n=0;n<e.length;n++)1===Number(e[n])&&t++;return 1===t}
```

Numbers / Math

Question: test

Solution:

function(e,t){for(var n=new Array(t).fill(0),a=0,r=0;e>0;){r===t&&(a++,r=0);var i=a*t+(r+1);if(e<i){n[r]+=e;break}n[r]+=i,e-=i,r++}return n}

Question: Write a power function

Solution:

function x(e,t){void 0===t&&(t=2);for(var n=1,a=0;a<t;a++)n*=e;return n}

Question: Swap: 2 variables

Solution:

Time is O(1)

function(e,t){return[e+=t-=e,t=e-t]}

function(e,t){var n=e;return[e=t,t=n]}

String Manipulation

Question: test case

Question: Write a function that reverses a string: approach swap, recursion, two pointers

Solution:

Time is Time is O(n) for all approaches

Space is two pointers space is O(1), recursion is O(n)

function(e){for(var t=0;t<e.length/2;t++){var n=e[t];e[t]=e[e.length-t-1],e[e.length-t-1]=n}}

function(e){if(1===e.length)return e;for(var t=0,n=e.length-1;t<n;){var a=e[t];e[t]=e[n],e[n]=a,t++,n--}}

function(e){A(e,0,e.length-1)}

Question: define anagrams

Solution:

Anagrams are 2 words meaning anagrams with the same characters but in different order (same exact characters but order doesn’t matter).

Define hash
Increase the count for the first string.
Decrease the count for the second string. If a letter in string 2 is not found in the hash then return false.
else return true

function L(e,t){if("string"!==typeof e||"string"!==typeof t)throw new Error("defineAnagrams requires two strings to be passed");if(""===e||""===t)return"empty strings";var n=e.length,a=t.length,r={};if(n!==a)return!1;if(n===a){for(var i=e.replace(/[^A-Za-z]+/g,"").toLowerCase(),l=t.replace(/[^A-Za-z]+/g,"").toLowerCase(),o=0;o<n;o++){var s=i.charCodeAt(o)-97;r[s]=(r[s]||0)+1}for(var u=0;u<a;u++){var c=l.charCodeAt(u)-97;if(!r[c])return!1;r[c]--}return Object.values(r).every((function(e){return 0===e}))}}

Question: making anagrams

Solution:

Given two strings, a and b, that may or may not be of the same length, determine the minimum number of character deletions required to make a and b anagrams. Any characters can be deleted from either of the strings.

function D(e,t){for(var n=e.length,a=t.length,r={},i={},l=0;l<n;l++)r[e[l]]=r[e[l]]?r[e[l]]+1:1;for(var o=0;o<a;o++)i[t[o]]=i[t[o]]?i[t[o]]+1:1;for(var s=0;s<n;s++)i.hasOwnProperty(e[s])&&(i[e[s]]--,0===i[e[s]]&&delete i[e[s]]);for(var u=0;u<a;u++)r.hasOwnProperty(t[u])&&(r[t[u]]--,0===r[t[u]]&&delete r[t[u]]);var c=Object.values(r),h=Object.values(i);return(c.length>0&&c.reduce((function(e,t){return e+t}))||0)+(h.length>0&&h.reduce((function(e,t){return e+t}))||0)}

Different tasks related to String Manipulation

Question: Alternating characters

Solution:

function W(e){for(var t=e.split(""),n=t.length-1,a=0,r=0;r<n;r++)t[r]===t[r+1]&&a++;return a}

Question: Sherlock valid string

Solution:

Sherlock considers a string to be valid if all characters of the string appear the same number of times and one symbol could be deleted.

function Q(e){for(var t=e.split(""),n=t.length,a={},r=0;r<n;r++){var i=t[r];a[i]=(a[i]||0)+1}var l=Object.values(a),o=Math.max.apply(Math,Object(I.a)(l)),s=Math.min.apply(Math,Object(I.a)(l)),u=F(l,o),c=F(l,s),h=!1;return(o===s||o-s===1&&1===u||1===s&&1===c&&2===Object(I.a)(new Set(l)).length)&&(h=!0),!0===h?"Yes":"No"}

Question: Number Jewels in stones

Solution:

function(e,t){var n=0;0===(t.length||e.length)&&(n=0);for(var a=e.split(""),r=t.split(""),i={},l=0;l<t.length;l++){var o=r[l];i[o]=i[o]?i[o]+1:1}for(var s=0;s<e.length;s++){var u=a[s];i[u]&&(n+=i[u])}return n}

function(e,t){for(var n=0,a=0;a<t.length;a++)for(var r=0;r<e.length;r++)if(e.charAt(r)===t.charAt(a)){n++;break}return n}

Question: First Unique Character in a String

Solution:

The best possible solution here could be of a linear time because to ensure that the character is unique you have to check the whole string anyway.

Time is O(n)

Space is O(n)

function(e){var t,n={},a=Object(v.a)(e);try{for(a.s();!(t=a.n()).done;){var r=t.value;n[r]=(n[r]||0)+1}}catch(l){a.e(l)}finally{a.f()}for(var i=0;i<e.length;i++){if(1===n[e[i]])return i}return-1}

Question: Find all anagrams in a String: approach sliding window and 2 counter Hashes

Solution:

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Time is O(N_s + N_p) since it's one pass along both strings

Space is O(1) (or O(n)), because pCount and sCount contain 26 elements each

function(e,t){var n=[];if(null==t||null==e||0===e.length||t.length>e.length)return n;for(var a={},r={},i=0;i<t.length;i++)a[t[i]]=(a[t[i]]||0)+1,r[e[i]]=(r[e[i]]||0)+1;for(var l=0,o=t.length;o<=e.length;)G(a,r)&&n.push(l),r[e.charAt(o)]=(r[e.charAt(o)]||0)+1,o++,r[e.charAt(l)]--,l++;return n}

Array

Question:

Question: Remove duplicates from sorted array: approach 2 pointers, slow and fast runner
Solution:
Time is O(n)
Space is O(1)
```
function(e){for(var t=[],n=1;n<e.length;n++)e[n]!==e[n+1]&&t.push(e[n]);return t.length}
```

Question: Clone arrays

Solution:

function(e){var t=e.slice(0);return t}

function(e){for(var t=[],n=e.length,a=0;a<n;a++)t.push(e[a]);return t}

function(e){for(var t=new Array(e.length),n=e.length,a=0;a<n;a++)t[a]=e[a];return t}

Question: Jump on clouds

Solution:

function $(e){for(var t=e.length,n=0,a=0;a<t;a++){var r=e[a+1],i=e[a+2];1===e[a]?a+=1:0===r&&0===i?(n+=2,a+=2):(n+=1,a+=1)}return n}

Question: merge two sorted arrays (mergeSort algorithm)

Solution:

Below is just an implementation of mergeSort algorithm

Time is runtime is O(n log n)

function(e,t){for(var n=0,a=0,r=[],i=e.length,l=t.length;n<i&&a<l;)e[n]<t[a]?(r.push(e[n]),n++):(r.push(t[a]),a++);return n<i&&(r=[].concat(Object(I.a)(r),Object(I.a)(e.slice(n)))),a<l&&(r=[].concat(Object(I.a)(r),Object(I.a)(t.slice(a)))),r}

Question: Single element in sorted array: approach brute force, binary search, BS only on even indexes

Solution:

for brute force time is O(n), space is O(1)

Time is binary search approach O(log n)

Space is binary search approachO(1)

function(e){for(var t=0;t<e.length-1;t+=2)if(e[t]!==e[t+1])return e[t];return e[e.length-1]}

function(e){for(var t=0,n=e.length-1;t<n;){var a=Math.floor(t+(n-t)/2),r=(n-a)%2===0;if(e[a+1]===e[a])r?t=a+2:n=a-1;else{if(e[a-1]!==e[a])return e[a];r?n=a-2:t=a+1}}return e[t]}

function oe(e){for(var t=0,n=e.length-1;t<n;){var a=Math.floor(t+(n-t)/2);a%2===1&&a--,e[a]===e[a+1]?t=a+2:n=a}return e[t]}

Question: Majority elements: using hash, sort, Voting Moore algorithm

Solution:

Time is Moore O(n)

Space is Moore O(1)

function(e){var t=e.length;if(0===t)return[];if(1===t)return e[0];var n,a={},r=Object(v.a)(e);try{for(r.s();!(n=r.n()).done;){var i=n.value;a[i]=(a[i]||0)+1}}catch(o){r.e(o)}finally{r.f()}for(var l in a)if(a[l]>t/2)return Number(l)}

function(e){var t,n,a=0,r=Object(v.a)(e);try{for(r.s();!(n=r.n()).done;){var i=n.value;0===a&&(t=i),a+=i===t?1:-1}}catch(l){r.e(l)}finally{r.f()}return t}

Question: Find judge in the town, approach with one and two arrays
Solution:
In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: 1 The town judge trusts nobody. 2 Everybody (except for the town judge) trusts the town judge. 3 There is exactly one person that satisfies properties 1 and 2. You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b. If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.
Recall that N is number of people, and E is the number of edges (trusts relationships) Time complexity is O(E). We need to loop through the E edges in trust, and the argument about relationship between N and E still applies. Space complexity: O(N) - allocating an array of length N
Time is O(max(N, E) = O(N+E), because is E >= N-1 => O(E) number of trusts relationship
Space is O(N) allocating an array of length N
```
function(e,t){if(t.length<e-1)return-1;var n,a=Array(e+1).fill(0),r=Object(v.a)(t);try{for(r.s();!(n=r.n()).done;){var i=n.value,l=Object(ee.a)(i,2),o=l[0],s=l[1];a[o]-=1,a[s]+=1}}catch(c){r.e(c)}finally{r.f()}for(var u=1;u<a.length;u++)if(a[u]===e-1)return u;return-1}
```
```
function(e,t){if(t.length<e-1)return-1;var n,a=Array(e+1).fill(0),r=Array(e+1).fill(0),i=Object(v.a)(t);try{for(i.s();!(n=i.n()).done;){var l=Object(ee.a)(n.value,2),o=l[0],s=l[1];a[o]++,r[s]++}}catch(c){i.e(c)}finally{i.f()}for(var u=1;u<=e;u++)if(0===a[u]&&r[u]===e-1)return u;return-1}
```

Question: Max contiguous subarray sum: brute force cubic and quadratic time

Solution:

test

function(e){for(var t=e.length,n=-1/0,a=0;a<t;a++)for(var r=a;r<t;r++){for(var i=0,l=a;l<=r;l++)i+=e[l];i>n&&(n=i)}return n}

function(e){var t=e.length;if(1===t)return e[0];for(var n=-1/0,a=0;a<t;a++)for(var r=0,i=a;i<t;i++)r+=e[i],n=Math.max(n,r);return n}

Linked Lists

Singly-linked List

Question: Singly linked list implementation

Solution:

function e(){Object(o.a)(this,e),this.head=null,this.size=0}

Stack

Question: Stack via Array
Solution:
Time is every operation takes constant time
Space is less wasted space
```
function e(){Object(o.a)(this,e),this.stack=[]}
```
Question: Stack via Linked List
Solution:
Time is for .push and pop() takes constant time
Space is need space for pointers
```
function e(){Object(o.a)(this,e),this.head=null,this.length=0}
```

Question: Stack via String

Solution:

function e(){Object(o.a)(this,e),this.storage=""}

Question: Stack via Object

Solution:

function ge(e){this.capacity=e||1/0,this.storage={},this.count=0}

Different problems related to Stacks
Question: Min Stack: approach 2 Stacks, approach minimum pairs
Solution:
Time is O(1) for all operation
Space is O(n)
```
function e(){Object(o.a)(this,e),this.stack=[],this.minStack=[]}
```
```
function e(){Object(o.a)(this,e),this.elements=[]}
```
Question: Max Stack: approach 2 Stacks
Solution:
Design a max stack that supports push, pop, top, peekMax and popMax.
Can we design operations in O(1) like the min stack problem? No Because if it were, you could use this data structure to sort an array of numbers in O(n) time. So, at the very least, either push(x) or popMax() must be O(log n)
Time is O(N) for the popMax operation, and O(1) for the other operations
Space is O(N), the maximum size of the stack.
```
function e(){Object(o.a)(this,e),this.stack=[],this.maxStack=[]}
```
```
function e(){Object(o.a)(this,e),this.stack=[],this.maxStack=[]}
```

Queue

Question: Queue via array

Solution:

function e(){Object(o.a)(this,e),this.queue=[]}

Question: Queue via linked list (1 pointer and 2 pointers)

Solution:

function e(){Object(o.a)(this,e),this.head=null,this.length=0}

function e(){Object(o.a)(this,e),this.head=null,this.tail=null,this.length=0}

Different problems related to Queues

Question:

Solution:

function e(){Object(o.a)(this,e),this.stackNewest=[],this.stackOldest=[]}

Hash / Hash Table

Question:

Solution:

function(e){for(var t=e.length,n=0,a=new Array(t+1).fill(0),r=0;r<t;r++)e[r]>=t?a[t]++:a[e[r]]++;for(var i=t;i>0;i--)if((n+=a[i])>=i)return i;return console.log("arr",a),0}

Question: HashMap / HashTable implementation: use array
Solution:
```
function e(){Object(o.a)(this,e),this.keys=[],this.values=[]}
```

Question: HashSet implementation: use object

Solution:

function e(){Object(o.a)(this,e),this.data={},this.length=0}

function e(){Object(o.a)(this,e),this.data={},this.length=0}

Question: Two sum using hash

Solution:

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input has exactly one solution. And you may not use the same element twice.

Time is O(n)

Space is O(n). The extra space required depends on the number of items stored in the hash table, which stores exactly nn elements

function De(e,t){var n=e.length;if(0===n)return[];for(var a=0;a<n;a++)for(var r=a+1;r<n;r++)if(e[r]===t-e[a])return[a,r];return-1}

function We(e,t){if(0===e.length)return[];for(var n=new Map,a=0;a<e.length;a++)n.set(e[a],a);for(var r=0;r<e.length;r++){var i=t-e[r];if(n.has(i)&&n.get(i)!==r)return[r,n.get(i)]}return-1}

function Ie(e,t){if(0===e.length)return[];for(var n={},a=0;a<e.length;a++){var r=n[t-e[a]];if(void 0!==r)return[r,a];n[e[a]]=a}return-1}

Graph

Question: test

Question: Flood fill image bitmap algorithm using dfs (Depth-First Search)

Solution:

We can use a function dfs to perform a flood-fill on a target pixel.

Time is O(N), where N is the number of pixels in the image. We might process every pixel

Space is O(N), the size of the implicit call stack when calling dfs.

function e(t,n,a,r){var i=arguments.length>4&&void 0!==arguments[4]?arguments[4]:t[n][a];return n<0||a<0||n>=t.length||a>=t[n].length||t[n][a]!==i||t[n][a]===r||(t[n][a]=r,e(t,n-1,a,r,i),e(t,n+1,a,r,i),e(t,n,a-1,r,i),e(t,n,a+1,r,i)),t}

function(e,t,n,a){var r=e[t][n];return r!==a&&function e(t,n,a,r,i){var l=t.length,o=t[0].length;if(n<0||n>=l||a<0||a>=o||t[n][a]!==r)return;t[n][a]=i,e(t,n-1,a,r,i),e(t,n+1,a,r,i),e(t,n,a-1,r,i),e(t,n,a+1,r,i)}(e,t,n,r,a),e}

Trees

Question:

Solution:

function(e,t){if(null===e)return!1;null!==e&&[].push([e,e.val]);return console.log("result2",[]),!1}

Question: BT implementation: .insert(node)
Solution:
insert(node): iterative + Queue
```
function e(t){Object(o.a)(this,e),this.root=new Je(t)}
```
Question: Binary Search Tree: .insert, .contains, height, lowest common ancestor
Solution:
Binary search trees provide logarithmic time for the common operations of lookup, insertion, and deletion in the average case, and linear time in the worst case. Why is this? Each of those basic operations requires us to find an item in the tree and because of the tree structure at each parent node we are branching left or right and effectively excluding half the size of the remaining tree. This makes the search proportional to the logarithm of the number of nodes in the tree, which creates logarithmic time for these operations in the average case.
Time is O(log(n)) in the average case, linear - in worst cases
```
function e(t){Object(o.a)(this,e),this.root=new Ye(t),this.count=1}
```

Question: Level order (bottom level) traversal BT

Solution:

Time is O(n)

Space is O(n)

function(e){var t=[];if(!e)return t;var n=[];for(n.push(e);n.length;){var a=n.shift();t.push(a.val),a.left&&n.push(a.left),a.right&&n.push(a.right)}return t}

Question: Preorder traversal BT

Solution:

function(e){var t=[];if(null===e)return t;var n=[];for(null!==e&&n.push(e);n.length;){var a=n.pop();t.push(a.val),a.right&&n.push(a.right),a.left&&n.push(a.left)}return t}

Question: Invert Binary Tree: approach recursion
Solution:
Time is is O(n), since each node in the tree is visited only once
Space is is O(h) because of recursion, O(h) function calls will be placed on the stack in the worst case, where h is the height of the tree
```
function e(t){if(!t)return null;var n=e(t.left),a=e(t.right);return t.left=a,t.right=n,t}
```

Heap

Question: test

Question: Max Binary Heap

Solution:

function e(){Object(o.a)(this,e),this.values=[]}

Trees

Question: Trie implementation

Solution:

function e(){Object(o.a)(this,e),this.head={key:"",children:{}}}

Question:

Solution:

function e(){Object(o.a)(this,e),this.root=new wt}

function e(){Object(o.a)(this,e)}

Question: Trie design
Solution:
```
function(){this.root={}}
```

Sorting

Question: Bubble sort: bubble up the biggest element to the right most position
Solution:
is a method for sorting arrays by comparing each array element to the element behind it
Unfortunately bubble sort is pretty slow
Time is (n-1) * (n-1) ... = n2 - 2n + 1 = O(n^2). The worst case situation is reverse ordered array.
Best time is Ω(n) when array is sorted. As the complete array is sorted, your number of swaps will be zero. If you do not swaps just quit.
Space is O(1)
```
function jt(e){var t,n=e.length;do{t=!1;for(var a=0;a<n-1;a++)if(e[a]>e[a+1]){var r=[e[a+1],e[a]];e[a]=r[0],e[a+1]=r[1],t=!0}}while(t);return e}
```
Question: Selection sort: move the smallest element to the very left position
Solution:
n + (n-1) + (n-2) + ... + 1 = n*(n+1)/2 = (n^2 + n)/2 = O(n^2)
Time is O(n^2) quadratic in all cases, Ω(n^2)
```
function Mt(e){for(var t=e.length,n=0;n<t;n++){for(var a=n,r=n+1;r<t;r++)e[r]<e[a]&&(a=r);var i=e[n];e[n]=e[a],e[a]=i}return e}
```
Question: Insertion sort: compare items on its left and shift if needed
Solution:
Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.
in worst cases number of shifts over that number to the beginning of the array = 1 + 2 + ... + (n-1) = n(n-1)/2 = n^2/2 = n^2
Time is O(n^2)
Space is O(1)
```
function Bt(e){for(var t=e.length,n=1;n<t;n++){for(var a=e[n],r=n-1;r>=0&&e[r]>a;)e[r+1]=e[r],r-=1;e[r+1]=a}return e}
```
Question: Merge sort
Solution:
we could magically sort the left half and sort the right half and repeat it again
It always give us O(n log n) runtime. There is no case than array looks really funky.
Time is O(n log n)
Space is The downside is merging 2 arrays together requires extra space - O(n) space
```
function At(e){if(e.length<=1)return e;var t=Math.floor(e.length/2),n=e.slice(0,t),a=e.slice(t);return Ct(At(n),At(a))}
```
```
function Ct(e,t){for(var n=[];e.length&&t.length;)e[0]<t[0]?(n.push(e[0]),e.shift()):(n.push(t[0]),t.shift());return n.concat(e,t)}
```

Question: Quick sort: pick a pivot

Solution:

first pick a random number - pivot

Quick sort’s worst case is O(n^2) (for example, if list was already sorted) but that can be avoided if we pick random pivot point (choose middle one)

Time is O(n log n)

Space is O(log n)

function zt(e){var t=e.length;if(t<2)return e;var n,a=e[t-1],r=[],i=[],l=Object(v.a)(e.slice(0,t-1));try{for(l.s();!(n=l.n()).done;){var o=n.value;o<a?r.push(o):i.push(o)}}catch(s){l.e(s)}finally{l.f()}return[].concat(Object(I.a)(zt(r)),[a],Object(I.a)(zt(i)))}

Question: Heapsort

Solution:

Time is O(nlogn)

Space is O(1)

function Lt(e){for(var t=e.length,n=Math.floor(t/2-1),a=t-1;n>=0;)Tt(e,t,n),n--;for(;a>=0;){var r=[e[a],e[0]];e[0]=r[0],e[a]=r[1],Tt(e,a,0),a--}return e}

Question: Find a median
Solution:
The median of a list of numbers is essentially it's middle element after sorting. The same number of elements occur after it as before.
```
function Dt(e){var t,n,a=e.length,r=e.sort((function(e,t){return e-t}));return 0===a?0:(a%2===0?(n=a/2,t=Math.floor((r[n]+r[n-1])/2)):t=r[n=Math.floor(a/2)],t)}
```

Search / Binary search

Question:

Question: Linear search: find an index of element in array
Solution:
The worst case performance scenario for a linear search is that it needs to loop through the entire collection.
Time is O(n)
```
function It(e,t){for(var n=e.length,a=0;a<n;a++){return e[a]===t?a:void 0}}
```

Question: Binary search with loop while and recursion

Solution:

left + right could overflow, correct mid = left + (right - left)/2

For iterative and recursive approach: time is O(log n), but for recursive space is O(log n)

Time is O(log n)

Space is O(1)

function Ft(e,t){for(var n=0,a=(e=e.sort((function(e,t){return e-t}))).length-1;n<=a;){var r=Math.floor(n+(a-n)/2);if(t===e[r])return r;t<e[r]?a=r-1:n=r+1}return-1}

function Qt(e,t){var n=arguments.length>2&&void 0!==arguments[2]?arguments[2]:0,a=arguments.length>3&&void 0!==arguments[3]?arguments[3]:e.length-1,r=Math.floor(n+(a-n)/2);switch(!0){case e[r]===t:return r;case a-n===0:return-1;case t>e[r]:return Qt(e,t,r+1,a);case t<e[r]:return Qt(e,t,n,r);default:console.log("Sorry, we are out of expressions")}}

Different tasks related to Binary search
Question: Balanced sum
Solution:
challenge is to find an element of the array such that the sum of all elements to the left is equal to the sum of all elements to the right
Time is O(n)
```
function Ht(e){var t=e.length;if(t<=0)return"YES";for(var n=0,a=t-1,r=0;n!==a;)r>=0?(r-=e[a],a--):(r+=e[n],n++);return 0===r?"YES":"NO"}
```
Question: First Bad version
Solution:
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
Time is O(log n)
Space is O(1)
```
function(e){return function(t){for(var n=1,a=t;n<a;){var r=n+(a-n)/2;e(r)?a=r:n=r+1}}}
```

Recursion

Question:

Solution:

function _t(e,t){t=e.length-t;for(var n=0,a=e.length-1;n<a;){var r=$t(e,n,a);if(r<t)n=r+1;else{if(!(r>t))break;a=r-1}}return e[t]}

Question: Recursion examples

Solution:

function Ut(e){for(var t=0,n=0;n<e.length;n++)t+=e[n];return t}

function e(t){if(console.log("N",t),!(t<=0))return e(t-1)}

Question: Factorial using recursion
Solution:
Time is The time complexity of recursive factorial is O(n)
Space is As there is no extra space taken during the recursive calls, the space complexity is O(n)
```
function Yt(e){return e<0?-1:0===e?1:e*Yt(e-1)}
```
Question: Fibonacci Number: approach recursion, iterative solution
Solution:
Recursion is the slowest way to solve the Fibonacci Sequence because it takes exponential time. We need space proportionate to N to account for the max size of the stack, in memory. This stack keeps track of the function calls to fib(N). This has the potential to be bad in cases hat there isn't enough physical memory to handle the increasingly growing stack, leading to a StackOverflowError.
Time is with recursion O(2^n)
Space is with recursion O(N)
```
function e(t){return 0===t?0:1===t?1:t>1?e(t-1)+e(t-2):void 0}
```
```
function Vt(e){for(var t=[0,1],n=2;n<=e;n++)t.push(t[n-2]+t[n-1]);return t[e]}
```

Greedy Algorithms

Question:

Question: Two city Scheduling
Solution:
There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1]. Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.
Time is O(NlogN) because of sorting of input data
Space is O(1) since it's a constant space solution
```
function(e){for(var t=0,n=(e=e.sort((function(e,t){return e[0]-t[0]-(e[1]-t[1])}))).length/2,a=0;a<n;a++)t+=e[a][0]+e[a+n][1];return t}
```
```
function(e){for(var t=0,n=(e=e.sort((function(e,t){return Math.abs(t[0]-t[1])-Math.abs(e[0]-e[1])}))).length,a=Math.floor(n/2),r=0,i=0,l=0;l<n;l++){var o=e[l][0],s=e[l][1];o<=s?r<a?(t+=o,r++):(t+=s,i++):i<a?(t+=s,i++):(t+=o,r++)}return t}
```
Question: Minimum absolute difference in an array
Solution:
We define the absolute difference between two elements a[i] and a[j] (where i!=j), to be the absolute value of a[i] - a[j].
```
function en(e){for(var t,n=e.length,a=e.sort((function(e,t){return e-t})),r=Math.abs(a[0]-a[1]),i=2;i<n;i++)(t=Math.abs(a[i]-a[i-1]))<r&&(r=t);return r}
```

Question: Luck Balance

Solution:

function tn(e,t){for(var n=t.slice().sort((function(e,t){return t[0]-e[0]})),a=n.length,r=0,i=e,l=0;l<a;l++){var o=Object(ee.a)(n[l],2),s=o[0];o[1]?(r+=i>0?s:-s,i-=1):r+=s}return r}

Dynamic Programming

Question:

Solution:

function(e){for(var t=1/0,n=0,a=0;a<e.length;a++)e[a]<t?t=e[a]:e[a]-t>n&&(n=e[a]-t);return n}

function e(t){return t<2?1:e(t-1)+e(t-2)}

Question: Coin change 2: DP and use as outer loop coins array

Solution:

Any DP problem should start from explanation of sub problems. The idea is in order to know how many combinations there were for 5, we needed to know how many combinations the previous numbers had.

Time is O(n*m), where n - coins, m - amount(combinations)

Space is Create an arr of O(amount+1)

function(e,t){if(e<=0)return 1;var n=new Array(e+1).fill(0);n[0]=1;var a,r=Object(v.a)(t);try{for(r.s();!(a=r.n()).done;)for(var i=a.value,l=1;l<n.length;l++)l>=i&&(n[l]+=n[l-i])}catch(o){r.e(o)}finally{r.f()}return n[e]}

function(e,t){for(var n=Object(I.a)(Array(e)).map((function(e){return Array(t).fill(0)})),a=0;a<e;a++)n[0][a]=1;for(var r=0;r<t;r++)n[0][r]=1;for(var i=1;i<e;i++)for(var l=1;l<t;l++)n[i][l]=n[i-1][l]+n[i][l-1];return console.log(n),n[e-1][t-1]}

Question: Unique Binary Search Trees

Solution:

Time is O(n^2)

Space is O(n)

function(e){var t=new Array(e+1).fill(0);t[0]=t[1]=1;for(var n=2;n<=e;n++)for(var a=1;a<=n;a++)t[n]+=t[a-1]*t[n-a];return t[e]}

Code Sandbox
Eloquent JavaScript

Question: Looping triangle

Solution:

Write a loop that makes seven calls to console.log to output the triangle

function mn(e){for(var t=arguments.length>1&&void 0!==arguments[1]?arguments[1]:"#",n=t;n.length<e+1;n+=t)console.log("line",n)}

Question: fizzbuzz
Create a for loop that iterates up to 100 while outputting "fizz" at multiples of 3, "buzz" at multiples of 5 and "fizzbuzz" at multiples of 3 and 5
Solution:
runtime - O(n)
```
function(){for(var e=1;e<=100;e++){var t="";e%3===0&&(t+="Fizz"),e%5===0&&(t+="Buzz"),console.log(t||e)}}
```
Question: Chessboard
Write a program that creates a string that represents an 8×8 grid, using newline characters to separate lines. At each position of the grid there is either a space or a "#" character. The characters should form a chessboard.
Solution:
complexity - n2
```
function dn(){for(var e=arguments.length>0&&void 0!==arguments[0]?arguments[0]:8,t="",n=0;n<e;n++){for(var a=0;a<e;a++)t+=(a+n)%2===0?" ":"#";t+="\n"}console.log(t)}
```
Question: Define whether a positive whole number is even or odd (using recursion): Zero is even, One is odd, for any other number N, its evenness is the same as N - 2.
Solution:
```
function gn(e){return e%2===0||1!==e&&gn(e<0?-e:e-2)}
```

Question: Reverse an array

Solution:

function(e){for(var t=[],n=e.length-1;n>=0;n--)t.push(e[n]);return t}

function pn(e){for(var t=e.length,n=0;n<Math.floor(t/2);n++){var a=e[n];e[n]=e[t-1-n],e[t-1-n]=a}return e}

function En(e){var t=[];return function e(n){n.length>0&&(t.push(n.pop()),e(n))}(e),t}

Bit Manipulation

Numbers / Math

String Manipulation

Array

Linked Lists

Singly-linked List

Stack

Queue

Hash / Hash Table

Graph

Trees

Heap

Trees

Sorting

Search / Binary search

Recursion

Greedy Algorithms

Dynamic Programming

Code Sandbox Eloquent JavaScript

Code Sandbox
Eloquent JavaScript